Can someone explain to me why the app function of ArrowApply makes them as powerful as monads?

Question

So I'll break my question into 4 parts, but first some background:

I feel relatively comfortable with Monads, but not very comfortable with Arrows. I suppose the main problem I have with them is, I don't see what they are useful for. Whether formally correct or not, I understand Monads to be a tool that allows us to introduce side effects from computation. As they generalize program fragments from pure values to values boxed with other actions. From my shotgun "read all the papers" approach to learning about arrows, I've come across two conflicting viewpoints:

A. Arrows are more powerful than Monads/ are generalizations of Monads. The haskell wiki starts off with "They can do everything monads can do, and more. They are roughly comparable to monads with a static component."

B. Arrows are a subset of Monads With ArrowApply we can define a monad

1. Is there any truth to viewpoint A?
2. What kind of functionality do arrows not have, I've read that the difference has to do with composition, so what does the >>> operator allow us to do that >>= doesn't?
3. What does app exactly do? it's type doesn't even have an (->)
4. Why would we ever want to use applicative arrows over monads?

Answer 1

Multiply-interpretable statements alert:

"A is more powerful than B" ... "C is a generalisation of D" ... "E can do everything F can do, and more" ... "G is a subset of H" ...

First we need to get a grip on what we mean by powerful etc. Suppose we had a class GripHandle for things which had a grip handle, and another class Screwdriver for screwdrivers. Which is more powerful?

• Well clearly, if you just have a griphandle, that's not as useful as if you're a screwdriver; a griphandle on its own isn't much use, so obviously since you can do more with a screwdriver than a griphandle, so screwdrivers are more powerful.
• Well clearly, more things have a grip handle than just screwdrivers - drills, knives and forks, all sort of things have griphandles, so griphandles are more powerful and flexible.
• Well clearly, if you have a screwdriver, you can not only hold it, you can turn it, and having the ability to turn rather than just hold makes screwdrivers much more powerful and flexible than griphandles.

OK, that's a silly argument, but it raises a good point about how the phrase "You can do more with a _____" is rather ambiguous.

If you stick to the interface alone, a screwdriver is more useful than a handle, but all things with griphandles are together more useful than all screwdrivers if you use more functions than just the interface.

How hierarchy works

A is more general than B
= A's interface-only capabilities are a subset of B's = you can do more with a B instance (alone)
= The class of all Bs is a subset of the class of all As = there are more As than Bs = you can do more with the A class

more general
= more possible instances
= able to be more widely used
= can do extra things behind the scenes
= fewer capabilities are specified in the interface
= can do fewer things via the interface

What's the hierarchy between arrows and monads?

• Arrow is more general than Monad.
• ArrowApply is exactly as general as Monad.

These two statements are proved in full detail in the paper Petr Pudlák linked to in his comment: Idioms are oblivious, arrows are meticulous, monads are promiscuous.

The assertions in A and B

• "Arrows can do everything monads can do, and more."
  This is marketing. It's true, but you have to jump around a bit semantically to make it true. An ArrowApply instance on its own allows you to do everything a Monad instance on its own does. You can't do more with an ArrowApply than with a Monad. You can do more with things that are Arrows. The claim "everything monads can do" probably refers to ArrowApply while the claim "and more" probably refers to Arrow! The Monad marketing board could say "With Monads, you can do everything Arrows can do, and more" because of the increased expressiveness of the interface. These statements are ambiguous and have little formal meaning because of that.
• "They are roughly comparable to monads with a static component."
  Strictly speaking, no, that's just something you can do with Arrow that you can't do directly with a Monad, not a mathematical fact about the Arrow interface. It's a way of helping you get to grips with what we might do with an Arrow, in a similar way to the analogy of a Monad being a box with a value in. Not all monads are readily interpretable as a box with a value in, but it might help you a bit in the early stages.
• "Arrows are a subset of Monads"
  This is perhaps misleading. It is true that the interface-only capabilities of Arrows are a subset of the interface-only capabilities of Monads, but it's fairer to say that the class of all Monads is a subset of the class of all Arrows, because Arrow is more general.
