为什么这个 memoized 的 Pascal 三角递归没有预期的那么快？

Question

参考上的这篇文章，我认为这种方法使用了记忆，应该很快。但是，这里好像不是这样：

pascal :: Int -> Int -> Integer
pascal a = (map ((map pascal' [0..]) !! a) [0..] !!)
  where pascal' a b | a == 1 && b == 1  = 1
                    | a <= 0 || b <= 0  = 0 
                    | otherwise         = pascal (a-1) (b-1) + pascal (a-1) b

Haskell如何解释这个？如何让这个功能更快？

Answer 1

您需要将（完整的）数据结构的构建与数据结构中正确元素的选择分开。

即需要定义整个帕斯卡三角形：

triangle :: [[Integer]]
triangle = [[pascal' a b | b <- [0..]] | a <- [0..]]
  where pascal' a b | a == 1 && b == 1  = 1
                    | a <= 0 || b <= 0  = 0
                    | otherwise         = triangle !! (a-1) !! (b-1) 
                                          + triangle !! (a-1) !! b

然后从三角形中选择的内容将被记忆：

> triangle !! 100 !! 50
50445672272782096667406248628
>

定义好数据结构并命名后，就可以定义访问元素的函数了：

pascal :: Int -> Int -> Integer
pascal a b = triangle !! a !! b

拨打电话：

> pascal 100 50
50445672272782096667406248628

可以将triangle移到where子句中，给出完整代码：

pascal :: Int -> Int -> Integer
pascal a b = triangle !! a !! b
  where
    triangle = [[pascal' a b | b <- [0..]] | a <- [0..]]
    pascal' a b | a == 1 && b == 1  = 1
                | a <= 0 || b <= 0  = 0
                | otherwise         = triangle !! (a-1) !! (b-1)
                                      + triangle !! (a-1) !! b

即使在未优化编译或加载到 GHCi 中时也应该可以正常工作。

为什么这个 memoized 的 Pascal 三角递归没有预期的那么快？

Why is this memoized Pascal's Triangle recursion not as fast as expected?

haskell

memoization

pascals-triangle