E
Ertugrul Söylemez
Hello there Pythoners,
It was almost a week ago, when I got bored and thought, Python is quite
a boring language, so I'd need to do some evil functional programming
again. I thought, I'd share the result.
This time, I added a Church style representation for lists [1] to
Python. The problem they solve: What do you do, if you've got only
scalar values, functions and function application, but you need lists?
Here is the solution: Represent lists as higher order functions:
def empty():
return lambda f, z: z
def cons(x, xs):
return lambda f, z: f(x, xs(f, z))
def fold(f, z, xs):
return xs(f, z)
The empty() function returns an empty list and the cons() function
returns the list in its second argument with the element in its first
argument prepended, so cons(x, xs) is equivalent to the list [x] + xs.
The 'fold' function is actually superfluous, but it makes much clearer
what you're doing, when using this type of lists. It's the
right-associative version of the 'reduce' function. All other list
operations can be defined in terms of these three functions. I've done
that for you [2] (mostly).
If Python implements closures efficiently, this list representation is
actually very fast for list folding, i.e. consuming an entire list to
construct a value (which may be anything, including lists or functions).
However, it's slow for extracting individual elements, because this
operation must be a fold, too, as folding is the only way to access the
elements of a list.
An interesting property of this representation is that it gets along
without any impure functions, i.e. all functions are completely free of
side effects. Unless you use an impure fold function, everything is
perfectly purely functional.
Have fun. =)
Greets,
Ertugrul.
[1] http://en.wikipedia.org/wiki/Church_encoding#Higher-order-function,
a representation of a list as a higher order function.
[2] http://ertes.de/python/fun/chlists.py, a little library of Python
functions implementing Church style lists using higher order
functions. The way the 'range' function is defined, was an
experiment: how to emulate partial application in Python.
Greets,
Ertugrul.
It was almost a week ago, when I got bored and thought, Python is quite
a boring language, so I'd need to do some evil functional programming
again. I thought, I'd share the result.
This time, I added a Church style representation for lists [1] to
Python. The problem they solve: What do you do, if you've got only
scalar values, functions and function application, but you need lists?
Here is the solution: Represent lists as higher order functions:
def empty():
return lambda f, z: z
def cons(x, xs):
return lambda f, z: f(x, xs(f, z))
def fold(f, z, xs):
return xs(f, z)
The empty() function returns an empty list and the cons() function
returns the list in its second argument with the element in its first
argument prepended, so cons(x, xs) is equivalent to the list [x] + xs.
The 'fold' function is actually superfluous, but it makes much clearer
what you're doing, when using this type of lists. It's the
right-associative version of the 'reduce' function. All other list
operations can be defined in terms of these three functions. I've done
that for you [2] (mostly).
If Python implements closures efficiently, this list representation is
actually very fast for list folding, i.e. consuming an entire list to
construct a value (which may be anything, including lists or functions).
However, it's slow for extracting individual elements, because this
operation must be a fold, too, as folding is the only way to access the
elements of a list.
An interesting property of this representation is that it gets along
without any impure functions, i.e. all functions are completely free of
side effects. Unless you use an impure fold function, everything is
perfectly purely functional.
Have fun. =)
Greets,
Ertugrul.
[1] http://en.wikipedia.org/wiki/Church_encoding#Higher-order-function,
a representation of a list as a higher order function.
[2] http://ertes.de/python/fun/chlists.py, a little library of Python
functions implementing Church style lists using higher order
functions. The way the 'range' function is defined, was an
experiment: how to emulate partial application in Python.
Greets,
Ertugrul.