列出一个列表来计算Haskell中的Pascal三角形 [英] Making a list of lists to compute Pascal's triangle in Haskell

问题描述

我试着制作一个函数，它接受一个整数 m 并返回Pascal三角形的行直到那个 m th row。

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

到目前为止，我有

  pascal 0 = [1] 
 pascal m = [x | x<  -  pascal（m-1）] ++ [选择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] 。

解决方案

有解决方案，然后是解决方案。首先，我们先从解决方案开始，然后继续解决解决方案。 首先要注意的是，如果我们想要您声明的结果，我们必须改变类型，并做更多的包装：

   - 是pascal :: Integer  - > [Integer] 
 pascal :: Integer  - > [[整数]] 
 pascal 0 = [[1]] 
 pascal m = [x | x < -  pascal（m-1）] ++ [[选择m k | k < -  [0,1..m]]] 
  

现在，几个语法指针： [x |只要 foo ，并且 [0,1..m] c $ c>通常与 [0..m] 相同：

  pascal m = pascal（m-1）++ [[选择mk | k < -  [0..m]]] 
  

您会发现这是追加单身人士列出每个递归调用的另一个列表的末尾。这是低效率的;最好从前面建立列表。所以，我们将使用一个常见的重构：我们将创建一个带累加器的助手。

  pascal = go [] where 
 go 0 acc = [1]：acc 
 go m acc = go（m-1）（[选择mk | k < -  [0..m]]：acc）
  

接下来的观察是您可以比重新计算更有效率选择mk 每次都可以：只使用前一行和一些添加来计算Pascal三角形的下一行。这意味着我们可以建立一个所有Pascal三角形行的懒惰（无限）列表。

  nextRow vs = [1] + + zipWith（+）vs（tail vs）++ [1] 
 allPascals = iterate nextRow [1] 
  

最后，由于所有Pascal三角形的行在它们的中点都是对称的，因此您可以尝试构建每行的前半部分的无限列表。这将有利于消除剩余的追加到列表末尾操作。我将此作为练习。请记住，行在偶数和奇数个元素之间交替，这使得这部分有点棘手（和丑陋）。

I'm trying to make a function that takes in an integer m and returns the rows of Pascal's triangle up to that mth row.

I have already constructed a choose function, that takes in two integers n and k, and returns the value n choose k. For example, choose 3 2 returns 3.

So far, I have

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

This is returning one big list, but really, I want a list of lists, where each list corresponds to a row in Pascal's triangle. For example pascal 3 should return [[1],[1,1],[1,2,1],[1,3,3,1]]. It currently is returning [1,1,1,1,2,1,1,3,3,1].

解决方案

There are solutions, and then there are solutions. Let's start with solutions first, and work our way up to solutions.

The first thing to observe is that if we want the result you claimed, we have to change the type, and do a bit more wrapping:

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

Now then, a few syntactic pointers: [x | x <- foo] is better written just foo, and [0,1..m] is often the same as just [0..m]:

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

You'll observe that this is appending singleton lists to the end of another list on each recursive call. This is inefficient; it's better to build lists from the front. So, we'll use a common refactoring: we'll create a helper with an accumulator.

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

The next observation is that you can do things a bit more efficiently than recomputing choose m k every time: you can compute the next row of Pascal's triangle using only the previous row and some additions. This means we can build a lazy (infinite) list of all the rows of Pascal's triangle.

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

Finally, since all of the rows of Pascal's triangle are symmetric across their midpoint, you might try to build an infinite list of just the first halves of each row. This would have the benefit of eliminating the remaining "append to the end of a list" operation. I leave this as an exercise; keep in mind that rows alternate between an even and odd number of elements, which makes this part a bit trickier (and uglier).

这篇关于列出一个列表来计算Haskell中的Pascal三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！