A simple generalization of a class of type Application (functor); pattern matching by constructor

Question

I tried to "get to know Haskell" through the LYAH online book.

The author describes the behavior of applicators of the applicative type as a kind of ability to extract a function from one functor and display it by a second functor; this is via the <*> function declared for the Applicative type class:

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

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

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

An example of the behavior described above:

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

therefore, the operator <*> "extracts" the function (* 2) from the first operand and displays it on top of the second operand.

Now, in applicative types, both operands from <*> are of the same type, so I thought it was an exercise, why not try to implement a generalization of this behavior, where 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 here is what I came up with:

 import Control.Applicative class (Applicative f, Functor g) => DApplicative fg where pure1 :: a -> fa pure1 = pure (<*:*>) :: f ( a -> b ) -> ga -> gb -- 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 this works above, I wonder if we can do better; Is it possible to provide a default implementation for <*: *>, which can be applied to many pairs of f and g, in the declaration for DApplicative fg itself? And this leads me to the following question: is there a way to map patterns to constructors of different data types?

I hope that my questions will make some sense, and I’m not just throwing nonsense (if I, please, don’t be too harsh, I’m just a beginner FP who passed him by his sleep ...)

Answer 1

This makes sense, but ultimately it is not particularly useful in its current form. The problem is that you noticed: there is no way to provide a default value that does reasonable things with different types, or even convert from f to g . Thus, you will have a quadratic explosion in the number of copies that you need to write.

You have not finished the DApplicative instance. Here's the 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 behavior of Maybe as well as [] , because with Just it does what you expect, but with Nothing it returns nothing, an empty list.

So, instead of writing a DApplicative that accepts two different types, what if you have a way to combine the two applications f and g into one type? If you generalize this action, you can use the standard Applicative with a new type.

This can be done with the standard formulation of Applicability as

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

but change Maybe instead:

 import Control.Applicative newtype MaybeT fa = MaybeT { runMaybeT :: f (Maybe a) } instance (Functor f) => Functor (MaybeT f) where fmap f (MaybeT m) = MaybeT ((fmap . fmap) fm) instance (Applicative f) => Applicative (MaybeT f) where pure a = MaybeT (pure (pure a)) (MaybeT f) <*> (MaybeT m) = MaybeT ( (<*>) <$> f <*> m) 

Now you just need to convert something into the internal application f into the combined applicative MaybeT f :

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

It looks like a lot of templates, but ghc can automatically output almost everything.

Now you can easily use 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 in Nothing can be surprising, but if you think of the list as representing indeterminism, you can probably see how this can be useful. If you want double behavior to return either Just [a] or Nothing , you just need a converted ListT Maybe a list.

This is not exactly the same as the instance I wrote for DApplicative . The reason is related to types. DApplicative converts a f to g . This is only possible when you know the specific f and g . To generalize it, the result must combine the behavior of both f and g , as the implementation does.

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

Answer 2

Your DApplicative instance for Maybe not complete: what should happen if the first argument <*:*> is Nothing ?

The choice of what to do for each combination is not clear. For two lists, <*> generates all combinations: [(+2),(+10)] <*> [3,4] gives [5,6,13,14] . For two ZipList you have a zip-like behavior: (ZipList [(+2),(+10)]) <*> (ZipList [3,4]) gives [5,14] . Therefore, you need to choose one of the possible behaviors for the DApplicative list and ZipList , there is no "correct" version.