| License | MIT |
|---|---|
| Maintainer | Uwe Schmidt (uwe\@fh-wedel.de) |
| Stability | experimental |
| Portability | portable |
| Safe Haskell | Safe-Inferred |
| Language | Haskell98 |
Data.Tree.NTree.Edit
Description
Space and time efficient editing of rose trees
Documentation
editNTreeBottomUp :: (NTree a -> Maybe [NTree a]) -> NTree a -> [NTree a] Source
editNTreeBottomUp is a space optimized tree edit function
The nodes in a tree are visited bottom up. An edit function is applied to all nodes. A Nothing result of the editing function indicates no changes. This is used to share the input tree within the resulting tree.
The following law holds:
editNTreeBottomUp (const Nothing) t == [t]
In this case the resulting tree does not only represent the same value but it is the same machine value (relative to some evaluations of closures during the tree walk
With a simple fold like editing function the whole tree would be reconstructed in memory