Proposal: improve the Data.Tree API

Ross Paterson R.Paterson at
Sat Mar 1 11:31:43 UTC 2014

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.

More information about the Libraries mailing list