[Haskell-beginners] Tying the knot

Alex Rozenshteyn rpglover64 at gmail.com
Wed Dec 29 20:31:48 CET 2010


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 at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>



-- 
          Alex R
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20101229/25d48f2f/attachment.htm>


More information about the Beginners mailing list