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.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

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:

The isZero argument is a flag that means something like "will my result by unequal to itself?"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

## No comments:

Post a Comment