文件夹和文件夹可以相互定义吗？

Question

可以foldr和foldl 彼此定义吗？

赫顿在Haskell编程说

我们需要手动定义什么？Foldable 该类实例的最小完整定义 是定义 foldMap或 foldr，因为可以使用默认定义和列表实例从这两个函数之一派生该类中的所有其他函数。

那么如何foldl 定义foldr呢？

可以foldr根据进行定义foldl，以便我们可以Foldable通过定义类型来定义类型foldl？

为什么在Foldable，fold在来定义foldMap这方面的定义foldr，而在列表可折叠，一些专业化fold来讲被定义foldl为：

maximum :: Ord a => [a] -> a
maximum = foldl max

minimum :: Ord a => [a] -> a
minimum = foldl min

sum :: Num a => [a] -> a
sum = foldl (+) 0

product :: Num a => [a] -> a
product = foldl (*) 1

？他们可以改写为

maximum :: Ord a => [a] -> a
maximum = foldr max

minimum :: Ord a => [a] -> a
minimum = foldr min

sum :: Num a => [a] -> a
sum = foldr (+) 0

product :: Num a => [a] -> a
product = foldr (*) 1

谢谢。

Answer 1

通常，两者 foldr都不foldl可以彼此实现。的核心运算Foldable是foldMap，从中可以得出所有其他运算。无论是foldr也不foldl是足够的。但是，这种差异仅在无限或（部分）不确定的结构的情况下才会显现出来，因此有一种掩盖这一事实的趋势。

@DamianLattenero已经显示出的“实施方式” foldl和foldr在彼此的术语：

foldl' c = foldr (flip c)
foldr' c = foldl (flip c)

但是它们并不总是具有正确的行为。考虑清单。然后，foldr (:) [] xs = xs为所有人xs :: [a]。但是，foldr' (:) [] /= xs对所有而言xs，因为foldr' (:) [] xs = foldl (flip (:)) n xs和和foldl（对于列表而言）必须先遍历列表的整个书脊，然后才能产生输出。但是，如果xs是无限的，foldl 则不能遍历整个无限列表，因此会foldr' (:) [] xs无限循环无限循环xs，而foldr (:) [] xs仅产生xs。foldl' = foldl但是，根据需要。本质上，for []，foldr是“自然的”并且foldl是“非自然的”。实现foldl与foldr作品，因为你只是失去“自然”，但实施foldr中的术语foldl是不行的，因为你无法恢复“

另一方面，考虑

data Tsil a = Lin | Snoc (Tsil a) a
-- backwards version of data [a] = [] | (:) a [a]

在这种情况下，foldl很自然：

foldl c n Lin = n
foldl c n (Snoc xs x) = c (foldl c n xs) x

并且foldr是不自然的：

foldr c = foldl (flip c)

现在，foldl在无限/部分未定义Tsils 上具有良好的“生产性”行为，而foldr没有。foldr以foldl工作的方式实现（就像我上面所做的一样），但是您不能foldl以的方式实现foldr，因为您无法恢复这种生产力。

foldMap避免了这个问题。对于[]：

foldMap f [] = mempty
foldMap f (x : xs) = f x <> foldMap f xs
-- foldMap f = foldr (\x r -> f x <> r) mempty

对于Tsil：

foldMap f Lin = mempty
foldMap f (Snoc xs x) = foldMap f xs <> f x
-- foldMap f = foldl (\r x -> r <> f x) mempty

现在，

instance Semigroup [a] where
  [] <> ys = ys
  (x : xs) <> ys = x : (xs <> ys)
  -- (<>) = (++)
instance Monoid [a] where mempty = []
instance Semigroup (Tsil a) where
  ys <> Lin = ys
  ys <> (Snoc xs x) = Snoc (ys <> xs) x
instance Monoid (Tsil a) where mempty = Lin

我们有

foldMap (: []) xs = xs -- even for infinite xs
foldMap (Snoc Lin) xs = xs -- even for infinite xs

的实现，foldl并foldr在文档中实际给出

foldr f z t = appEndo (foldMap (Endo . f) t ) z
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z

f用来将ain中的每个都t a变成b -> b（Endo b），然后将所有b -> bs组合在一起（以foldr一种方式执行，同时使用foldl反向组合它们Dual (Endo b)），b -> b然后将最终值应用于初始值z :: b。

foldr被替换foldl的专长sum，minimum在等instance Foldable []，出于性能的考虑。这个想法是您sum无论如何都不能取一个无限列表（这个假设是错误的，但通常是足够正确的），因此我们不需要foldr处理它。使用foldl时，在某些情况下，超过高性能foldr，所以foldr更改为foldl。我希望，对Tsil，这foldr有时比更好的性能foldl，因此sum，minimum等可以在以下方面重新实现foldr，而不是fold为了获取性能的改善。请注意，文档中的sum，minimum等应与使用foldMap/ 的形式等效fold，但可能定义不多，这正是发生的情况。

附录的一点点，但我认为值得注意的是：

genFoldr c n [] = n; genFoldr c n (x : xs) = c x (genFoldr c n xs)
instance Foldable [] where
  foldl c = genFoldr (flip c)
  foldr c = foldl (flip c)
-- similarly for Tsil

实际上是一个有效的，合法的Foldable情况下，其中两个 foldr和foldl不自然也不可以处理无穷的可能（foldMap被拖欠的方面foldr，因而也不会处理无限列表）。在这种情况下，foldr和foldl可以彼此书写（foldl c = foldr (flip c)尽管使用来实现genFoldr）。但是，这种情况是不可取的，因为我们确实希望a foldr可以处理无限列表，所以我们改为实现

instance Foldable [] where
  foldr = genFoldr
  foldl c = foldr (flip c)

平等foldr c = foldl (flip c)不再成立的地方