Map with multiple arguments an Trees

Question

i have a problem with a map function and recursion.

I have a Tree data structure like this:

data Tree a = T a [Tree a] deriving (Eq,Ord,Show)

I already have a working function to count "through" the Tree which works.

count :: Tree a -> Int
count (T _ xs) = 1 + sum(map count xs)

No i want a function to proof every element of the tree with a predicate

filterKnoten :: (a -> Bool) -> Tree a -> [a]
filterKnoten p (T x []) = (if p(x) then [x] else []) 
filterKnoten p (T x xs) 
                    | p(x) == True = x:(map multP xs)
                    | p(x) == False = map multP xs
                    where multP = filterKnoten p

Some sample date would be

ex1 = T True [T False [T True[]] , T True []]

No when i call the method with for example

filterKnoten (==True) ex1

As a result I want to have list with all elements which fits my predicate, but the compile gives me this when i want to load the module

Couldn't match type `a' with `[a]'
  `a' is a rigid type variable bound by
      the type signature for filterKnoten :: (a -> Bool) -> Tree a -> [a]
      at WS11.hs:138:17
Expected type: Tree a -> a
  Actual type: Tree a -> [a]
In the first argument of `map', namely `multP'
In the expression: map multP xs
In an equation for `filterKnoten':
    filterKnoten p (T x xs)
      | p (x) == True = x : (map multP xs)
      | p (x) == False = map multP xs
      where
          multP = filterKnoten p
Failed, modules loaded: none.

So my question, why does map works with count and not with filterKnoten?

Thanks in advance

Answer 1

I imagine that writing the function using recursion is a useful exercise, but from a practical standpoint, you can just derive all of these functions with GHC extensions:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

import Data.Foldable    
import Data.Traversable 

data Tree a = T a [Tree a] deriving (Eq,Ord,Show, Functor, Traversable, Foldable)

filterTree :: (a -> Bool) -> Tree a -> [a]
filterTree f = filter f . toList  -- toList is defined in Foldable

You don't need Traversable for this example, it is just one of the other useful things you can derive.

Answer 2

Your major problem is that you're mapping a function of type T a -> [a] which gives you back [[a]] instead of the [a] you want. This can be fixed by changing map to concatMap from Data.List

import Data.List
...
filterKnoten :: (a -> Bool) -> Tree a -> [a]
filterKnoten p (T x []) = if p x then [x] else []
filterKnoten p (T x xs) 
                    | p x       = x:(concatMap multP xs)
                    | otherwise = concatMap multP xs
                    where multP = filterKnoten p

Notice that I've also gotten rid of the useless ==True and ==False's. x == True is precisely the same as x and when we're talking about to cases there's no point in computing the same thing twice. Especially since it's potentially very expensive. otherwise is just a synonym for True that prelude provides. I've also gotten rid of some of the unnecessary parens.

Finally, you can just dump the entire first case since map and concatMap work on empty lists.