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 B
s is a subset of the class of all A
s = there are more A
s than B
s = 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 thanMonad
.ArrowApply
is exactly as general asMonad
.
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. AnArrowApply
instance on its own allows you to do everything aMonad
instance on its own does. You can't do more with anArrowApply
than with aMonad
. You can do more with things that areArrows
. The claim "everything monads can do" probably refers toArrowApply
while the claim "and more" probably refers toArrow
! 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 withArrow
that you can't do directly with aMonad
, 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, becauseArrow
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
- 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. 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 becauseMonad m => a -> m b
is a function, so you can execute arbitrary pure code on the inputa
before deciding which monadic thing to run, whereasArrow m => m a b
isn't a function, and you've decided which arrow thing is going to run before you examined the inputa
.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 usingapp
fromArrowApply
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
toa
becausem
feels more like a computation anda
feels like a value. Some people like to use a type operator (infix type constructor), so you getapp :: ArrowApply (~>) => (b ~> c, b) ~> c
We think of
b ~> c
as an arrow, and we think of an arrow as a thing which takesb
s, does something and givesc
s. So this meansapp
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 usingarr :: 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 withproduceArrow 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 functionMonad m => a -> m b
(just doid :: m a -> m a
!), because, crucially, arrows aren't functions, but usingapp
, 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.
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
runsma
thenmb
thenmc
and applies the pure functionf
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 thatApplicative
is more general thanMonad
, but you could make Applicative functors have the same abilities by providing a functionrun :: Applicative f => f (f b) -> f b
that lets you run a produced computation, oruse :: Applicative f => f (a -> f b) -> f a -> f b
that allows you to promote a produced computation to a computation. If we definejoin = run
andunit = (<$>)
we get the two functions that make one theoretical basis for Monads, and if we define(>>=) = flip (use.pure)
andreturn = unit
we get the other one that's used in Haskell. There isn't anApplicativeRun
class, simply because if you can make that, you can make a monad, and the type signatures are almost identical. The only reason we haveArrowApply
instead of reusingMonad
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.< 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 functionconst x
in arrow form, hencereturn x = arr (\_ -> x)
. - The equivalent of bind
>>=
, which runs a computation then uses the output as the input to a functionf
which can then calculate the next computation to run is: Firstm >>>
run the first computationm
, thenarr (\x -> (f x, ....
with the output, apply the functionf
, then use that arrow as the input toapp
which behaves as if it were the outputted arrow acting on the supplied input()
as usual. Neat!