Thank you. I'm still unclear as to how tying the know works and when it is useful, but at least one of my misconceptions has been clarified. I haven't given my `Person`s unique ids yet, thinking that I could avoid it if I worked carefully. Guess it's not worth the effort. On Wed, Dec 29, 2010 at 7:49 AM, Heinrich Apfelmus < apfelmus@quantentunnel.de> wrote:

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

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- Alex R

My brain turns into strange braid when I see this kind of thing. I don't quite understand it and I've never used it in real world code but I'll try and explain anyway. Caveat emptor. First forget about 'labelLeaves' and think a function that only returned the leaf count: count :: Tree a -> Int count tree = c where c = count' tree count' (Branch a b) = na+nb where na = count' a nb = count' b count' (Leaf _) = 1

count $ Branch (Leaf "hello") (Leaf "world") 2

Now look at 'n' and imagine it was a memory location. Mentally substitute some hex address (like 0x0000) if it makes it easier. Here's what the function looks like now: labelLeaves :: Tree a -> Tree Int labelLeaves tree = tree' where (0x0000, tree') = label 0x0000 tree -- n is both result and argument! label 0x0000 (Branch a b) = (na+nb, Branch a' b') where (na,a') = label 0x0000 a (nb,b') = label 0x0000 b label 0x0000 (Leaf _) = (1, Leaf 0x0000) So if labelLeaves is given (Branch (Leaf "hello") (Leaf "world")) as an argument, and we continue to think of 'n' as a memory location the function returns something like: (Branch (Leaf 0x0000) (Leaf 0x0000)) The part of the function where the leaves are counted up is exactly like my 'count' example above, but when the function is done instead of just returning it this line: (n,tree') = label n tree assigns the final count to 'n'. If 'n' is a memory location the final leaf count would be sitting in 0x0000. Subbing the value at that location into the result we get: (Branch (Leaf 2) (Leaf 2)) -deech On Wed, Dec 29, 2010 at 4:52 PM, Patrick LeBoutillier wrote:

Heinrich,

...

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)

This looks completely freaky to me... how does it work? Is it the laziness that allows the sum to be calculated first while preserving the structure (as thunks?), and then once the value of n is known it is propagated back down the tree and the actual tree values constructed? Anyways this is really amazing to my newbie eyes...

Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

aditya siram wrote:

My brain turns into strange braid when I see this kind of thing. I don't quite understand it and I've never used it in real world code but I'll try and explain anyway. Caveat emptor.

[..]

Now look at 'n' and imagine it was a memory location. Mentally substitute some hex address (like 0x0000) if it makes it easier.

Another way to look at it is to observe that the result n does not depend on the input n , even though the notation might suggest otherwise. To see that, let _|_ denote an expression that is undefined , i.e. raises an error when you try to evaluate at it. Using the definition data Tree a = Branch (Tree a) (Tree a) | Leaf a 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) we have label _|_ (Branch (Leaf 'c') (Leaf 'd')) = (na+nb, Branch a' b') where (na,a') = label _|_ (Leaf 'c') (nb,b') = label _|_ (Leaf 'd') = (1+1, Branch (Leaf _|_) (Leaf _|_)) So, even though the argument n is undefined, the function label still produces a partially defined result. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com