Haskell中列表的递归

Question

例如,我有一个像['a','b','c','d','e']这样的列表.
我想做这样的事情:
首先用前两个元素做一些事情,f'a''b'
然后用f的返回值和列表中的下一个元素做同样的事情,结果= f'a''b ',让我们说像结果'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'和朋友.