穿越Biapplicative 穿越|

农村四月闲人少，勤学苦攻把名扬。这篇文章主要讲述穿越Biapplicative相关的知识，希望能为你提供帮助。
我正在考虑解压缩操作，并意识到表达它们的一种方法是遍历Biapplicative仿函数。

import Data.Biapplicativeclass Traversable2 t where traverse2 :: Biapplicative p => (a -> p b c) -> t a -> p (t b) (t c)-- Note: sequence2 :: [(a,b)] -> ([a], [b]) sequence2 :: (Traversable2 t, Biapplicative p) => t (p b c) -> p (t b) (t c) sequence2 = traverse2 idinstance Traversable2 [] where traverse2 _ [] = bipure [] [] traverse2 f (x : xs) = bimap (:) (:) (f x) < < *> > traverse2 f xs

它闻起来像我Traversable的每一个实例都可以机械地转换成Traversable2的一个实例。但是我还没有找到一种方法来实际使用traverse2实现traverse，没有转换到列表或从列表转换或者可能用unsafeCoerce玩极其肮脏的技巧。有一个很好的方法来做到这一点？
任何Traversable是Traversable2的进一步证据：

class (Functor t, Foldable t) => Traversable2 t where traverse2 :: Biapplicative p => (a -> p b c) -> t a -> p (t b) (t c) default traverse2 :: (Biapplicative p, Generic1 t, GTraversable2 (Rep1 t)) => (a -> p b c) -> t a -> p (t b) (t c) traverse2 f xs = bimap to1 to1 $ gtraverse2 f (from1 xs)class GTraversable2 r where gtraverse2 :: Biapplicative p => (a -> p b c) -> r a -> p (r b) (r c)instance GTraversable2 V1 where gtraverse2 _ x = bipure (case x of) (case x of)instance GTraversable2 U1 where gtraverse2 _ _ = bipure U1 U1instance GTraversable2 t => GTraversable2 (M1 i c t) where gtraverse2 f (M1 t) = bimap M1 M1 $ gtraverse2 f tinstance (GTraversable2 t, GTraversable2 u) => GTraversable2 (t :*: u) where gtraverse2 f (t :*: u) = bimap (:*:) (:*:) (gtraverse2 f t) < < *> > gtraverse2 f uinstance (GTraversable2 t, GTraversable2 u) => GTraversable2 (t :+: u) where gtraverse2 f (L1 t) = bimap L1 L1 (gtraverse2 f t) gtraverse2 f (R1 t) = bimap R1 R1 (gtraverse2 f t)instance GTraversable2 (K1 i c) where gtraverse2 f (K1 x) = bipure (K1 x) (K1 x)instance (Traversable2 f, GTraversable2 g) => GTraversable2 (f :.: g) where gtraverse2 f (Comp1 x) = bimap Comp1 Comp1 $ traverse2 (gtraverse2 f) xinstance Traversable2 t => GTraversable2 (Rec1 t) where gtraverse2 f (Rec1 xs) = bimap Rec1 Rec1 $ traverse2 f xsinstance GTraversable2 Par1 where gtraverse2 f (Par1 p) = bimap Par1 Par1 (f p)

答案我想我可能有适合您账单的东西。（编辑：它没有，请参阅注释。）您可以在p () c和p b ()上定义新类型，并使它们成为Functor实例。
履行这是你的班级再次使用默认定义。我在sequence2方面实施sequenceA的路线，因为它似乎更简单。

