-4

可以foldr和foldl 相互定义吗？

Hutton 在 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

谢谢。

4

4 回答 4

6

一般来说，两者都 foldr不能，也foldl不能相互实现。的核心操作Foldableis 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, and foldl（在列表的情况下）必须遍历列表的整个脊椎才能产生输出。但是，如果xs是无限的，foldl 则无法遍历整个无限列表，因此foldr' (:) [] xs无限循环xs，而foldr (:) [] xs只是产生xs。foldl' = foldl但是，根据需要。本质上，对于[]，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在无限/部分未定义Tsil的 s 上具有良好的“生产性”行为，而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)），然后将 finalb -> b应用于初始值z :: b。

foldr出于性能原因，在 ,中被替换为foldlin specializations sum,minimum等。instance Foldable []这个想法是无论如何你都不能接受sum一个无限列表（这个假设是错误的，但它通常是正确的），所以我们不需要foldr处理它。在某些情况下， usingfoldl比 , 性能更高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实例，其中和都是 不自然的，并且都不能处理无限结构（默认为，因此也不会处理无限列表）。在这种情况下，和可以相互写成（，尽管它是用 实现的）。然而，这个实例是不可取的，因为我们真的想要一个可以处理无限列表的，所以我们改为实现foldrfoldlfoldMapfoldrfoldrfoldlfoldl c = foldr (flip c)genFoldrfoldr

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

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

于 2019-07-29T20:52:28.127 回答
3

在列表的情况下：foldl可以定义为，foldr但反之则不行。

foldl f a l = foldr (\b e c -> e (f c b)) id l a

对于其他实现Foldable: 的类型可能相反。

于 2019-07-29T21:08:52.710 回答
3

这是一个既不能 foldl也不foldr能用另一个来实现的类型：

import Data.Functor.Reverse
import Data.Monoid

data DL a = DL [a] (Reverse [] a)
  deriving Foldable

实现Foldable看起来像

instance Foldable DL where
  foldMap f (DL front rear) = foldMap f front <> foldMap f rear

内联Foldable实例Reverse []，并添加相应的foldr和foldl，

  foldMap f (DL front rear) = foldMap f front <> getDual (foldMap (Dual . f) (getReverse rear))
  foldr c n (DL xs (Reverse ys)) =
    foldr c (foldl (flip c) n ys) xs
  foldl f b (DL xs (Reverse ys)) =
    foldr (flip f) (foldl f b xs) ys

如果前面的列表是无限的，那么foldr定义 usingfoldl将不起作用。如果后面的列表是无限的，那么foldl定义 usingfoldr将不起作用。

于 2019-08-02T17:26:50.557 回答
1

编辑2：

还有另一种方法可以满足（基于这篇文章）foldl：

foldl f a list = (foldr construct (\acc -> acc) list) a
  where
    construct x r = \acc -> r (f acc x)

编辑 1

翻转函数的参数不会创建相同的 foldr/foldl，这意味着此示例不满足 foldr-foldl 的相等性：

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

并foldl在foldr方面：

foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldl' f b = foldr (flip f) b

和foldr：

foldr' :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr' f b = foldl (flip f) b

反之则不成立，因为 foldr 可能适用于无限列表，而 foldl 变体永远无法做到。然而，对于有限列表，foldr 也可以用 foldl 来写，尽管在这个过程中失去了惰性。（更多检查在这里）

Ando 也不满足这个例子：

foldr (-) 2 [8,10] = 8 - (10 - 2) == 0

foldl (flip (-)) 2 [8,10] = (flip (-) (flip (-) 2 8) 10) == 4
于 2019-07-29T19:36:02.797 回答