• "With ArrowApply we can define a monad"
  Yes. See later, and with a Monad, we can define an ArrowApply.

Your four questions

1. Is there any truth to viewpoint A?
   Some. See above. There's some truth in B too. Both are misleading in some way or other.

2. What kind of functionality do arrows not have, I've read that the difference has to do with composition, so what does the >>> operator allow us to do that >>= doesn't?
   In fact >>= allows you do to more than >>> (more interface-supplied capability). It allows you to context-switch. This is because Monad m => a -> m b is a function, so you can execute arbitrary pure code on the input a before deciding which monadic thing to run, whereas Arrow m => m a b isn't a function, and you've decided which arrow thing is going to run before you examined the input a.

   monadSwitch :: Monad m => m a -> m a -> (Bool -> m a)
   monadSwitch computation1 computation2 test 
         = if test then computation1 else computation2
   

   It's not possible to simulate this using Arrow without using app from ArrowApply

3. What does app exactly do? it's type doesn't even have an (->)
   It lets you use the output of an arrow as an arrow. Let's look at the type.

   app :: ArrowApply m => m (m b c, b) c
   

   I prefer to use m to a because m feels more like a computation and a feels like a value. Some people like to use a type operator (infix type constructor), so you get

   app :: ArrowApply (~>) => (b ~> c, b) ~> c
   

   We think of b ~> c as an arrow, and we think of an arrow as a thing which takes bs, does something and gives cs. So this means app is an arrow that takes an arrow and a value, and can produce the value that the first arrow would have produced on that input.

   It doesn't have -> in the type signature because when programming with arrows, we can turn any function into an arrow using arr :: Arrow (~>) => (b -> c) -> b ~> c, but you can't turn every arrow into a function, thus (b ~> c, b) ~> c is usable where (b ~> c, b) -> c or (b -> c, b) ~> c would not be.

   We can easily make an arrow that produces an arrow or even multiple arrows, even without ArrowApply, just by doing produceArrow :: Arrow (~>) => (b ~> c) -> (any ~> (b ~> c)) defined with produceArrow a = arr (const a). The difficulty is in making that arrow do any arrow work - how to you get an arrow that you produced to be the next arrow? You can't pop it in as the next computation using >>> like you can do with a monadic function Monad m => a -> m b (just do id :: m a -> m a!), because, crucially, arrows aren't functions, but using app, we can make the next arrow do whatever the arrow produced by the previous arrow would have done.

   Thus ArrowApply gives you the runtime-generated computation runnability that you have from Monad.

4. Why would we ever want to use applicative arrows over monads?
   Er, do you mean Arrows or Applicative Functors? Applicative Functors are great. They're more general than either Monad or Arrow (see the paper) so have less interface-specified functionality, but are more widely applicable (get it? applicable/applicative chortle chortle lol rofl category theory humor hahahaha).

   Applicative Functors have a lovely syntax that looks very like pure function application. f <$> ma <*> mb <*> mc runs ma then mb then mc and applies the pure function f to the three results. For example. (+) <$> readLn <*> readLn reads two integers from the user and adds them.

   You can use Applicative to get the generality, and you can use Monads to get the interface-functionality, so you could argue that theoretically we don't need them, but some people like the notation for arrows because it's like do notation, and you can indeed use Arrow to implement parsers that have a static component, thus apply compile-time optimisations. I believe you can do that with Applicative, but it was done with Arrow first.

   A note about Applicative being "less powerful":
   The paper points out that Applicative is more general than Monad, but you could make Applicative functors have the same abilities by providing a function run :: Applicative f => f (f b) -> f b that lets you run a produced computation, or use :: Applicative f => f (a -> f b) -> f a -> f b that allows you to promote a produced computation to a computation. If we define join = run and unit = (<$>) we get the two functions that make one theoretical basis for Monads, and if we define (>>=) = flip (use.pure) and return = unit we get the other one that's used in Haskell. There isn't an ApplicativeRun class, simply because if you can make that, you can make a monad, and the type signatures are almost identical. The only reason we have ArrowApply instead of reusing Monad is that the types aren't identical; ~> is abstracted (generalised) into the interface in ArrowApply but function application -> is used directly in Monad. This distinction is what makes programming with Arrows feel different in many ways to programming in monads, despite the equivalence of ArrowApply and Monad.

