在 Haskell 中创建一个列表来计算帕斯卡三角形

我正在尝试创建一个接受整数的函数m并返回帕斯卡三角形的行数mth row.

我已经构建了一个choose函数，它接受两个整数 n 和 k，并返回值 n 选择 k。例如，choose 3 2返回 3。

到目前为止，我已经

pascal 0 = [1]
pascal m = [x | x <- pascal (m-1)] ++ [choose m k | k <- [0,1..m]

这返回一个大列表，但实际上，我想要一个列表列表，其中每个列表对应于帕斯卡三角形中的一行。例如pascal 3应该返回[[1],[1,1],[1,2,1],[1,3,3,1]]。目前正在回归[1,1,1,1,2,1,1,3,3,1].

有解决方案，然后就有解决方案。让我们首先从解决方案开始，然后逐步解决解决方案.

首先要观察的是，如果我们想要您声明的结果，我们必须更改类型，并进行更多包装：

-- was pascal :: Integer -> [Integer]
pascal :: Integer -> [[Integer]]
pascal 0 = [[1]]
pascal m = [x | x <- pascal (m-1)] ++ [[choose m k | k <- [0,1..m]]]

现在，一些语法提示：[x | x <- foo]最好写成foo, and [0,1..m]通常与刚刚相同[0..m]:

pascal m = pascal (m-1) ++ [[choose m k | k <- [0..m]]]

您会发现，这是在每次递归调用时将单例列表附加到另一个列表的末尾。这是低效的；最好从前面建立列表。因此，我们将使用常见的重构：我们将创建一个带有累加器的助手。

pascal = go [] where
    go 0 acc = [1] : acc
    go m acc = go (m-1) ([choose m k | k <- [0..m]] : acc)

下一个观察结果是，你可以比重新计算更有效地做事choose m k每次：您可以仅使用前一行和一些加法来计算帕斯卡三角形的下一行。这意味着我们可以构建帕斯卡三角形所有行的惰性（无限）列表。

nextRow vs = [1] ++ zipWith (+) vs (tail vs) ++ [1]
allPascals = iterate nextRow [1]

最后，由于帕斯卡三角形的所有行都在中点对称，因此您可能会尝试构建一个仅包含每行前半部分的无限列表。这将有利于消除剩余的“附加到列表末尾”操作。我把这个作为练习；请记住，行在偶数和奇数元素之间交替，这使得这部分有点棘手（也更丑陋）。