Applicative Programming

I want to explore the Applicative functor, more than a functor and less than a monad. The reason to use it is that, by being less powerful, it can be applied in more situations.

This post is a companion to the talk I gave at HaskellMAD, you can find the slides of the talk here.

Applicatives or Idioms, as they were named back then, were introduced in 2008, in a Functional Pearl named Idioms: applicative programming with effects.

As the begin of this writeup, let’s first introduce the typeclass:

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

Simple enough, this typeclass allows you to put elements inside an Applicative context –with pure–, and smash Applicative values together through <*>.

We can understand <*> as fmap from Functor, but with the function lifted to an Applicative context.

But while you’re scratching your head trying to imagine a moment in your development career in which you have a function inside a container, let me show you an example:

Prelude> let square = \ x -> x * x
Prelude> let plusTwo = \ x -> x + 2
Prelude> let functions = [square, plusTwo]
Prelude> let numbers = [1,2,3]
Prelude> functions <*> numbers
[1,4,9,3,4,5]

As you can see, the <*> implementation for Applicative [a], is the application of each function in the first list to each element in the second list.

But, you don’t need to tell me that functions inside a list is not the most common thing in the world. Let’s explore a more useful way of using Applicative.

Validation

Validation is a well known problem. You have some data that you need to validate before it makes part of your domain, easy. For our validation example we will use the Either a b type. Either is a sum type, meaning that the number of possible values of Either a b is the sum of possible values of type a, and possible values of type b.

Basically, the as in our validations will be validation errors –represented as strings– and the bs, the final values.

data Person = Person {
  name :: String,
  lastName :: String
} deriving Show

data Err = String

validateName :: String -> Either Err String
validateName n = if n == "Pepe" then Right n
                                else Left "name is not Pepe"

validateLastName :: String -> Either Err String
validateLastName l = if l == "García" then Right l
                                      else Left "last name is not García"

Our validateName function takes a string as paramenter, and validates it as a name, and the same does validateLastName.

Now, let’b build up a validatePerson function from the validation of each one of its parts:

validatePersonM :: String -> String -> Either String Person
validatePersonM n l = do
    vName <- validateName n
    vLast <- validateLastName l
    return $ Person vName vLast

Since Either a is a monad, we can use all the monadic tricks in our hat to compose it, for example this do block. But, the cool part of Either, is that it is an Applicative, so we can use all the Applicative machinery to compose our program.

validatePersonA :: String -> String -> Either String Person
validatePersonA n l = Person <$> validateName n <*> validateLastName l

How can the last function possibly work? Well, in case you missed it, <$> is the infix version of fmap. and the typing of the body of the function is the following:

Prelude> :t Person
Person :: String -> String -> Person
Prelude> :t Person <$> validateName "pepe"
Person <$> validateName "pepe" :: Either String (String -> Person)
Prelude> :t Person <$> validateName "pepe" <*> validateLastName "Garcia"
Person <$> validateName "pepe" <*> validateLastName "Garcia" :: Either String Person

Create your own Applicatives

You cand do this directly by providing an instance of the typeclass, like follows:

data Maybe a = Just a
             | Nothing


instance Applicative Maybe where
    pure = Just

    Just f  <*> m = fmap f m
    Nothing <*> _ = Nothing

This will enable ourselves to use our new Maybe data type as an Applicative. But there is another case I want to cover here. What can we do when what we want is to provide an Applicative instance for an ADT we have? We can use Free Applicatives.

Free Applicatives

Free Applicatives are an abstraction over Applicatives, and are basically a lift from Applicative’s typeclass operations to constructors of an Algebraic Data Type.

You can find more information about free applicatives here. Basically, the definition of Free Applicative is:

data Ap f a where
    Pure :: a -> Ap f a
    Ap   :: f a -> Ap f (a -> b) -> Ap f b

instance Functor (Ap f) where
  fmap f (Pure a)   = Pure (f a)
  fmap f (Ap x y)   = Ap x ((f .) <$> y)

instance Apply (Ap f) where
  Pure f <.> y = fmap f y
  Ap x y <.> z = Ap x (flip <$> y <.> z)

instance Applicative (Ap f) where
  pure = Pure
  Pure f <*> y = fmap f y
  Ap x y <*> z = Ap x (flip <$> y <*> z)

Now, we can provide an instance of Applicatve for every data type with kind * -> * we have!

Let’s create a small ADT for all the operations in our blog. It could be something like follows:

{-# LANGUAGE GADTs #-}

import Control.Applicative.Free
import Control.Applicative

data Author = Author {
    name :: String,
    lastName :: String
} deriving Show

data Post = Post {
    id :: Int,
    title :: String,
    content :: String,
    excerpt :: String
} deriving Show

data BlogF a where
    GetPost :: Id -> BlogF Post
    GetAuthor :: Id -> BlogF Author


type Blog a = Ap BlogF a

The most important part of this block is where we define our language, the BlogF GADT, and where we lift it using a Free Applicative.

Also, we will need to add some operations to make our blog usable. Let’s create smart constructors for GetPost, and GetAuthor operations, but lifted to the Blog type.

getPost :: Id -> Blog Post
getPost id = liftAp $ GetPost id

getAuthor :: Id -> Blog Author
getAuthor id = liftAp $ GetAuthor id

As you can imagine, liftAp is part of the Control.Applicative.Free library, and it takes a value of the type f a, and lifts it to the type Ap f a.

Now let’s build a program for rendering a page of our blog!

data Page = Page {
    post :: Post,
    author :: Author
} deriving Show

getPage :: Id -> Id -> Blog Page
getPage postId authorId = Page <$> getPost postId
                                  <*> getAuthor authorId

Boom! Since there were no depencencies between our getPost, and getAuthor operations, we can compose them idiomatically¹.

But, there is a part of our problem of rendering a page that we are lacking, it is drawing the rest of the f*cking owl. Right now, we are not going to the database to fetch our post and our author, we are just creating values of all the operations in our program. We are building an Abstract Syntax Tree.

What we need right now is to interpret the AST to an actual value of Page, and that’s done via Natural Transformations. Natural Transformations are a way of transforming one Functor into another while mantaining the internal structure. So, what we want to create is a function like this:

naturalTransformation :: BlogF a -> IO a

Why do we want to interpret to IO? Because IO is where side effects occur in Haskell. Fetching elements from our database will return IO a actions. Now let’s do the actual implementation of the interpret function:

interpret :: BlogF a -> IO a
interpret (GetPost id)   = putStrLn ("getting post " ++ show id ++ " from DB")   *> pure $ Post id "this is the post" "content of the post" "excerpt"
interpret (GetAuthor id) = putStrLn ("getting author " ++ show id ++ " from DB") *> pure $ Author "Pepe" "García"

And finally, let’s wire everything together:

main :: IO ()
main = do
    page <- runAp interpret $ getPage 1 1
    print page

-- Output:
-- getting post 1 from DB
-- getting author 1 from DB
-- Page {post = Post {id = 1, title = "this is the post", content = "content of the post", excerpt = "excerpt"}, author = Author {name = "Pepe", lastName = "Garc\237a"}}

And this, simply, is our fully functioning blog!²

As you can imagine, runAp is part of the free library, and it takes first a Natural Transformation on any two functors, and then an Ap f a, and interprets the AST.

The newly introduced AST is just an Abstract Syntax Trees, and we mention it because that’s what we are producing with the calls to getPost and getAuthor. This means that what we were doing when calling getPost, getAuthor, or getPage we are just creating small programs, no executing code. The part of the code execution is done by our interpreter.

Static Analysis

One of the coolest things that we can do with Applicative Abstract Syntax Trees is static analysis³. And this is because applicative programs, unlike monadic programs, are not dependent on runtime values. In other words, we can know more about our program, without evaluating it.

So now, imagine that you want to limit the number of requests to the DB that your Blog programs have to 10. If you know that any expression GetAuthor or GetPost is gonna be interpreted to a SQL sentence, you can just count the number of these, and you’re done. How can we achieve this?

instance Monoid Int where
    mempty = 0
    mappend = (+)

countInstructions :: BlogF a -> Int
countInstructions _ = 1

main :: IO ()
main = do
    putStrLn "NUMBER OF REQUESTS TO THE DB:"
    print instructions
    where instructions = runAp_ countInstructions page
          page = getPage 1 1

-- Output:
--
-- NUMBER OF REQUESTS TO THE DB:
-- 2

runAp_ is a modified version of runAp, and as an interpreter it takes a function like:

fn :: Monoid b => f a -> b

And mappends all the elements produced by it together

Conclusions

We need to identify when to use Applicatives. It’s a bit tricky in the beginning because we are not so used to it but as a few rules of thumb, I use the following:

Use Applicatives if your monadic expressions do not depends ones on the others, or program does not depend on runtime values. This last sentence means that you don’t need to evaluate functions with given arguments to keep evaluating your AST.