haskell - 为什么 Traversable 不能多次访问其元素？

Question

我记得在某处读到这样的类型不能是 Traversable :

data Bar a = Bar a deriving(Show)

instance Functor Bar where
  fmap f (Bar x) = Bar (f x)

instance Foldable Bar where
  foldMap f (Bar x) = f x <> f x

我记得的解释是 foldMap = foldMapDefault持有， Traversable instance 将不得不多次访问其元素，而合法的 instance 则无法做到这一点。但是，我不记得为什么合法的实例不能这样做。考虑这个:

instance Traversable Bar where
  sequenceA (Bar x) = Bar <$ x <*> x

乍一看还不错。这样做有什么违法的？

Answer 1

我仍然无法解释为什么 Traversable s 通常不能多次访问它们的元素，但我确实弄清楚了为什么我的问题中的特定实例是非法的:

一个 Traversable具有三个定律:自然性、同一性和组合性。 fmap = fmapDefault 也应该是这种情况。和 foldMap = foldMapDefault .自然性通过参数化是免费的。对于Traversable有问题，身份，fmap = fmapDefault , 和 foldMap = foldMapDefault都是微不足道的验证。因此，失败的必然是组合法则。我开始操作 sequenceA它的版本并将其插入其中，最后得到以下结果:

(\y z -> Bar <$ y <*> z) <$> x <*> x = (\y z -> Bar <$ z <*> z) <$> x <*> x

现在很清楚如何找到反例了。首先，我们需要找到一个 y和 z这样 Bar <$ y <*> z和 Bar <$ z <*> z是不同的。由于 y不是因为它的内在值(value)而使用它，它必须引起某种效果。经检查， y = Nothing和 z = Just ()将导致第一个是 Nothing第二个是 Just (Bar ()) .

接下来，我们需要找到一个 x这样第一次使用 x将是我们的 y , Nothing以及 x 的第二次使用将是我们的 z , Just () .我们可以使用 State为此，初始状态为 Nothing , 和 x是 get <* put (Just ()) .

现在我们认为我们有一个完整的反例，所以让我们验证一下。原法为 sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA ，所以让我们把它的每一面都放在自己的变量中:

import Data.Functor.Compose

lhs = sequenceA . fmap Compose
rhs = Compose . fmap sequenceA . sequenceA

并存储我们的 x :

import Control.Monad.State

x = get <* put (Just ())

最后，把它们放在一起:

λ> evalState (getCompose $ lhs $ Bar x) Nothing
Nothing
λ> evalState (getCompose $ rhs $ Bar x) Nothing
Just (Bar ())

我们的反例有效!如果法律成立， lhs和 rhs将是等效的，但显然不是，因为将一个换成另一个会产生不同的结果。