Task

In the Church encoding of natural numbers, the number N is encoded by a function that applies its first argument N times to its second argument.

 Church zero always returns the identity function, regardless of its first argument. In other words, the first argument is not applied to the second argument at all.
 Church one applies its first argument f just once to its second argument x, yielding f(x)
 Church two applies its first argument f twice to its second argument x, yielding f(f(x))
 and each successive Church numeral applies its first argument one additional time to its second argument, f(f(f(x))), f(f(f(f(x)))) ... The Church numeral 4, for example, returns a quadruple composition of the function supplied as its first argument.


Arithmetic operations on natural numbers can be similarly represented as functions on Church numerals.

In your language define:

 Church Zero,
 a Church successor function (a function on a Church numeral which returns the next Church numeral in the series),
 functions for Addition, Multiplication and Exponentiation over Church numerals,
 a function to convert integers to corresponding Church numerals,
 and a function to convert Church numerals to corresponding integers.


You should:

 Derive Church numerals three and four in terms of Church zero and a Church successor function.
 use Church numeral arithmetic to obtain the the sum and the product of Church 3 and Church 4,
 similarly obtain 4^3 and 3^4 in terms of Church numerals, using a Church numeral exponentiation function,
 convert each result back to an integer, and return it or print it to the console.


'''Church numerals'''
 
from itertools import repeat
from functools import reduce
 
 
# ----- CHURCH ENCODINGS OF NUMERALS AND OPERATIONS ------
 
def churchZero():
    '''The identity function.
       No applications of any supplied f
       to its argument.
    '''
    return lambda f: identity
 
 
def churchSucc(cn):
    '''The successor of a given
       Church numeral. One additional
       application of f. Equivalent to
       the arithmetic addition of one.
    '''
    return lambda f: compose(f)(cn(f))
 
 
def churchAdd(m):
    '''The arithmetic sum of two Church numerals.'''
    return lambda n: lambda f: compose(m(f))(n(f))
 
 
def churchMult(m):
    '''The arithmetic product of two Church numerals.'''
    return lambda n: compose(m)(n)
 
 
def churchExp(m):
    '''Exponentiation of Church numerals. m^n'''
    return lambda n: n(m)
 
 
def churchFromInt(n):
    '''The Church numeral equivalent of
       a given integer.
    '''
    return lambda f: (
        foldl
        (compose)
        (identity)
        (replicate(n)(f))
    )
 
 
# OR, alternatively:
def churchFromInt_(n):
    '''The Church numeral equivalent of a given
       integer, by explicit recursion.
    '''
    if 0 == n:
        return churchZero()
    else:
        return churchSucc(churchFromInt(n - 1))
 
 
def intFromChurch(cn):
    '''The integer equivalent of a
       given Church numeral.
    '''
    return cn(succ)(0)
 
 
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
    'Tests'
 
    cThree = churchFromInt(3)
    cFour = churchFromInt(4)
 
    print(list(map(intFromChurch, [
        churchAdd(cThree)(cFour),
        churchMult(cThree)(cFour),
        churchExp(cFour)(cThree),
        churchExp(cThree)(cFour),
    ])))
 
 
# ------------------ GENERIC FUNCTIONS -------------------
 
# compose (flip (.)) :: (a -> b) -> (b -> c) -> a -> c
def compose(f):
    '''A left to right composition of two
       functions f and g'''
    return lambda g: lambda x: g(f(x))
 
 
# foldl :: (a -> b -> a) -> a -> [b] -> a
def foldl(f):
    '''Left to right reduction of a list,
       using the binary operator f, and
       starting with an initial value a.
    '''
    def go(acc, xs):
        return reduce(lambda a, x: f(a)(x), xs, acc)
    return lambda acc: lambda xs: go(acc, xs)
 
 
# identity :: a -> a
def identity(x):
    '''The identity function.'''
    return x
 
 
# replicate :: Int -> a -> [a]
def replicate(n):
    '''A list of length n in which every
       element has the value x.
    '''
    return lambda x: repeat(x, n)
 
 
# succ :: Enum a => a -> a
def succ(x):
    '''The successor of a value.
       For numeric types, (1 +).
    '''
    return 1 + x if isinstance(x, int) else (
        chr(1 + ord(x))
    )
 
 
if __name__ == '__main__':
    main()