4

我正在尝试制作一个函数，该函数接受一个整数m并将帕斯卡三角形的行返回到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 3应该返回[[1],[1,1],[1,2,1],[1,3,3,1]]。它目前正在返回[1,1,1,1,2,1,1,3,3,1]。

4

1 回答 1

12

有解决方案，然后有解决方案。让我们先从解决方案开始，然后逐步找到解决方案。

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

-- 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]最好写成 just foo，并且[0,1..m]通常与 just 相同[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]

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

于 2012-09-13T23:41:35.750 回答