[Haskell-beginners] Does Haskell have a function that creates a list corresponding to the nodes in a tree, from the leaf node to the root node?

[Thomas Davie]

The problem with knot tying exercises is that as soon as you try to update you're in trouble.

With an update in a tree with no parent pointers only the spine to get to the node being replaced in the tree need be recreated, all other parts of the tree can simply be referenced as they were before.  If you tie the knot on the other hand, every part of the tree must be recreated as soon as you update one node.

Bob

On 12 Jun 2011, at 23:17, Markus Läll wrote:

> Hi Roger,
> 
> how that function works depends on what kind of tree you have. Without
> parent-pointers it's essentially impossible to find the way back to
> the root. If you have the root, and an instruction of how to get to
> the leaf, then it's just a matter of prepending nodes to a list until
> the instruction runs out.
> 
> But it actually *is* possible to efficiently have parent-pointers,
> though it's not obvious when you come into to the language. The
> technique is called tying the knot. What it basically means is to have
> circular definitions, e.g having some expression bound to a name and
> using that name in that same expression. Check it out:
> 
> data Tree a = Tree {
>  { left  :: Maybe (Tree a)
>  , right :: Maybe (Tree a) }
> 
> data PTree a = PTree
>  { pLeft   :: Maybe (Tree a)
>  , pRight  :: Maybe (Tree a)
>  , pParent :: Maybe (Tree a) }
> 
> toP (Tree l r v) = let
>     f :: Tree a -> TreeP -> TreeP
>     f Nothing _ = Nothing
>     f (Just (Tree l r)) parent = let
>           self = TreeP (f l self) (f r self) (Just parent) -- tying
> the knot here ..
>        in self
>     root = TreeP (f l root) (f r root) Nothing             -- .. and here
>  in root
> 
> (The Maybes are there to mark lack of children in left and right
> positions and lack of a parent in the parent position.)
> 
> Using this technique you can have all graphy data structures like
> doubly linked lists and so on. The most simple knot tied is the black
> hole:
> x = x
> , which takes forever to evaluate. And you can explicitly write graphs like:
> 
> data Node = Node Char [Node]
> 
> g = let
>     a = Node 'A' [b, c]
>     b = Node 'B' [c]
>     c = Node 'C' [g, b, c]
>  in Node 'G' [a]
> 
> 
> --
> Markus Läll
> 
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners