Examples of Haskell Applicative Transformers

Question

The wiki on www.haskell.org tells us the following about Applicative Transformers:

So where are applicative transformers? The answer is, that we do not need special transformers for applicative functors since they can be combined in a generic way. http://www.haskell.org/haskellwiki/Applicative_functor#Applicative_transfomers

I tried the following in order to try to combine a bunch of applicative functors. But all I got was bunch of errors. Here is the code:

import Control.Applicative
import System.IO

ex x y = (:) <$> x <*> y 
test1 = ex "abc" ["pqr", "xyz"]  -- only this works correctly as expected
test2 = ex "abc" [Just "pqr", Just "xyz"]
test3 = ex "abc" (Just "pqr")
test4 = ex (Just 'a') ["pqr", "xyz"]
test5 = ex (return ("abc"):: IO ()) [Just "pqr", Just "xyz"]

This produces a lot of type errors, which though I can partially understand, I couldn't resolve them at all.

The errors are given at the end.

So, how do I combine the Maybe Applicative and the List Applicative for example?

How do I combine the State Applicative and the List Applicative for example? Are there any other examples, let's say, combining Maybe and List, Maybe and State and finally the dreadful of all the IO and State applicatives?

Thanks.

The GHCi error msgs follow.

example.hs:6:19:
    Couldn't match expected type `[Char]' with actual type `Maybe a0'
    In the return type of a call of `Just'
    In the expression: Just "pqr"
    In the second argument of `ex', namely `[Just "pqr", Just "xyz"]'

example.hs:7:19:
    Couldn't match expected type `[[Char]]' with actual type `Maybe a0'
    In the return type of a call of `Just'
    In the second argument of `ex', namely `(Just "pqr")'
    In the expression: ex "abc" (Just "pqr")

example.hs:8:23:
    Couldn't match expected type `Maybe' with actual type `[]'
    In the second argument of `ex', namely `["pqr", "xyz"]'
    In the expression: ex (Just 'a') ["pqr", "xyz"]
    In an equation for `test4': test4 = ex (Just 'a') ["pqr", "xyz"]

example.hs:9:21:
    Couldn't match expected type `()' with actual type `[Char]'
    In the first argument of `return', namely `("abc")'
    In the first argument of `ex', namely `(return ("abc") :: IO ())'
    In the expression:
      ex (return ("abc") :: IO ()) [Just "pqr", Just "xyz"]
Failed, modules loaded: none.
Prelude>

Answer 1

The wiki article says that liftA2 (<*>) can be used to compose applicative functors. It's easy to see how to use it from its type:

o :: (Applicative f, Applicative f1) =>
     f (f1 (a -> b)) -> f (f1 a) -> f (f1 b)
o = liftA2 (<*>)

So to if f is Maybe and f1 is [] we get:

> Just [(+1),(+6)] `o` Just [1, 6] 
Just [2,7,7,12]

The other way around is:

>  [Just (+1),Just (+6)] `o` [Just 1, Just 6]
[Just 2,Just 7,Just 7,Just 12]

As @McCann said your ex function is equivalent to liftA2 (:):

test1 = liftA2 (:) "abc" ["pqr", "xyz"]

To use (:) with deeper applicative stack you need multiple applications of liftA2:

*Main> (liftA2 . liftA2) (:) (Just "abc") (Just ["pqr", "xyz"])
Just ["apqr","axyz","bpqr","bxyz","cpqr","cxyz"]

However it only works when both operands are equally deep. So besides double liftA2 you should use pure to fix the level:

*Main> (liftA2 . liftA2) (:) (pure "abc") (Just ["pqr", "xyz"])
Just ["apqr","axyz","bpqr","bxyz","cpqr","cxyz"]

Answer 2

Saying they can be combined in a generic way does not mean they can be combined implicitly or invisibly or anything like that. =)

You still need to write a bit of code, either by using different mungers than <*> and pure or by adding some newtype noise. For example, using the TypeCompose package, you might write

test2 = ex (O (Just "abc")) [O (Just "pqr"), O (Just "xyz")]

Answer 3

As usual, it's useful here to focus on the types to figure out what composition of applicative functors should mean.

If we write a for the type of a particular pure value x, that therefore has no side effects, then we can lift this pure value to a computation of the applicative functor f using the pure combinator. But by the same token, we can use the pure function from g's Applicative instance to lift pure x into the g functor.

pure (pure x) :: g (f a)

Now g (f a) is the type of computations that combine the effects of g and the effects of f. Looking at your tests, we notice that

test1 :: [String]

