title: Speed up calculation of partitions in Haskell
body: <p>I'm trying to solve Euler problem 78, which basically asks for the first number where the <a href="http://en.wikipedia.org/wiki/Partition_%28number_theory%29" rel="nofollow">partition function</a> p(n) is divisible by 1000000. </p>
  
  <p>I use Euler's recursive fomula based on pentagonal numbers (calculated here in <code>pents</code> together with the proper sign). Here is my code:</p>
  
  <pre><code>ps = 1 : map p [1..] where
    p n = sum $ map getP $ takeWhile ((&lt;= n).fst) pents where
      getP (pent,sign) = sign * (ps !! (n-pent)) 
  
  pents = zip (map (\n -&gt; (3*n-1)*n `div` 2) $ [1..] &gt;&gt;= (\x -&gt; [x,-x]))
              (cycle [1,1,-1,-1])
  </code></pre>
  
  <p>While <code>ps</code> seems to produce the correct results, it is too slow. Is there a way to speed the calculation up, or do I need a completely different approach?</p>