I was thinking about unzipping operations and realized that one way to express them is by traversing in a Biapplicative
functor.
import Data.Biapplicative
class 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 id
instance Traversable2 [] where
traverse2 _ [] = bipure [] []
traverse2 f (x : xs) = bimap (:) (:) (f x) <<*>> traverse2 f xs
It smells to me as though every instance of Traversable
can be transformed mechanically into an instance of Traversable2
. But I haven't yet found a way to actually implement traverse2
using traverse
, short of converting to and from lists or perhaps playing extremely dirty tricks with unsafeCoerce
. Is there a nice way to do this?
Further evidence that anything Traversable
is 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 U1
instance GTraversable2 t => GTraversable2 (M1 i c t) where
gtraverse2 f (M1 t) = bimap M1 M1 $ gtraverse2 f t
instance (GTraversable2 t, GTraversable2 u) => GTraversable2 (t :*: u) where
gtraverse2 f (t :*: u) = bimap (:*:) (:*:) (gtraverse2 f t) <<*>> gtraverse2 f u
instance (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) x
instance Traversable2 t => GTraversable2 (Rec1 t) where
gtraverse2 f (Rec1 xs) = bimap Rec1 Rec1 $ traverse2 f xs
instance GTraversable2 Par1 where
gtraverse2 f (Par1 p) = bimap Par1 Par1 (f p)
One only mildly evil way to do this is using something like
Magma
fromlens
. This seems considerably simpler than leftaroundabout's solution, although it's not beautiful either.I think I might have something that fits your bill. (Edit: It doesn't, see comments.) You can define newtypes over
p () c
andp b ()
and make themFunctor
instances.Implementation
Here's your class again with default definitions. I went the route of implementing
sequence2
in terms ofsequenceA
because it seemed simpler.Now, the "right part" of the
Biapplicative
iswith the "left part" much the same. The full code is in this gist.
Now we can make
p (t b) ()
andp () (t c)
and reassemble them intop (t b) (t c)
.I needed to turn on FlexibleInstances and UndecidableInstances for that instance declaration. Also, somehow ghc wanted a Functor constaint.
Testing
I verified with your instance for
[]
that it gives the same results:outputs
This was a fun exercise!
The following seems to do the trick, exploiting “only”
undefined
. Possibly the traversable laws guarantee that this is ok, but I've not attempted to prove it.And even if this is safe, I wouldn't be surprised if it gives horrible performance, what with the irrefutable patterns and quadratic (or even exponential?) tuple-tree buildup.
A few observations short of a complete, original answer.
If you have a
Biapplicative
bifunctor, what you can do with it is apply it to something and separate it into a pair of bifunctors isomorphic to its two components.It would be possible to combine the approaches of @nnnmmm and @leftroundabout by applying
fmap (makeHelper . f)
to the structures
, eliminating the need forundefined
, but then you would need to makeHelper
or its replacement aninstance
of some typeclass with the useful operations that let you solve the problem.If you have a
Traversable
structure, what you can do issequenceA
Applicative
functors (in which case your solution will look liketraverse2 f = fromHelper . sequenceA . fmap (makeHelper . f)
, where yourApplicative
instance builds a pair oft
structures) ortraverse
it using aFunctor
(in which case your solution will look liketraverse2 f = fromHelper . traverse (g . makeHelper . f) where
...). Either way, you need to define aFunctor
instance, sinceApplicative
inherits fromFunctor
. You might try to build yourFunctor
from<<*>>
andbipure id id
, orbimap
, or you might work on both separated variables in the same pass.Unfortunately, to make the types work for the
Functor
instance, you have to paramaterize:: p b c
to a type we would informally call:: w (b,c)
where the one parameter is the Cartesian product of the two parameters ofp
. Haskell’s type system doesn’t seem to allow this without non-standard extensions, but @leftroundabout pulls this off ably with theBimock
class. usingundefined
to coerce both separated functors to have the same type.For performance, what you want to do is make no more than one traversal, which produces an object isomorphic to
p (t b) (t c)
that you can then convert (similar to the Naturality law). You therefore want to implementtraverse2
rather thansequence2
and definesequence2
astraverse2 id
, to avoid traversing twice. If you separate variables and produce something isomorphic to(p (t b) (), p () (t c))
, you can then recombine them as @mmmnnn does.In practical use, I suspect you would want to impose some additional structure on the problem. Your question kept the components
b
andc
of theBifunctor
completely free, but in practice they will usually be either covariant or contravariant functors that can be sequenced withbiliftA2
or traversed together over aBitraversable
rather thanTraversable
t
, or perhaps even have aSemigroup
,Applicative
orMonad
instance.A particularly efficient optimization would be if your
p
is isomorphic to aMonoid
whose<>
operation produces a data structure isomorphic to yourt
. (This works for lists and binary trees;Data.ByteString.Builder
is an algebraic type that has this property.) In this case, the associativity of the operation lets you transform the structure into either a strict left fold or a lazy right fold.This was an excellent question, and although I don’t have better code than @leftroundabout for the general case, I learned a lot from working on it.