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