Personal tools

Functor-Applicative-Monad Proposal

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(GHC Proposal)
(Rewrite the page!)
Line 1: Line 1:
The standard class hierarchy is a consequence of Haskell's historical development, rather than logic. The <hask>Functor</hask>, <hask>Applicative</hask>, and <hask>Monad</hask> type classes could be defined as:
+
The standard class hierarchy is a consequence of Haskell's historical development, rather than logic.
   
<haskell>
+
This article attempts to document various suggestions that have been brought up over the years, along with arguments for and against.
class Functor f where
 
map :: (a -> b) -> f a -> f b
 
   
class Functor f => Applicative f where
+
== Make <hask>Applicative</hask> a superclass of <hask>Monad</hask> ==
return :: a -> f a
 
(<*>) :: f (a -> b) -> f a -> f b
 
(*>) :: f a -> f b -> f b
 
(<*) :: f a -> f b -> f a
 
   
  +
<haskell>
 
class Applicative m => Monad m where
 
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
+
...
f >>= x = join $ map f x
 
 
join :: m (m a) -> m a
 
join x = x >>= id
 
 
class Monad m => MonadFail m where
 
fail :: String -> m a
 
 
</haskell>
 
</haskell>
   
This would eliminate the necessity of declaring a Monad instance for every Applicative, and eliminate the need for sets of duplicate functions such as [<hask>fmap</hask>, <hask>liftM</hask>, <hask>map</hask>, <hask>liftA</hask>], [<hask>(<*>)</hask>, <hask>ap</hask>], and [<hask>concat</hask>, <hask>join</hask>].
+
=== For ===
   
A monad which requires custom handling for pattern match failures can implement <hask>MonadFail</hask>; otherwise, a failed pattern match will error in the same way as is does for pure code.
+
* Code that is polymorphic over the Monad can use Applicative operators rather than the ugly <hask>liftM</hask> and <hask>ap</hask>.
   
<hask>Pointed</hask> has not been included due to controversy as to whether it should be a subclass of Functor, a superclass of Functor, independent of Functor, or perhaps it is not sufficiently useful to include at all.
+
* Most types that implement Monad also implement Applicative already. This change will only make explicit a current best practice.
   
Backward compatibility could be eased with a legacy module, such as:
+
=== Against ===
   
<haskell>
+
* 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.
module Legacy where
 
   
fmap :: Functor f => (a -> b) -> f a -> f b
+
* 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.
fmap = map
 
   
liftA :: Applicative f => (a -> b) -> f a -> f b
+
== Add <hask>join</hask> as a method of <hask>Monad</hask> ==
liftA = map
 
 
liftM :: Monad m => (a -> b) -> m a -> m b
 
liftM = map
 
 
ap :: Monad m => m (a -> b) -> m a -> m b
 
ap = (<*>)
 
 
(>>) :: Monad m => m a -> m b -> m b
 
(>>) = (*>)
 
 
concat :: [[a]] -> [a]
 
concat = join
 
 
etc.
 
</haskell>
 
 
And for those who really want a list map,
 
   
 
<haskell>
 
<haskell>
listMap :: (a -> b) -> [a] -> [b]
+
class Applicative m => Monad m where
listMap = map
+
(>>=) :: (a -> m b) -> m a -> m b
  +
join :: m (m a) -> m a
  +
...
  +
m >>= k = join (fmap k m)
  +
join m = m >>= id
 
</haskell>
 
</haskell>
   
[[Context alias]] would also be a great help with backwards compatibility. The [[class system extension proposal]] may also help.
+
=== For ===
   
Another variant might be to split a <hask>Pointed</hask> class from the <hask>Applicative</hask> class.
+
* <hask>fmap</hask>/<hask>join</hask> is more orthogonal than <hask>fmap</hask>/<hask>>>=</hask>, and the former is closer to the categorical definition.
   
<haskell>
+
* <hask>join</hask> is often easier to implement. See [http://article.gmane.org/gmane.comp.lang.haskell.libraries/14926].
class Pointed f where
 
return :: a -> f a
 
   
class (Functor f, Pointed f) => Applicative f where
+
* The analogous [http://hackage.haskell.org/packages/archive/comonad/3.0.2/doc/html/Control-Comonad.html comonad] package is written this way.
(<*>) :: f (a -> b) -> f a -> f b
 
(*>) :: f a -> f b -> f b
 
(<*) :: f a -> f b -> f a
 
</haskell>
 
   
Such <hask>Pointed</hask> functionality by itself could be useful, for example, in a DSL in which it is only possible to embed values and not to lift functions to functions over those embedded values.
+
=== Against ===
   
== GHC Proposal ==
+
* <hask>>>=</hask> is used much more frequently in real-world code than <hask>join</hask>.
A subset of this proposal has been formally proposed for GHC. The patches attached to the [http://hackage.haskell.org/trac/ghc/ticket/4834 ticket] make Applicative into a superclass of Monad, but does not deprecate any names.
 
   
Copied from the [http://article.gmane.org/gmane.comp.lang.haskell.libraries/14905 mailing list]:
+
* Performance: The default implementation of <hask>>>=</hask> requires two traversals. Any container-like type which only implements <hask>fmap</hask> and <hask>join</hask> would be slower.
   
The patch for base makes a few changes:
+
== Remove <hask>liftM</hask>, <hask>ap</hask>, etc. in favor of their Applicative counterparts ==
   
1) Make Applicative a superclass of Monad. So the new hierarchy becomes:
+
=== For ===
<haskell>
 
class Functor f where
 
fmap :: (a -> b) -> f a -> f b
 
   
(<$) :: a -> f b -> f a
+
* We will end up with a simpler base library.
(<$) = fmap . const
 
   
class Functor f => Applicative f where
+
=== Against ===
pure :: a -> f a
 
   
(<*>) :: f (a -> b) -> f a -> f b
+
* A lot of code will be broken by this change. There is no compelling reason to remove these functions outright, rather than gradually deprecating them as with <hask>Prelude.catch</hask>.
   
(*>) :: f a -> f b -> f b
+
* A common pattern is to write a full instance of Monad, then set <hask>fmap = liftM</hask> and <hask>(<*>) = ap</hask>.
a *> b = fmap (const id) a <*> b
 
   
(<*) :: f a -> f b -> f a
+
== Split <hask>fail</hask> into its own class ==
a <* b = fmap const a <*> b
 
 
class Applicative m => Monad m where
 
(>>=) :: forall a b. m a -> (a -> m b) -> m b
 
m >>= f = join $ fmap f m
 
 
join :: m (m a) -> m a
 
join m = m >>= id
 
 
(>>) :: forall a b. m a -> m b -> m b
 
(>>) = (*>)
 
 
return :: a -> m a
 
return = pure
 
   
  +
<haskell>
  +
class Monad m => MonadFail m where
 
fail :: String -> m a
 
fail :: String -> m a
fail s = error s
 
 
</haskell>
 
</haskell>
2) Make 'join' a method of Monad.
 
   
3) Export Applicative(pure, (<*>), (*>), (<*)) from the Prelude.
+
== Rename <hask>fmap</hask> to <hask>map</hask> ==
(Maybe we shouldn't export the (*>) and (<*) methods.)
 
   
4) Also export the join method from the Prelude.
+
== Export <hask>Applicative</hask> in the Prelude ==
   
5) Add Applicative instances for all monads in base.
+
== Redefine <hask>>></hask> in terms of <hask>*></hask> rather than <hask>>>=</hask> ==
  +
  +
== Add a <hask>Pointed</hask> class ==
   
6) Add a Monad instance for ((,) a): (There are already Functor and
 
Applicative instances for it.)
 
 
<haskell>
 
<haskell>
instance Monoid a => Monad ((,) a) where
+
class Pointed p where
(u, x) >>= f = let (v, y) = f x
+
point :: a -> p a
in (u `mappend` v, y)
 
 
</haskell>
 
</haskell>
(Maybe this one should be left out of the patch)
 
   
The patch for ghc simply adds Applicative instances for all monads in
+
This is already implemented in the [http://hackage.haskell.org/package/pointed pointed] package.
ghc. Also included in the ghc patch bundle are some refactoring
 
patches that will make the transition easier:
 
   
* Added (<>) = mappend to compiler/utils/Util.hs.
+
=== For ===
* Add a Monoid instance for AGraph and remove the <*> splice operator.
 
Instead of <*>, the (<>) = mappend operator is now used to splice AGraphs.
 
This change is needed because <*> clashes with the Applicative apply
 
operator <*>, which is probably going to be exported from the Prelude
 
when the new Monad hierarchy is going through. (Simply hiding <*> from
 
the Prelude is also possible of course. However, I think this makes
 
things easier to understand)
 
* Make SDoc an abstract newtype and add a Monoid instance for it.
 
The (<>) combinator of SDocs is removed and replaced by the more
 
general (<>) = mappend combinator from Util.
 
   
Note that all the ghc patches can be applied independently of the base patch.
+
=== Against ===
   
Now which notable things are not included in the patch for base:
+
* 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.
   
* fmap is not renamed to map.
+
== Related proposals ==
* return and (>>) are not removed as a method.
 
* fail is not removed as a method.
 
* All the liftM functions are not removed in favour of fmap and liftAs.
 
   
I think these are better left as separate 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
  +
** See [http://thread.gmane.org/gmane.comp.lang.haskell.libraries/14883/focus=14905] for the associated discussion.
  +
* [[The Other Prelude]]
   
== See also ==
+
[[Context alias]] would also be a great help with backwards compatibility. The [[class system extension proposal]] may also help.
* A similar proposal exist on the wiki: [[The Other Prelude]]
 
   
 
[[Category:Proposals]]
 
[[Category:Proposals]]

Revision as of 02:05, 3 June 2013

The standard class hierarchy is a consequence of Haskell's historical development, rather than logic.

This article attempts to document various suggestions that have been brought up over the years, along with arguments for and against.

Contents

1 Make
Applicative
a superclass of
Monad

class Applicative m => Monad m where
    ...

1.1 For

  • Code that is polymorphic over the Monad can use Applicative operators rather than the ugly
    liftM
    and
    ap
    .
  • Most types that implement Monad also implement Applicative already. This change will only make explicit a current best practice.

1.2 Against

  • 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.
  • Some libraries, such as blaze-markup, only implement Monad for its do-notation. For these types, an Applicative instance would have no meaning.

2 Add
join
as a method of
Monad

class Applicative m => Monad m where
    (>>=) :: (a -> m b) -> m a -> m b
    join :: m (m a) -> m a
    ...
    m >>= k = join (fmap k m)
    join m = m >>= id

2.1 For

  • fmap
    /
    join
    is more orthogonal than
    fmap
    /
    >>=
    , and the former is closer to the categorical definition.
  • join
    is often easier to implement. See [1].
  • The analogous comonad package is written this way.

2.2 Against

  • >>=
    is used much more frequently in real-world code than
    join
    .
  • Performance: The default implementation of
    >>=
    requires two traversals. Any container-like type which only implements
    fmap
    and
    join
    would be slower.

3 Remove
liftM
,
ap
, etc. in favor of their Applicative counterparts

3.1 For

  • We will end up with a simpler base library.

3.2 Against

  • A lot of code will be broken by this change. There is no compelling reason to remove these functions outright, rather than gradually deprecating them as with
    Prelude.catch
    .
  • A common pattern is to write a full instance of Monad, then set
    fmap = liftM
    and
    (<*>) = ap
    .

4 Split
fail
into its own class

class Monad m => MonadFail m where
    fail :: String -> m a

5 Rename
fmap
to
map

6 Export
Applicative
in the Prelude

7 Redefine
>>
in terms of
*>
rather than
>>=

8 Add a
Pointed
class

class Pointed p where
    point :: a -> p a

This is already implemented in the pointed package.

8.1 For

8.2 Against

  • This class has seen little real-world use. On Hackage, there are only 9 reverse dependencies for pointed, most of which are by the same author.

9 Related proposals

  • From early 2011: GHC ticket – Makes Applicative into a superclass of Monad, but does not deprecate any existing names
    • See [2] for the associated discussion.
  • The Other Prelude

Context alias would also be a great help with backwards compatibility. The class system extension proposal may also help.