haskell - Haskell 中的帕斯卡三角形

Question

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

我必须编写一个包含递归函数的程序，以使用帕斯卡三角技术生成 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

Here I've simply put the triangle on its side so that we can number them. So here I'd say that the element at (6, 4) is 15, whereas (4, 6) doesn't exist. Now focus on writing a function

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)值(value)，但这样做也会给你太多解决朴素递归的提示。

由于存在一些混淆，我给出这个解决方案的原因是在它与经常显示的斐波那契数列的惰性实现之间绘制一个平行线:

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

相比

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

这个定义生成了一个所有斐波那契数列的无限列表，并且非常有效(从 CPU 的角度来看，RAM 是另一回事)。它在它的前 2 个元素中编码基本情况，然后是一个可以计算其余部分的递归表达式。对于斐波那契，您需要 2 个值才能开始，但对于帕斯卡三角形，您只需要一个值，该值恰好是一个无限列表。我在上面发布的网格中的列中有一个很容易看到的模式，scanl1 (+)函数只是利用了这种模式并允许我们很容易地生成它，但这是生成三角形的对角线而不是行。要获取行，你可以索引这个列表，或者你可以用 take 做一些花哨的技巧。 , drop ，以及其他此类功能，但这是另一天的练习。