Switching from monads to applicative functors

- January 26, 2014
Kwang's Haskell Blog - Switching from monads to applicative functors

Switching from monads to applicative functors

Posted on January 26, 2014 by Kwang Yul Seo

Many applications of monads actually do not require monads but only applicative functors. Monads allow us to run actions depending on the results of earlier actions, but not all applications of monads need this extended functionality.

It is better to use applicative functors where possible because there are some advantages of applicative functors. Applicative functor on the Haskell Wiki mentions two:

  • Code that uses only on the Applicative interface are more general than ones uses the Monad interface, because there are more applicative functors than monads. The ZipList is an applicative functor on lists, where liftA2 is implemented by zipWith. It is a typical example of an applicative functor that is not a monad.

  • Programming with Applicative has a more applicative/functional feel. Especially for newbies, it may encourage functional style even when programming with effects. Monad programming with do notation encourages a more sequential & imperative style.

There is another advantage. Applicative functors do not need special transformers because they can be combined in a generic way.

But there is a problem. It is usually not easy to decide if we need monads or applicative functors up front. You ambitiously start with applicative functors and find later that you actually needed monads. Sad!

Here is my tip. I start with monads but use only return, ap, liftM, liftM2, … instead of do, >>=. The most common pattern is

do x <- fx
   y <- fy
   return (g x y)

This can be rewritten as liftM2 g fx fy. Once you are sure that you need only those monad methods, you can mechanically switch from monads to applicative functors using the following translation table:

  • import Control.Monad -> import Control.Applicative
  • return -> pure
  • ap -> -> (<*>)
  • liftM -> liftA or (<$>)
  • liftM2 -> liftA2
  • (Monad m =>) -> (Applicative f =>)
Read more

Applicative parsing

- January 16, 2014
Kwang's Haskell Blog - Applicative parsing

Applicative parsing

Posted on January 16, 2014 by Kwang Yul Seo

While implementing a parser for a toy imperative language, I used a parser combinator library Parsec, which supports both applicative parsing and monadic parsing. I first wrote the parser in monadic style and then changed it to applicative style because it gave me a more succinct parser.

This article explains the difference between these two styles and discusses the benefits of applicative parsing over monadic parsing.

Here a simple C like program fragment:

int max(int a, b)
    if (a > b)
        return a;
        return b;

The following is a snippet of the AST.

data Def = DFun Type Id [Arg] [Stm]

data Stm =
    | SIfElse Exp Stm Stm

The parser for function definitions is compact. DFun is a pure function which takes 4 arguments. For each argument, we need to perform an effectful computation, which is parsing. So I used ($) to lift a pure value to the effectful world and applied effectful arguments using (*).

def :: Parser Def
def = DFun <$> typ <*> ident <*> parens (commaSep arg) <*> braces (many stm)

The same parser can be written in monadic style as in the following. You can see that we need to create more bindings to name intermediate results.

def :: Parser Def
def = do
    t <- typ
    id <- ident
    args <- parens (commaSep arg)
    stms <- braces (many stm)
    return $ Dfun t id args stms

Let’s look at another example. ifElseStm is a parser which parses an if-else statement into a STM instance with SIfElse data constructor. Here (*>) is used to sequencing actions, discarding the result of the first operand because we don’t need to store “if” and “else” keywords in the AST.

ifElseStm :: Parser Stm
ifElseStm =  SIfElse <$> (reserved "if" *> parens exp) <*> stm <*> (reserved "else" *> stm)

The same parser also can be written in monadic style.

ifElseStm :: Parser Stm
ifElseStm =  do
    reserved "if"
    condExp <- exp
    thenStm <- stm
    reserved "else"
    elseStm <- stm
    return $ SIfElse condExp thenStm elseStm

In monadic parsing, (>>) is used to discard the result of an effectful computation. This parser also creates a lot of bindings to name intermediate results.

From these two examples, we can see the stylistic difference between applicative parsing and monadic parsing. Applicative parsing is more succinct in this particular example. This is not always true, so I usually try both options to find the better one.

However, the difference is not just on the style. The real difference is in how sequential composition is handled. Monad is more powerful than applicative functor, but that’s the exact reason why we can reason about monad less than applicative functor. This difference in turn gives applicative parsing better performance optimization chances. What are the benefits of applicative parsing over monadic parsing? explains this point well.

For more in-depth understanding of applicative programming, refer to FUNCTIONAL PEARL: Applicative programming with effects.

Read more