Sri*_*aic 7 haskell applicative traversable foldable
尽管标题充满了行话,但我认为这个问题并不复杂。
这里有两个重要的 Functor 组合子。Flip等同于 haskell 函数,flip但对类型进行操作
newtype Flip p a b
  = Flip
    { unFlip :: p b a
    }
和Join相当于对类型在W组合子,它需要一个bifunctor和沿其两个参数产生算符
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可以在两个参数上遍历但在连接时不可遍历的 a 。
到目前为止,我已经尝试了所有基础知识,但没有一个是反例。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
我通过组合类型提出了更多示例,为了简单起见,我将省略这些示例,但不用说它们最终都是可遍历的。
有反例吗?这个实例可以写吗?