Haskell / GHC记忆多少？

我写了下面的代码来显示Pascal的三角形：

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

忽略++ [0] 1的丑陋，我想知道这个代码有多高效。 在我看来，有两种可能性。

在计算所有map pascalRow [1..n-1]后计算pascalRow n ：

GHC 记忆先前的值，因此previousRow是在一段时间内计算的。 （或者对于追加操作，也许是O（n））。因此， pascalRow n的计算仅需要O（n）时间，并且构造所有直到n的行（即map pascalRow [1..n] ）应该O（n2）时间。

GHC 忘记了以前的值，因此必须一直递减以计算previousRow 。 这看起来应该是O（n3）（因为它是Σi= 0→n O（n2））。

哪种情况，我如何改进我的实施？

---

1虽然建议在这里也将不胜感激！

---

通过将函数与“记住”过去的应用程序的数据结构相关联来记忆函数。 Ghc不会记得任意过去的函数应用程序，但它确实记得它已经在结构上工作，它仍然在工作。 在这种情况下，函数pascalRow并非真的必要：我们只是描述了无限的pascal三角形并根据需要打印了它。

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

链接地址: http://www.djcxy.com/p/43175.html

上一篇: How much does Haskell/GHC memoize?

下一篇: Haskell Thrift library 300x slower than C++ in performance test