TyingTheKnot

Remember that Haskell is a lazy language. A consequence of this is that while you are building the node, you can set the children to the final values straight away, even though you don't know them yet! It twists your brain a bit the first few times you do it, but it works fine.

Here's an example. Say you want to build a circular, doubly-linked list, given a standard Haskell list as input. The back pointers are easy, but what about the forward ones?

  data DList a = DLNode (DList a) a (DList a)
   mkDList :: [a] -> DList a
   mkDList [] = error "must have at least one element"
  mkDList xs = let (first,last) = go last xs first
               in  first
     where go :: DList a -> [a] -> DList a -> (DList a, DList a)
          go prev []     next = (next,prev)
          go prev (x:xs) next = let this        = DLNode prev x rest
                                    (rest,last) = go this xs next
                                in  (this,last)
   takeF :: Integer -> DList a -> [a]
  takeF 0     _                 = []
  takeF (n+1) (DLNode _ x next) = x : (takeF n next)
   takeR :: Show a => Integer -> DList a -> [a]
  takeR 0     _                 = []
  takeR (n+1) (DLNode prev x _) = x : (takeR n prev)
 

The trickery takes place in `go'. `go' builds a segment of the list, given a pointer to the node off to the left of the segment and off to the right. Look at the second case of `go'. We build the first node of the segment, using the given prev pointer for the left link, and the node pointer we are *about* to compute in the next step for the right link.

This goes on right the way through the segment. But how do we manage to create a *circular* list this way? How can we know right at the beginning what the pointer to the end of the list will be?

Take a look at mkDList. Here, we simply take the (first,last) pointers we get from `go', and *pass them back in* as the next and prev pointers respectively, thus tying the knot. This all works because of lazy evaluation.