CODEWITHSUNDEEP
haskelldata-structuresfilter
Negar Alinaghi
Negar Alinaghi

Reputation: 177

How to filter a tree based on a certain condition in Haskell?

I have defined a tree data type as follow:

data Tree a = T (Tree a, Tree a) | Leaf a deriving (Show, Eq, Ord)

and I want to filter this tree based on a certain condition. The function I tried to write is: 

filterT :: (a -> Bool) -> Tree a -> Tree a
filterT c (T(Leaf x,T(t1,t2))) = if c x 
                                then (T(Leaf x, T(filterT c t1, filterT c t2)))
                                else T(filterT c t1,filterT c t2)

this function is not working properly due to the fact that the function has nothing to return in the case where none of the two leaf values (at the end) satisfies the condition. I would be grateful if you could help.

Upvotes: 3

Views: 1703

Answers (2)

behzad.nouri
behzad.nouri

Reputation: 77951

There is a possibility that no item in the entire tree satisfies the condition. Then you will have an empty tree. So you have to either expand the definition of tree to:

data Tree a = Empty | Leaf a | Node (Tree a) (Tree a)

that is, include the case for an Empty tree or change the signature of filterT to:

filterT :: (a -> Bool) -> Tree a -> Maybe (Tree a)

so that make it possible to return Nothing.

Going with the 2nd approach (1), a possibility would be to derive a Foldable instance and define the filter function in terms of right fold:

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

instance Foldable Tree where
  foldr f z (Leaf x)   = f x z
  foldr f z (Node l r) = foldr f (foldr f z r) l

filterT :: (a -> Bool) -> Tree a -> Maybe (Tree a)
filterT f = foldr go Nothing
  where
  go x z = if not (f x) then z else Just $ case z of
    Nothing -> Leaf x
    Just tr -> Node (Leaf x) tr

1. because it keeps the data type simpler and avoids redundant Node Empty Empty values.

Upvotes: 3

chepner
chepner

Reputation: 531055

Part of the problem is that you simply don't have a way to represent an empty tree.

-- Get rid of unnecessary tuple
data Tree a = Empty 
            | Leaf a 
            | T (Tree a) (Tree a) deriving (Show, Eq, Ord)

-- A filtered empty tree is still empty
filterT p Empty = Empty
-- A leaf either stays the same or becomes empty
filterT p (Leaf x) | p x = Leaf x
                   | otherwise = Empty
-- Any other tree is just the result of filtering each child
filterT p (T left right) = T (filterT p left) (filterT p right)

This isn't a great fix; it still leaves you with multiple ways of representing essentially the same tree, since Empty and T Empty Empty aren't significantly different. You could write another function which "prunes" such trees.

prune :: Tree a -> Tree a
prune (T Empty Empty) = Empty
prune x = x

which can be incorporated into your filterT function like so:

filterT _ Empty = Empty
filterT p (Leaf x) | p x = Leaf x
                   | otherwise = Empty
filterT p (T left right) = let prune (T Empty Empty) = Empty
                               prune x = x
                          in prune $ T (filterT p left) (filterT p right)

You might also extend prune to contract single-leaf trees to a single leaf (should Tree (Leaf 3) Empty and Leaf 3 be considered the same tree?), as in

filterT' _ Empty = Empty
filterT' p (Leaf x) | p x = Leaf x
                    | otherwise = Empty
filterT' p (T left right) = let prune (T Empty Empty) = Empty
                                prune (T (Leaf x) Empty)) = Leaf x
                                prune (T Empty (Leaf x)) = Leaf x
                                prune x = x
                            in prune $ T (filterT p left) (filterT p right)

Finally, whether or not you use prune will depend on whether the filtered tree should preserve the structure of the original; maybe you want to distinguish between a leaf and a node that used to have two children, for example.

Upvotes: 3

Related Questions