# Church lists in Python
# Copyright (C) 2009 Ertugrul Soeylemez
#
# Python lists are boring, so here is my reinterpretation. =)
# Version: 1.0.3


# The empty list.
def empty(f, z):
  return z


# Prepend x to the list xs.
def cons(x, xs):
  return lambda f, z: f(x, xs(f, z))


# Append x to the list xs.
def clAppend(xs, x):
  return lambda f, z: xs(f, f(x, z))


# True, if xs is the empty list, False otherwise.
def clIsEmpty(xs):
  return xs(lambda x, y: False, True)


# Length of the list xs.
def clLength(xs):
  return xs(lambda x, l: l+1, 0)


# First element of the list xs.
def clHead(xs):
  def err(): raise IndexError
  return xs(lambda x, y: lambda: x, err)()


# The list xs with its head removed.
def clTail(xs):
  def err(): raise IndexError
  (_, r) = xs(lambda x, (ys, _): (cons(x, ys), lambda: ys), (empty, err))
  return r()


# Map function f over list xs.
def clMap(f, xs):
  return xs(lambda x, ys: cons(f(x), ys), empty)


# Filter list xs using predicate p.
def clFilter(p, xs):
  return xs(lambda x, ys: cons(x, ys) if p(x) else ys, empty)


# Convert Church list to Python list.
def clToList(xs):
  return xs(lambda x, ys: [x] + ys, [])


# Convert Python list to Church list.
def clFromList(xs):
  return reduce(lambda xs, y: clAppend(xs, y), xs, empty)


# The fixed point combinator (the Y combinator from lambda calculus).
def fix(f):
  return lambda *x: f(fix(f), *x)


# clRange(a, b):  List of numbers from a to b.
def clRange_(r, a, b):
  return empty if a > b else cons(a, r(a+1, b))

clRange = fix(clRange_)