CODEWITHSUNDEEP
haskell
KillPinguin
KillPinguin

Reputation: 410

Debugging type Errors in Haskell

I'm trying to write a function, returning all permutations from a list in Haskell:

perms :: [a] -> [[a]]
perms [] = [[]]
perms xs = map (\y -> concat_each y (perms (list_without y xs))) xs

list_without :: (Eq a) => a -> [a] -> [a]
list_without x xs =
    filter (\y -> not (y==x)) xs

concat_each :: a -> [[a]] -> [[a]]
concat_each x xs =
    map (\y -> x:y) xs

What I think happens in line3: y is a and x is [a], so list_without y xs is [a].

perms (list_without ...) is thus [[a]]

so concat_each y (perms ...) gets a and [[a]], resulting in [[a]]

So the function for map is a -> [[a]] and everything should be okay.

But the compiler seems to see things differently:

Couldn't match type `a' with `[a]'
  `a' is a rigid type variable bound by
      the type signature for perms :: [a] -> [[a]]
      at C:\Users\Philipp\Desktop\permutations.hs:1:10
Expected type: [a]
  Actual type: [[a]]
Relevant bindings include
  y :: a (bound at permutations.hs:3:18)
  xs :: [a] (bound at permutations.hs:3:7)
  perms :: [a] -> [[a]]
    (bound at permutations.hs:2:1)
In the expression: concat_each y (perms (list_without y xs))
In the first argument of `map', namely
  `(\ y -> concat_each y (perms (list_without y xs)))'

How would I debug this error message properly? I don't really know where to start checking my types.

Upvotes: 3

Views: 129

Answers (1)

Li-yao Xia
Li-yao Xia

Reputation: 33519

map :: (x -> y) -> [x] -> [y]

The first argument you gave to map has type a -> [[a]], i.e., x = a and y = [[a]] so

                :: [x] -> [  y  ]
map (\y -> ...) :: [a] -> [[[a]]]
                --  ^      ^^^^^
                -- x = a,  y = [[a]]

In this case, the result of that map (\y -> ...) xs is a list where each element corresponds to the permutations starting with a fixed element y in xs. In the end, you don't care which element a permutation starts with; you can forget that separation using concat:

perms = concat (map (\y -> ...) xs)

-- or

perms = concatMap (\y -> ...) xs

-- or

perms = xs >>= \y -> ...

Upvotes: 5

Related Questions