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