Why does Integral constraint require fromIntegral on call to length?

Question

I've just started programming in Haskell, and I am solving 99 Haskell problems, and when I was nearly done with 10th, I've encountered this problem:

-- Exercise 9
pack :: Eq a => [a] -> [[a]]
pack [] = []
pack list = let (left,right) = span (== head list) list in
            left : pack right

-- Exercise 10        
encode :: (Eq a, Integral c) => [a] -> [(c, a)]
encode [] = []
encode list = map (\x -> (length x, head x)) (pack list)
-- this doesn't work      ^^^^^^^^

The error produced told me that

Could not deduce (c ~ Int)
from the context (Eq a, Integral c)
  bound by the type signature for
             encode :: (Eq a, Integral c) => [a] -> [(c, a)]
  at C:\fakepath\ex.hs:6:11-47
  `c' is a rigid type variable bound by
      the type signature for
        encode :: (Eq a, Integral c) => [a] -> [(c, a)]
      at C:\fakepath\ex.hs:6:11
In the return type of a call of `length'
In the expression: length x
In the expression: (length x, head x) 

I've managed to fix that by inserting a function I've read about in Learn you a Haskell: fromIntegral.

encode list = map (\x -> (fromIntegral $ length x, head x)) (pack list)

So, my question is, why is that needed?

I've run :t length and got [a] -> Int, which is a pretty defined type for me, which should satisfy Integral c constraint.

Answer 1

The type signature (Eq a, Integral c) => [a] -> [(c, a)] means the function works for any types a and c in the appropriate typeclasses. The actual type used is specified at the call site.

As a simple example, let's take a look at the type of the empty list:

:t []
[a]

What this means is that [] represents an empty list of String, and empty list of Int, an empty list of Maybe [Maybe Bool] and whatever other types you can imagine. We can imagine wrapping this in a normal identifier:

empty :: [a]
empty = []

empty obviously works the same way as []. So you can see that the following definition would make no sense:

empty :: [a]
empty = [True]

after all, [True] can never be a [Int] or [String] or whatever other empty list you want.

The idea here is the same, except we have typeclass constraints on the variables as well. For example, you can use encode to return a [(Integer, String)] list because Integer is also in the Integral class.

So you have to return something polymorphic that could be any Integral--just what fromIntegral does. If you just returned Int, encode would only be usable as an Int and not any Integral.