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