On Thu, Feb 27, 2014 at 11:34:23AM +0000, João Cristóvão wrote:
So, proposal 2.0, with the received feedback:
-- | get the sub-tree rooted at the first (left-most, depth-first) occurrence -- of the specified node value lookupTree :: Eq a => a -> Tree a -> Maybe (Tree a)
-- | get the sub-tree rooted at the first (left-most, depth-first) value that -- matches the provided condition findTree :: (a -> Bool) -> Tree a -> Maybe (Tree a)
-- | get the sub-tree for the specified node value in the first tree in -- forest in which it occurs. lookupTreeInForest :: Eq a => a -> [Tree a] -> Maybe (Tree a)
These functions are similar, and one can imagine many more along similar lines: get all the subtrees whose roots satisfy a condition, conditions involving the number of children, etc. There's a concern that the interface becomes large and unwieldy, but without covering all uses. Instead of all these, perhaps it would be better to provide a more general function from which all these could be easily constructed: -- | List of subtrees (including the tree itself), in pre-order. subTrees :: Tree a -> [Tree a] Maybe one would want post-order too. It might also be useful to have a breadth-first variant: -- | List of subtrees at each level of the tree. subTreesByLevel :: Tree a -> [[Tree a]] Then again subTrees and subTreesByLevel are compositions of flatten and levels with the cojoin -- | Label each node of the tree with its full subtree. cojoin :: :: Tree a -> Tree (Tree a) cojoin t@(Node _ ts) = Node t (map cojoin ts) but maybe that's too abstract.
-- | keep only the elements that match the provided condition filter :: (a -> Bool) -> Tree a -> Tree a
Is the idea here to drop roots (promoting the child trees) or whole subtrees? Again one might want conditions that involve the subtrees as well as the root labels.