You have used only one effect in test1, that is the non-determinism that the list instance of Applicative gives you. Indeed, breaking it down:

"abc" :: String
((:) <$>) :: [Char] -> [String -> String]
((:) <$> "abc") :: [String -> String]
((:) <$> "abc" <*> ["pqr", "xyz"]) :: [String]

Now, if we want to compose the failure effect and the non-determinism effect, we would expect to construct a computation of type Maybe [a], or perhaps [Maybe a]. It turns out that the two are equivalent, because applicative functors always commute.

Here's a computation of type [Maybe Char]. It will non-deterministally return a Char, but if it does, it might fail:

x1 = [Just 'a', Just 'b', Just 'c']

Likewise, here's a computation of type [Maybe String]:

x2 = [Just "pqr", Just "xyz"]

Now we want to lift (:) to this combined applicative functor. To do so, we have to lift it it twice:

pure (pure (:)) :: [Maybe (Char -> String -> String)]

Likewise, to apply it, we need to push this computation through both functors. We can therefore introduce a new combinator (<<*>>) that does that:

(<<*>>) :: (Applicative f, Applicative f1) =>
           f (f1 (a -> b)) -> f (f1 a) -> f (f1 b)
(<<*>>) = liftA2 (<*>)

Which now allows us to write:

pure (pure (:)) <<*>> x1 <<*>> x2

which you can check has the expected type.

But since applicative functors are closed under composition, [Maybe a] is itself an applicative functor and so you may wish to be able to reuse pure and (<*>). The Data.Functor.Compose module of the transformers package shows you how to.

Answer 4

Consider the following type signatures:

liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c
(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b

Combined, the resulting type is:

liftA2 (<*>) :: (Applicative f, Applicative g) 
             => f (g (a -> b)) -> f (g a) -> f (g b)

This is indeed a combination of two Applicatives. In fact, it's a combination of exactly two Applicatives. In other words, although you can combine Applicatives in a generic way, this is not in any way way done automatically. Everything must be explicitly lifted the correct number of times.

Your ex function is equivalent to liftA2 (:), which has type (Applicative f) => f a -> f [a] -> f [a]. Going through your examples, making some guesses about what you wanted to do:

test1 = ex "abc" ["pqr", "xyz"]

Here f is [], and we're applying it to arguments of type [Char] and [[Char]].

test2 = ex "abc" [Just "pqr", Just "xyz"]

The second argument is of type [Maybe [Char]], so we need to lift twice. The first argument also needs to be lifted, since it has type [Char] and should be [Maybe Char].

test3 = ex "abc" (Just "pqr")

This time the second argument is of type Maybe [Char], so f is Maybe and we only need one lift. The first argument should therefore be of type Maybe Char.

test4 = ex (Just 'a') ["pqr", "xyz"]

This time the first argument is Maybe Char but the second is [[Char]], so you have two completely different Applicatives; both will need to be lifted, to give you either [Maybe Char] or Maybe [Char].

test5 = ex (return ("abc"):: IO ()) [Just "pqr", Just "xyz"]

The type signature here makes no sense; you probably wanted IO [Char]. The second argument has type [Maybe [Char]]. Like the previous example they don't match up, but this time you have three Applicatives. If you want something like IO [Maybe a], you'll need to lift (:) all three times, e.g. liftA2 (liftA2 ex).

This way of combining Applicatives is called "functor composition", and the page you linked to mentions libraries that define an explicit composition type constructor. For example, using the transformers library, you could have a type like Compose IO (Compose [] Maybe) to describe your fifth example. This composed type is defined as an Applicative instance in the aforementioned generic way, and applies the correct number of lifting operations. The downside is that you'll need to wrap and unwrap the newtype layers this requires.

---

As an addendum, this statement:

So where are applicative transformers? The answer is, that we do not need special transformers for applicative functors since they can be combined in a generic way.

...is a bit bogus. It's true that the composition of two Applicatives is also Applicative, but this is not the only way to combine Applicatives!

Consider StateT s m a, which is equivalent to s -> m (s, a), though it's defined slightly differently. This could also be written as the composition of three functors: ((->) s), m, and ((,) s), and the resulting Functor instance would be correct, but the Applicative instance would be completely wrong. If you start with just State s a = s -> (a, s) instead, there's no way to define StateT s m by composing State s and m.

Now, observe that the non-composition combination StateT s (Either e) is essentially a simplified version of the typical parser combinator monad used in libraries like Parsec, and such parsers are one of the well-known places where using Applicative style is popular. As such, it seems more than a bit misleading to suggest that monad transformer-style combinations are somehow unnecessary or superfluous where Applicative is concerned!