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

Question

文档Foldable列出了“通用可折叠结构”所需的几个属性：

• 对于foldr：

  对于一般的可折叠结构，这在语义上应该是相同的，

  foldr f z = foldr f z . toList
  

• 对于foldl：

  对于一般的可折叠结构，这在语义上应该是相同的，

  foldl f z = foldl f z . toList
  

• 对于foldl'（对我来说看起来像是一个错字）：

  对于一般的可折叠结构，这在语义上应该是相同的，

  foldl f z = foldl' f z . toList
  

Foldable这些属性不需要或不能保持的情况有哪些？

标签： haskellfoldable

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实例，但这个也定义了foldrand 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

toListandfoldMap函数的行为与您期望的一样，但请注意它不会foldr f z产生与foldr f z . toList.

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