haskell - 为什么这个实现是可折叠类型类的错误实例？

Question

我正在处理精彩的 Haskell Book .在 Traversable 章节(21)的最后，我需要为以下 Tree 编写一个实例:

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

这里是 a link to the full code我的解决方案。练习建议尝试同时实现 foldMap和 foldr .这就是我实现 foldr 的方式(没有过多考虑调用顺序):

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  f x $ foldr f (foldr f z left) right

然后我实现了 foldMap如下:

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

当我运行 QuickCheck 的 foldable测试批处理，我遇到了一些失败。改变我的 foldr实现以下使所有测试通过:

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left

我尝试自己运行失败的测试用例，但无法重新创建失败:

*Ch21_12_ExercisesTree Data.Monoid> tree = Node (Node (Leaf (-5)) 3 (Node (Leaf 3) 5 Empty)) (-2) Empty
*Ch21_12_ExercisesTree Data.Monoid> foldr (<>) (mempty :: Sum Int) t
Sum {getSum = 4}
*Ch21_12_ExercisesTree Data.Monoid> foldMap Sum t
Sum {getSum = 4}

我怀疑有一些关于 fold 的事情我没有弄清楚。 QuickCheck 正在使用的功能。
问题:

为什么会出现故障？

有没有办法通过 QuickCheck 获取测试中使用的功能？

Answer 1

foldr可以从foldMap获得by using the Endo monoid , 与 a -> b -> b功能车削a值转换为 b -> b可以(单向)组合的函数。既然如此，如果您的 foldMap是...

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

...对应的 foldr一定是:

foldr f z Empty = id z  -- mempty amounts to id
foldr f z (Leaf x) = (f x) z
foldr f z (Node left x right) = 
  ((\e -> foldr f e left) . f x . (\e -> foldr f e right)) z  -- (<>) amounts to (.)

如果我们稍微整理一下...

foldr f z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left)

...我们得到了 foldr的正确定义正如你的问题所写。由于实现之间的差异与组合顺序有关，因此尝试非交换幺半群很容易导致失败案例， as you have found out .
关于 QuickCheck 子问题，我遵从 DDub's answer. .