Why does this Haskell code produce the "infinite type" error?
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
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.
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.
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.