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