是否有可折叠类型类的定律来限制如何派生可折叠实例?

Question

我正在 Haskell 中试验Foldable类型类，使用以下数据类型作为示例：

data Tree a = Empty
| Node (Tree a) a (Tree a)

如果我使用DeriveFoldableGHC 扩展，它似乎会派生一个Foldable实例，

如下所示

instance Foldable Tree where
foldMap _ Empty = mempty
foldMap f (Node l n r) = (foldMap f l) <> (f n) <> (foldMap f r)

即树的无序遍历。但是，我没有看到任何明显的阻止不同Foldable实例的东西，例如预序遍历：

instance Foldable Tree where
foldMap _ Empty = mempty
foldMap f (Node l n r) = (f n) <> (foldMap f l) <> (foldMap f r)

是否有针对Foldable类型类的法律会使预购遍历实例非法？

Answer 1

Foldable

没有指导遍历顺序的定律。事实上，我们可以将编写Foldable实例的行为视为选择特定的遍历顺序。如果使用DeriveFoldable，则选择遵循类型定义中字段的顺序(另请参阅丹尼尔·瓦格纳的答案(;详细信息记录在GHC用户指南的相关部分中。

(旁注：正如dfeuer的回答中所讨论的，Traversable有更丰富的法律，除其他外，限制了可接受的foldMap实现的范围。尽管如此，对于您的Tree的无序和预序遍历都会给出Traversable的合法实现。

Answer 2

Foldable本身在法律上非常糟糕。基本方法是foldMap.其他方法的行为应类似于其默认定义，直至延迟详细信息。参数性产生两个定律：

1. 如果g :: m -> n是幺半群态射，f :: a -> m是函数，则

   g . foldMap f = foldMap (g . f)
   

2. 如果Foldable也是Functor，则对于所有函数g :: b -> m和f :: a -> b，

   foldMap (g . f) = foldMap g . fmap f
   

实际上，大多数Foldable实例也是Traversable。Traversable对traverse有更丰富的法律，并强加了法律

foldMap f = getConst . traverse (Const . f)

这保证了对于一个Traversable，容器中的每个元素都被折叠一次。而

instance Foldable [] where
foldMap _ [] = mempty
foldMap f (x:_:xs) = f x <> f x <> foldMap f xs

将是完全有效的，没有合法的Traversable实例匹配。

Answer 3

不，没有法律规定必须按什么顺序访问字段。通常按照字段在数据结构定义中出现的顺序(如果使用模式同义词，则至少是用户可见的 API(访问字段，但这只是约定。