Friday, July 01, 2005

Circular programming in Haskell

Haskell lets you write some strange-looking programs in a style known as "circular programming." If you remember how you felt the first time you saw a recursive program (usually something in between awe and fear), get ready for this... Imagine transforming a tree with integer leaves into a tree that replaces all the leaves with the minimum leaf value. Normally we'd do this in two passes: first find the minimum leaf, and then traverse the tree a second time, replacing the leaves with the minimum value. In a lazy language you can do this in one go:
data Tree = Leaf Int
| Node Tree Tree

minTree :: Tree -> Tree
minTree t = t'
where minTree' (Leaf n) = (n, Leaf n')
minTree' (Node t1 t2) = let (m1, t1') = minTree' t1
(m2, t2') = minTree' t2
in (min m1 m2, Node t1' t2')
(n', t') = minTree' t
What is so absolutely bizarre about this program is that it uses the result of the entire recursion n' in one of the recursive calls, before the result has been computed! But because it isn't actually observed until after the tree has been constructed, it's safe to do so. Another way to think of this is to imagine the value n' as a reference cell or "box" whose contents get set once at the end of the computation; we don't look inside it until after the computation is over, but during the computation we're allowed to pass the box around and put it inside other nodes.

I've seen some pretty weird Haskell programs that use this kind of trick, passing the result of a function in as one of its own arguments, for example. Of course, you can't just do this however you like. For example, we can't possibly imagine this program would give us a useful result:
data Thing = Leaf
| Node Thing

f :: Bool -> Thing -> Int
f _ (Node v) = i'
where i' = f (i' == 0) v
f isZero Leaf = if isZero then 1 else 0
The isZero argument is a flag that means something like "will my result by unequal to itself?"

No comments: