title: Why does this Haskell code produce the "infinite type" error?
body: <p>I am new to Haskell and facing a "cannot construct infinite type" error that I cannot make sense of. </p>
  
  <p>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.</p>
  
  <p>Here's the code: </p>
  
  <pre><code>intersperse :: a -&gt; [[a]] -&gt; [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
  </code></pre>
  
  <p>And here's the error trying to load it into the interpreter: </p>
  
  <pre><code>Prelude&gt; :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.
  </code></pre>
  
  <p>Thanks.</p>
  
  <p>--</p>
  
  <p>Here is some corrected the code and a general guideline for dealing with the "infinite type" error in Haskell:</p>
  
  <p><strong>Corrected code</strong></p>
  
  <pre><code>intersperse _ [] = []
  intersperse _ [x] = x
  intersperse s (x:xs) =  x ++ s:intersperse s xs 
  </code></pre>
  
  <p><strong>What the problem was:</strong></p>
  
  <p>My type signature states that the second parameter to intersperse is a <em>list of lists</em>. Therefore, when I pattern matched against "s (x:y:xs)", x and y became <strong>lists</strong>. And yet I was treating x and y as elements, not lists. </p>
  
  <p><strong>Guideline for dealing with the "infinite type" error:</strong></p>
  
  <p><em>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.</em></p>