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?

Answer 1

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

Answer 2

First we need an arrow with the same semantics as the Maybe monad. We could define it from scratch, but the easiest way is to wrap the Maybe monad into Kleisli:

type MaybeArrow = Kleisli Maybe

Then we'll also need a way how to run this monad to extract the result:

runMaybeArrow :: MaybeArrow () a -> Maybe a
runMaybeArrow = flip runKleisli ()

Also it'll be handy to have a way how to create a constant arrow from a given value (which just ignores its input):

val :: (Arrow a) => c -> a b c
val = arr . const

And finally, we get:

g' = runMaybeArrow (val 5 >>> arr f)