Is there something similar to the Applicative
type class, but where there are two functors for each side of the application which are different?
i.e. (<*>) :: (Functor f, Functor g) => f (a -> b) -> g a -> f b
Is there something similar to the Applicative
type class, but where there are two functors for each side of the application which are different?
i.e. (<*>) :: (Functor f, Functor g) => f (a -> b) -> g a -> f b
(Following a suggestion from @dfeuer in the comments.)
There is a construction called day convolution that lets you preserve the distinction between two functors when performing applicative operations, and delay the moment of transforming one into the other.
The Day
type is simply a pair of functorial values, together with a function that combines their respective results:
data Day f g a = forall b c. Day (f b) (g c) (b -> c -> a)
Notice that the actual return values of the functors are existencialized; the return value of the composition is that of the function.
Day
has advantages over other ways of combining applicative functors. Unlike Sum
, the composition is still applicative. Unlike Compose
, the composition is "unbiased" and doesn't impose a nesting order. Unlike Product
, it lets us easily combine applicative actions with different return types, we just need to provide a suitable adapter function.
For example, here are two Day ZipList (Vec Nat2) Char
values:
{-# LANGUAGE DataKinds #-}
import Data.Functor.Day -- from "kan-extensions"
import Data.Type.Nat -- from "fin"
import Data.Vec.Lazy -- from "vec"
import Control.Applicative
day1 :: Day ZipList (Vec Nat2) Char
day1 = Day (pure ()) ('b' ::: 'a' ::: VNil) (flip const)
day2 :: Day ZipList (Vec Nat2) Char
day2 = Day (ZipList "foo") (pure ()) const
(Nat2
is from the fin package, it is used to parameterize a fixed-size Vec
from vec.)
We can zip them together just fine:
res :: Day ZipList (Vec Nat2) (Char,Char)
res = (,) <$> day1 <*> day2
And then transform the Vec
into a ZipList
and collapse the Day
:
res' :: ZipList (Char,Char)
res' = dap $ trans2 (ZipList . toList) res
ghci> res'
ZipList {getZipList = [('b','f'),('a','o')]}
Using the dap
and trans2
functions.
Possible performance catch: when we lift one of the functors to Day
, the other is given a dummy pure ()
value. But this is dead weight when combining Day
s with (<*>)
. One can work smarter by wrapping the functors in Lift
for transformers, to get faster operations for the simple "pure" cases.
Day
: my "process-streaming" library uses Day
internally to combine handlers for the stdin, stdout and stderr of an external process into a single Applicative
. hackage.haskell.org/package/process-streaming-0.9.3.0/docs/… It also uses the Lift
trick.
– danidiaz
Apr 17 at 19:17
One general concept of "sequence type" is a free monoid. Since you're looking at polymorphic sequence types, we can build on Traversable
.
class Semigroup1 t where
(<=>) :: t a -> t a -> t a
class Semigroup1 t => Monoid1 t where
mempty1 :: t a
See note below.
class (Traversable t, Monoid1 t) => Sequence t where
singleton :: a -> t a
How is that a sequence type? Very inefficiently. But we could add a bunch of methods with default implementations to make it efficient. Here are some basic functions:
cons :: Sequence t => a -> t a -> t a
cons x xs = singleton x <=> xs
fromList
:: (Foldable f, Sequence t)
=> f a -> t a
fromList = foldr cons mempty1
uncons :: Sequence t => t a -> Maybe (a, t a)
uncons xs = case toList xs of
y:ys -> Just (y, fromList ys)
[] -> Nothing
With these tools, you can zip any two sequences to make a third.
zipApp :: (Foldable t, Foldable u, Sequence v) = t (a -> b) -> u a -> v b
zipApp fs xs = fromList $ zipWith ($) (toList fs) (toList xs)
For bleeding edge GHC, you can use QuantifiedConstraints
and RankNTypes
and ConstraintKinds
and define
type Semigroup1 t = forall a. Semigroup (t a)
type Monoid1 t = forall a. Monoid (t a)
Doing it this way would let you write, e.g.,
fromList = foldMap singleton
From your comment, I think you might be trying to construct:
import Data.Foldable
import Data.Traversable
foo :: (Traversable f, Foldable g) => f (a -> b) -> g a -> f b
foo f g = snd $ mapAccumR (\(a:as) fab -> (as, fab a)) (toList g) f
This allows, for example:
> import qualified Data.Vector as V
> foo [(+1),(+2),(+3)] (V.fromList [5,6,7])
[8,8,8]
>
foo [(+1),(+2),(+3)] (V.fromList [5,6,7,8])
works, foo [(+1),(+2),(+3)] (V.fromList [5,6])
bombs with "Non-exhaustive patterns in lambda"
.
– Will Ness
Apr 17 at 16:42
cycle
the list from g
, which seems like a terrible idea, or you could restrict the function to f
that are isomorphic to []
(e.g., use constraint IsList f
).
– K. A. Buhr
Apr 17 at 17:54
I don't know of any general I would write the concrete version, or at most generalize over the input types. Here are examples with fromList
.Vector
, ignoring that Data.Vector.zip
already exists.
import qualified Data.Vector as V
import Data.Vector (Vector)
import Data.Foldable
import GHC.Exts (IsList(fromList))
zipV1 :: Vector (a -> b) -> Vector a -> Vector b
zipV1 fs as = V.fromList (zipWith ($) (V.toList fs) (V.toList as))
zipV2 :: (Foldable f, Foldable g, IsList (f b)) => f (a -> b) -> g a -> f b
zipV2 fs as = fromList (zipWith ($) (toList fs) (toList as))
You could use IsList
instead of Foldable
in the second example.
fromList
from IsList
, so that would work, and many standard list-isomorphic sequences will support it (e.g., Vector
already as an instance).
– K. A. Buhr
Apr 17 at 17:56
f
and apply it to theg a
to get ag b
, you still need something with typeg b -> f b
to get your final result. – chepner Apr 17 at 14:20g (a -> b)
fromf (a -> b)
in the first place.) – chepner Apr 17 at 14:23