为什么 Traversable for list 的这个实例不正确？

Question

以下代码未通过跳棋测试可遍历。我希望能解释失败的原因，而不仅仅是如何修复它。

import Test.QuickCheck
import Test.QuickCheck.Checkers
import Test.QuickCheck.Classes

data List a =
  Nil
  | Cons a (List a)
    deriving (Show, Eq, Ord)

instance Functor List where
  fmap _ Nil = Nil
  fmap f (Cons x xs) = (Cons (f x) (fmap f xs))

instance Foldable List where
  foldr f z (Cons x xs) = f x z
  foldr _ z Nil = z

instance Traversable List where
  traverse f Nil = pure Nil
  -- traverse f (Cons x Nil) = Cons <$> f x <*> pure Nil
  traverse f (Cons x xs) = Cons <$> f x <*> (traverse f xs)

instance Arbitrary a => Arbitrary (List a) where
  arbitrary = sized go
    where go 0 = pure Nil
          go n = do
            xs <- go (n - 1)
            x <- arbitrary
            return (Cons x xs)

type TI = List

instance Eq a => EqProp (List a) where (=-=) = eq

main = do
  let trigger = undefined :: TI (Int, Int, [Int])
  -- quickBatch (functor trigger)
  quickBatch (traversable trigger)

在这里您可以看到它通过了 fmap 定律，但没有通过 foldMap 定律：

λ> main

traversable:
  fmap:    +++ OK, passed 500 tests.
  foldMap: *** Failed! Falsifiable (after 6 tests): 
<function>
Cons 4 (Cons (-2) (Cons (-5) (Cons 5 (Cons 2 Nil))))

Answer 1

instance Foldable List where
  foldr f z (Cons x xs) = f x z
  foldr _ z Nil = z

您的 Foldable 实例没有遍历列表的尾部。

checkers 通过一起测试 Functor 和 Foldable 来测试您的 Traversable 实例：它从您的实现中派生出 foldMap 和 fmap Traversable 并确保它们产生与您定义的 foldMap 和 fmap 相同的结果。

为什么 Traversable for list 的这个实例不正确？

Why is this instance of Traversable for list not correct?

haskell

traversable