title: Generating finite lists of primes in Haskell
body: <p>There are a lot topics on generating prime numbers in Haskell, but in my opinion, they all rely on '<code>isPrime</code>' function, which, if we don't know the primes sequence yet, should look like:</p>
  <pre><code>isPrime k = if k &gt; 1 then null [ x | x &lt;- [2,3..(div k 2) + 1], k `mod` x == 0]
                       else False
  </code></pre>
  <p>(<code>div</code> might be replaced with <code>sqrt</code>, but still...)</p>
  <p>I've tried to construct prime numbers based on 'inductive definition' (assume we have a set of first <em>n</em> primes, then <em>(n+1)th</em> prime is the least integer such that none of the first <em>n</em> primes is a divisor of it). I've tried to do it in the Fibonacci sequence way, which is:</p>
  <pre><code>fib :: Int -&gt; Int
  fib 0 = 0
  fib 1 = 1
  fib n = fibs !! n
      where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
  </code></pre>
  <p>And I ended up with this:</p>
  <pre><code>-- checking if second number is a divisor of first one
  ifDoesn'tDivide :: Int -&gt; Int -&gt; Bool
  ifDoesn'tDivide n k 
      | mod n k == 0 = False
      | otherwise    = True
  
  -- generating list which consists of first n prime numbers
  firstPrimes :: Int -&gt; [Int]
  -- firstPrimes 1  = [2]
  firstPrimes n     = take n primes 
      where primes = 2:(tail primes) ++ 
           [head [x | x &lt;- [3,4..], k &lt;- primes, ifDoesn'tDivide x k == True]]
  </code></pre>
  <p>But it doesn't work, <em>stack overflow</em> when <code>n &gt;= 2</code>. Any advice on how to fix it?</p>
  <p><em>&quot;Haskell can define data structures in terms of themselves in effect creating infinite data structures&quot;</em>. Those prime numbers and Fibonacci sequences mentioned earlier are specific cases of defining data structures in terms of themselves, and Fibonacci sequence works just fine, but these <code>primes</code> doesn't.</p>
  <p>Am I missing something, are those two algorithms different in a substantive way?</p>
  <p>P.S. So, I think, I'm just looking for most 'Haskellish' way to do that.</p>