Joachim Breitner wrote:
Assume you have a tree (and you can think of a real tree here), defined by something like this:
data Tree a = Bud | Branch a Double Tree Tree -- | ` Lenght of this branch -- ` General storage field for additional information
Now, I have a nice algorithm that calulates something for each branch, but it only works on lists of branches, so I have to cut them apart first, remembering their position in space, and then work on these, well, logs.
data Point = Point Double Double data Log = Log Point Point type Info = ... noInfo :: Info
cutTreeApart :: Tree a -> [(Log, a)] someAlgorithm :: [(Log,a)] -> [(a, Info)]
Conveniently, the algorithm allows me to tag the logs with something, to be able to keep track at least somewhat of the logs.
[...]
Some ideas where numbering the Nodes and then using this number as the tag on the log, but this is not much different from using STRefs, it seems.
Yes, tagging the logs with their position in the tree isn't really different from using STRefs. There are many options for representing positions (depth/breath first numbers; paths like [L,R,L,...] etc.) but in the end, it boils down to the same thing. Here's an example with with numbers annotate tree = thread tree (\(x:xs) -> (x,xs)) . map snd . sort (comparing fst) . someAlgorithm . cutTreeApart . thread tree (\n -> (n, succ n)) $ (0 :: Int) where thread tree f x = evalState (mapM (const $ State f) tree) x However, I would be surprised if someAlgorithm could not be formulated directly on the tree or at least satisfies a few invariants like for example map fst . someAlgorithm = map snd Also, how does cutTreeApart arrange the list? The idea is that most of the tree structure survives in the list and can be reconstructed. Regards, apfelmus -- http://apfelmus.nfshost.com