[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?

[Markus Läll]

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