2014-12-21-arrows.lhs

---
title: "24 Days of GHC Extensions: Arrows"
---
 
Today's guest post comes from [Tom Ellis](http://web.jaguarpaw.co.uk/~tom/blog/). If you haven't heard, Tom released a novel library for interacting with relational databases this year - [Opaleye](http://hackage.haskell.org/package/opaleye). While similar to HaskellDB in some respects, Opaleye is distinct in its extensive use of arrows in order to guarantee safety of queries. In this post, Tom's going to guide us through GHC's special syntax support for the `Arrow` type class.

> {-# LANGUAGE Arrows #-}
>
> import Control.Monad (guard)
> import Control.Monad.Identity (Identity, runIdentity)
> import Control.Arrow (returnA, Kleisli(Kleisli), runKleisli)

In Haskell we use the `Monad` typeclass to provide an interface for
encoding certain forms of computation.  The `Arrow` typeclass provides
an interface that is in many ways similar.  Everything that can be
made an instance of `Monad` (in a law-abiding way) can also be adapted
to be an `Arrow` (in a law-abiding way).  This means that the `Arrow`
interface is less powerful than `Monad`, but that more things can be
made instances of `Arrow`.

Working directly with `Monad` combinators like `>>=` and `>>` can
sometimes be awkward so Haskell provides "`do` notation" as an
alternative way of writing monad expressions in a way that can often
be clearer.  Likewise there is an "arrow notation" for writing arrow
expressions.  It is not enabled in GHC by default but can be turned on
with the `Arrows` language extension.

The subject of this blog post is how to understand and use arrow
notation.  It will also serve as an introduction to the `Arrow`
typeclass whilst keeping mention of the arrow combinators to a
minimum.  We will use develop our intuition for arrow computation
rather than learn any technical and formal definitions!

Let's kick off by refreshing our memory of `do` notation.  A very
basic way to think of `do` notation is that it is similar to a
sequence of let bindings.  For example, a basic Haskell expression to
perform a numerical calculation might be

> f :: Int -> (Int, Int)
> f = \x ->
>   let y  = 2 * x
>       z1 = y + 3
>       z2 = y - 5
>   in (z1, z2)
>
> -- ghci> f 10
> -- (23, 15)

`do` notation supports expressing the exact same computation inside
the `Identity` monad, that is, a monad that has no "side effects".

> fM :: Int -> Identity (Int, Int)
> fM = \x -> do
>   y  <- return (2 * x)
>   z1 <- return (y + 3)
>   z2 <- return (y - 5)
>   return (z1, z2)
>
> -- ghci> runIdentity (fM 10)
> -- (23,15)

The `let` bindings in `f` become `<-` under `do` notation. (For
technical reasons we have to wrap every intermediate expression in
`return` to lift them into the `Identity` monad.)  Arrow notation
supports a similar translation:

> fA :: Int -> (Int, Int)
> fA = proc x -> do
>   y  <- (2 *) -< x
>   z1 <- (+ 3) -< y
>   z2 <- (subtract 5) -< y
>   returnA -< (z1, z2)
>
> -- ghci> fA 10
> -- (23,15)

In arrow notation `proc` plays the part of "lambda", i.e. backslash,
`\`, `<-` plays the part of `=` and `-<` feeds an argument into a
"function".  We use `returnA` instead of `return`.

The benefit of `do` notation comes when we want to encode a
computation that can't be written using pure `let` bindings alone.
Here's an example that uses the list monad to generate all coordinates
within a given radius of the origin:

> range :: Int -> [Int]
> range r = [-r..r]
>
> cM :: Int -> [(Int, Int)]
> cM = \r -> do
>   x <- range 5
>   y <- range 5
>   guard (x*x + y*y <= r*r)
>   return (x, y)
>
> -- ghci> take 10 (cM 5)
> -- [(-5,0),(-4,-3),(-4,-2),(-4,-1),(-4,0),(-4,1),(-4,2),(-4,3),(-3,-4),(-3,-3)]

We read this as

* for each `x` in -5 to 5
* for each `y` in -5 to 5
* where `x*x + y*y <= r*r`
* return the pair of `x` and `y`

Now let's see how to use arrow notation to express the same
computation.  For trivial technical reasons we need to wrap the list
monad to make it suitable for use with arrow notation.  The wrapping
and unwrapping don't actually do anything except shuffle some type
parameters around.  In arrow computations we will use `K [] a b` where
instead of `a -> [b]`.  We'll use abbreviated versions of the relevant
wrapping and unwrapping functions:

> type K = Kleisli
>
> k :: (a -> m b) -> Kleisli m a b
> k = Kleisli
>
> runK :: Kleisli m a b -> (a -> m b)
> runK = runKleisli

Then we can use arrow notation to implement the radius list
computation as follows:

> cA :: Kleisli [] Int (Int, Int)
> cA = proc r -> do
>   x <- k range -< 5
>   y <- k range -< 5
>   k guard -< (x*x + y*y <= r*r)
>   returnA -< (x, y)
>
> -- ghci> take 10 (runK cA 5)
> -- [(-5,0),(-4,-3),(-4,-2),(-4,-1),(-4,0),(-4,1),(-4,2),(-4,3),(-3,-4),(-3,-3)]

What's the point of arrow notation?  So far we have only seen that it
is able to replicate some examples in `do` notation.  Well, the point
is that arrow notation forbids some computations that `do` notation
allows.  In particular all "arrow actions" must be "statically"
known".  That sentence was a mouthful!  What does it mean?  I am
calling the expression that comes between `<-` and `-<` in a row of
arrow notation the "arrow action".  "Statically known" means that if
we have a couple of rows of arrow notation

> --    y <- action1 -< x
> --    z <- action2 -< y

then the expression `action2` cannot depend on `x` or indeed anything
bound on the left hand side of an arrow notation row.

This restriction has important practical consequences.  For example,
our Haskell IO system might be based on the following primitives

> getLineM :: String -> IO String
> getLineM prompt = do
>   print prompt
>   getLine
>
> printM :: String -> IO ()
> printM = print
>
> writeFileM :: FilePath -> String -> IO ()
> writeFileM (filePath, string) = writeFile filePath string

then we could use `do` notation to write a procedure which reads a
line of user input and either prints something out or writes to a file
based on that input.

> procedureM :: String -> IO ()
> procedureM = \prompt -> do
>   input <- getLineM prompt
>   if input == "Hello"
>     then printM "You said 'Hello'"
>     else writeFileM ("/tmp/output", "The user said '" ++ input ++ "'")
>
> -- ghci> procedureM "Say something"
> -- "Say something"
> -- Hello
> -- "You said 'Hello'"
>
> -- ghci> procedureM "Say something"
> -- "Say something"
> -- Bye bye
> -- (Writes to /tmp/output)

However, there is no way to express this in arrow notation using only
the same primitives.

> -- procedureA :: K IO String ()
> -- procedureA = proc prompt -> do
> --  input <- k getLineM -< prompt
> --  if input == "Hello"
> --   then printM
> --   else writeFileM "/tmp/output" ...
>
> -- Oh no!  This won't work because we were trying to refer to a <-
> -- bound variable on the left hand side of a -<

Why do we want to use arrows when they have these restrictions?  Going
into details would take a whole other blog post of its own, but I will
mention briefly a few places where the full generality of monads is
too much.

Firstly, an arrow-only interface can often allow you to take advantage
of opmizations that a monadic interface could not. For example parsers
written using parser combinators can be made more memory efficient if
we know statically the parsing action they are going to perform.
Similarly it can help to reduce the chance of memory leaks in
functional reactive programming (e.g. with `netwire`) if actions
cannot depend in an unrestrained way on the result of previous
actions.

In embedded domain specific languages this forcing non-dependence can
make code generation more easily match a target language.  For example
in the SQL-generating relational query language Opaleye queries are
built up from arrows called `QueryArr`.  Using an arrow rather than a
monad allows the semantics of the domain specific language to more
closely match the semantics of the underlying SQL language.

So in summary, arrows are a Haskell abstraction, similar to monads,
and arrow notation is a way of writing arrow expressions which is
similar to to `do` notation.  However, there are some restrictions on
what you can do with arrows that are not shared by monads.  The
benefit of the restriction is you can often receive a performance
benefit or use your more specific knowledge about the structure of an
arrow computation to your advantage.

----

*This post is part of
[24 Days of GHC Extensions](/pages/2014-12-01-24-days-of-ghc-extensions.html) -
for more posts like this, check out the
[calendar](/pages/2014-12-01-24-days-of-ghc-extensions.html)*.