哈斯克尔的Pascal Triangle

Question

我是Haskell的新手,我真的需要一些帮助!

我必须编写一个包含递归函数的程序,使用Pascal三角形技术生成n = 12次幂的二项式系数列表.

我脑子里有一些想法,但因为我刚刚开始,我不知道如何将其实现到haskell？!

有人可以帮帮我吗？

first row: (a+b)^0 = 1
second row: (a+b)^1 = 1a+1b
third row: (a+b)^2 = 1a^2+2ab+1b^2

等等......这是我的主要想法.但我甚至无法尝试这一点,因为我不知道我是如何把它放在Haskell中的......一直都在考虑错误

Answer 1

首先为三角形中的每个元素分配一个索引:

  | 0   1   2   3   4   5   6
--+--------------------------
0 | 1
1 | 1   1
2 | 1   2   1
3 | 1   3   3   1
4 | 1   4   6   4   1
5 | 1   5  10  10   5   1
6 | 1   6  15  20  15   6   1

在这里,我只是将三角形放在一边,以便我们可以对它们进行编号.所以在这里我想说的是,元件的(6, 4)IS 15,而(4, 6)并不存在.现在专注于编写一个函数

pascal :: Integer -> Integer -> Integer
pascal x y = ???

这样就可以生成这个版本的三角形.你可以从写作开始

pascal x y
    | x == 0 = 1
    | x == y = 1
    | x <  y = error "Not a valid coordinate for Pascal's triangle."
    | otherwise = pascal ? ? + pascal ? ?

请注意,这里不是通过对角线确定哪些元素应该加在一起,而是通过直角坐标来实现.在这里,您将注意到,您y所在的三角形中的哪一行是该行中x元素的位置.你需要做的就是找出代替?s的东西.

一旦你开始工作,我就会为这个三角形提供一个单线程,它更高效,并且可以同时生成整个三角形,同时仍然使用递归:

import Data.List (scanl1)

pascals :: [[Integer]]
pascals = repeat 1 : map (scanl1 (+)) pascals

不要试图将这个解决方案转交给你的教授,这不是他们正在寻找的东西,如果你只做Haskell一个星期,那么很明显会有人给你这个解决方案.但是,它确实显示了Haskell对于这类问题的强大功能.我将展示如何索引pascals以获得给定(n, k)值,但这样做也会给你太多提示来解决天真的递归.

由于存在一些混淆,我给出这个解决方案的原因是在它与Fibonacci序列经常显示的惰性实现之间绘制一个并行:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

相比

fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

这个定义生成了所有Fibonacci数的无限列表,并且非常有效(从CPU的角度来看,RAM是一个不同的故事).它在前两个元素中编码基本情况,然后是一个可以计算其余部分的递归表达式.对于Fibonaccis,您需要2个值才能启动,但对于Pascal的三角形,您只需要一个值,该值恰好是无限列表.我在上面发布的网格中有一个易于查看的图案,该scanl1 (+)函数只是利用了这种模式,并且允许我们非常容易地生成它,但这会生成三角形的对角线而不是行.为了让行,你可以索引此列表,或者你可以做一些花哨的技巧take,drop以及其他这样的功能,但是这是另一天的演习.

Answer 2

从三角形本身开始：

     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1
    ...

您应该注意到，要记下下一行，您必须应用此规则：对前一行的相邻元素求和0，对孤立的边缘元素使用 a 。视觉上：

    0   1   0
     \+/ \+/
  0   1   1   0
   \+/ \+/ \+/
0   1   2   1   0
 \+/ \+/ \+/ \+/
  1   3   3   1
       ...

在操作上，这看起来像这样：

For row 0:
[1]  (it's a given; i.e. base case)

For row 1:
[0, 1]   <- row 0 with a zero prepended ([0] ++ row 0)
 +  +
[1, 0]   <- row 0 with a zero appended  (row 0 ++ [0])
 =  =
[1, 1]   <- element-wise addition

For row 2:
[0, 1, 1]
 +  +  +
[1, 1, 0]
 =  =  =
[1, 2, 1]

Generally, for row N:

element-wise addition of:
  [0] ++ row(N-1)
  row(N-1) ++ [0]

请记住，在 Haskell 中按元素添加列表是zipWith (+).

因此，我们得出以下 Haskell 定义：

pascal 0 = [1]
pascal n = zipWith (+) ([0] ++ pascal (n-1)) (pascal (n-1) ++ [0])

或者以类似于著名的“lazy fibs”的方式：

pascals = [1] : map (\xs -> zipWith (+) ([0] ++ xs) (xs ++ [0])) pascals

Answer 3

从基本案例开始。

pascal 0 0 = 1

然后处理边缘情况

pascal n 0 = 1
pascal n r | n == r = 1

现在用递归步骤进行扩展

pascal n r = pascal (n - 1) (r - 1) + pascal (n - 1) r

如果您想要特定行的列表，请编写一个包装器

binom n = map (pascal n) [0..n]

弄清楚类型应该不难

pascal :: Integral a => a -> a -> a
binom :: Integral a => a -> [a]