5. < cough > Why would we ever want to use Arrows/ArrowApply over Monad?
   OK, I admit I knew that's what you meant, but wanted to talk about Applicative functors and got so carried away I forgot to answer!

   Capability reasons: Yes, you would want to use Arrow over Monad if you had something that can't be made into a monad. The motivating example that brought us Arrows in the first place was parsers - you can use Arrow to write a parser library that does static analysis in the combinators, thus making more efficient parsers. The previous Monadic parsers can't do this because they represent a parser as a function, which can do arbitrary things to the input without recording them statically, so you can't analyse them at compile time/combine time.

   Syntactic reasons: No, I personally wouldn't want to use Arrow based parsers, because I dislike the arrow proc/do notation - I find it even worse than the monadic notation. My preferred notation for parsers is Applicative, and you might be able to write an Applicative parser library that does the efficient static analysis that the Arrow one does, although I freely admit that the parser libraries I commonly use don't, possibly because they want to supply a Monadic interface.

   • Monad:

         parseTerm = do
              x <- parseSubterm
              o <- parseOperator
              y <- parseSubterm
              return $ Term x o y
     

   • Arrow:

         parseTerm = proc _ -> do
              x <- parseSubterm -< ()
              o <- parseOperator -< ()
              y <- parseSubterm -< ()
              returnA -< Term x o y
     

   • Applicative:

         parseTerm = Term <$> parseSubterm <*> parseOperator <*> parseSubterm
     

     That just looks like function application using $ a few times. Mmmmm. Neat. Clear. Low syntax. Reminds me why I prefer Haskell to any imperative programming language.

Why does app in ArrowApply make a Monad?

There's a Monad instance in the ArrowApply section of the Control.Arrow module, and I'll edit in (~>) instead of a for my clarity of thought. (I've left Functor in because it's silly to define Monad without Functor anyway - you should define fmap f xs = xs >>= return . f.):

newtype ArrowMonad (~>) b = ArrowMonad (() ~> b)

instance Arrow (~>) => Functor (ArrowMonad (~>)) where
    fmap f (ArrowMonad m) = ArrowMonad $ m >>> arr f

instance ArrowApply (~>) => Monad (ArrowMonad (~>)) where
    return x = ArrowMonad (arr (\_ -> x))
    ArrowMonad m >>= f = ArrowMonad $
        m >>> arr (\x -> let ArrowMonad h = f x in (h, ())) >>> app

What does that do? Well, first, ArrowMonad is a newtype instead of a type synonym just so we can make the instance without all sorts of nasty type system problems, but lets ignore that to go for conceptual clarity over compilability by substituting in as if it were type ArrowMonad (~>) b = () ~> b

instance Arrow (~>) => Functor (() ~>) where
    fmap f m = m >>> arr f

(using an uncompilable type operator section (()~>) as a type constructor)

instance ArrowApply (~>) => Monad (() ~>) where
 -- return :: b -> (() ~> b)
    return x = arr (\_ -> x)
 -- (>>=) ::   ()~>a   ->    (a  ->  ()~>b )   ->   ()~>b 
    m >>= f = 
        m >>> arr (\x ->  (f x, ()) ) >>> app

OK, that's a bit clearer what's going on. Notice first that the correspondence between arrows and monads is between Monad m => b -> m c and Arrow (~>) => b ~> c, but the monad class doesn't involve the b in the declaration. That's why we need to supply the dummy value () in () ~> b to get things started on zero input and replicate something of type m b.

