performance - 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的丑陋性，我想知道这段代码的效率如何。在我看来，有两种可能性。

在计算所有pascalRow n之后计算map pascalRow [1..n-1]时:

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

关于performance - Haskell/GHC可以内存多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27570371/