a simple generalisation of the Applicative (Functor) type-class; pattern matching on constructors

Question

I've been trying to "learn me a Haskell" through the online book LYAH.

The author describes the behaviour of Functors of the Applicative type as sort of having the ability to extract a function from one functor and mapping it over a second functor; this is through the <*> function declared for the Applicative type class:

class (Functor f) => Applicative f where  
    pure :: a -> f a  
    (<*>) :: f (a -> b) -> f a -> f b

As a simple example, the Maybe type is an instance of Applicative under the following implementation:

    instance Applicative Maybe where  
    pure = Just  
    Nothing <*> _ = Nothing  
    (Just f) <*> something = fmap f something

An example of the behaviour mentioned previously:

ghci> Just (*2) <*> Just 10         -- evaluates to Just 20

so the <*> operator "extracts" the (*2) function from the first operand and maps it over the second operand.

Now in Applicative types, both operands of <*> are of the same type, so I thought as an exercise why not try implementing a generalisation of this behaviour, where the two operands are Functors of different types, so I could evaluate something like this:

Just (2*) <*:*> [1,2,3,4]  -- should evaluate to [2,4,6,8]

So this is what I came up with:

import Control.Applicative

class (Applicative f, Functor g) => DApplicative f g where
    pure1 :: a -> f a
    pure1 = pure
    (<*:*>) :: f ( a -> b )  -> g a -> g b      -- referred below as (1)

instance DApplicative Maybe [] where    -- an "instance pair" of this class
    (Just func) <*:*> g = fmap func g

main = do putStrLn(show x)
    where x = Just (2*) <*:*> [1,2,3,4]  -- it works, x equals [2,4,6,8]

Now, although the above works, I'm wondering if we can do better; is it possible to give a default implementation for <*:*> that can be applied to a variety of f & g pairs, in the declaration for DApplicative f g itself? And this leads me to the following question: Is there a way to pattern match on constructors across different data types?

I hope my questions make some sense and I'm not just spewing nonsense (if I am, please don't be too harsh; I'm just an FP beginner up way past his bedtime...)

John L John L · Accepted Answer · 2011-09-10T10:16:38

This does make sense, but it ends up being not particularly useful in its current form. The problem is exactly what you've noticed: there is no way to provide a default which does sensible things with different types, or to generally convert from f to g. So you'd have a quadratic explosion in the number of instances you'd need to write.

You didn't finish the DApplicative instance. Here's a full implementation for Maybe and []:

instance DApplicative Maybe [] where    -- an "instance pair" of this class
    (Just func) <*:*> g = fmap func g
    Nothing     <*:*> g = []

This combines the behaviors of both Maybe and [], because with Just it does what you expect, but with Nothing it returns nothing, an empty list.

So instead of writing DApplicative which takes two different types, what if you had a way of combining two applicatives f and g into a single type? If you generalize this action, you could then use a standard Applicative with the new type.

This could be done with the standard formulation of Applicatives as

liftAp :: f (g (a -> b)) -> f (g a) -> f (g b)
liftAp l r = (<*>) <$> l <*> r

but instead let's change Maybe:

import Control.Applicative

newtype MaybeT f a = MaybeT { runMaybeT :: f (Maybe a) }

instance (Functor f) => Functor (MaybeT f) where
    fmap f (MaybeT m) = MaybeT ((fmap . fmap) f m)

instance (Applicative f) => Applicative (MaybeT f) where
    pure a = MaybeT (pure (pure a))
    (MaybeT f) <*> (MaybeT m) = MaybeT ( (<*>) <$> f <*> m)

Now you just need a way to convert something in the inner applicative, f, into the combined applicative MaybeT f:

lift :: (Functor f) => f a -> MaybeT f a
lift = MaybeT . fmap Just

This looks like a lot of boilerplate, but ghc can automatically derive nearly all of it.

Now you can easily use the combined functions:

*Main Control.Applicative> runMaybeT $ pure (*2) <*> lift [1,2,3,4]
[Just 2,Just 4,Just 6,Just 8]

*Main Control.Applicative> runMaybeT $ MaybeT (pure Nothing) <*> lift [1,2,3,4]
[Nothing,Nothing,Nothing,Nothing]

This behavior at Nothing may be surprising, but if you think of a list as representing indeterminism you can probably see how it could be useful. If you wanted the dual behavior of returning either Just [a] or Nothing, you just need a transformed List ListT Maybe a.

This isn't quite the same as the instance I wrote for DApplicative. The reason is because of the types. DApplicative converts an f into a g. That's only possible when you know the specific f and g. To generalize it, the result needs to combine the behaviors of both f and g as this implementation does.

All of this works with Monads too. Transformed types such as MaybeT are provided by monad transformer libraries such as mtl.

a simple generalisation of the Applicative (Functor) type-class; pattern matching on constructors

2 Answers