• The equivalent of fmap where you apply a function to your ouput, is just produce the output, then run the function in arrow form: fmap f m = m >>> arr f
• The equivalent of return (which just produces the specified value x) is just to run the function const x in arrow form, hence return x = arr (\_ -> x).
• The equivalent of bind >>=, which runs a computation then uses the output as the input to a function f which can then calculate the next computation to run is: First m >>> run the first computation m, then arr (\x -> (f x, .... with the output, apply the function f , then use that arrow as the input to app which behaves as if it were the outputted arrow acting on the supplied input () as usual. Neat!

Answer 2

Viewpoint A is a bit odd--generally speaking, an abstraction is not going to be both more powerful and more general than some other abstraction; the two are at odds. Having "more power" means knowing more about the structure of what you're working with, which means more restrictions. At one extreme, you know exactly which type you're working with. This is extremely powerful; you can apply any valid function to it. On the other hand, it is also not general in the least: code written with this assumption only applies to that type! At the other extreme, you can know nothing about your type (e.g. having a type variable a). This is very general, applying to every type, but also not powerful at all, since you don't have enough information to do anything at all!

An example more rooted in real code is the difference between Functor and Applicative. Here, Functor is more general--strictly more types are Functors than Applicatives, since every Applicative is also a Functor but no vice versa. However, since Applicative carries more structure, it's strictly more powerful. With Functor, you can only map single-argument functions over your type; with Applicative, you can map functions of any number of arguments. Again: one is more general, the other more powerful.

So which is it? Are arrows more powerful or more general than monads? This is a harder question than comparing functors, applicative functors and monads because arrows are a very different beast. They even have a different kind: monads et al have kind * -> * where arrows have kind * -> * -> *. Happily, it turns out that we can identify arrows with applicative functors/monads, so we can actually answer this question meaningfully: arrows are more general than monads and, consequently, less powerful. Given any monad, we can construct an arrow out of it, but we can't construct a monad for every arrow.

The basic idea is as follows:

instance Monad m => Category (a -> m b) where
  id = return
  (f . g) x = g x >>= f

instance Monad m => Arrow (a -> m b) where
  arr f = return . f
  first f (x, y) = f x >>= \ x' -> return (x', y)

However, since we have an arrow instance for a -> b, we have to wrap a -> m b into a newtype in real code. This newtype is called Klesli (because of Klesli categories).

However, we can't go the other way--there is no construction to get a Monad out of any Arrow. This happens because an Arrow computation can't change its structure based on the values flowing through it while monads can. The only way around this is to add power to your arrow abstraction with some additional primitive function; this is exactly what ArrowApply does.

The >>> operator for arrows is a generalization of . for functions, and so has the same general restrictions. >>=, on the other hand, is more like a generalization of function application. Note the types: for >>>, both sides are arrows; for >>=, the first argument is a value (m a) and the second a function. Moreover, the result of >>> is another arrow where the result of >>= is a value. Since arrows only have >>> but no notion equivalent to >>=, you can't "apply" them to arguments in general--you can only construct arrow pipelines. The actual apply/run function would have to be specific to any given arrow. Monads, on the other hand, are defined in terms of >>= and so come with some notion of application by default.

ArrowApply just extends arrows with app, which is a general notion of application. Let's imagine normal function application:

apply :: (b -> c) -> b -> c
apply f x = f x

we can uncurry this to get:

apply :: ((b -> c), b) -> c

The way arrows generalize functions is basically by replacing -> with a variable (a). Let's do this for apply by replacing both occurrences of -> with an infix a:

apply :: (b `a` c, b) `a` c

We can still see the same structure as the first version of apply, just uncurried and with `a` instead of ->. Now if we just get rid of the backticks and make a prefix, we get the signature for app:

app :: a (a b c, b) c

So we see how ArrowApply just adds some notion of application to arrows. This is a prallel to >>=, which is a notion of application for monads (or, in particular, functions of the shape a -> m b). This is enough additional structure to build a monad from an arrow, so ArrowApply is isomorphic to Monad.

Why would we ever want to use these? Honestly, I don't think we would. Arrows are pretty overrated, so stick to monads and applicative functors.

Answer 3

Monad is an instrument, which allows us write in imperative style (step by step).

Arrow is an instrument, which allows us write in block diagram style.

So, monad for arrows looks like linear block diagram.

http://www.soi.city.ac.uk/~ross/talks/fop.pdf

http://www.haskell.org/arrows/syntax.html