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.