How much does Haskell/GHC memoize?
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] 1, 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] :
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(n2) time. previousRow . This seems like it should be O(n3) (because it's Σi = 0 → n O(n2)). Which is the case, and how can I improve my implementation?
1 though advice here would be appreciated as well!
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
上一篇: 通过Core进行性能分析
下一篇: Haskell / GHC记忆多少？