haskell 嵌套列表中的帕斯卡三角形

Question

我正在尝试获取 pascal 列表中每个列表的第 k 行。例如，pascal 4 将获得每一行中的第 4 个元素。所以它将 return 1,4,10,20... 等。我了解如何构建一个无限的 pascal 列表，这是下面的输出，但我不确定如何在每个嵌套列表中获取第 n 个元素。有什么建议么？我正在考虑使用地图，但我不一定要在这里映射一个函数，这让我有点失望。谢谢你。

// im trying to get pascal k to return the nth element of every row in the triangle
pascal n = map(\n -> ??) take n pascal 
pascal_infite = [1] : map (\l -> zipWith (+) (l ++ [0]) (0:l)) pascal_infinite

Answer 1

获取第k行：

>>> pascal_infinite !! 4
[1,4,6,4,1]

从 [0..k] 获取所有行：

>>> map (pascal_infinite !!) [0..4]
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

从 [0..k] fast 获取所有行：

>>> take (4+1) pascal_infinite
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

哎呀，有点看错题了。为了得到你想要的东西，如果你关心速度，你应该只使用好的旧 n choose k 公式或类似的东西来构建。

如果这只是一个练习，忽略速度，这里有一个方法：

pascal n = map (!! n) $ drop n pascal_infinite

然后简单地采样几个第 4 个元素：

>>> take 8 $ pascal (4-1)
[1,4,10,20,35,56,84,120]

Answer 2

这基本上是一个 iterate :: (a -> a) -> a -> [a] 函数，其中有一个状态，每次更新状态时都会生成一个元素列表。

作为迭代函数，我们基本上想对前面的列表 xs 和 (0:xs) 执行 zipWith (+)，但我们会不断迭代，直到两个列表都用完。我们可以为此实现一个zipWithLongest：

zipWithLongest :: a -> b -> (a -> b -> c) -> [a] -> [b] -> [c]
zipWithLongest x0 y0 f = go
    where go (x:xs) (y:ys) = f x y : go xs ys
          go [] t = map (f x0) t
          go t [] = map (flip f y0) t

现在我们可以使用以下方法生成列表：

import Control.Monad(ap)

pascalTriangle :: Num n => [[n]]
pascalTriangle = iterate (ap (zipWithLongest 0 0 (+)) (0:)) [1]

我们可以使用 (!!) :: [a] -> Int -> a 索引列表。但是请注意，由于两个原因，这通常有点反模式：

一次查找需要 O(k) 时间，其中 k 我们要获取的索引值；和
它是一个部分函数，因为索引可以超出范围（这里是负索引，对于有限列表，索引太大）。

我们知道帕斯卡三角形的每一行都比上一行多一个元素。所以第 k 行包含 k 个元素。如果我们想获得每个子列表的第k个元素，那么我们应该首先忽略所有没有第k个元素的列表.所以我们使用 drop k 删除列表的第一个 k 元素，然后使用 map (!! k) 获取我们不过滤的每个子列表的第 k 个元素.

所以我们可以写一个函数：

kThPascalTriangle :: Num n => Int -> [n]
kThPascalTriangle k = map (!! k) (drop k pascalTriangle)

haskell 嵌套列表中的帕斯卡三角形

pascal triangle in haskell nested lists

haskell

pascals-triangle