Explanation of “tying the knot”

Question

In reading Haskell-related stuff I sometimes come across the expression “tying the knot”, I think I understand what it does, but not how.

So, are there any good, basic, and simple to understand explanations of this concept?

Disable

Check here. – Loveland

Or here. :) – Biotope

Answer 1

Tying the knot is a solution to the problem of circular data structures. In imperative languages you construct a circular structure by first creating a non-circular structure, and then going back and fixing up the pointers to add the circularity.

Say you wanted a two-element circular list with the elements "0" and "1". It would seem impossible to construct because if you create the "1" node and then create the "0" node to point at it, you cannot then go back and fix up the "1" node to point back at the "0" node. So you have a chicken-and-egg situation where both nodes need to exist before either can be created.

Here is how you do it in Haskell. Consider the following value:

alternates = x where
   x = 0 : y
   y = 1 : x

In a non-lazy language this will be an infinite loop because of the unterminated recursion. But in Haskell lazy evaluation does the Right Thing: it generates a two-element circular list.

To see how it works in practice, think about what happens at run-time. The usual "thunk" implementation of lazy evaluation represents an unevaluated expression as a data structure containing a function pointer plus the arguments to be passed to the function. When this is evaluated the thunk is replaced by the actual value so that future references don't have to call the function again.

When you take the first element of the list 'x' is evaluated down to a value (0, &y), where the "&y" bit is a pointer to the value of 'y'. Since 'y' has not been evaluated this is currently a thunk. When you take the second element of the list the computer follows the link from x to this thunk and evaluates it. It evaluates to (1, &x), or in other words a pointer back to the original 'x' value. So you now have a circular list sitting in memory. The programmer doesn't need to fix up the back-pointers because the lazy evaluation mechanism does it for you.

Ammerman

This was easy! I think, the next question is: how to insert something into a doubly linked list in Haskell? – Biotope

@Biotope - The basic answer is: you make a copy of the entire list with the inserted element added. Haskell data structures are non-mutable, which is why we tend not to use doubly linked lists very much. – Ammerman

I have found some discussions, talks and articles on this subject in the Internet and i am trying learn from them, but your basic answer looks unconvincing to me: if you copy a single node of a doubly linked list in your realization, you copy the entire list, and thus you cannot add anything to it. – Biotope

Alexey, what I mean is, you have to construct a new list that contains the both the old elements and the new one. – Ammerman

I am currently wondering how to insert an item into a doubly linked list or a graph in "constant" time using "constant" additional space. – Biotope

@Biotope Well you probably can't. (unless there is some really weird edge case I am not thinking about) Well at least not within pure code, doing such a thing within ST or IO or similar would not be very difficult. – Leisha

Answer 2

It's not quite what you asked for, and it's not directly related to Haskell, but Bruce McAdam's paper That About Wraps It Up goes into this topic in substantial breadth and depth. Bruce's basic idea is to use an explicit knot-tying operator called WRAP instead of the implicit knot-tying that is done automatically in Haskell, OCaml, and some other languages. The paper has lots of entertaining examples, and if you are interested in knot-tying I think you will come away with a much better feel for the process.

Astrodome