Synook

Functional Python

Ever tried to learn Haskell? Confused? Know Python? How about trying to write some functional code in Python? And no, I don’t even mean just using functional principles in Python as the docs describe, I mean actually writing Python like you write Haskell:

"""
printing
"""

def dirty_print (a):
    print printr (a)
    return a
def printr (a, inside = False):
    if type(a ()) is tuple:
        lstr = "%s:%s" % (printr(a()[0],True),printr(a()[1]))
        return "(%s)" % lstr if inside else lstr
    else: return a ()

"""
base / translation (lots of currying) (also, everything-is-a-function)
needed since Python's basic functions aren't in the `functional' style
"""

_ = lambda n: lambda: n # literal function
multiply = lambda a: lambda b: lambda: a () * b ()
minus = lambda a: lambda b: lambda: a () - b ()
plus = lambda a: lambda b: lambda: a () + b ()
div = lambda a: lambda b: lambda: a () / b ()
gt = lambda a: lambda b: lambda: a () > b ()
eq = lambda a: lambda b: lambda: a () == b ()
flip = lambda f: lambda a: lambda b: f (b) (a)
choice = lambda cond: lambda t: lambda f: lambda: (
    t () if cond () else f ()
)

"""
`lists' (cons cells in Haskell) - we'll use 2-tuples.
"""

# `dirty' (i.e, deal with the underlying data structure)

emptylist = lambda: [] # i.e., [] in haskell
cons = lambda x: lambda xs: lambda: (x, xs)
head = lambda xs: lambda: xs()[0]()
tail = lambda xs: lambda: xs()[1]()
__ = lambda l: lambda: ( # sugar (like Haskell's [...] syntax)
    choice (lambda: len(l) == 0)
        (emptylist)
        (choice (lambda: len(l) == 1)
            (cons (l[0]) (emptylist))
            (cons (l[0]) (__(l[1:])))
        )
) ()

# `clean' higher-order list functions

length = lambda xs: lambda: (
    choice (eq (xs) (emptylist))
        (_(0))
        (plus (_(1)) (length (tail (xs))))
) ()
foldr = lambda f: lambda xs: lambda: (
    choice (eq (tail (xs)) (emptylist))
        (head (xs))
        (f (head (xs)) (foldr (f) (tail (xs))))
) ()
f_map = lambda f: lambda xs: lambda: (
    choice (eq (xs) (emptylist))
        (emptylist)
        (cons (f (head (xs))) (f_map (f) (tail (xs))))
) ()
repeat = lambda a: lambda: (
    cons (a) (repeat (a))
) ()
take = lambda a: lambda xs: lambda: (
    choice (gt (a) (_(0)))
        (cons (head (xs)) (take (minus (a) (_(1))) (tail (xs))))
        (emptylist)
) ()

"""
higher order demonstrations
"""

# sum (partial application)
f_sum = foldr (plus)

# fibonacci function - the need for an extra lambda wrapper is a
# quirk of how Python handles recursive evaluation, AFAIK
fib = lambda n: lambda: (
    choice (gt (n) (_(2)))
        (plus 
            (fib (minus (n) (_(1))))
            (fib (minus (n) (_(2))))
        )
        (_(1))
) ()

# partial application (also, argument omission)
mult_two = multiply (_(2))

# completely lazy evaluation (a natural consequence of the
# functional style!)
not_an_error = f_map (flip (div) (_(0))) (__([_(2),_(4)]))

"""
output
"""

dirty_print (mult_two (_(3)))
dirty_print (f_map (mult_two) (__([_(1), minus (_(4)) (_(5)), _(3)])))
dirty_print (choice (gt (_(2)) (_(1))) (_(1)) (_(0)))
l = __([_(1),_(2),_(3),_(4)])
dirty_print (length (l))
dirty_print (f_sum (l))
dirty_print (fib (_(6)))
dirty_print (take (_(5)) (repeat (_(1))))
dirty_print (__([__([_(1)]), l]))

Does Haskell make a bit more sense now? Perhaps not, but the point is, most of Haskell’s seemingly “magical” features, such as partial evaluation and lazy evaluation, are not necessary special to the language: rather, they are just a natural consequence of functional programming. It is perfectly possible to have things like infinite-length “lists” anywhere, as demonstrated above — it’s just how functional programming works.