evan_tech

A post in three sections, each a step of evolution beyond the last. Contrast with The Evolution of a Haskell Programmer.

Here's a situation that comes up decently frequently. Say you have some monadic operation that gives you back a basic type. Actually, let me make it concrete so it's easier to follow. Say you have a parsec parser that parses an integer:

p_int :: Parser Int

Deep elsewhere in your code, you have some data type that you'd like to stuff the result of that parse into. E.g.:

data Expr = EInt Int | EString String  -- etc
p_expr :: Parser Expr

So the question is: how do you use p_int within p_expr, converting the output? Let's start with the obvious way:

p_expr = do i <- p_int       -- parse an int
            return (EInt i)  -- wrap it in EInt

But it's so verbose! You can shorten by going point-free with the monad operators:

p_expr = p_int >>= return . EInt

But it always feels like golf to me when I see that in code; you may as well just do the do-expression in one line in only seven more characters:

p_expr = do x <- p_int; return (EInt x)

---

On the other hand, it does feel redundant to give the integer a name just to throw it away. The more experienced Haskell hacker knows about Control.Monad, which provides some operators to work with monads. Notably, there's liftM (parens added for clarity):

liftM :: (Monad m) => (a -> b) -> (m a -> m b)

That "lifts" a plain function to a function that works on monad values, so our running example can become:

p_expr = liftM EInt p_int

Can we do better? From reading other code I picked up that the prelude's fmap, which is map over the Functor type class, is the same as liftM for a monad. It feels a bit golfy but not so bad: conceptually you're mapping EInt over the result of the parse (but only if it's succesful):

p_expr = fmap EInt p_Int

---

But recently I gained a newfound understanding of Control.Applicative and found something better. From their docs, Applicative is "a structure intermediate between a functor and a monad: it provides pure expressions and sequencing, but no binding."

To keep it straight, here's a table with increasing abstraction as you go downwards. (Note the types of the columns aren't exactly the same, but maybe it illustrates the point.)

Typeclass	bring value in	primary operation	helpers
Monad	return	>>=	liftM, ap
Applicative	pure	<*>	<$>
Functor		fmap

Conceptually, Applicative lets you bring values in and combine values, but doesn't let you get back at the values. It suits the parser example just fine:

p_expr = pure EInt <*> p_int

That is, pure brings the whole function into Applicative and then <*> is normal Haskell composition (normally just written with whitespace or $) within Applicative. But there's a helper operator that's just for this sort of thing:

(<$>) :: Functor f => (a -> b) -> f (a -> b)

You'll note it's the same signature as liftM, but in usage it's quite clear:

p_expr = EInt <$> p_int

The name is analagous to the $ operator but the brackets indicate within Applicative. You can read that as "apply EInt to p_int, but within Applicative". Succinct and clear.

The nice thing about Applicative (and sort of the point of it) as compared to monads is that you don't have this continual diving in and out of the monad; you just lift everything in and then combine. Contrast these two binary expressions:

add x y = x + y
normal_expression = add int_1 int_2
applicative_expr  = add <$> p_int <*> p_int

<*> (equivalently ap for monads) is there to let you to do further composition on the right, all within Applicative.

Finally, note that all of this isn't specific to this parser problem; you can use these functions just as well with other monads (like IO) and also to other places involving functors:

(+1) <$> [1, 2, 3]
-- equivalent to map (+1) [1, 2, 3]

See also Perl 6 meta-operators, which is this sort of thing done at the syntax level.