Haskell “could not deduce” error

Question

I have the following code:

class Coll c e where
    map :: (e1 -> e2) -> c e1 -> c e2
    merge :: (e -> e -> e) -> e -> c e -> e
    sum :: (Num e) => c e -> e
    sum = merge (+) 0

So far so good. But then I have:

    sumMap :: (Num e2) => (e1 -> e2) -> c e1 -> e2
    sumMap f c = (merge (+) 0) (map f c)

Compiling gives an error:

Could not deduce (Coll c e2) arising from a use a 'merge' from the context (Coll c e) [...] Possible fix: add (Coll c e2) to the context of the type signature for sumMap [...]

So I replace sumMap :: (Num e2) => (e1 -> e2) -> c e1 -> e2 with sumMap :: (Num e2, Coll c e2) => (e1 -> e2) -> c e1 -> e2, but then it gives another error:

Could not deduce (Coll c e0) arising from a use of 'map' from the context (Coll c e) [...] Possible fix: add a type signature that fixes these type variable(s) [...]

I'm confused, so I comment out the definition for sumMap, and run :t (merge (+) 0) . (map (* 2)), which gives me [...] :: (Num c, Coll c1 c, Coll c1 e) => c1 c -> c. Ignoring how it mangled my variables' names, Coll c1 e is bizarre; e is not even used in the definition!, so why is it there!? Anyways, then I run ((merge (+) 0) . (map (* 2))) [1,2,3,4], which successfully returns 20. What's going on here? Why does this function work only when I don't try to tie it to a name?

"e is not even used in the definition!, so why is it there!? " - That is exactly the problem! e isn't used in the definition, so the compiler can never determine what type it should have, but it must be there because the class was declared with 2 parameters. As an aside, I anticipate this was a learning exercise, but your class is just Foldable is disguise. — user2407038

Tikhon Jelvis Tikhon Jelvis · Accepted Answer · 2014-12-12T22:58:35

Your problems stems from the way you defined your Col class. In particular, the class definition includes both types c and e. This means that you can have different instances for different types of elements—presumably not what you want. Instead, you want to have a single instance for each possible c that works with any type of element at all.

It would be better to write the class as:

class Coll c where
  map :: (e1 -> e2) -> c e1 -> c e2
  merge :: (e -> e -> e) -> e -> c e -> e
  sum :: Num e => c e -> e
  sum = merge (+) 0

Now each individual instance only depends on c, not the type of its elements.

I suspect that you wrote class Coll c e where because you wanted to ensure that c was a collection of elements. (Like writing C<E> in Java.) However, this is unnecessary in Haskell: a type variable like c can stand in for parameterized types with no other annotation. The type system will figure out that c takes a parameter by the way you use it in the signatures for map, merge and so on.

Since this is unnecessary, class Coll c e means that the class is based on two different type variables, which don't even have to be related. This means that, to figure out which instance to use, the type system needs to know the specific type for both the collection and its elements, and in your specific case it does not have enough information to do this. If you just leave e out of the class definition, it should not be a problem.

Haskell “could not deduce” error

1 Answers