CODEWITHSUNDEEP
haskell
user2476499
user2476499

Reputation: 31

A Filter function in Haskell

My Tree definition is as follows:

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

I want to write a filter function that picks only every 3rd element of an array (1st, 4th, 7th, ...). As an example, suppose my tree is as follows:

Node 
    (Node 
        (Node 
            (Leaf 'a') 
            (Leaf 'b')) 
        (Leaf 'c'))
    (Node 
        (Node 
            (Leaf 'd') 
            (Leaf 'e')) 
        (Leaf 'f'))

Then the filter function should result in a new tree as:

Node (Leaf 'a') (Leaf 'd')

Upvotes: 3

Views: 791

Answers (1)

luqui
luqui

Reputation: 60463

Here's a gameplan for you.

  1. Write a function that applies a function to each element of your tree. 

    mapTree :: (a -> b) -> Tree a -> Tree b

    (Bonus: make Tree a Functor instance, and use fmap instead of mapTree)

  2. Write a function that labels the elements of a tree in order of their left-to-right occurrence.

    labelTree :: Tree a -> Tree (Integer, a)

    (Hint: you will need an auxiliary function which takes a "current label" and returns the labeled tree together with a new label; i.e. :: Integer -> Tree a -> (Tree (Integer, a), Integer). The branch case of this function goes like this:

    aux n (Branch l r) = 
    let (l', n')  = aux n l
        (r', n'') = aux n' r in
    (Branch l' r', n'')

    Carefully read this code, and then see if you can come up with the Leaf case)

    (Bonus: do it using the State monad)

  3. Write a function which removes the elements of a tree which do not satisfy a condition.

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

    Notice that we return a Maybe (Tree a) rather than just a Tree a -- this is because we need to have something to return if no elements match the condition, and your Tree type does not permit empty trees. It so happens that returning a Maybe (Tree a) also makes this function quite straightforward to write recursively.

  4. Combine these functions to get the function you are looking for -- filtering out only the elements with labels that are divisible by 3.

The nice thing about decomposing it this way is that, in addition to solving your specific problem, you have written yourself a number of generally useful tools for working with your Tree type. Maps and filters are very common functions that appear when implementing a data structures.

Advanced: the State monad bonus implementation of labelTree is a specific case of another common type of function called a "traversal":

traverse :: (Applicative f) => (a -> f b) -> Tree a -> f (Tree b)

which is like a map but also combines the "effects" that can occur on each element. Super double-plus bonus if you can implement it and then use it to write labelTree.

Upvotes: 4

Related Questions