7

我正在阅读精彩的Haskell Book。在 Traversable 章节（21）的最后，我需要为以下 Tree 编写一个实例：

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

这是我的解决方案的完整代码的链接。练习建议尝试同时实现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 正在使用的 ing 函数有什么我没有弄清楚的地方。

问题：

  1. 为什么会出现故障？
  2. 有没有办法通过 QuickCheck 获取测试中使用的功能？
4

3 回答 3

4

foldr可以foldMap 通过使用Endomonoid获得，该a -> b -> b函数将a值转换为b -> b可以（monoidally）组合的函数。既然如此，如果你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...我们得到了您问题中所写的正确定义。由于实现之间的差异与组合顺序有关，因此尝试非交换幺半群很容易导致失败案例，正如您所发现的那样。

在 QuickCheck 子问题上，我遵从 DDub 的回答。.

于 2021-01-01T23:30:15.343 回答
3

正如您已经推断的那样，您遇到失败的原因是因为这两种实现是可区分的，您可以通过使用非交换幺半群来观察这一点。

获取 quickcheck 使用的函数并不是那么简单。例如，请参阅有关由 quickcheck 生成的 ing 函数的问题/答案Show以获取更多信息。

从 QuickCheck 中获取Show可用函数的方法是将函数包装在typeFun中。也就是说，您正在调用的代码（在此处找到）只是直接使用函数，因此它们永远无法显示。您可以尝试的一种选择是创建您自己的foldable函数版本，您可以在其中使用类型Fun a b代替a -> b并applyFun根据需要应用函数。

于 2021-01-01T22:40:31.250 回答
2

我刚刚意识到我使用了可交换 Monoid ...我能够使用非交换 Monoid 重新创建故障：

> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}

这可能是一个简单的案例。我想在具有真实数据类型的生产代码中，这可能要复杂得多。

于 2021-01-01T20:00:24.737 回答