Proposal: improve the Data.Tree API

[Yitzchak Gale]

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)

Why is filter now missing? That's the one I've needed the most.

Note however, that there are two possible implementations
of filtering for Trees and Forests. The type signature you
provided doesn't match any of them, so I'm not sure exactly what
you had in mind. I support adding all four of these:

-- | Prune every subtree whose root label does not match.
filterPruneTree :: (a -> Bool) -> Tree a -> Maybe (Tree a)
filterPruneTree p (Node x ns)
  | p x = Just . Node x $ filterPruneForest p ns
  | otherwise = Nothing

filterPruneForest :: (a -> Bool) -> Forest a -> Forest a
filterPruneForest = mapMaybe . filterPruneTree

-- | Remove nodes that do not match, and graft the children of the
removed node onto the tree in place of the parent.
filterGraftTree :: (a -> Bool) -> Tree a -> Forest a
filterGraftTree p (Node x ns)
  | p x = [Node x $ filterGraftForest p ns]
  | otherwise = filterGraftForest p ns

filterGraftForest :: (a -> Bool) -> Forest a -> Forest a
filterGraftForest = concatMap . filterGraftTree

Ross Paterson wrote:
> 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...
> perhaps it would be better to provide...
> compositions of flatten and levels with the cojoin..
> but maybe that's too abstract.

I think it's just that people missed the fact that we already
have these functions via the Comonad instance.
For that reason, I really haven't missed those functions.
I'm not sure why you're saying it's abstract - the Comonad
instance for Tree is very concrete, and in fact it's one of the
fundamental examples of a comonad.

Unfortunately, it's going to be tricky to write implementations
of these functions in terms of extend and duplicate in the
containers library itself, because containers is distributed
with GHC whereas the comonad library isn't even in the
Haskell Platform yet (it should be).

We should either just document these uses in Data.Tree,
or (for now) re-implement unexported versions of
extend and duplicate inside Data.Tree, and mention
in the documentation that these functions are simple
applications of them.

Thanks,
Yitz