Converting Monad notation to Arrow notation

Question

I'm trying to understand arrow notation, in particularly how it works with Monads. With Monads I can define the following:

f = (*2)
g = Just 5 >>= (return . f)

and g is Just 10

How do I do the above but using arrow notation?

AndrewC AndrewC · Accepted Answer · 2014-02-16T16:40:59

Changing your Monad thinking to Arrow thinking

The first step to translating into Arrow is to move from thinking about m b on its own to thinking about a -> m b.

With a monad, you'd write

use x = do
   .....
   ....
doThis = do
   ....
   ...

thing = doThis >>= use

whereas an arrow always has an input, so you'd have to do

doThis' _ = do
   .....
   ....

and then use (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c from Control.Monad do have

thing' = doThis' >=> use

>=> removes the asymmetry of >>=, and is what we would call the Kleisli arrow of the Monad.

Using `()` for input or "What if my first thing really isn't a function though?"

That's OK, it's just the co-problem to if your monad doesn't produce anything (like putStrLn doesn't), whereupon you just get it to return ().

If your thing doesn't need any data, just make it a function that takes () as an argument.

doThis () = do .... ....

that way everthing has the signature a -> m b and you can chain them with >=>.

Arrows have input and output, but no function

Arrows have the signature

Arrow a => a b c

which is perhaps less clear than the infix

Arrow (~>) => b ~> c

but you should still be thinking of it as analagous to b -> m c.

The main difference is that with b -> m c you have your b as an argument to a function and can do what you like with it, like if b == "war" then launchMissiles else return () but with an arrow you can't (unless it's an ArrowApply - see this question for why ArrowApply gives you Monad capabilities) - in general, an arrow just does what it does and doesn't get to switch operation based on the data, a bit like an Applicative does.

Converting Monads to Arrows

The problem with b -> m c is that there you can't partially apply it in an instance declaration to get the -> m bit from the middle, so given that b -> m c is called a Kleisli arrow, Control.Monad defines (>>>) so that after all the wrapping and unwrapping, you get f >>> g = \x -> f x >>= g - but this is equivalent to (>>>) = (>=>). (In fact, (.) is defined for Categories, rather than the forwards composition >>>, but I did say equivalent!)

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

instance Monad m => Category (Kleisli m) where
    id = Kleisli return
    (Kleisli f) . (Kleisli g) = Kleisli (\b -> g b >>= f) -- composition of Kleisli arrows

instance Monad m => Arrow (Kleisli m) where
    arr f = Kleisli (return . f)
    first (Kleisli f) = Kleisli (\ ~(b,d) -> f b >>= \c -> return (c,d))
    second (Kleisli f) = Kleisli (\ ~(d,b) -> f b >>= \c -> return (d,c))

Your example, at last

(Try to ignore all the Kleisli and runKleisli - they're just wrapping and unwrapping monadic values - when you define your own arrow, they're not necessary.)

If we unwrap what that means for the Maybe, we get the equivalent of composing

f :: a -> Maybe b
g :: b -> Maybe c
f >>> g :: a -> Maybe c  
f >>> g = \a -> case f a of       -- not compilable code!
                Nothing -> Nothing
                Just b -> g b

and the Arrow way of applying a (pure) function is with arr :: Arrow (~>) => (b -> c) -> b ~> c

I'll fix (~->) to mean Kleisli Maybe so you can see it in action:

{-# LANGUAGE TypeOperators #-}
import Control.Arrow
type (~->) = Kleisli Maybe

g :: Integer ~-> Integer
g = Kleisli Just >>> arr (*2)

giving

ghci> runKleisli g 10
Just 20

Like `do` notation, but with input as well as output. (GHC)

GHC implements the equivalent of do notation, proc notation, which lets you do

output <- arrow -< input

You're used to output <- monad but now there's the arrow -< input notation. Just as with Monads, you don't do <- on the last line, you don't do that in proc notation either.

Let's use the Maybe versions of tail and read from safe to illustrate the notation (and advertise safe).

{-# LANGUAGE Arrows #-}
import Control.Arrow
import Safe

this = proc inputList -> do
    digits <- Kleisli tailMay -< inputList
    number <- Kleisli readMay -<< digits
    arr (*10) -<< number

Notice I've used the -<< variant of -<, which lets you use output as input by bringing things on the left of <- into scope at the right of -<.

Clearly this is equivalent to Kleisli tailMay >>> Kleisli readMay >>> arr (*10), but it's just (!) to give you the idea.

ghci> runKleisli this "H1234"  -- works
Just 1234
ghci> runKleisli this "HH1234"  -- readMay fails
Nothing
ghci> runKleisli this ""     -- tailMay fails
Nothing
ghci> runKleisli this "10"     -- works
Just 0

All that `()`

Like I said, we use () if we don't have input, and as we do in Monad, return it if we don't need to output anything.

You'll see () in proc notation examples too:

thing = proc x -> do
     this <- thing1 -< ()
     () <- thing2 -< x
     returnA -< this

Converting Monad notation to Arrow notation

2 Answers