list - 制作一个列表列表来计算 Haskell 中的帕斯卡三角形

Question

我正在尝试创建一个函数，该函数接受一个整数 m 并返回 Pascal 三角形的行，直到该 m th 行。

我已经构建了一个 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 三角形中的一行。例如 pascal 3 应该返回 [[1],[1,1],[1,2,1],[1,3,3,1]] 。它目前正在返回 [1,1,1,1,2,1,1,3,3,1] 。

Answer 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 ，并且 [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 相比，您可以更有效地执行操作:您可以仅使用前一行和一些加法来计算 Pascal 三角形的下一行。这意味着我们可以构建一个包含帕斯卡三角形所有行的惰性(无限)列表。

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

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