'Forest inversion'?

[Ralf Hinze]

Dear Marnix,

your transformation can be rewritten as the composition of three
functions: one that converts the forest into a binary tree (this
is based on the natural correspondence between forests and binary
trees (*), see Knuth TAOCP, Vol 1), one that mirrors a binary tree
swapping left and right subtrees, and one that transforms the
resulting binary tree back into a forest. Each of these transformations
is quite well-known, but alas I know of no name for the composition.

Cheers, Ralf

(*) The binary tree representation of forest is sometimes called
left-child, right-sibling representation. But you probably already
know that.

> Recently I've discovered an inversion operation on forests that transforms
> 'wide' forests into 'deep' onces and vice versa.  I'm sure that this
> operation is already known, however, I could not find any information on
> it. (Largely because I don't know under what name to look for it.)  You
> Haskell guys know about data structures, so you should know more. :-)
>
> Example (use a fixed with font to view): the single-tree forest
>
>           A
>          /|\
>         B C D
>
>         | | |\
>
>         E F G H
>
>           I   J
>
>           K
>
> is inverted to the forest
>
>     A      B    E
>          /| |\
>         C F I K
>        / \
>       D   G
>          / \
>         H   J
>
> and vice versa.
>
> In an implementation where every node has two pointers, one to its first
> child and one to its right-hand sibling, the inversion means that in every
> node those two pointers are swapped.
>
> In Haskell the algorithm looks like this:
> > data Forest a = Forest {trees :: [(a, Forest a)]} deriving (Show, Eq)
> >
> > inv :: Forest a -> Forest a
> > inv (Forest [])          = Forest []
> > inv (Forest ((a,f) : g)) = Forest ((a, inv (Forest g)) : trees (inv f))
>
> and it is easy to prove that for every f :: Forest a, inv (inv f) = f.
>
> What would I want to do with it?  Well, deep trees are difficult to
> navigate using existing tree controls.  Example: Suppose I want to let the
> user play a text adventure, but I allow 'undo'.  Then I can show him the
> tree of moves that he already tried, and let him backup to a previous
> state, and try something else at that point.  This results often in a deep
> tree.  So showing a wide tree instead (using the above inversion) might
> help the user. Especially if the children of a node are 'ordered' in the
> sense that the first child node is most important.
>
> So: is this 'forest inversion' known, under which name, what are the known
> uses, etc.?
>
> Thanks in advance!
>
> Groetjes,
>  <><
> Marnix
> --
> Marnix Klooster
> mklooster@baan.nl
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell