Personal tools

Functor-Applicative-Monad Proposal

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Add more things!)
m (MonadZero does not exist. You were thinking of MonadPlus)
(10 intermediate revisions by one user not shown)
Line 1: Line 1:
The standard class hierarchy is a consequence of Haskell's historical development, rather than logic.
+
Haskell calls a couple of historical accidents its own. While some of them, such as the "number classes" hierarchy, can be justified by pragmatism or lack of a strictly better suggestion, there is one thing that stands out as, well, not that: Applicative not being a superclass of Monad.
   
This article attempts to document various suggestions that have been brought up over the years, along with arguments for and against.
+
The topic has been discussed multiple times in the past (cf. link section at the very end). '''This article was updated to describe the current, and very likely to succeed, Haskell 2014 Applicative => Monad proposal (AMP)'''.
   
== Make <hask>Applicative</hask> a superclass of <hask>Monad</hask> ==
+
Some relevant links:
  +
* [https://github.com/quchen/articles/blob/master/applicative_monad.md Initial text of the Haskell 2014 AMP]
  +
* [http://article.gmane.org/gmane.comp.lang.haskell.libraries/19482 AMP mailing list discussion]
  +
* Phase one: ticket [http://hackage.haskell.org/trac/ghc/ticket/8004 #8004]
   
<haskell>
 
class Applicative m => Monad m where
 
...
 
</haskell>
 
   
=== For ===
 
   
* Code that is polymorphic over the Monad can use Applicative operators rather than the ugly <hask>liftM</hask> and <hask>ap</hask>.
+
== Proposal contents ==
   
* Most types that implement Monad also implement Applicative already. This change will only make explicit a current best practice.
+
The list of changes is as follows:
   
=== Against ===
+
# Applicative becomes a superclass of Monad, and is added to the Prelude.
  +
# Alternative becomes a superclass of MonadPlus (in addition to Monad, of course).
  +
# <hask>join</hask> is promoted into the Monad typeclass.
   
* Monad is part of standard Haskell, but Applicative is not. If Monad is made a subclass of Applicative, then we will need to add Applicative to the language standard.
+
The general rationale behind these changes:
   
* Some libraries, such as [http://hackage.haskell.org/packages/archive/blaze-markup/0.5.1.5/doc/html/Text-Blaze-Internal.html#t:MarkupM blaze-markup], only implement Monad for its do-notation. For these types, an Applicative instance would have no meaning.
+
# ''Break as little code as possible.'' For example, do not move <hask>return</hask> to Applicative and remove <hask>pure</hask>. Instead, leave <hask>return</hask> in Monad, and give it <hask>pure</hask> as default implementation.
  +
# ''Change only things that are closely related to the proposal.'' For example, using <hask>join</hask> in a monad definition requires it to be a functor, so it goes hand in hand with the AMP. On the other hand, removing <hask>fail</hask> has nothing to do with what we're trying to accomplish.
   
== Add <hask>join</hask> as a method of <hask>Monad</hask> ==
 
   
  +
  +
== How do programmers need to change their code? ==
  +
  +
The following is a list of things you may have to change in your code so the AMP doesn't break it.
  +
  +
* Add Applicative/Functor instances for all your Monads. If you don't care about efficiency, you can simply derive these instances from the Monad by adding the following code:
 
<haskell>
 
<haskell>
class Applicative m => Monad m where
+
-- Monad m
(>>=) :: (a -> m b) -> m a -> m b
+
join :: m (m a) -> m a
+
import Control.Monad (liftM, ap)
...
+
import Control.Applicative (Applicative(..))
m >>= k = join (fmap k m)
+
join m = m >>= id
+
instance Functor m where
  +
fmap = liftM
  +
  +
instance Applicative m where
  +
pure = return
  +
(<*>) = ap
 
</haskell>
 
</haskell>
   
=== For ===
+
* Add an Alternative instance for all instances of MonadPlus. This can again be done easily using
  +
<haskell>
  +
-- MonadPlus m
   
* <hask>fmap</hask>/<hask>join</hask> is more orthogonal, and is closer to the categorical definition.
+
import Control.Monad (mzero, mplus)
  +
import Control.Applicative (Alternative(..))
   
* <hask>join</hask> is often easier to implement. See [http://article.gmane.org/gmane.comp.lang.haskell.libraries/14926].
+
instance Alternative m where
  +
(<|>) = mplus
  +
empty = mzero
  +
</haskell>
   
* The analogous [http://hackage.haskell.org/packages/archive/comonad/3.0.2/doc/html/Control-Comonad.html comonad] package is written this way.
+
* Change your API to not define functions named <hask><*></hask>, <hask>join</hask> or <hask>pure</hask>.
   
=== Against ===
+
Future versions of GHC will issue warnings if code doesn't comply to these rules; there will be a long enough transitional phase so Hackage can adapt to the AMP in advance before the above mentioned changes are actually enforced.
   
* <hask>>>=</hask> is used much more frequently in real-world code than <hask>join</hask>.
+
== Discussion and consequences ==
   
* Performance: The default implementation of <hask>>>=</hask> requires two traversals. A container-like type which only implements <hask>join</hask> would most likely be slower.
 
   
== Remove <hask>liftM</hask>, <hask>ap</hask>, etc. in favor of their Applicative counterparts ==
+
=== It's the right thing to do™ ===
   
=== For ===
+
Math. You've all heard this one, it's good and compelling so I don't need to spell it out.
   
* We will end up with a simpler base library.
 
   
=== Against ===
+
=== Redundant functions ===
   
* A lot of code will be broken by this change. Of course, we can gradually deprecate them as with <hask>Prelude.catch</hask>.
+
* <hask>pure</hask> and <hask>return</hask> do the same thing.
  +
* <hask>>></hask> and <hask>*></hask> are identical.
  +
* <hask>liftM</hask> and <hask>liftA</hask> are <hask>fmap</hask>. The <hask>liftM*</hask> are <hask>liftA*</hask>, <hask><*></hask> is <hask>ap</hask>.
  +
* Prelude's <hask>sequence</hask> requres <hask>Monad</hask> right now, while <hask>Applicative</hask> is sufficient to implement it. The more general version of this issue is captured by <hask>Data.Traversable</hask>, whose main typeclass implements the *same* functionality twice, namely <hask>traverse</hask> and <hask>mapM</hask>, and <hask>sequenceA</hask> and <hask>sequence</hask>.
  +
* The <hask>WrappedMonad</hask> type from <hask>Control.Applicative</hask> provides a semi-automatic way to using Functor/Applicative/Alternative functions for Monad/MonadPlus instances as a makeshift patch.
   
* A common pattern is to write a full instance of Monad, then set <hask>fmap = liftM</hask> and <hask>(<*>) = ap</hask>. The functions are still useful for this purpose.
+
That very much violates the "don't repeat yourself" principle, and even more so it ''forces'' the programmer to repeat himself to achieve maximal generality. It may be too late to take all redundancies out, but at least we can prevent new ones from being created.
   
== Split <hask>fail</hask> into its own class ==
+
(Note that it is not proposed to remove any functions for compatibility reasons. Maybe some of them can be phased out in the long run, but that's beyond scope here.)
   
<haskell>
 
class Monad m => MonadFail m where
 
fail :: String -> m a
 
</haskell>
 
   
== Rename <hask>fmap</hask> to <hask>map</hask> ==
+
=== Using Functor/Applicative functions in monadic code ===
   
<haskell>
+
Whenever there's Monad code, you can use Functor/Applicative functions, without introducing an additional constraint. Keep in mind that "Functor/Applicative functions" does not only include what their typeclasses define but many more, for example <hask>void</hask>, <hask>(<$>)</hask>, <hask>(<**>)</hask>.
class Functor f where
 
map :: (a -> b) -> f a -> f b
 
</haskell>
 
   
== Export <hask>Applicative</hask> in the Prelude ==
+
Even if you think you have monadic code, strictly using the least restrictive functions may result in something that requires only Applicative. This is similar to writing a function that needs <hask>Int</hask>, but it turns out any <hask>Integral</hask> will do - more polymorphism for free.
   
== Redefine <hask>>></hask> in terms of <hask>*></hask> rather than <hask>>>=</hask> ==
 
   
== Add a <hask>Pointed</hask> class ==
+
=== Compatibility issues ===
  +
  +
These are the kinds of issues to be expected:
  +
  +
# Monads lacking Functor or Applicative instances. This is easily fixable by either setting <hask>fmap = liftM</hask>, <hask>pure = return</hask> and <hask>(<*>) = ap</hask>, although more efficient implementations may exist, or by moving an already existing definition from <hask>Control.Applicative</hask> to the appropriate module.
  +
# This one is specific to building GHC: importing <hask>Control.Monad/Applicative</hask> introduces a circular module dependency. In this case, one can rely on handwritten implementations of the desired function, e.g. <hask>ap f x = f >>= ...</hask>.
  +
# Libraries using their own <hask>(<*>)</hask>. This one is potentially the most laborious consequence. For building GHC though, this only concerns Hoopl, and a handful of renames.
  +
  +
  +
  +
=== Beginner friendliness ===
  +
  +
How often did you say ...
  +
  +
* "A Monad is always an Applicative but due to historical reasons it's not but you can easily verify it by setting <hask>pure = return</hask> and <hask>(<*>) = ap</hask>"
  +
* "<hask>liftM</hask> is <hask>fmap</hask> but not really." - "So when should I use <hask>fmap</hask> and when <hask>liftM</hask>?" - *sigh*
  +
  +
With the new hierarchy, the answer would *always* be "use the least restrictive one".
  +
  +
  +
  +
== Applying the AMP to GHC and then Haskell in practice ==
  +
  +
Proposed is a gradual introduction of the AMP in three phases:
  +
  +
  +
=== '''Current stage''': Prepare GHC ===
  +
  +
Using a GHC fork with the full patch applied, find and fix all compilation errors introduced by the change by adding Functor/Applicative instances for all Monads.
  +
  +
According to SPJ, adding an ad-hoc warning of sorts "Monad without Applicative detected" is not a problem, which will be crucial for the next phase. More specifically, issue a warning if:
  +
  +
* Monad without Applicative
  +
* MonadPlus without Alternative
  +
* One of <hask><*></hask>, <hask>pure</hask>, <hask>join</hask> is defined in a different context to avoid naming conflicts, as these functions will go into the Prelude
  +
  +
=== Prepare Hackage ===
  +
  +
The warning just mentioned will hint to all authors that they should fix (or help others fix) the non-complying packages. This will ideally lead to libraries eventually adding Applicative instances, and changing their APIs if they redefine operators like <hask><*></hask>.
  +
  +
After enough time has passed by so libraries adapted to the circumstances, move on to the next phase.
   
<haskell>
 
class Pointed p where
 
point :: a -> p a
 
</haskell>
 
   
This is already implemented in the [http://hackage.haskell.org/package/pointed pointed] package.
+
=== Apply the proposal ===
   
=== For ===
+
Once Hackage is prepared, applying the changes to the Base package is painless. However, this is not primarily a GHC, but a Haskell change. The previous steps were basically preparing the landscape, and when we've (hopefully) found out that it is a good idea to go through with it, it can be proposed to go into the Report. If we make it this far, the AMP should pass quite easily.
   
=== Against ===
 
   
* This class has seen little real-world use. On Hackage, there are only [http://packdeps.haskellers.com/reverse/pointed 9 reverse dependencies] for <code>pointed</code>, most of which are by the same author.
 
   
== Related proposals ==
+
== Previous proposals ==
   
* From early 2011: [http://hackage.haskell.org/trac/ghc/ticket/4834 GHC ticket] &ndash; Makes Applicative into a superclass of Monad, but does not deprecate any existing names
+
* Early 2011: [http://hackage.haskell.org/trac/ghc/ticket/4834 GHC ticket] &ndash; changes similar to this proposal, but closed as "not GHC, but Haskell". See [http://thread.gmane.org/gmane.comp.lang.haskell.libraries/14883/focus=14905 here] for the associated discussion.
** See [http://thread.gmane.org/gmane.comp.lang.haskell.libraries/14883/focus=14905] for the associated discussion.
 
 
* [[The Other Prelude]]
 
* [[The Other Prelude]]
   
[[Context alias]] would also be a great help with backwards compatibility. The [[class system extension proposal]] may also help.
 
   
 
[[Category:Proposals]]
 
[[Category:Proposals]]

Revision as of 14:39, 22 June 2013

Haskell calls a couple of historical accidents its own. While some of them, such as the "number classes" hierarchy, can be justified by pragmatism or lack of a strictly better suggestion, there is one thing that stands out as, well, not that: Applicative not being a superclass of Monad.

The topic has been discussed multiple times in the past (cf. link section at the very end). This article was updated to describe the current, and very likely to succeed, Haskell 2014 Applicative => Monad proposal (AMP).

Some relevant links:


Contents

1 Proposal contents

The list of changes is as follows:

  1. Applicative becomes a superclass of Monad, and is added to the Prelude.
  2. Alternative becomes a superclass of MonadPlus (in addition to Monad, of course).
  3. join
    is promoted into the Monad typeclass.

The general rationale behind these changes:

  1. Break as little code as possible. For example, do not move
    return
    to Applicative and remove
    pure
    . Instead, leave
    return
    in Monad, and give it
    pure
    as default implementation.
  2. Change only things that are closely related to the proposal. For example, using
    join
    in a monad definition requires it to be a functor, so it goes hand in hand with the AMP. On the other hand, removing
    fail
    has nothing to do with what we're trying to accomplish.


2 How do programmers need to change their code?

The following is a list of things you may have to change in your code so the AMP doesn't break it.

  • Add Applicative/Functor instances for all your Monads. If you don't care about efficiency, you can simply derive these instances from the Monad by adding the following code:
-- Monad m
 
import Control.Monad       (liftM, ap)
import Control.Applicative (Applicative(..))
 
instance Functor m where
    fmap = liftM
 
instance Applicative m where
    pure  = return
    (<*>) = ap
  • Add an Alternative instance for all instances of MonadPlus. This can again be done easily using
-- MonadPlus m
 
import Control.Monad       (mzero, mplus)
import Control.Applicative (Alternative(..))
 
instance Alternative m where
    (<|>) = mplus
    empty = mzero
  • Change your API to not define functions named
    <*>
    ,
    join
    or
    pure
    .

Future versions of GHC will issue warnings if code doesn't comply to these rules; there will be a long enough transitional phase so Hackage can adapt to the AMP in advance before the above mentioned changes are actually enforced.

3 Discussion and consequences

3.1 It's the right thing to do™

Math. You've all heard this one, it's good and compelling so I don't need to spell it out.


3.2 Redundant functions

  • pure
    and
    return
    do the same thing.
  • >>
    and
    *>
    are identical.
  • liftM
    and
    liftA
    are
    fmap
    . The
    liftM*
    are
    liftA*
    ,
    <*>
    is
    ap
    .
  • Prelude's
    sequence
    requres
    Monad
    right now, while
    Applicative
    is sufficient to implement it. The more general version of this issue is captured by
    Data.Traversable
    , whose main typeclass implements the *same* functionality twice, namely
    traverse
    and
    mapM
    , and
    sequenceA
    and
    sequence
    .
  • The
    WrappedMonad
    type from
    Control.Applicative
    provides a semi-automatic way to using Functor/Applicative/Alternative functions for Monad/MonadPlus instances as a makeshift patch.

That very much violates the "don't repeat yourself" principle, and even more so it forces the programmer to repeat himself to achieve maximal generality. It may be too late to take all redundancies out, but at least we can prevent new ones from being created.

(Note that it is not proposed to remove any functions for compatibility reasons. Maybe some of them can be phased out in the long run, but that's beyond scope here.)


3.3 Using Functor/Applicative functions in monadic code

Whenever there's Monad code, you can use Functor/Applicative functions, without introducing an additional constraint. Keep in mind that "Functor/Applicative functions" does not only include what their typeclasses define but many more, for example
void
,
(<$>)
,
(<**>)
. Even if you think you have monadic code, strictly using the least restrictive functions may result in something that requires only Applicative. This is similar to writing a function that needs
Int
, but it turns out any
Integral
will do - more polymorphism for free.


3.4 Compatibility issues

These are the kinds of issues to be expected:

  1. Monads lacking Functor or Applicative instances. This is easily fixable by either setting
    fmap = liftM
    ,
    pure = return
    and
    (<*>) = ap
    , although more efficient implementations may exist, or by moving an already existing definition from
    Control.Applicative
    to the appropriate module.
  2. This one is specific to building GHC: importing
    Control.Monad/Applicative
    introduces a circular module dependency. In this case, one can rely on handwritten implementations of the desired function, e.g.
    ap f x = f >>= ...
    .
  3. Libraries using their own
    (<*>)
    . This one is potentially the most laborious consequence. For building GHC though, this only concerns Hoopl, and a handful of renames.


3.5 Beginner friendliness

How often did you say ...

  • "A Monad is always an Applicative but due to historical reasons it's not but you can easily verify it by setting
    pure = return
    and
    (<*>) = ap
    "
  • "
    liftM
    is
    fmap
    but not really." - "So when should I use
    fmap
    and when
    liftM
    ?" - *sigh*

With the new hierarchy, the answer would *always* be "use the least restrictive one".


4 Applying the AMP to GHC and then Haskell in practice

Proposed is a gradual introduction of the AMP in three phases:


4.1 Current stage: Prepare GHC

Using a GHC fork with the full patch applied, find and fix all compilation errors introduced by the change by adding Functor/Applicative instances for all Monads.

According to SPJ, adding an ad-hoc warning of sorts "Monad without Applicative detected" is not a problem, which will be crucial for the next phase. More specifically, issue a warning if:

  • Monad without Applicative
  • MonadPlus without Alternative
  • One of
    <*>
    ,
    pure
    ,
    join
    is defined in a different context to avoid naming conflicts, as these functions will go into the Prelude

4.2 Prepare Hackage

The warning just mentioned will hint to all authors that they should fix (or help others fix) the non-complying packages. This will ideally lead to libraries eventually adding Applicative instances, and changing their APIs if they redefine operators like
<*>
.

After enough time has passed by so libraries adapted to the circumstances, move on to the next phase.


4.3 Apply the proposal

Once Hackage is prepared, applying the changes to the Base package is painless. However, this is not primarily a GHC, but a Haskell change. The previous steps were basically preparing the landscape, and when we've (hopefully) found out that it is a good idea to go through with it, it can be proposed to go into the Report. If we make it this far, the AMP should pass quite easily.


5 Previous proposals

  • Early 2011: GHC ticket – changes similar to this proposal, but closed as "not GHC, but Haskell". See here for the associated discussion.
  • The Other Prelude