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

Question

在 Memoization 上引用这篇文章，我相信这种方法使用内存，应该很快。然而，这里似乎并非如此:

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 中，它也应该可以正常工作。