Why does this Haskell code produce the "infinite type" error?

Question

I am new to Haskell and facing a "cannot construct infinite type" error that I cannot make sense of.

In fact, beyond that, I have not been able to find a good explanation of what this error even means, so if you could go beyond my basic question and explain the "infinite type" error, I'd really appreciate it.

Here's the code:

intersperse :: a -> [[a]] -> [a]

-- intersperse '*' ["foo","bar","baz","quux"] 
--  should produce the following:
--  "foo*bar*baz*quux"

-- intersperse -99 [ [1,2,3],[4,5,6],[7,8,9]]
--  should produce the following:
--  [1,2,3,-99,4,5,6,-99,7,8,9]

intersperse _ [] = []
intersperse _ [x] = x
intersperse s (x:y:xs) = x:s:y:intersperse s xs

And here's the error trying to load it into the interpreter:

Prelude> :load ./chapter.3.ending.real.world.haskell.exercises.hs
[1 of 1] Compiling Main (chapter.3.ending.real.world.haskell.exercises.hs, interpreted )

chapter.3.ending.real.world.haskell.exercises.hs:147:0:
Occurs check: cannot construct the infinite type: a = [a]
When generalising the type(s) for `intersperse'
Failed, modules loaded: none.

Thanks.

--

Here is some corrected the code and a general guideline for dealing with the "infinite type" error in Haskell:

Corrected code

intersperse _ [] = []
intersperse _ [x] = x
intersperse s (x:xs) =  x ++ s:intersperse s xs 

What the problem was:

My type signature states that the second parameter to intersperse is a list of lists. Therefore, when I pattern matched against "s (x:y:xs)", x and y became lists. And yet I was treating x and y as elements, not lists.

Guideline for dealing with the "infinite type" error:

Most of the time, when you get this error, you have forgotten the types of the various variables you're dealing with, and you have attempted to use a variable as if it were some other type than what it is. Look carefully at what type everything is versus how you're using it, and this will usually uncover the problem.

Solution 1

The problem is in the last clause, where you treat x and y as elements, while they are lists. This will work:

intersperse _ [] = []
intersperse _ [x] = x 
intersperse s (x:y:xs) = x ++ [s] ++ y ++ intersperse s xs

The infinite type error occurs because the : operator has type a -> [a] -> [a], while you treat it as [a] -> a -> [a], which means that [a] must be identified with a, which would mean that a is an infinitely nested list. That is not allowed (and not what you mean, anyway).

Edit: there is also another bug in the above code. It should be:

intersperse _ [] = []
intersperse _ [x] = x
intersperse s (x:xs) = x ++ [s] ++ intersperse s xs

Solution 2

Often adding an explicit type definition can make the compiler's type error message make more sense. But in this case, the explicit typing makes the compiler's error message worse.

Look what happens when I let ghc guess the type of intersperse:

Occurs check: cannot construct the infinite type: a = [a]
  Expected type: [a] -> [[a]] -> [[a]]
  Inferred type: [a] -> [[a]] -> [a]
In the second argument of `(:)', namely `intersperse s xs'
In the second argument of `(:)', namely `y : intersperse s xs'

That clearly points toward the bug in the code. Using this technique you don't have to stare at everything and think hard about the types, as others have suggested doing.

Solution 3

I may be wrong, but it seems you're trying to solve a more difficult problem. Your version of intersperse doesn't just intersperse the value with the array, but also flattens it one level.

The List module in Haskell actually provides an intersperse function. It puts in the value given between every element in the list. For example:

intersperse 11 [1, 3, 5, 7, 9] = [1, 11, 3, 11, 5, 11, 7, 11, 9]
intersperse "*" ["foo","bar","baz","quux"] = ["foo", "*", "bar", "*", "baz", "*", "quux"]

I'm assuming this is what you want to do because it's what my professor wanted us to do when I was learning Haskell. I could, of course, be totally out.

Solution 4

Also I found this which explains the meaning of the error.

Every time the interpreter/compiler gives me this error it's because I'm using some type-parametrized tuple as formal parameter. Everything works correctly by removing the type definition of the function, which was containing type variables.

I still cannot figure out how to both fix it and keep the function type definition.

View more solutions

Comments

[Charlie Flowers]

Thanks. I figured both of those out and then came back here and saw your response, which was excellent verification for me. You also fixed my bug better than i did. My bug was that it was skipping a separator between y and xs. To fix it, I introduced yet another level of pattern matching, like this: intersperse s (x:y:[]) = x ++ s:y intersperse s (x:y:xs) = intersperse s [x,y] ++ s:intersperse s xs But it looks like you fixed my bug without the need for that extra level.

[Charlie Flowers]

Thanks for the comment. In this case, though, I do want to flatten it one level, because I'm doing exercise 7 from the end of Chapter 3 of "Real World Haskell".

[Charlie Flowers]

Here's the lesson I learn: "When facing an 'infinite type' error, you're probably forgetting what types you're dealing with and therefore doing something you didn't mean to do. Carefully look at what type every one of your variables is, and that will usually uncover the problem." Is there anything you would add or change in that?

[Stephan202]

That's certainly correct, and I would change nothing in that. Infinite types are not allowed, and hence an infinite type error means that somewhere a functions receives an argument with an incorrect type. Good luck with RWH :)

[Ryan Maddox]

Gotcha. If I had the book, I would have checked before I wrote. Alas, all I could do was guess. Glad you got it sorted anyway. :-)

[Stephan202]

The book's content is made freely available online: book.realworldhaskell.org

[Ryan Maddox]

Excellent. Bookmarked. Thanks for the link - I'll be helping in the Haskell labs come next year, and this will no doubt come in handy when brushing up.

[Nawaz]

where you treat x and y as elements, while they are lists. Why are they lists though, you didn't explain that? In x:xs , x is an element, right? I was hoping it'll be same in x:y:xs as well. Also, if they're lists, how they get splitted, containing how many elements? I guess one?

[Chris Stryczynski]

What does "which means that [a] must be identified with a" mean? What does identify mean here?

[Stephan202]

@ChrisStryczynski it means "to be the same as" / "to be considered equal to". Hope that helps :)