How much does Haskell/GHC memoize?

Question

I wrote the following code to display Pascal's triangle:

import Control.Monad
import Data.List

pascalRow :: Integer -> [Integer]
pascalRow 0 = [1]
pascalRow n = map sumParents pairs
  where previousRow = 0:(pascalRow $ n - 1)++[0]
        pairs = zip previousRow (tail previousRow)
        sumParents (a, b) = a + b

-- Read an integer from stdin, and print the Pascal triangle of that height.
main = do
  n <- readLn
  forM_ [0..n-1] printRow
    where printRow k = putStrLn $ intercalate " " $ map show $ pascalRow k

Ignoring the ugliness of ++ [0]¹, I'm wondering how efficient this code is. It seems to me that there are two possibilities.

In computing pascalRow n after computing all of map pascalRow [1..n-1]:

• GHC memoizes the previous values, so previousRow is computed in constant time. (Or maybe O(n) for the append operation.) Therefore, the calculation of pascalRow n takes only O(n) time, and constructing all rows up to n (that is, map pascalRow [1..n]) should take O(n²) time.
• GHC forgets the previous values, and so has to recurse all the way down to compute previousRow. This seems like it should be O(n³) (because it's Σ_{i = 0 → n} O(n²)).

Which is the case, and how can I improve my implementation?

---

¹ though advice here would be appreciated as well!

Answer 1

You memoize a function by associating it with a data structure that 'remembers' past applications. Ghc won't remember arbitrary past function applications, but it does remember as much as it has worked out of structure that it is still working on. In this case, the function pascalRow is not really necessary anyway: we just describe the infinite pascal triangle and print as much of it as is needed.

import Control.Monad
import Data.List

pstep :: [Integer] -> [Integer]
pstep xs = zipWith (+) (0:xs) (xs ++ [0])

-- the infinite pascal triangle
pascal = iterate pstep [1] 
pascalRow n = pascal !! n  -- not needed, but fine

-- Read an integer from stdin, 
-- and print that much of the infinite Pascal triangle.
main = do
      n <- readLn
      mapM_ printRow (take n pascal)
  where printRow xs = putStrLn $ intercalate " " $ map show xs