'Forest inversion'?

[Marnix Klooster]

Hi all,

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