哈斯克尔列表的递归

Question

例如，我有一个列表，例如['a'，'b'，'c'，'d'，'e']。
我想做这样的事情：
首先使用前两个元素（f'a''b'做点事
然后，使用f的返回值和列表中的下一个元素，结果= f'a''b'，让我们说f结果'c'。然后f结果（结果'c'）'d'等等。
我该怎么做？

Answer 1

首先让我们考虑一下该功能 f 你有。它需要某种累积的价值，一个简单的价值，并将它们结合到结果中。因此，在类型的签名中，我们会说 a 对于累积值的类型， v 对于值的类型， r 对于结果的类型。

f :: a -> v -> r

现在我们要创建一个使用的折叠功能 f 和值列表。

someFold :: (a -> v -> r) -> [v] -> ?

它应该返回什么？它应该产生结果类型 r, ， 正确的？现在注意 a 和 r 实际上应该是相同的类型，因为我们继续喂养 f 再次进入第一个论点。

someFold :: (a -> v -> a) -> [v] -> a

现在缺少一件事。你怎么得到第一 a？有两种方法可以看一下。您要么选择第一个值，在这种情况下 a 与 v, ，或者您指定基本价值，因此 a 实际上可能与 v. 。让我们继续前进，因为这更有趣。我们还决定在此列表中向左向右移动。 （那是您需要的，对吗？）

someFold :: (a -> v -> a) -> a -> [v] -> a

那么...我们如何实施它？它将是递归的，所以让我们从基本案例开始。

someFold f acc [] = acc

如果我们达到了列表的结尾，那么我们已经积累了足够的吧？那很简单。那么递归情况呢？从您说的话，在每个步骤中，我们都应该申请 f 将“到目前为止的累积值”作为第一个参数，而“列表的第一个值”作为第二个参数。 f acc x. 。然后我们继续折叠，使用 那 作为我们的新“积累”价值。

someFold f acc (x:xs) = someFold f (f acc x) xs

容易，对吧？但是...如果我们想像您说的那样做并通过获取列表的前两个值来启动功能怎么办？也很容易。只需采用第一个元素，然后称其为原始的“基础”累加器！

someFold1 :: (v -> v -> v) -> [v] -> v
someFold1 f (x:xs) = someFold f x xs

请注意 a 与 v 对于此特殊情况，功能 someFold1 具有非常有趣的类型签名。如果您理解了这种解释，那就恭喜。我们刚刚实施 foldl 和 foldl1.

Prelude> foldl1 min "abcde" -- "abcde" is sugar for ['a','b','c','d','e']
'a'

在实际代码中，您实际上应该使用 foldl' 和朋友。

Answer 2

听起来像是作业。看看褶皱。

Answer 3

在这种情况下，折叠的问题通常是一次在元素上处理。您可以尝试手动滚动。

假设，您有您的功能 f, ，一次有两个要素 累加器 （最后一次迭代的结果）喂养。然后，您的功能看起来像这样：

fold2 :: (a -> a -> b -> b) -> [a] -> b -> b
fold2 f accum (x:y:zs) = fold2 f (f x y) zs
fold2 _ accum []       = accum
fold2 _ _     _        = error "odd number of elements"

尝试理解这一点。 fold2 剃光列表的前两个元素，并将其馈入 f. 。结果然后将其作为新的蓄能器传递给递归调用。这是完成列表为空之前完成的。