制作列表以在Haskell中计算Pascal的三角形

Question

我正在尝试创建一个接受整数的函数,并将mPascal三角形的行返回到该m行.

我已经构造了一个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三角形.这意味着我们可以构建一个Pascal三角形的所有行的惰性(无限)列表.

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

最后,由于Pascal三角形的所有行都在其中点对称,因此您可能会尝试构建每行的前半部分的无限列表.这将有利于消除剩余的"附加到列表末尾"操作.我将此作为练习; 请记住,行在偶数和奇数个元素之间交替,这使得这部分有点棘手(而且更加丑陋).