recursion.py

from functools import partial


class Infix:
    def __init__(self, func):
        self.func = func
    def __or__(self, other):
        return self.func(other)
    def __ror__(self, other):
        return Infix(partial(self.func, other))
    def __call__(self, v1, v2):
        return self.func(v1, v2)


head = lambda xs: xs[0]
tail = lambda xs: xs[1:]
init = lambda xs: xs[:-1]
last = lambda xs: xs[-1]


@Infix
def sum_list(l1, l2):
    return list(map(lambda t: head(t) + head(tail(t)), zip(l1, l2)))


def zip_with(f, l1, l2):
    if l1 == [] or l2 == []: return []

    x, xs = head(l1), tail(l1)
    y, ys = head(l2), tail(l2)
    return [f(x, y)] + zip_with(f, xs, ys)


def reverse(lst):
    if lst == []: return []
    return reverse(tail(lst)) + [head(lst)]


def foldl(f, acc, lst):
    if lst == []: return acc
    return foldl(f, f(acc, head(lst)), tail(lst))


def foldr(f, acc, lst):
    if lst == []: return acc
    return foldr(f, f(last(lst), acc), init(lst))


def length(lst):
    if lst == []: return 0
    return 1 + length(tail(lst))


a = [1,2,3] |sum_list| [4,5,6]
b = zip_with(lambda x, y: x+y, [1,2,3], [4,5,6])
c = zip_with(lambda x, y: x*y, [1,2,3], [4,5,6])
d = reverse([1, 2, 3, 4, 5])
e = foldl(lambda acc, x: x+acc, 0, [1,2,3,4])
f = foldl(lambda acc, x: x*acc, 1, [1,2,3,4])
g = foldl(lambda acc, x: [x]+acc, [], [1,2,3,4])
h = foldr(lambda x, acc: [x]+acc, [], [1,2,3,4])
i = foldr(lambda x, acc: acc+[x], [], [1,2,3,4])
j = length([1,2,3,4])
k = length(list(range(10)))


print(a) # [5, 7, 9]
print(b) # [5, 7, 9]
print(c) # [4, 10, 18]
print(d) # [5, 4, 3, 2, 1]
print(e) # 10
print(f) # 24
print(g) # [4, 3, 2, 1]
print(h) # [1, 2, 3, 4]
print(i) # [4, 3, 2, 1]
print(j) # 4
print(k) # 10