CODEWITHSUNDEEP
haskell
Petter Bjao
Petter Bjao

Reputation: 325

rigid type variable error in Haskell

Why this gives rigid type variable error:

data MyTree a  = Leaf [a]
               | Branch (String, a) [MyTree a] 
               deriving (Show)


list :: MyTree a -> [a]
list (Leaf [])                = []
list (Leaf m)                 = m
list (Branch _ (x:xs))        = list x ++ map (list) xs

-------------------------------------------------------------
Couldn't match type `a' with `[a]'
      `a' is a rigid type variable bound by
          the type signature for list :: MyTree a -> [a]
          at test.hs:6:15
    Expected type: MyTree a -> a
      Actual type: MyTree a -> [a]
    In the first argument of `map', namely `(list)'
    In the second argument of `(++)', namely `map (list) xs'
    In the expression: list x ++ map (list) xs

Upvotes: 2

Views: 1385

Answers (2)

David Young
David Young

Reputation: 10783

The type of map (list) xs is [[a]] and you want something of type [a]. There is a function concat that we can use: concat (map list xs), but we can write it more idiomatically with concatMap: concatMap list xs

Upvotes: 3

duplode
duplode

Reputation: 34378

The part of the error that actually tells you what is happening is:

Expected type: MyTree a -> a
  Actual type: MyTree a -> [a]
In the first argument of `map', namely `(list)'

So the type of the function you give to map is wrong. But why is it so? map has type:

map :: (a -> b) -> [a] -> [b]

list is MyTree a -> [a], and therefore:

map list :: (MyTree a -> [a]) -> [MyTree a] -> [[a]]

That means map list xs will have type [[a]]. You are using it like this:

list x ++ map list xs -- omitting unnecessary parentheses.

(++) is list concatenation; it expects two lists of the same type. list x, however, is [a] instead of [[a]], which leads to the type error. Since [a] is the type of an element of [[a]], you might try using (:), instead of (++), to prepend list x to the rest of your list-of-lists.

list (Branch _ (x:xs))        = list x : map list xs

That, however, is redundant: you are applying the same list function to x and the elements of xs. That means you can simplify it to:

list (Branch _ xs)        = map list xs

We are still not done, as map list xs has type [[a]], and you want [a]. That is easy to solve, though: just use concatMap, which maps the function and flattens the resulting list-of-lists. The full definition would then become:

list :: MyTree a -> [a]
list (Leaf m)             = m
list (Branch _ xs)        = concatMap list xs

I have removed the redundant (Leaf []) case. Note that your function did not cover the ( Branch _ []) case; that's not a problem now that we are not matching (x:xs) only.

Upvotes: 5

Related Questions