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 > [EMAIL PROTECTED] > _______________________________________________ > Haskell mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell