from typing import Callable, TypeVar, Sequence, Any, Tuple, List
import run_tests
T = TypeVar( 'T' )
S = TypeVar( 'S' )

def foldr( f: Callable[ [ S, T ], T ], l: Sequence[ S ], i: T ) -> T:
    res = i
    for x in reversed( l ):
        res = f( x, res )
    return res

def fold_len( l: Sequence[ T ] ) -> int:
    return foldr( lambda x, y: y + 1, l, 0 )

def fold_pairs( l: Sequence[ T ] ) -> Sequence[ Any ]:
    return foldr( lambda x, y: (x, y), l, () )

def fold_rev( l: Sequence[ T ] ) -> List[ T ]:
    def app( x: T, y: List[ T ] ) -> List[ T ]:
        y.append( x )
        return y

    return foldr( app, l, [] )