Functional Paradigm with Composition#

https://www.wikiwand.com/en/Lambda_calculus

To achieve this:

  • Only use functions that take one parameter

  • Only use anonymous functions

Predecessor and Successor#

def predecessor(x: int) -> int:
    if x == 1:
        return 0
    return 1 + predecessor(x - 1)


assert predecessor(1) == 0
assert predecessor(10) == 9

def successor(x: int) -> int:
    if x == 0:
        return 1
    return 1 + successor(predecessor(x))


assert successor(0) == 1
assert successor(10) == 11

Addition#

def addition(x: int, y: int) -> int:
    if y == 0:
        return x
    return addition(successor(x), predecessor(y))


assert addition(0, 0) == 0
assert addition(1, 0) == 1
assert addition(0, 1) == 1
assert addition(10, 10) == 20

Multiplication#

def multiplication(x: int, y: int) -> int:
    if y == 0:
        return 0
    return addition(x, multiplication(x, predecessor(y)))


assert multiplication(0, 0) == 0
assert multiplication(2, 0) == 0
assert multiplication(0, 2) == 0
assert multiplication(10, 10) == 100

Exponentiation#

def exponentiation(x: int, y: int) -> int:
    if x == 0:
        return 0
    if y == 0:
        return 1
    return multiplication(x, exponentiation(x, predecessor(y)))


assert exponentiation(1, 0) == 1
assert exponentiation(0, 1) == 0
assert exponentiation(3, 3) == 27

Functional Paradigm with Anonymous Functions and Recursion#

Lambda Calculus Programming Approach https://www.wikiwand.com/en/Lambda_calculus

To achieve this:

  • Only use functions that take one parameter

  • Only use anonymous functions

Predecessor and Successor#

predecessor_lambda = lambda x: 0 if x == 1 else 1 + predecessor_lambda(x - 1)

assert predecessor_lambda(1) == 0
assert predecessor_lambda(10) == 9

successor_lambda = (
    lambda x: 1 if x == 0 else 1 + successor_lambda(predecessor_lambda(x))
)

assert successor_lambda(0) == 1
assert successor_lambda(10) == 11

Addition#

addition = lambda x: lambda y: x if y == 0 else addition(x + 1)(y - 1)

assert addition(1)(0) == 1
assert addition(0)(0) == 0
assert addition(0)(1) == 1
assert addition(10)(10) == 20

Multiplication#

multiplication = lambda x: lambda y: 0 if y == 0 else x + multiplication(x)(y - 1)

assert multiplication(0)(0) == 0
assert multiplication(1)(0) == 0
assert multiplication(0)(1) == 0
assert multiplication(10)(10) == 100

Exponentiation#

exponentiation = (
    lambda x: lambda y: 0 if x == 0 else 1 if y == 0 else x * exponentiation(x)(y - 1)
)

assert exponentiation(1)(0) == 1
assert exponentiation(0)(1) == 0
assert exponentiation(3)(3) == 27

Functional Paradigm with Anonymous Functions Without Recursion#

Lambda Calculus without direct recursion

To achieve this:

  • Use Y Combinator

Auxiliary Functions#

Y = lambda f: (lambda z: z(z))(lambda g: f(lambda n: g(g)(n)))

Predecessor and Successor#

predecessor_lambda = Y(lambda f: lambda x: 0 if x == 1 else 1 + f(x - 1))

assert predecessor_lambda(1) == 0
assert predecessor_lambda(10) == 9

successor_lambda = Y(lambda f: lambda x: 1 if x == 0 else 1 + f(predecessor_lambda(x)))

assert successor_lambda(0) == 1
assert successor_lambda(10) == 11

Addition#

addition_lambda = Y(
    lambda f: lambda x: lambda y: x
    if y == 0
    else f(successor_lambda(x))(predecessor_lambda(y))
)

assert addition_lambda(1)(0) == 1
assert addition_lambda(0)(0) == 0
assert addition_lambda(0)(1) == 1
assert addition_lambda(10)(10) == 20

Multiplication#

multiplication_lambda = Y(
    lambda f: lambda x: lambda y: 0 if y == 0 else x + f(x)(predecessor_lambda(y))
)

assert multiplication_lambda(0)(0) == 0
assert multiplication_lambda(1)(0) == 0
assert multiplication_lambda(0)(1) == 0
assert multiplication_lambda(10)(10) == 100

Exponentiation#

exponentiation_lambda = Y(
    lambda f: lambda x: lambda y: 0
    if x == 0
    else 1
    if y == 0
    else x * f(x)(predecessor_lambda(y))
)

assert exponentiation_lambda(1)(0) == 1
assert exponentiation_lambda(0)(1) == 0
assert exponentiation_lambda(3)(3) == 27