How do I implement a filter through an instance?-CodePudding

Is there any instance to use a filter with its own type? Right now I have this type:

data Tree a = Leaf | Node a Color (Tree a) (Tree a) deriving (Show)

And I'd like to write something like:

filter (>4) tree

If there is such an instance, can someone give me an example code, because I do not understand how it should be different from fmap

CodePudding user response：

In base, there's no typeclass for filter and it can only be used on lists. But if you use the witherable package, then you'll get a Filterable typeclass that you can use. Here's the beginning of one possible instance for your type:

instance Filterable Tree where
    mapMaybe _ Leaf = Leaf
    mapMaybe f (Node x c l r) = case f x of
        Just j -> _
        Nothing -> _
        where l' = mapMaybe f l
              r' = mapMaybe f r

Once you finish writing mapMaybe, you'll get catMaybes and filter for free.

CodePudding user response：

Any filter that removes items will involve a lot of rebalancing anyway, for a red-black tree, won't it? So I'm not really sure this will be more efficient than getting the elements to keep as a list and rebuilding the tree from scratch by insertions. Presuming the obvious Foldable Tree instance and a function insert :: a -> Tree a -> Tree a, I'd just define

filterTree :: (a -> Bool) -> Tree a -> Tree a
filterTree f = foldr insert Leaf . foldMap keep
  where keep n | f n = [n]
               | otherwise = []

But of course since it's obviously expensive, I'd try to avoid using it.