[Haskell-beginners] Tying the knot

[Heinrich Apfelmus]

Alex Rozenshteyn wrote:
> I'm trying to understand the technique referred to as "tying the knot", but
> documentation on the internet seems to be much sparser and more obtuse than
> I like.
> 
> So I'm asking here.
> 
> As far as I understand, "tying the knot" refers to a way of using laziness
> to implement something like references in a purely functional way.

Not really.

"Tying the knot" refers to writing a seemingly circular program, where 
the result of a function is used as argument to the very same function.

A canonical example is the following solution to the problem of labeling 
all the leaves in a tree with the total leaf count:

     data Tree a = Branch (Tree a) (Tree a) | Leaf a

     labelLeaves :: Tree a -> Tree Int
     labelLeaves tree = tree'
         where
         (n, tree') = label n tree  -- n is both result and argument!

         label n (Branch a b) = (na+nb, Branch a' b')
             where
             (na,a') = label n a
             (nb,b') = label n b
         label n (Leaf _)     = (1, Leaf n)


In some cases, this be used to implement read-only doubly-linked lists 
and other things that seem to require references, but not everything 
involving references can be solved by tying a knot; in particular, the 
references will be read-only.


(Feel free to put my blurb above on the HaskellWiki.)

> I'm trying to write a toy simulation:
> I have a population :: [Person]
> I want to collect a random subset of possible pairs of distinct people.
> So I go to each person in the population and select a subset of the people
> after him/her in the list; these are pairs in which s/he is the first
> element.
> 
> I want to then be able to ask for all pairs in which a person is the first
> or the second element.  I could give each person a unique id, but it seems
> like tying the knot is a valid way to implement this.

This situation doesn't have anything to do with tying the knot. After 
all, how do you distinguish persons in the first place? You probably 
already gave the unique IDs. Then, it's simply a matter of applying the 
function

     filter (\(x,y) -> x == p || y == p)

where  p  is the person you are looking for.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com