Haskell Tree - searching through tree

Question

I'm having issues with my assignment: I'm trying to write a code that makes a list of all node-values I tell him to (for example, all nodes with the value 4 into a neat list).

I wrote the following:

findValue :: a -> (MyTree a) -> [a]
findValue x Leaf = []
findValue x (Node a l r)
    |a == x = x++(findValue x l)++(findValue x r)
    |a /= x = (findValue x l)++(findValue x r)

I had defined trees as follow:

data MyTree a = Leaf  | Node a (MyTree a) (MyTree a)

I get the following error-message:

Couldn't match expected type ‘[a]’ with actual type ‘a’
      ‘a’ is a rigid type variable bound by
          the type signature for findValue :: a -> MyTree a -> [a]
          at assignment.hs:10:14
    Relevant bindings include
      r :: MyTree a (bound at assignment.hs:12:25)
      l :: MyTree a (bound at assignment.hs:12:23)
      a :: a (bound at assignment.hs:12:21)
      x :: a (bound at assignment.hs:12:11)
      findValue :: a -> MyTree a -> [a]
        (bound at assignment.hs:11:1)
    In the first argument of ‘(++)’, namely ‘x’
    In the expression: x ++ (findValue x l) ++ (findValue x r)

I would be very happy if someone explained the error message to me. Thanks in advance!

Answer 1

The type of (++) is [a] -> [a] -> [a], but the type of x is a. Thus you can write

x : (findValue x l) ++ (findValue x r) (which uses the "cons" operator (:) :: a -> [a] -> [a]), or

[x] ++ (findValue x l) ++ (findValue x r)

Here's how you should determine this yourself:

The error says Couldn't match exptected type '[a]' with actual type 'a' ... in the first argument of '(++)', namely 'x'

This means that the argument x to (++) (on the line indicated) should have type [a] (that's the expected type), but actually has type a (the inferred type).

Then you should look up the type signature for (++) to see what the problem might be (e.g. using hoogle, hayoo, or ghci) In your case, the problem was that the types of the first and second arguments to (++) were not the same, but they should be.

Answer 2

Think about what you are doing. findValue is of the type a -> MyTree a -> [a] which means that x is of the type a.

However, the (++) operator is of the type [a] -> [a] -> [a], but you are writing x ++ (findValue x l) ++ (findValue x r). Hence it gives you an error saying:

Couldn't match expected type ‘[a]’ with actual type ‘a’
      ‘a’ is a rigid type variable bound by
          the type signature for findValue :: a -> MyTree a -> [a]
          at assignment.hs:10:14
    Relevant bindings include
      r :: MyTree a (bound at assignment.hs:12:25)
      l :: MyTree a (bound at assignment.hs:12:23)
      a :: a (bound at assignment.hs:12:21)
      x :: a (bound at assignment.hs:12:11)
      findValue :: a -> MyTree a -> [a]
        (bound at assignment.hs:11:1)
    In the first argument of ‘(++)’, namely ‘x’
    In the expression: x ++ (findValue x l) ++ (findValue x r)

The error message clearly says that it Couldn't match expected type ‘[a]’ with actual type ‘a’. It further tells you where the problem is, In the first argument of ‘(++)’, namely ‘x’. It even tells you where to find that expression, In the expression: x ++ (findValue x l) ++ (findValue x r).

Haskell error messages might look very scary, but they are actually quite informative and easy to understand. Don't let phrases like ‘a’ is a rigid type variable bound by scare you.

I understand that it's easy to give up when the second sentence you read is something you don't understand, and I understand that it's easier to post a question about it on SO. Do yourself a favor and don't. Learn how to understand error messages.

Give a man a fish and he'll eat for one day. Teach a man to fish and he'll eat for his entire life.

---

BTW, why do you need a findValue function of the type a -> MyTree a -> [a]? It would make more sense to have:

hasValue :: a -> MyTree a -> Bool
hasValue x Leaf         = False
hasValue x (Node a l r)
    | a == x            = True
    | otherwise         = findValue x l || findValue x r

numValue :: a -> MyTree a -> Int
numValue x Leaf         = 0
numValue x (Node a l r)
    | a == x            = depth + 1
    | otherwise         = depth
    where depth = findValue x l + findValue x r

To me it doesn't make any sense to have a findValue function because given findValue x t the result is:

1. Either an empty list or a non-empty list (False or True respectively). Hence hasValue.

2. A list of only x values repeated, in which case only the length matters. Hence numValue.

   findValue :: a -> MyTree a -> [a]
   findValue x t = replicate (numValue x t) x