How does "tying the knot" on this cyclic linked list in Haskell work?

Question

I am learning Haskell and was reading through Tying the Knot on how to build a cyclic linked list. In the code

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)

I am trying to understand the call where they link the last element to the first through a "little trick" (!) called tying the knot:

mkDList xs = let (first,last) = go last xs first

But I am having difficulty seeing how this works. What is "go" initially called with? And per the comment in the article, how is the first result from "go" "passed back in"?

Thanks!

Answer 1

Since Haskell is lazy, values are evaluated until strictly necessary. We can walk through a simple example using equational reasoning to see where that gets us.

Start with the simplest example: a one-element list.

mkDList [1] == let (first, last) = go last [1] first in first

It seems that you can't call go, because you don't know what last and first are equal to yet. However, you can think of them as unevaluated black boxes: it doesn't matter what they are, just that you can proceed with equational reasoning with them.

-- Just plug last and first into the definition of go
-- last2 is just a renaming of the argument for clarity
go last [1] first == let this = DLNode last 1 rest
                         (rest, last2) = go this [] first
                     in (this, last2)

Let's try to evaluate the next call to go in the same way.

go this [] first == (first, this)

Conveniently, we didn't need to imagine any new black boxes; go simply evaluates to its original arguments in a slightly repackaged manner.

OK, now we can go back the way we came, and replace the recursive call to go with its evaluation.

go last [1] first == let this = DLNode last 1 rest
                         (rest, last2) = (first, this)
                     in (this, last2)

And we'll plug this back into our original equation with mkDList:

mkDList [1] == let (first, last) = let this = DLNode last 1 rest
                                       (rest, last2) = (first, this)
                                   in (this, last2)
               in first

This doesn't look too helpful, but remember, we haven't actually called mkDList yet; we just used equational reasoning to simplify its definition a little bit. In particular, there are no recursive calls to go, just one let expression nested in another.

---

Since Haskell is lazy, we don't have to evaluate any of this until it is absolutely necessary, such as when we try to pattern-match against the return value of mkDlist [1]:

let (DLNode p x n) = mkDList [1] in x

To evaluate this expression, we just need to ask the following questions:

1. "What is the value of x?" Answer: we need to pattern-match against mkDList [1] first.
2. "What is the value of mkDList?" Answer: first.
3. "What is the value of first?" Answer: this.
4. "What is the value of this?" Answer: DLNode last 1 rest

At this point, you have enough information to see that x == 1, and last and rest don't need to be evaluated further. You could, though, pattern match again to see what, for example, p is, and discover that

p == last == last2 == this == DLNode last 1 rest

and

n == rest == first == this == DLNode last 1 rest

---

The magic is a call like (first, last) = go last xs first doesn't actually need values for its arguments; it just needs placeholders to keep track of what values first and last will eventually get when they are evaluated. These placeholders are called "thunks", and they represent pieces of unevaluated code. They let us refer to boxes that we haven't filled with anything yet, and we can pass the empty boxes to go safe in the knowledge that somebody will fill them before anyone else tries to look in them. (In fact, go itself never does; it simply keeps passing them along until somebody outside of mkDList tries to look at them.)