Proposal: improve the Data.Tree API

[Ross Paterson]

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.