CODEWITHSUNDEEP
haskellfunctorapplicative
Jean-Baptiste
Jean-Baptiste

Reputation: 31

Applicative typeclass based on two different functors

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

Upvotes: 3

Views: 190

Answers (4)

dfeuer
dfeuer

Reputation: 48581

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)

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

Upvotes: 2

danidiaz
danidiaz

Reputation: 27771

(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.

Upvotes: 5

bergey
bergey

Reputation: 3071

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.

Upvotes: 0

K. A. Buhr
K. A. Buhr

Reputation: 50819

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]
>

Upvotes: 1

Related Questions