haskell - 加入的 Bitraversable 是否需要 Monad？

Question

尽管标题充满了行话，但我认为这个问题并不复杂。

人物介绍

这里有两个重要的 Functor 组合子在起作用。Flip等效于 haskell 函数flip，但对类型进行操作

newtype Flip p a b
  = Flip
    { unFlip :: p b a
    }

并且Join等效于类型上的 W 组合子，它接受一个双函子并沿其两个参数生成一个函子

newtype Join p a
  = W
    { unW :: p a a
    }

---

可遍历

现在Foldable可以创建以下实例：

instance
  ( forall a . Foldable (p a)
  , forall a . Foldable (Flip p a)
  )
    => Foldable (Join p) where
  foldr g x (W xs) = foldr g (foldr g x xs) (Flip xs)

也就是说，如果p在它的两个参数上都是可折叠的，那么它Join p是可折叠的。这是通过向左折叠然后向右折叠来完成的。

现在我想为 做一个类似的实例Traversable，但是我遇到了一个问题。sequence我可以很容易地写作

sequence (W xs) = (map W . join . map (sequenceA . unFlip) . sequenceA . Flip) xs

但是，我似乎需要能够使用join，所以我在编写时遇到了麻烦sequenceA。事实上，写一个sequenceA.

但是我很难想出一个反例。那是p可以在两个参数上遍历但在连接时不可遍历的。

到目前为止，我已经尝试了所有基础知识，但没有一个是反例。Join (,)是可遍历的

sequenceA (W (x, y)) = liftA2 (W . (,)) x y

高阶元组，例如Join ((,,) a)很好。

sequenceA (W (x, y, z)) = liftA2 (W . (,,) x) y z

Join Either也是可遍历的

sequenceA (W (Left x)) = map (W . Left) x
sequenceA (W (Right x)) = map (W . Right) x

我通过组合类型提出了更多示例，为了简单起见，我将省略这些示例，但不用说它们最终都是可遍历的。

有反例吗？这个实例可以写吗？

标签： haskellapplicativetraversablefoldable