class Functor t => Traversable2 t where {-# MINIMAL traverse2 | sequence2 #-} traverse2 :: Biapplicative p => (a -> p b c) -> t a -> p (t b) (t c) traverse2 f = sequence2 . fmap fsequence2 :: Biapplicative p => t (p b c) -> p (t b) (t c) sequence2 = traverse2 id

现在，Biapplicative的“正确部分”是

newtype R p c = R { runR :: p () c }instance Bifunctor p => Functor (R p) where fmap f (R x) = R $ bimap id f xinstance Biapplicative p => Applicative (R p) where pure x = R (bipure () x) R f < *> R x = let f' = biliftA2 const (flip const) (bipure id ()) f inR $ f' < < *> > xmkR :: Biapplicative p => p b c -> R p c mkR = R . biliftA2 const (flip const) (bipure () ())sequenceR :: (Traversable t, Biapplicative p) => t (p b c) -> p () (t c) sequenceR = runR . sequenceA . fmap mkR

与“左侧部分”大致相同。完整的代码在this gist。
现在我们可以制作p (t b) ()和p () (t c)并将它们重新组装成p (t b) (t c)。

instance (Functor t, Traversable t) => Traversable2 t where sequence2 x = biliftA2 const (flip const) (sequenceL x) (sequenceR x)

我需要为该实例声明启用FlexibleInstances和UndecidableInstances。此外，不知何故，ghc想要一个Functor constaint。
测试我验证了[]的实例，它给出了相同的结果：

main :: IO () main = do let xs = [(x, ord x - 97) | x < - ['a'..'g']] print xs print (sequence2 xs) print (sequence2' xs)traverse2' :: Biapplicative p => (a -> p b c) -> [a] -> p [b] [c] traverse2' _ [] = bipure [] [] traverse2' f (x : xs) = bimap (:) (:) (f x) < < *> > traverse2 f xssequence2' :: Biapplicative p => [p b c] -> p [b] [c] sequence2' = traverse2' id

输出

[('a',0),('b',1),('c',2),('d',3),('e',4),('f',5),('g',6)] ("abcdefg",[0,1,2,3,4,5,6]) ("abcdefg",[0,1,2,3,4,5,6])

这是一个有趣的运动！
另一答案以下似乎可以解决问题，利用“仅”undefined。可行的法律可能保证这是可以的，但我没有试图证明这一点。

{-# LANGUAGE GADTs, KindSignatures, TupleSections #-}import Data.Biapplicativeimport Data.Traversabledata Bimock :: (* -> * -> *) -> * -> * where Bimock :: p a b -> Bimock p (a,b) Bimfmap :: ((a,b) -> c) -> p a b -> Bimock p c Bimpure :: a -> Bimock p a Bimapp :: Bimock p ((a,b) -> c) -> p a b -> Bimock p cinstance Functor (Bimock p) where fmap f (Bimock p) = Bimfmap f p fmap f (Bimfmap g p) = Bimfmap (f . g) p fmap f (Bimpure x) = Bimpure (f x) fmap f (Bimapp gs xs) = Bimapp (fmap (f .) gs) xs instance Biapplicative p => Applicative (Bimock p) where pure = Bimpure Bimpure f< *> xs = fmap f xs fs< *> Bimpure x = fmap ($x) fs fs< *> Bimock p = Bimapp fs p Bimfmap g h< *> Bimfmap i xs = Bimfmap ((~(a?,a?),~(b?,b?)) -> g (a?,b?) $ i (a?, b?)) $ bimap (,) (,) h< < *> > xs Bimapp g h< *> xs = fmap uncurry g < *> ((,)< $> Bimock h< *> xs)runBimock :: Biapplicative p => Bimock p (a,b) -> p a b runBimock (Bimock p) = p runBimock (Bimfmap f p) = bimap (fst . f . (,undefined)) (snd . f . (undefined,)) p runBimock (Bimpure (a,b)) = bipure a b runBimock (Bimapp (Bimpure f) xs) = runBimock . fmap f $ Bimock xs runBimock (Bimapp (Bimfmap h g) xs) = runBimock . fmap ((~(a?,a?),~(b?,b?)) -> h (a?,b?) (a?,b?)) . Bimock $ bimap (,) (,) g< < *> > xs runBimock (Bimapp (Bimapp h g) xs) = runBimock . (fmap (θ (~(a?,a?),~(b?,b?)) -> θ (a?,b?) (a?,b?)) h< *> ) . Bimock $ bimap (,) (,) g< < *> > xstraverse2 :: (Biapplicative p, Traversable t) => (a -> p b c) -> t a -> p (t b) (t c) traverse2 f s = runBimock . fmap (cs-> (fmap fst bcs, fmap snd bcs)) $ traverse (Bimock . f) ssequence2 :: (Traversable t, Biapplicative p) => t (p b c) -> p (t b) (t c) sequence2 = traverse2 id

即使这是安全的，如果它给出了可怕的性能，那么无可辩驳的模式和二次（甚至是指数？）元组树的构建也不会让我感到惊讶。
另一答案一些观察结果缺乏一个完整的，原始的答案。
如果你有一个Biapplicative bifunctor，你可以用它做什么就是把它应用到某个东西上并将它分成一对与其两个组件同构的分子。

data Helper w a b = Helper { left :: w a (), right :: w () b }runHelper :: forall p a b. Biapplicative p => Helper p a b -> p a b runHelper x = biliftA2 const (flip const) (left x) (right x)makeHelper :: (Biapplicative p) => p a b -> Helper p a b makeHelper w = Helper (bimap id (const ()) w) (bimap (const ()) id w)type Separated w a b = (w a (), w () b)

通过将fmap (makeHelper . f)应用于结构s，消除对undefined的需要，可以将@nnnmmm和@leftroundabout的方法结合起来，但是你需要使Helper或它的替换为某些类型类的instance，并使用有用的操作你解决了这个问题。
如果你有Traversable结构，你可以做的是sequenceA Applicative仿函数（在这种情况下你的解决方案将看起来像traverse2 f = fromHelper . sequenceA . fmap (makeHelper . f)，你的Applicative实例建立一对t结构）或traverse它使用Functor（在这种情况下你的解决方案将看起来像traverse2 f = fromHelper . traverse (g . makeHelper . f) where ......）。无论哪种方式，你需要定义一个Functor实例，因为Applicative继承自Functor。您可以尝试从Functor和

<
<
*>
>

或bipure id id构建bimap，或者您可以在同一个传递中处理两个分离的变量。
不幸的是，为了使类型适用于Functor实例，你必须将:: p b c转换为我们非正式地称为:: w (b,c)的类型，其中一个参数是p的两个参数的笛卡尔积。如果没有非标准的扩展，Haskell的类型系统似乎不允许这样做，但@leftroundabout使用Bimock类可以很好地解决这个问题。使用undefined强制两个分离的仿函数具有相同的类型。
为了表现，你想要做的只是进行一次遍历，这会产生一个与p (t b) (t c)同构的对象，然后你可以转换（类似于自然性定律）。因此，您希望实现traverse2而不是sequence2并将sequence2定义为traverse2 id，以避免遍历两次。如果你将变量分开并产生与(p (t b) (), p () (t c))同构的东西，那么你可以将它们重新组合为@mmmnnn。
在实际使用中，我怀疑你会想要在问题上强加一些额外的结构。你的问题保持b的组件c和Bifunctor完全免费，但实际上它们通常是协变或逆变函子，可以用biliftA2测序或在Bitraversable而不是Traversable t上一起遍历，或者甚至可能有Semigroup， Applicative或Monad实例。
一个特别有效的优化将是你的p与Monoid同构，其

<
>

操作产生与你的t同构的数据结构。（这适用于列表和二叉树; Data.ByteString.Builder是具有此属性的代数类型。）在这种情况下，操作的关联性允许您将结构转换为严格的左折叠或惰性右折叠。
这是一个很好的问题，虽然我没有比@leftroundabout更好的代码用于一般情况，但我从中学到了很多东西。
另一答案【穿越Biapplicative】一个唯一有点恶意的做法就是使用来自Magma的lens。这似乎比leftaroundabout的解决方案简单得多，尽管它也不漂亮。

data Mag a b t where Pure :: t -> Mag a b t Map :: (x -> t) -> Mag a b x -> Mag a b t Ap :: Mag a b (t -> u) -> Mag a b t -> Mag a b u One :: a -> Mag a b binstance Functor (Mag a b) where fmap = Mapinstance Applicative (Mag a b) where pure = Pure (< *> ) = Aptraverse2 :: forall t a b c f. (Traversable t, Biapplicative f) => (a -> f b c) -> t a -> f (t b) (t c) traverse2 f0 xs0 = go m m where m :: Mag a x (t x) m = traverse One xs0go :: forall x y. Mag a b x -> Mag a c y -> f x y go (Pure t) (Pure u) = bipure t u go (Map f x) (Map g y) = bimap f g (go x y) go (Ap fs xs) (Ap gs ys) = go fs gs < < *> > go xs ys go (One x) (One y) = f0 x go _ _ = error "Impossible"