haskell - yet another infinite type error

Question

I am trying to solve problem 10 from the ninety nine haskell problems. Here is my solution that I believe is correct.

The pack function (from question 9) is already correct. The problem is with the encode function.

pack :: (Eq a) => [a] -> [[a]]
pack [] = []
pack (x:xs) = (x : takeWhile (== x) xs) : (pack $ dropWhile (== x) xs)

encode :: (Eq a) => [a] -> [(Int, a)]
encode [] = []
encode list = (encode' $ head packed) : (encode $ tail packed)
    where packed = pack list
          encode' l = (length l, head l) 

When I load the file from ghci, this is the error:

encode.hs:6:0: Occurs check: cannot construct the infinite type: a = [a] When generalising the type(s) for `encode'

Line 6 is the line containing encode [] = []

What's wrong with my encode function? I keep checking the types of the variables used and I believe there is nothing wrong.

Function usage example (assuming code is working correctly):

pack "aaaabbbbccccccddddddd"
> ["aaaa","bbbb","cccccc","ddddddd"]
encode "aaaabbbbccccccddddddd"
> [(4,'a'),(4,'b'),(6,'c'),(7,'d')]

Answer 1

Recursion is somewhat clumsy here. It's much better to use a higher-order function.

You already have a function encode' :: [a] -> (Int, a) that encodes one sub-list, and you want to encode all of them. Applying a function to every element of a list is a very common pattern which is encapsulated by the higher-order function map :: (a -> b) -> [a] -> [b].

Taking advantage of map, we can simply write:

encode :: (Eq a) => [a] -> [(Int, a)]
encode list = map encode' $ pack list
   where encode' xs = (length xs, head xs)

You can also avoid the helper function by using a list comprehension:

encode :: (Eq a) => [a] -> [(Int, a)]
encode list = [(length xs, head xs) | xs <- pack list]

In general, try to use existing higher-order functions where appropriate instead of doing your own recursion. It's both more readable and less prone to mistakes.

Answer 2

encode $ tail packed

We have

packed :: [[a]]
tail packed :: [[a]]

But we need to pass an [a] to encode.

(Think about it like this: list needs to go through pack. packed is the output from pack, but in the recursive call it will be passed to pack again.)

Answer 3

Your problem is that the function encode expects "unpacked" lists, but you pass a "packed" list.

Adding type signatures helps a lot here, I added a type signature for encode'

{-# LANGUAGE ScopedTypeVariables #-}

pack :: (Eq a) => [a] -> [[a]]
pack [] = []
pack (x:xs) = (x : takeWhile (== x) xs) : (pack $ dropWhile (== x) xs)

encode :: forall a. (Eq a) => [a] -> [(Int, a)]
encode [] = []
encode list = (encode' $ head packed) : (encode $ tail packed)
    where packed = pack list
          encode' :: [a] -> (Int, a)
          encode' l = (length l, head l)

and the compiler finds the error quickly:

[1 of 1] Compiling Main             ( test.hs, interpreted )

test.hs:9:42:
    Couldn't match type `a' with `[a]'
      `a' is a rigid type variable bound by
          the type signature for encode :: Eq a => [a] -> [(Int, a)]
          at test.hs:8:1
    Expected type: [(Int, a)]
      Actual type: [(Int, [a])]
    In the second argument of `(:)', namely `(encode $ tail packed)'
    In the expression: (encode' $ head packed) : (encode $ tail packed)
Failed, modules loaded: none.

Because that would only work if a was the same as [a] and therefore the same as [[a]] etc. That's an infinite type error. Or simply the difference between a "packed" list ([[a]]) and a "unpacked" list ([a]) in your sample.

(For better understanding: "packed" list is a list after applying the pack function ;-) )

edit: fixed ScopedTypeVariables vs. ExistentialQuantification error, thanks John L

Answer 4

You can do pattern matching on the result to pack, instead of using head and tail. Then it looks like this:

encode :: (Eq a) => [a] -> [(Int, a)]
encode [] = []
encode list = encode' x : encode xs
   where (x:xs)    = pack list
         encode' l = (length l, head l)

The type error comes from xs is of type [[a]] because pack returns [[a]], but encode expects an [a] argument.

Answer 5

I agree with @hammar that higher-order functions are a great way to handle this problem.
Here's a general explanation of what happened, though:

Every time I've had an infinite type error, it's had the following form:
I've had a function which called itself, but called itself with a "deeper"* type than it had been passed.

Let's make a simple infinite type error:

*Main> let f (_:xs) = f [xs]

<interactive>:1:19:
    Occurs check: cannot construct the infinite type: t0 = [t0]

And let's break down why: the type of f can't be determined: If f :: [a] -> [[a]], then the f [xs] :: [[a]] -> [[[a]]], which gets passed to the original f, which can't return [[[a]]].

---

*My definition of "deeper":
[[a]] is "deeper" than [a]
Constructor (Constructor a) is "deeper" than Constructor a