coin_change.py

#functional libraries
cons = lambda x, y : lambda a : x if a is True else y
car = lambda x : x(True)
cdr = lambda x : x(False)
pair = lambda x, y : cons(x, cons(y, None))
fst = car
snd = lambda x: car(cdr(x))
length = lambda x : 0 if isEmpty(x) else 1 + length(cdr(x))
isEmpty = lambda x : True if x is None else False
f_list = lambda *args : None if len(args) == 0 else cons(args[0], f_list(*args[1:]))
map_f = lambda f, c : None if isEmpty(c) else cons(f(car(c)), map_f(f, cdr(c)))
range_f = lambda n, m: None if n == m else cons(n, range_f(n+1, m))
partial_f = lambda f, v: lambda *args : f(v, *args)
default_range_f = partial_f(range_f, 0)
foldl = lambda f, i, c : i if isEmpty(c) else foldl(f, f(i, car(c)), cdr(c))
sum_f = lambda c : foldl(lambda acc, x: x+acc, 0, c)
drop = lambda n, c : c if n == 0 else drop(n-1, cdr(c))
zipLists = lambda c1, c2 : None if length(c1) == 0  or length(c2) == 0 else cons(pair(car(c1), car(c2)), zipLists(cdr(c1), cdr(c2)))

#coin_change
coin_inputs = lambda coins : map_f(lambda a : drop(a, coins), default_range_f(length(coins)))
amount_inputs = lambda amount, coins : map_f(lambda coin_input: amount - car(coin_input), coin_inputs(coins))
coin_change = lambda amount, coins: 1 if amount == 0 else 0 if amount < 0 or length(coins) == 0 else \
				sum_f(map_f(lambda inputs : coin_change(fst(inputs), snd(inputs)), zipLists(amount_inputs(amount, coins), coin_inputs(coins))))

#tests
assert car(cdr(f_list(1,2,3))) == 2
assert sum_f(f_list(1,2)) == 3
assert coin_change(2, f_list(1,5)) == 1