haskell - 如何在 Haskell 中递归定义一个无限的 2D 数组？

Question

我是 Haskell 的新手，我喜欢它优美的语法。但我还没有找到定义无限二维数组的合适方法——例如，帕斯卡三角形:

1  1  1  1  1  ...
1  2  3  4  5  ...
1  3  6 10 15  ...
1  4 10 20 35  ...
1  5 15 35 70  ...
...

我知道如何定义一个简单的函数:

pascal :: Int -> Int -> Int
pascal 1 _ = 1
pascal _ 1 = 1
pascal x y = (pascal (x - 1) y) + (pascal x (y - 1))

由于 Haskell 不内存函数值，因此调用 pascal 20 20 需要很长时间。我怎么能定义一个快速版本(比如一个无限的二维数组)？

Answer 1

您可以将帕斯卡三角形创建为一个无限的、惰性的、嵌套的列表

pascal :: [[Integer]]
pascal = repeat 1 : map (scanl1 (+)) pascal

上面的定义有点简洁，但它本质上的意思只是每一行都是前一行的累加和，从 repeat 1 开始，即一个无限的列表。这样做的好处是我们可以直接计算三角形中的每个值，而无需进行任何 O(n) 索引。

现在您可以索引列表以找到您需要的值，例如

> pascal !! 19 !! 19
35345263800

该列表将仅针对您需要的值进行部分评估。

您还可以轻松输出一系列值:

> putStrLn $ unlines $ take 5 $ map (unwords . map show . take 5) $ pascal
1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
1 4 10 20 35
1 5 15 35 70

另一种选择是使用您的原始函数，但使用可用的各种内存库之一来内存它。例如，使用 data-memocombinators :

import Data.MemoCombinators

pascal :: Integer -> Integer -> Integer
pascal = memo2 integral integral pascal'

pascal' :: Integer -> Integer -> Integer
pascal' 1 _ = 1
pascal' _ 1 = 1
pascal' x y = (pascal (x - 1) y) + (pascal x (y - 1))