proposal #2517: remove 'pure' method from Arrow class

[David Menendez]

On Fri, Aug 15, 2008 at 9:58 AM, Isaac Dupree <isaacdupree at charter.net> wrote:
> It looks like all Arrows are Applicative; is that a useful observation?

The WrappedArrow type in Control.Applicative creates an applicative
functor from any arrow.

The paper "Idioms are oblivious, arrows are meticulous, monads are
promiscuous" by Lindley, Wadler, and Yallop has a good explanation of
the relationship between arrows and applicative functors.

<http://homepages.inf.ed.ac.uk/wadler/papers/arrows-and-idioms/arrows-and-idioms.pdf>
<http://lambda-the-ultimate.org/node/2799>


> ArrowPlus, of course, corresponds with Alternative; the full types of the
> appending operation's arguments must be identical in all cases.
> instance (Arrow arr) => Alternative (arr x) where
>  empty = zeroArrow; (<|>) = (<+>)
> and thenceforth with Monoid
> instance (Arrow arr) => Alternative (arr a b) where
>  mempty = zeroArrow; mappend = (<+>)
> . It makes me wonder what is the point of ArrowPlus, MonadPlus,
> Alternative... when we have Monoid.
>
> But are they usable in all the same situations?  It seems some places that
> use
> f :: (MonadPlus f) => ...
> would indeed need to require the polymorphic (invented syntax)
> f :: (forall a. Monoid (f a)) => ...
> not just for some particular 'a'
> f :: (Monoid (f a)) => ...
>
> Why does that make sense? Should it?  Did I get confused somehow?

MonadPlus is more restrictive than Monoid in (at least) two ways.

First, the instances of MonadPlus have kind * -> *, whereas the
instances of Monoid have kind *. With Monoid, you can easily constrain
a type constructor's parameter, e.g.:

    instance (Foo a) => Monoid (Bar a) where ...

With MonadPlus, this is not possible.

Second, instances of MonadPlus must obey additional laws governing
their relationship to the Monad operations. In addition to mplus and
mzero forming a monoid, mzero must[1] be a left zero for (>>=),

    mzero >>= f = mzero

and (>>=) must[2] left-distribute over mplus,

    mplus a b >>= f = mplus (a >>= f) (b >>= f)

The differences between Monoid, ArrowPlus, and Alternative are
similar, although I don't recall seeing laws stated for Alternative.


[1] Has anyone examined whether it's possible to violate this law
while still satisfying the monad and monoid laws?

[2] Not everyone agrees with this law. In fact, the instance for Maybe
in Control.Monad doesn't satisfy it. Generally, any monad which uses
mplus for exception handling instead of non-determinism will not
satisfy this law.

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>