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