Idris `foldl` 默认实现

Question

interface Foldable t where
  foldr : (func : elem -> acc -> acc) -> (init : acc) -> (input : t elem) -> acc
  foldl : (func : acc -> elem -> acc) -> (init : acc) -> (input : t elem) -> acc
  foldl f z t = foldr (flip (.) . flip f) id t z

这里的foldr (flip (.) . flip f) id t z是什么意思？
还有另一种使用 foldr 来实现 foldl 的方法吗？
感谢您的回答。

Answer 1

上面定义的 foldl 中的第一个参数可以变成这样的 lambda：

\element -> (. (flip f element))
-- or
\element prevFun -> prevFun . flip f element
-- or
\element prevFun next -> prevFun $ f next element

让我们举一个例子，你想在列表中向左折叠[a, b, c]。您希望最终结果为 f (f (f z a) b) c)，其中 z 是累加器。

在第一次迭代中，第一个参数为 c，第二个参数为 id。因此，结果将是 id . flip f c，或者只是 flip f c（因为 id . f 只是 f，正如@chepner 指出的那样）。

第二次迭代会得到 flip f c . flip f b，之后你会得到 flip f c . flip f b . flip f a（基本上，为每个下一个元素 x 添加一个 . flip f x。

扩展为：

acc -> flip f c (flip f b (flip f a acc))
-- or
acc -> flip f c (flip f b (f acc a))
-- or
acc -> f (f (f acc a) b) c)

瞧瞧！我们有一个接受累加器 acc 和 returns foldl f acc t 结果的函数，因此我们只需将其应用于实际累加器 z。

Idris `foldl` 默认实现

Idris `foldl` default implementation

haskell

functional-programming

fold

idris

dependent-type