Project Euler 78

78.hs

import Data.Array (Array, array, (!), assocs)
import Data.List (transpose, foldl')

interleave :: [a] -> [a] -> [a]
interleave xs ys = concat . transpose $ [xs, ys]

pent :: [Int] -> [Int]
pent = map (\x ->  div (3*x^2 - x) 2) 

pentagonals :: [Int]
pentagonals = interleave (pent [1..195]) (pent [-1,-2.. (-195)])

cache :: Array Int Int
cache = array (0, 57000) [(x, partition x `mod` 1000000) | x <- [0..57000]]

partition :: Int -> Int
partition n 
  | n <= 1 = 1
  | otherwise = foldl' (+) 0 [s * cache ! (n - p) | (s, p) <- zip (cycle [1, 1, -1, -1]) $ takeWhile (<= n) pentagonals]

main :: IO ()
main = print $ head [i | (i, p) <- assocs cache, p == 0]