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

  • 3
    Are there specific concrete types that you're looking to use this with? This function can't be derived for just any two functors. – 4castle Apr 17 at 13:05
  • 2
    Or any two applicatives. – Cubic Apr 17 at 13:16
  • @4castle: Sorry I didn't think things through well enough. I'm looking for a generalized zip that can handle and convert different sequence types automatically. – Neal Alexander Apr 17 at 13:35
  • I think you would need to provide the natural transformation from one functor to the other yourself; even assuming you can get the function out of the applicative f and apply it to the g a to get a g b, you still need something with type g b -> f b to get your final result. – chepner Apr 17 at 14:20
  • (Probably two natural transformations, the other to get a g (a -> b) from f (a -> b) in the first place.) – chepner Apr 17 at 14:23

(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 Days with (<*>). One can work smarter by wrapping the functors in Lift for transformers, to get faster operations for the simple "pure" cases.


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

  :: (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)

Note on recent GHC versions

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])
  • 2
    I'm wondering if Day convolution ala Kmett is in play. – dfeuer Apr 17 at 16:21
  • 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
  • Yes, I was aware the function was partial, but I don't think there's a clear alternative. You could 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 fromList. I would write the concrete version, or at most generalize over the input types. Here are examples with 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.

  • 1
    Note that there is 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
  • Great point! I edited to use IsList. – bergey Apr 17 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.