在_not_的意义上，哪些是Data.Foldable“一般折叠结构”的可折叠实例？

Question

Foldable列出了“一般可折叠结构”所需的几个属性：

• 对于foldr： 对于一般的可折叠结构，这应该在语义上是相同的， f= foldr。toList
• 对于foldl： 对于一般的可折叠结构，这应该在语义上是相同的， f= foldltoList
• 对于foldl' (在我看来是一个错误)： 对于一般的可折叠结构，这应该在语义上是相同的， f=f‘f。toList

这些属性不需要或不能保存的Foldable的一些实例是什么？

Answer 1

据我所知，如果实例定义了这些可选函数，则必须遵守这些规则。默认情况下，Foldable实例只需定义foldMap或foldr。从这两个定义中的一个，类型类的所有其他函数都会自动跟随。

但是，类型类通常为您提供了定义更多类型类行为的选项。如果toList的默认自动定义效率低下，并且您希望提供更高效的实现，这将是非常有用的。对于Monoid类型类来说，这可能更容易理解，它将mconcat定义为一个可选函数，“这样就可以为特定类型提供优化版本”。

OP中引用的法律是实例必须遵守的法律，如果您选择自己定义这些功能的一部分或全部。作为打破规则的(无意义的)类型的一个例子，请考虑以下Invalid类型：

import Data.Foldable

data Invalid a = Invalid a deriving (Show, Eq)

instance Foldable Invalid where
  foldMap f (Invalid x) = f x
  foldr _ x _ = x -- Unlawful!!
  toList (Invalid x) = [x]

虽然它只需要将foldMap定义为一个Foldable实例，但这个实例也定义了foldr和toList。虽然toList定义很好，但foldr定义违反了规则：

*Q53460772 Data.Monoid Data.Foldable> toList $ Invalid 42
[42]
*Q53460772 Data.Monoid Data.Foldable> foldMap Sum $ Invalid 42
Sum {getSum = 42}
*Q53460772 Data.Monoid Data.Foldable> f = \x acc -> x + acc
*Q53460772 Data.Monoid Data.Foldable> z = 0
*Q53460772 Data.Monoid Data.Foldable> (foldr f z . toList) $ Invalid 42
42
*Q53460772 Data.Monoid Data.Foldable> foldr f z $ Invalid 42
0

toList和foldMap函数的行为与您预期的一样，但请注意，foldr f z产生的输出与foldr f z . toList不同。

虽然Invalid是一个荒谬的例子，但它说明您可以编写编译代码，并且看起来它提供了Foldable的一个实例。然而，与每个功能相关的法律和规则清楚地表明，这不是一个有效的实例。