Difference between revisions of "Typeclassopedia"

From HaskellWiki
Jump to: navigation, search
m (Foldable: update doc link)
(Note that fail was removed in GHC 8.8)
 
(128 intermediate revisions by 17 users not shown)
Line 1: Line 1:
''By [[User:Byorgey|Brent Yorgey]], byorgey@cis.upenn.edu''
+
''By [[User:Byorgey|Brent Yorgey]], byorgey@gmail.com''
   
 
''Originally published 12 March 2009 in [http://www.haskell.org/wikiupload/8/85/TMR-Issue13.pdf issue 13] of [http://themonadreader.wordpress.com/ the Monad.Reader]. Ported to the Haskell wiki in November 2011 by [[User:Geheimdienst|Geheimdienst]].''
 
''Originally published 12 March 2009 in [http://www.haskell.org/wikiupload/8/85/TMR-Issue13.pdf issue 13] of [http://themonadreader.wordpress.com/ the Monad.Reader]. Ported to the Haskell wiki in November 2011 by [[User:Geheimdienst|Geheimdienst]].''
Line 37: Line 37:
 
This document can only be a starting point, since good intuition comes from hard work, [http://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/ not from learning the right metaphor]. Anyone who reads and understands all of it will still have an arduous journey ahead—but sometimes a good starting point makes a big difference.
 
This document can only be a starting point, since good intuition comes from hard work, [http://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/ not from learning the right metaphor]. Anyone who reads and understands all of it will still have an arduous journey ahead—but sometimes a good starting point makes a big difference.
   
It should be noted that this is not a Haskell tutorial; it is assumed that the reader is already familiar with the basics of Haskell, including the standard <code>[http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html Prelude]</code>, the type system, data types, and type classes.
+
It should be noted that this is not a Haskell tutorial; it is assumed that the reader is already familiar with the basics of Haskell, including the standard [{{HackageDocs|base|Prelude}} <code>Prelude</code>], the type system, data types, and type classes.
   
The type classes we will be discussing and their interrelationships:
+
The type classes we will be discussing and their interrelationships ([[:File:Dependencies.txt|source code for this graph can be found here]]):
   
 
[[Image:Typeclassopedia-diagram.png]]
 
[[Image:Typeclassopedia-diagram.png]]
   
{{note|<code>Semigroup</code> can be found in the [http://hackage.haskell.org/package/semigroups <code>semigroups</code> package], <code>Apply</code> in the [http://hackage.haskell.org/package/semigroupoids <code>semigroupoids</code> package], and <code>Comonad</code> in the [http://hackage.haskell.org/package/comonad <code>comonad</code> package].}}
+
{{note|<code>Apply</code> can be found in the [http://hackage.haskell.org/package/semigroupoids <code>semigroupoids</code> package], and <code>Comonad</code> in the [http://hackage.haskell.org/package/comonad <code>comonad</code> package].}}
   
 
* <span style="border-bottom: 2px solid black">Solid arrows</span> point from the general to the specific; that is, if there is an arrow from <code>Foo</code> to <code>Bar</code> it means that every <code>Bar</code> is (or should be, or can be made into) a <code>Foo</code>.
 
* <span style="border-bottom: 2px solid black">Solid arrows</span> point from the general to the specific; that is, if there is an arrow from <code>Foo</code> to <code>Bar</code> it means that every <code>Bar</code> is (or should be, or can be made into) a <code>Foo</code>.
* <span style="border-bottom: 2px dotted black">Dotted arrows</span> indicate some other sort of relationship.
+
* <span style="border-bottom: 2px dotted black">Dotted lines</span> indicate some other sort of relationship.
 
* <code>Monad</code> and <code>ArrowApply</code> are equivalent.
 
* <code>Monad</code> and <code>ArrowApply</code> are equivalent.
* <code>Semigroup</code>, <code>Apply</code> and <code>Comonad</code> are greyed out since they are not actually (yet?) in the standard Haskell libraries {{noteref}}.
+
* <code>Apply</code> and <code>Comonad</code> are greyed out since they are not actually (yet?) in the standard Haskell libraries {{noteref}}.
   
 
One more note before we begin. The original spelling of “type class” is with two words, as evidenced by, for example, the [http://www.haskell.org/onlinereport/haskell2010/ Haskell 2010 Language Report], early papers on type classes like [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.5639 Type classes in Haskell] and [http://research.microsoft.com/en-us/um/people/simonpj/papers/type-class-design-space/ Type classes: exploring the design space], and [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.168.4008 Hudak et al.’s history of Haskell]. However, as often happens with two-word phrases that see a lot of use, it has started to show up as one word (“typeclass”) or, rarely, hyphenated (“type-class”). When wearing my prescriptivist hat, I prefer “type class”, but realize (after changing into my descriptivist hat) that there's probably not much I can do about it.
 
One more note before we begin. The original spelling of “type class” is with two words, as evidenced by, for example, the [http://www.haskell.org/onlinereport/haskell2010/ Haskell 2010 Language Report], early papers on type classes like [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.5639 Type classes in Haskell] and [http://research.microsoft.com/en-us/um/people/simonpj/papers/type-class-design-space/ Type classes: exploring the design space], and [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.168.4008 Hudak et al.’s history of Haskell]. However, as often happens with two-word phrases that see a lot of use, it has started to show up as one word (“typeclass”) or, rarely, hyphenated (“type-class”). When wearing my prescriptivist hat, I prefer “type class”, but realize (after changing into my descriptivist hat) that there's probably not much I can do about it.
   
We now begin with the simplest type class of all: <code>Functor</code>.
+
[[Instances of List and Maybe]] illustrates these type classes with simple examples using List and Maybe. We now begin with the simplest type class of all: <code>Functor</code>.
   
 
=Functor=
 
=Functor=
   
The <code>Functor</code> class ([http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#t:Functor haddock]) is the most basic and ubiquitous type class in the Haskell libraries. A simple intuition is that a <code>Functor</code> represents a “container” of some sort, along with the ability to apply a function uniformly to every element in the container. For example, a list is a container of elements, and we can apply a function to every element of a list, using <code>map</code>. As another example, a binary tree is also a container of elements, and it’s not hard to come up with a way to recursively apply a function to every element in a tree.
+
The <code>Functor</code> class ([{{HackageDocs|base|Prelude}}#t:Functor haddock]) is the most basic and ubiquitous type class in the Haskell libraries. A simple intuition is that a <code>Functor</code> represents a “container” of some sort, along with the ability to apply a function uniformly to every element in the container. For example, a list is a container of elements, and we can apply a function to every element of a list, using <code>map</code>. As another example, a binary tree is also a container of elements, and it’s not hard to come up with a way to recursively apply a function to every element in a tree.
   
 
Another intuition is that a <code>Functor</code> represents some sort of “computational context”. This intuition is generally more useful, but is more difficult to explain, precisely because it is so general. Some examples later should help to clarify the <code>Functor</code>-as-context point of view.
 
Another intuition is that a <code>Functor</code> represents some sort of “computational context”. This intuition is generally more useful, but is more difficult to explain, precisely because it is so general. Some examples later should help to clarify the <code>Functor</code>-as-context point of view.
Line 69: Line 69:
 
class Functor f where
 
class Functor f where
 
fmap :: (a -> b) -> f a -> f b
 
fmap :: (a -> b) -> f a -> f b
  +
  +
(<$) :: a -> f b -> f a
  +
(<$) = fmap . const
 
</haskell>
 
</haskell>
   
<code>Functor</code> is exported by the <code>Prelude</code>, so no special imports are needed to use it.
 
  +
<code>Functor</code> is exported by the <code>Prelude</code>, so no special imports are needed to use it. Note that the <code>(<$)</code> operator is provided for convenience, with a default implementation in terms of <code>fmap</code>; it is included in the class just to give <code>Functor</code> instances the opportunity to provide a more efficient implementation than the default. To understand <code>Functor</code>, then, we really need to understand <code>fmap</code>.
   
First, the <code>f a</code> and <code>f b</code> in the type signature for <code>fmap</code> tell us that <code>f</code> isn’t just a type; it is a ''type constructor'' which takes another type as a parameter. (A more precise way to say this is that the ''kind'' of <code>f</code> must be <code>* -> *</code>.) For example, <code>Maybe</code> is such a type constructor: <code>Maybe</code> is not a type in and of itself, but requires another type as a parameter, like <code>Maybe Integer</code>. So it would not make sense to say <code>instance Functor Integer</code>, but it could make sense to say <code>instance Functor Maybe</code>.
+
First, the <code>f a</code> and <code>f b</code> in the type signature for <code>fmap</code> tell us that <code>f</code> isn’t a concrete type like <code>Int</code>; it is a sort of ''type function'' which takes another type as a parameter. More precisely, the ''kind'' of <code>f</code> must be <code>* -> *</code>. For example, <code>Maybe</code> is such a type with kind <code>* -> *</code>: <code>Maybe</code> is not a concrete type by itself (that is, there are no values of type <code>Maybe</code>), but requires another type as a parameter, like <code>Maybe Integer</code>. So it would not make sense to say <code>instance Functor Integer</code>, but it could make sense to say <code>instance Functor Maybe</code>.
   
 
Now look at the type of <code>fmap</code>: it takes any function from <code>a</code> to <code>b</code>, and a value of type <code>f a</code>, and outputs a value of type <code>f b</code>. From the container point of view, the intention is that <code>fmap</code> applies a function to each element of a container, without altering the structure of the container. From the context point of view, the intention is that <code>fmap</code> applies a function to a value without altering its context. Let’s look at a few specific examples.
 
Now look at the type of <code>fmap</code>: it takes any function from <code>a</code> to <code>b</code>, and a value of type <code>f a</code>, and outputs a value of type <code>f b</code>. From the container point of view, the intention is that <code>fmap</code> applies a function to each element of a container, without altering the structure of the container. From the context point of view, the intention is that <code>fmap</code> applies a function to a value without altering its context. Let’s look at a few specific examples.
  +
  +
Finally, we can understand <code>(<$)</code>: instead of applying a function to the values a container/context, it simply replaces them with a given value. This is the same as applying a constant function, so <code>(<$)</code> can be implemented in terms of <code>fmap</code>.
   
 
==Instances==
 
==Instances==
Line 87: Line 92:
 
<haskell>
 
<haskell>
 
instance Functor [] where
 
instance Functor [] where
  +
fmap :: (a -> b) -> [a] -> [b]
 
fmap _ [] = []
 
fmap _ [] = []
 
fmap g (x:xs) = g x : fmap g xs
 
fmap g (x:xs) = g x : fmap g xs
Line 92: Line 98:
   
 
instance Functor Maybe where
 
instance Functor Maybe where
  +
fmap :: (a -> b) -> Maybe a -> Maybe b
 
fmap _ Nothing = Nothing
 
fmap _ Nothing = Nothing
 
fmap g (Just a) = Just (g a)
 
fmap g (Just a) = Just (g a)
Line 98: Line 105:
 
As an aside, in idiomatic Haskell code you will often see the letter <code>f</code> used to stand for both an arbitrary <code>Functor</code> and an arbitrary function. In this document, <code>f</code> represents only <code>Functor</code>s, and <code>g</code> or <code>h</code> always represent functions, but you should be aware of the potential confusion. In practice, what <code>f</code> stands for should always be clear from the context, by noting whether it is part of a type or part of the code.
 
As an aside, in idiomatic Haskell code you will often see the letter <code>f</code> used to stand for both an arbitrary <code>Functor</code> and an arbitrary function. In this document, <code>f</code> represents only <code>Functor</code>s, and <code>g</code> or <code>h</code> always represent functions, but you should be aware of the potential confusion. In practice, what <code>f</code> stands for should always be clear from the context, by noting whether it is part of a type or part of the code.
   
There are other <code>Functor</code> instances in the standard libraries; below are a few. Note that some of these instances are not exported by the <code>Prelude</code>; to access them, you can import <code>Control.Monad.Instances</code>.
+
There are other <code>Functor</code> instances in the standard library as well:
   
 
* <code>Either e</code> is an instance of <code>Functor</code>; <code>Either e a</code> represents a container which can contain either a value of type <code>a</code>, or a value of type <code>e</code> (often representing some sort of error condition). It is similar to <code>Maybe</code> in that it represents possible failure, but it can carry some extra information about the failure as well.
 
* <code>Either e</code> is an instance of <code>Functor</code>; <code>Either e a</code> represents a container which can contain either a value of type <code>a</code>, or a value of type <code>e</code> (often representing some sort of error condition). It is similar to <code>Maybe</code> in that it represents possible failure, but it can carry some extra information about the failure as well.
Line 108: Line 115:
 
* <code>IO</code> is a <code>Functor</code>; a value of type <code>IO a</code> represents a computation producing a value of type <code>a</code> which may have I/O effects. If <code>m</code> computes the value <code>x</code> while producing some I/O effects, then <code>fmap g m</code> will compute the value <code>g x</code> while producing the same I/O effects.
 
* <code>IO</code> is a <code>Functor</code>; a value of type <code>IO a</code> represents a computation producing a value of type <code>a</code> which may have I/O effects. If <code>m</code> computes the value <code>x</code> while producing some I/O effects, then <code>fmap g m</code> will compute the value <code>g x</code> while producing the same I/O effects.
   
* Many standard types from the [http://hackage.haskell.org/package/containers/ containers library] (such as <code>Tree</code>, <code>Map</code>, and <code>Sequence</code>) are instances of <code>Functor</code>. A notable exception is <code>Set</code>, which cannot be made a <code>Functor</code> in Haskell (although it is certainly a mathematical functor) since it requires an <code>Ord</code> constraint on its elements; <code>fmap</code> must be applicable to ''any'' types <code>a</code> and <code>b</code>. However, <code>Set</code> (and other similarly restricted data types) can be made an instance of a suitable generalization of <code>Functor</code>, either by [http://article.gmane.org/gmane.comp.lang.haskell.cafe/78052/ making <code>a</code> and <code>b</code> arguments to the <code>Functor</code> type class themselves], or by adding an [http://blog.omega-prime.co.uk/?p=127 associated constraint].
+
* Many standard types from the [http://hackage.haskell.org/package/containers/ containers library] (such as <code>Tree</code>, <code>Map</code>, and <code>Sequence</code>) are instances of <code>Functor</code>. A notable exception is <code>Set</code>, which cannot be made a <code>Functor</code> in Haskell (although it is certainly a mathematical functor) since it requires an <code>Ord</code> constraint on its elements; <code>fmap</code> must be applicable to ''any'' types <code>a</code> and <code>b</code>. However, <code>Set</code> (and other similarly restricted data types) can be made an instance of a suitable generalization of <code>Functor</code>, either by [http://archive.fo/9sQhq making <code>a</code> and <code>b</code> arguments to the <code>Functor</code> type class themselves], or by adding an [http://blog.omega-prime.co.uk/?p=127 associated constraint].
   
 
{{Exercises|
 
{{Exercises|
Line 157: Line 164:
 
-- Evil Functor instance
 
-- Evil Functor instance
 
instance Functor [] where
 
instance Functor [] where
  +
fmap :: (a -> b) -> [a] -> [b]
 
fmap _ [] = []
 
fmap _ [] = []
 
fmap g (x:xs) = g x : g x : fmap g xs
 
fmap g (x:xs) = g x : g x : fmap g xs
Line 163: Line 171:
 
Any Haskeller worth their salt would reject this code as a gruesome abomination.
 
Any Haskeller worth their salt would reject this code as a gruesome abomination.
   
Unlike some other type classes we will encounter, a given type has at most one valid instance of <code>Functor</code>. This [http://article.gmane.org/gmane.comp.lang.haskell.libraries/15384 can be proven] via the [http://homepages.inf.ed.ac.uk/wadler/topics/parametricity.html#free ''free theorem''] for the type of <code>fmap</code>. In fact, [http://byorgey.wordpress.com/2010/03/03/deriving-pleasure-from-ghc-6-12-1/ GHC can automatically derive] <code>Functor</code> instances for many data types.
+
Unlike some other type classes we will encounter, a given type has at most one valid instance of <code>Functor</code>. This [http://archive.fo/U8xIY can be proven] via the [http://homepages.inf.ed.ac.uk/wadler/topics/parametricity.html#free ''free theorem''] for the type of <code>fmap</code>. In fact, [http://byorgey.wordpress.com/2010/03/03/deriving-pleasure-from-ghc-6-12-1/ GHC can automatically derive] <code>Functor</code> instances for many data types.
   
{{note|Actually, if <code>seq</code>/<code>undefined</code> are considered, it [http://stackoverflow.com/a/8323243/305559 is possible] to have an implementation which satisfies the first law but not the second. The rest of the comments in this section should considered in a context where <code>seq</code> and <code>undefined</code> are excluded.}}
+
{{note|Actually, if <code>seq</code>/<code>undefined</code> are considered, it [http://stackoverflow.com/a/8323243/305559 is possible] to have an implementation which satisfies the first law but not the second. The rest of the comments in this section should be considered in a context where <code>seq</code> and <code>undefined</code> are excluded.}}
   
 
A [https://github.com/quchen/articles/blob/master/second_functor_law.md similar argument also shows] that any <code>Functor</code> instance satisfying the first law (<code>fmap id = id</code>) will automatically satisfy the second law as well. Practically, this means that only the first law needs to be checked (usually by a very straightforward induction) to ensure that a <code>Functor</code> instance is valid.{{noteref}}
 
A [https://github.com/quchen/articles/blob/master/second_functor_law.md similar argument also shows] that any <code>Functor</code> instance satisfying the first law (<code>fmap id = id</code>) will automatically satisfy the second law as well. Practically, this means that only the first law needs to be checked (usually by a very straightforward induction) to ensure that a <code>Functor</code> instance is valid.{{noteref}}
Line 179: Line 187:
   
 
Just like all other Haskell functions of “more than one parameter”, however, <code>fmap</code> is actually ''curried'': it does not really take two parameters, but takes a single parameter and returns a function. For emphasis, we can write <code>fmap</code>’s type with extra parentheses: <code>fmap :: (a -> b) -> (f a -> f b)</code>. Written in this form, it is apparent that <code>fmap</code> transforms a “normal” function (<code>g :: a -> b</code>) into one which operates over containers/contexts (<code>fmap g :: f a -> f b</code>). This transformation is often referred to as a ''lift''; <code>fmap</code> “lifts” a function from the “normal world” into the “<code>f</code> world”.
 
Just like all other Haskell functions of “more than one parameter”, however, <code>fmap</code> is actually ''curried'': it does not really take two parameters, but takes a single parameter and returns a function. For emphasis, we can write <code>fmap</code>’s type with extra parentheses: <code>fmap :: (a -> b) -> (f a -> f b)</code>. Written in this form, it is apparent that <code>fmap</code> transforms a “normal” function (<code>g :: a -> b</code>) into one which operates over containers/contexts (<code>fmap g :: f a -> f b</code>). This transformation is often referred to as a ''lift''; <code>fmap</code> “lifts” a function from the “normal world” into the “<code>f</code> world”.
  +
  +
==Utility functions==
  +
  +
There are a few more <code>Functor</code>-related functions which can be imported from the <code>Data.Functor</code> module.
  +
  +
* <code>(<$>)</code> is defined as a synonym for <code>fmap</code>. This enables a nice infix style that mirrors the <code>($)</code> operator for function application. For example, <code>f $ 3</code> applies the function <code>f</code> to 3, whereas <code>f <$> [1,2,3]</code> applies <code>f</code> to each member of the list.
  +
* <code>($>) :: Functor f => f a -> b -> f b</code> is just <code>flip (<$)</code>, and can occasionally be useful. To keep them straight, you can remember that <code>(<$)</code> and <code>($>)</code> point towards the value that will be kept.
  +
* <code>void :: Functor f => f a -> f ()</code> is a specialization of <code>(<$)</code>, that is, <code>void x = () <$ x</code>. This can be used in cases where a computation computes some value but the value should be ignored.
   
 
==Further reading==
 
==Further reading==
Line 186: Line 202:
 
=Applicative=
 
=Applicative=
   
A somewhat newer addition to the pantheon of standard Haskell type classes, ''applicative functors'' represent an abstraction lying in between <code>Functor</code> and <code>Monad</code> in expressivity, first described by McBride and Paterson. The title of their classic paper, [http://www.soi.city.ac.uk/~ross/papers/Applicative.html Applicative Programming with Effects], gives a hint at the intended intuition behind the [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Applicative.html <code>Applicative</code>] type class. It encapsulates certain sorts of “effectful” computations in a functionally pure way, and encourages an “applicative” programming style. Exactly what these things mean will be seen later.
+
A somewhat newer addition to the pantheon of standard Haskell type classes, ''applicative functors'' represent an abstraction lying in between <code>Functor</code> and <code>Monad</code> in expressivity, first described by McBride and Paterson. The title of their classic paper, [http://www.soi.city.ac.uk/~ross/papers/Applicative.html Applicative Programming with Effects], gives a hint at the intended intuition behind the [{{HackageDocs|base|Control-Applicative}} <code>Applicative</code>] type class. It encapsulates certain sorts of “effectful” computations in a functionally pure way, and encourages an “applicative” programming style. Exactly what these things mean will be seen later.
   
 
==Definition==
 
==Definition==
Line 195: Line 211:
 
class Functor f => Applicative f where
 
class Functor f => Applicative f where
 
pure :: a -> f a
 
pure :: a -> f a
infixl 4 <*>
+
infixl 4 <*>, *>, <*
 
(<*>) :: f (a -> b) -> f a -> f b
 
(<*>) :: f (a -> b) -> f a -> f b
  +
  +
(*>) :: f a -> f b -> f b
  +
a1 *> a2 = (id <$ a1) <*> a2
  +
  +
(<*) :: f a -> f b -> f a
  +
(<*) = liftA2 const
 
</haskell>
 
</haskell>
   
 
Note that every <code>Applicative</code> must also be a <code>Functor</code>. In fact, as we will see, <code>fmap</code> can be implemented using the <code>Applicative</code> methods, so every <code>Applicative</code> is a functor whether we like it or not; the <code>Functor</code> constraint forces us to be honest.
 
Note that every <code>Applicative</code> must also be a <code>Functor</code>. In fact, as we will see, <code>fmap</code> can be implemented using the <code>Applicative</code> methods, so every <code>Applicative</code> is a functor whether we like it or not; the <code>Functor</code> constraint forces us to be honest.
  +
  +
<code>(*>)</code> and <code>(<*)</code> are provided for convenience, in case a particular instance of <code>Applicative</code> can provide more efficient implementations, but they are provided with default implementations. For more on these operators, see the section on [[#Utility functions|Utility functions]] below.
   
 
{{note|Recall that <code>($)</code> is just function application: <code>f $ x {{=}} f x</code>.}}
 
{{note|Recall that <code>($)</code> is just function application: <code>f $ x {{=}} f x</code>.}}
Line 212: Line 236:
   
 
{{note|See
 
{{note|See
[http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Applicative.html haddock for Applicative] and [http://www.soi.city.ac.uk/~ross/papers/Applicative.html Applicative programming with effects]}}
+
[{{HackageDocs|base|Control-Applicative}} haddock for Applicative] and [http://www.soi.city.ac.uk/~ross/papers/Applicative.html Applicative programming with effects]}}
   
 
Traditionally, there are four laws that <code>Applicative</code> instances should satisfy {{noteref}}. In some sense, they are all concerned with making sure that <code>pure</code> deserves its name:
 
Traditionally, there are four laws that <code>Applicative</code> instances should satisfy {{noteref}}. In some sense, they are all concerned with making sure that <code>pure</code> deserves its name:
Line 229: Line 253:
 
</haskell>
 
</haskell>
   
It says that mapping a pure function <code>g</code> over a context <code>x</code> is the same as first injecting <code>g</code> into a context with <code>pure</code>, and then applying it to <code>x</code> with <code>(<*>)</code>. In other words, we can decompose <code>fmap</code> into two more atomic operations: injection into a context, and application within a context. The <code>Control.Applicative</code> module also defines <code>(<$>)</code> as a synonym for <code>fmap</code>, so the above law can also be expressed as:
+
It says that mapping a pure function <code>g</code> over a context <code>x</code> is the same as first injecting <code>g</code> into a context with <code>pure</code>, and then applying it to <code>x</code> with <code>(<*>)</code>. In other words, we can decompose <code>fmap</code> into two more atomic operations: injection into a context, and application within a context. Since <code>(<$>)</code> is a synonym for <code>fmap</code>, the above law can also be expressed as:
   
 
<code>g <$> x = pure g <*> x</code>.
 
<code>g <$> x = pure g <*> x</code>.
Line 251: Line 275:
   
 
instance Applicative ZipList where
 
instance Applicative ZipList where
  +
pure :: a -> ZipList a
 
pure = undefined -- exercise
 
pure = undefined -- exercise
  +
  +
(<*>) :: ZipList (a -> b) -> ZipList a -> ZipList b
 
(ZipList gs) <*> (ZipList xs) = ZipList (zipWith ($) gs xs)
 
(ZipList gs) <*> (ZipList xs) = ZipList (zipWith ($) gs xs)
 
</haskell>
 
</haskell>
Line 261: Line 288:
 
<haskell>
 
<haskell>
 
instance Applicative [] where
 
instance Applicative [] where
pure x = [x]
+
pure :: a -> [a]
  +
pure x = [x]
  +
  +
(<*>) :: [a -> b] -> [a] -> [b]
 
gs <*> xs = [ g x | g <- gs, x <- xs ]
 
gs <*> xs = [ g x | g <- gs, x <- xs ]
 
</haskell>
 
</haskell>
Line 320: Line 347:
   
 
The double brackets are commonly known as “idiom brackets”, because they allow writing “idiomatic” function application, that is, function application that looks normal but has some special, non-standard meaning (determined by the particular instance of <code>Applicative</code> being used). Idiom brackets are not supported by GHC, but they are supported by the [http://personal.cis.strath.ac.uk/~conor/pub/she/ Strathclyde Haskell Enhancement], a preprocessor which (among many other things) translates idiom brackets into standard uses of <code>(<$>)</code> and <code>(<*>)</code>. This can result in much more readable code when making heavy use of <code>Applicative</code>.
 
The double brackets are commonly known as “idiom brackets”, because they allow writing “idiomatic” function application, that is, function application that looks normal but has some special, non-standard meaning (determined by the particular instance of <code>Applicative</code> being used). Idiom brackets are not supported by GHC, but they are supported by the [http://personal.cis.strath.ac.uk/~conor/pub/she/ Strathclyde Haskell Enhancement], a preprocessor which (among many other things) translates idiom brackets into standard uses of <code>(<$>)</code> and <code>(<*>)</code>. This can result in much more readable code when making heavy use of <code>Applicative</code>.
  +
  +
In addition, as of GHC 8, the <code>ApplicativeDo</code> extension enables <code>g <$> x1 <*> x2 <*> ... <*> xn</code> to be written in a different style:
  +
<haskell>
  +
do v1 <- x1
  +
v2 <- x2
  +
...
  +
vn <- xn
  +
pure (g v1 v2 ... vn)
  +
</haskell>
  +
See the Further Reading section below as well as the discussion of do-notation in the Monad section for more information.
  +
  +
==Utility functions==
  +
  +
<code>Control.Applicative</code> provides several utility functions that work generically with any <code>Applicative</code> instance.
  +
  +
* <code>liftA :: Applicative f => (a -> b) -> f a -> f b</code>. This should be familiar; of course, it is the same as <code>fmap</code> (and hence also the same as <code>(<$>)</code>), but with a more restrictive type. This probably exists to provide a parallel to <code>liftA2</code> and <code>liftA3</code>, but there is no reason you should ever need to use it.
  +
  +
* <code>liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c</code> lifts a 2-argument function to operate in the context of some <code>Applicative</code>. When <code>liftA2</code> is fully applied, as in <code>liftA2 f arg1 arg2</code>,it is typically better style to instead use <code>f <$> arg1 <*> arg2</code>. However, <code>liftA2</code> can be useful in situations where it is partially applied. For example, one could define a <code>Num</code> instance for <code>Maybe Integer</code> by defining <code>(+) = liftA2 (+)</code> and so on.
  +
  +
* There is a <code>liftA3</code> but no <code>liftAn</code> for larger <code>n</code>.
  +
  +
* <code>(*>) :: Applicative f => f a -> f b -> f b</code> sequences the effects of two <code>Applicative</code> computations, but discards the result of the first. For example, if <code>m1, m2 :: Maybe Int</code>, then <code>m1 *> m2</code> is <code>Nothing</code> whenever either <code>m1</code> or <code>m2</code> is <code>Nothing</code>; but if not, it will have the same value as <code>m2</code>.
  +
  +
* Likewise, <code>(<*) :: Applicative f => f a -> f b -> f a</code> sequences the effects of two computations, but keeps only the result of the first, discarding the result of the second. Just as with <code>(<$)</code> and <code>($>)</code>, to keep <code>(<*)</code> and <code>(*>)</code> straight, remember that they point towards the values that will be kept.
  +
  +
* <code>(<**>) :: Applicative f => f a -> f (a -> b) -> f b</code> is similar to <code>(<*>)</code>, but where the first computation produces value(s) which are provided as input to the function(s) produced by the second computation. Note this is not the same as <code>flip (<*>)</code>, because the effects are performed in the opposite order. This is possible to observe with any <code>Applicative</code> instance with non-commutative effects, such as the instance for lists: <code>(<**>) [1,2] [(+5),(*10)]</code> produces a different result than <code>(flip (<*>))</code> on the same arguments.
  +
  +
* <code>when :: Applicative f => Bool -> f () -> f ()</code> conditionally executes a computation, evaluating to its second argument if the test is <code>True</code>, and to <code>pure ()</code> if the test is <code>False</code>.
  +
  +
* <code>unless :: Applicative f => Bool -> f () -> f ()</code> is like <code>when</code>, but with the test negated.
  +
  +
* The <code>guard</code> function is for use with instances of <code>Alternative</code> (an extension of <code>Applicative</code> to incorporate the ideas of failure and choice), which is discussed in the [[#Failure_and_choice:_Alternative.2C_MonadPlus.2C_ArrowPlus|section on <code>Alternative</code> and friends]].
  +
  +
{{Exercises|
  +
# Implement a function <haskell>sequenceAL :: Applicative f => [f a] -> f [a]</haskell>. There is a generalized version of this, <code>sequenceA</code>, which works for any <code>Traversable</code> (see the later section on Traversable), but implementing this version specialized to lists is a good exercise.
  +
}}
   
 
==Alternative formulation==
 
==Alternative formulation==
Line 357: Line 420:
 
# Implement <code>pure</code> and <code>(<*>)</code> in terms of <code>unit</code> and <code>(**)</code>, and vice versa.
 
# Implement <code>pure</code> and <code>(<*>)</code> in terms of <code>unit</code> and <code>(**)</code>, and vice versa.
 
# Are there any <code>Applicative</code> instances for which there are also functions <code>f () -> ()</code> and <code>f (a,b) -> (f a, f b)</code>, satisfying some "reasonable" laws?
 
# Are there any <code>Applicative</code> instances for which there are also functions <code>f () -> ()</code> and <code>f (a,b) -> (f a, f b)</code>, satisfying some "reasonable" laws?
# (Tricky) Prove that given your implementations from the previous exercise, the usual <code>Applicative</code> laws and the <code>Monoidal</code> laws stated above are equivalent.
+
# (Tricky) Prove that given your implementations from the first exercise, the usual <code>Applicative</code> laws and the <code>Monoidal</code> laws stated above are equivalent.
 
}}
 
}}
   
 
==Further reading==
 
==Further reading==
 
There are many other useful combinators in the standard libraries implemented in terms of <code>pure</code> and <code>(<*>)</code>: for example, <code>(*>)</code>, <code>(<*)</code>, <code>(<**>)</code>, <code>(<$)</code>, and so on (see [http://hackage.haskell.org/package/base/docs/Control-Applicative.html haddock for Applicative]). Judicious use of such secondary combinators can often make code using <code>Applicative</code>s much easier to read.
 
   
 
[http://www.soi.city.ac.uk/~ross/papers/Applicative.html McBride and Paterson’s original paper] is a treasure-trove of information and examples, as well as some perspectives on the connection between <code>Applicative</code> and category theory. Beginners will find it difficult to make it through the entire paper, but it is extremely well-motivated—even beginners will be able to glean something from reading as far as they are able.
 
[http://www.soi.city.ac.uk/~ross/papers/Applicative.html McBride and Paterson’s original paper] is a treasure-trove of information and examples, as well as some perspectives on the connection between <code>Applicative</code> and category theory. Beginners will find it difficult to make it through the entire paper, but it is extremely well-motivated—even beginners will be able to glean something from reading as far as they are able.
Line 368: Line 429:
 
{{note|Introduced by [http://conal.net/papers/simply-reactive/ an earlier paper] that was since superseded by [http://conal.net/papers/push-pull-frp/ Push-pull functional reactive programming].}}
 
{{note|Introduced by [http://conal.net/papers/simply-reactive/ an earlier paper] that was since superseded by [http://conal.net/papers/push-pull-frp/ Push-pull functional reactive programming].}}
   
Conal Elliott has been one of the biggest proponents of <code>Applicative</code>. For example, the [http://conal.net/papers/functional-images/ Pan library for functional images] and the reactive library for functional reactive programming (FRP) {{noteref}} make key use of it; his blog also contains [http://conal.net/blog/posts/tag/applicative-functor many examples of <code>Applicative</code> in action]. Building on the work of McBride and Paterson, Elliott also built the [[TypeCompose]] library, which embodies the observation (among others) that <code>Applicative</code> types are closed under composition; therefore, <code>Applicative</code> instances can often be automatically derived for complex types built out of simpler ones.
+
Conal Elliott has been one of the biggest proponents of <code>Applicative</code>. For example, the [http://conal.net/papers/functional-images/ Pan library for functional images] and the reactive library for functional reactive programming (FRP) {{noteref}} make key use of it; his blog also contains [http://conal.net/blog/tag/applicative-functor many examples of <code>Applicative</code> in action]. Building on the work of McBride and Paterson, Elliott also built the [[TypeCompose]] library, which embodies the observation (among others) that <code>Applicative</code> types are closed under composition; therefore, <code>Applicative</code> instances can often be automatically derived for complex types built out of simpler ones.
   
 
Although the [http://hackage.haskell.org/package/parsec Parsec parsing library] ([http://legacy.cs.uu.nl/daan/download/papers/parsec-paper.pdf paper]) was originally designed for use as a monad, in its most common use cases an <code>Applicative</code> instance can be used to great effect; [http://www.serpentine.com/blog/2008/02/06/the-basics-of-applicative-functors-put-to-practical-work/ Bryan O’Sullivan’s blog post] is a good starting point. If the extra power provided by <code>Monad</code> isn’t needed, it’s usually a good idea to use <code>Applicative</code> instead.
 
Although the [http://hackage.haskell.org/package/parsec Parsec parsing library] ([http://legacy.cs.uu.nl/daan/download/papers/parsec-paper.pdf paper]) was originally designed for use as a monad, in its most common use cases an <code>Applicative</code> instance can be used to great effect; [http://www.serpentine.com/blog/2008/02/06/the-basics-of-applicative-functors-put-to-practical-work/ Bryan O’Sullivan’s blog post] is a good starting point. If the extra power provided by <code>Monad</code> isn’t needed, it’s usually a good idea to use <code>Applicative</code> instead.
Line 375: Line 436:
   
 
Gershom Bazerman's [http://comonad.com/reader/2012/abstracting-with-applicatives/ post] contains many insights into applicatives.
 
Gershom Bazerman's [http://comonad.com/reader/2012/abstracting-with-applicatives/ post] contains many insights into applicatives.
  +
  +
The <code>ApplicativeDo</code> extension is described in [https://ghc.haskell.org/trac/ghc/wiki/ApplicativeDo this wiki page], and in more detail in [http://doi.org/10.1145/2976002.2976007 this Haskell Symposium paper].
   
 
=Monad=
 
=Monad=
Line 381: Line 444:
   
 
* Haskell does, in fact, single out monads for special attention by making them the framework in which to construct I/O operations.
 
* Haskell does, in fact, single out monads for special attention by making them the framework in which to construct I/O operations.
* Haskell also singles out monads for special attention by providing a special syntactic sugar for monadic expressions: the <code>do</code>-notation.
+
* Haskell also singles out monads for special attention by providing a special syntactic sugar for monadic expressions: the <code>do</code>-notation. (As of GHC 8, <code>do</code>-notation can be used with <code>Applicative</code> as well, but the notation is still fundamentally related to monads.)
 
* <code>Monad</code> has been around longer than other abstract models of computation such as <code>Applicative</code> or <code>Arrow</code>.
 
* <code>Monad</code> has been around longer than other abstract models of computation such as <code>Applicative</code> or <code>Arrow</code>.
 
* The more monad tutorials there are, the harder people think monads must be, and the more new monad tutorials are written by people who think they finally “get” monads (the [http://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/ monad tutorial fallacy]).
 
* The more monad tutorials there are, the harder people think monads must be, and the more new monad tutorials are written by people who think they finally “get” monads (the [http://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/ monad tutorial fallacy]).
Line 390: Line 453:
   
 
==Definition==
 
==Definition==
 
  +
As of GHC 8.8, [{{HackageDocs|base|Prelude}}#t:Monad <code>Monad</code>] is defined as:
The type class declaration for [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#t:Monad <code>Monad</code>] is:
 
   
 
<haskell>
 
<haskell>
class Monad m where
+
class Applicative m => Monad m where
 
return :: a -> m a
 
return :: a -> m a
 
(>>=) :: m a -> (a -> m b) -> m b
 
(>>=) :: m a -> (a -> m b) -> m b
 
(>>) :: m a -> m b -> m b
 
(>>) :: m a -> m b -> m b
 
m >> n = m >>= \_ -> n
 
m >> n = m >>= \_ -> n
  +
</haskell>
   
fail :: String -> m a
 
  +
(Prior to GHC 7.10, for historical reasons, <code>Applicative</code> was not a superclass of <code>Monad</code> and prior to GHC 8.8 <code>Monad</code> had an extra <code>fail</code> method.)
</haskell>
 
   
The <code>Monad</code> type class is exported by the <code>Prelude</code>, along with a few standard instances. However, many utility functions are found in [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html <code>Control.Monad</code>], and there are also several instances (such as <code>((->) e)</code>) defined in [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad-Instances.html <code>Control.Monad.Instances</code>].
+
The <code>Monad</code> type class is exported by the <code>Prelude</code>, along with a few standard instances. However, many utility functions are found in [{{HackageDocs|base|Control-Monad}} <code>Control.Monad</code>].
   
{{note|However, as of GHC 7.10 this will be fixed!}}
 
  +
Let’s examine the methods in the <code>Monad</code> class one by one. The type of <code>return</code> should look familiar; it’s the same as <code>pure</code>. Indeed, <code>return</code> ''is'' <code>pure</code>, but with an unfortunate name. (Unfortunate, since someone coming from an imperative programming background might think that <code>return</code> is like the C or Java keyword of the same name, when in fact the similarities are minimal.) For historical reasons, we still have both names, but they should always denote the same value (although this cannot be enforced). Likewise, <code>(>>)</code> should be the same as <code>(*>)</code> from <code>Applicative</code>. It is possible that <code>return</code> and <code>(>>)</code> may eventually be removed from the <code>Monad</code> class: see the [https://ghc.haskell.org/trac/ghc/wiki/Proposal/MonadOfNoReturn Monad of No Return proposal].
Let’s examine the methods in the <code>Monad</code> class one by one. The type of <code>return</code> should look familiar; it’s the same as <code>pure</code>. Indeed, <code>return</code> ''is'' <code>pure</code>, but with an unfortunate name. (Unfortunate, since someone coming from an imperative programming background might think that <code>return</code> is like the C or Java keyword of the same name, when in fact the similarities are minimal.) From a mathematical point of view, every monad is an applicative functor, but for historical reasons, the <code>Monad</code> type class declaration unfortunately does not require this.{{noteref}}
 
   
 
We can see that <code>(>>)</code> is a specialized version of <code>(>>=)</code>, with a default implementation given. It is only included in the type class declaration so that specific instances of <code>Monad</code> can override the default implementation of <code>(>>)</code> with a more efficient one, if desired. Also, note that although <code>_ >> n = n</code> would be a type-correct implementation of <code>(>>)</code>, it would not correspond to the intended semantics: the intention is that <code>m >> n</code> ignores the ''result'' of <code>m</code>, but not its ''effects''.
 
We can see that <code>(>>)</code> is a specialized version of <code>(>>=)</code>, with a default implementation given. It is only included in the type class declaration so that specific instances of <code>Monad</code> can override the default implementation of <code>(>>)</code> with a more efficient one, if desired. Also, note that although <code>_ >> n = n</code> would be a type-correct implementation of <code>(>>)</code>, it would not correspond to the intended semantics: the intention is that <code>m >> n</code> ignores the ''result'' of <code>m</code>, but not its ''effects''.
   
The <code>fail</code> function is an awful hack that has no place in the <code>Monad</code> class; more on this later.
 
  +
The only really interesting thing to look at—and what makes <code>Monad</code> strictly more powerful than <code>Applicative</code>—is <code>(>>=)</code>, which is often called ''bind''.
 
The only really interesting thing to look at—and what makes <code>Monad</code> strictly more powerful than <code>Applicative</code>—is <code>(>>=)</code>, which is often called ''bind''. An alternative definition of <code>Monad</code> could look like:
 
 
<haskell>
 
class Applicative m => Monad' m where
 
(>>=) :: m a -> (a -> m b) -> m b
 
</haskell>
 
   
 
We could spend a while talking about the intuition behind <code>(>>=)</code>—and we will. But first, let’s look at some examples.
 
We could spend a while talking about the intuition behind <code>(>>=)</code>—and we will. But first, let’s look at some examples.
Line 438: Line 492:
 
<haskell>
 
<haskell>
 
instance Monad Maybe where
 
instance Monad Maybe where
  +
return :: a -> Maybe a
 
return = Just
 
return = Just
  +
  +
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
 
(Just x) >>= g = g x
 
(Just x) >>= g = g x
 
Nothing >>= _ = Nothing
 
Nothing >>= _ = Nothing
Line 485: Line 542:
 
Let’s look more closely at the type of <code>(>>=)</code>. The basic intuition is that it combines two computations into one larger computation. The first argument, <code>m a</code>, is the first computation. However, it would be boring if the second argument were just an <code>m b</code>; then there would be no way for the computations to interact with one another (actually, this is exactly the situation with <code>Applicative</code>). So, the second argument to <code>(>>=)</code> has type <code>a -> m b</code>: a function of this type, given a ''result'' of the first computation, can produce a second computation to be run. In other words, <code>x >>= k</code> is a computation which runs <code>x</code>, and then uses the result(s) of <code>x</code> to ''decide'' what computation to run second, using the output of the second computation as the result of the entire computation.
 
Let’s look more closely at the type of <code>(>>=)</code>. The basic intuition is that it combines two computations into one larger computation. The first argument, <code>m a</code>, is the first computation. However, it would be boring if the second argument were just an <code>m b</code>; then there would be no way for the computations to interact with one another (actually, this is exactly the situation with <code>Applicative</code>). So, the second argument to <code>(>>=)</code> has type <code>a -> m b</code>: a function of this type, given a ''result'' of the first computation, can produce a second computation to be run. In other words, <code>x >>= k</code> is a computation which runs <code>x</code>, and then uses the result(s) of <code>x</code> to ''decide'' what computation to run second, using the output of the second computation as the result of the entire computation.
   
{{note|Actually, because Haskell allows general recursion, this is a lie: using a Haskell parsing library one can recursively construct ''infinite'' grammars, and hence <code>Applicative</code> (together with <code>Alternative</code>) is enough to parse any context-sensitive language with a finite alphabet. See [http://byorgey.wordpress.com/2012/01/05/parsing-context-sensitive-languages-with-applicative/ Parsing context-sensitive languages with Applicative].}}
+
{{note|Actually, because Haskell allows general recursion, one can recursively construct ''infinite'' grammars, and hence <code>Applicative</code> (together with <code>Alternative</code>) is enough to parse any context-sensitive language with a finite alphabet. See [http://byorgey.wordpress.com/2012/01/05/parsing-context-sensitive-languages-with-applicative/ Parsing context-sensitive languages with Applicative].}}
 
Intuitively, it is this ability to use the output from previous computations to decide what computations to run next that makes <code>Monad</code> more powerful than <code>Applicative</code>. The structure of an <code>Applicative</code> computation is fixed, whereas the structure of a <code>Monad</code> computation can change based on intermediate results. This also means that parsers built using an <code>Applicative</code> interface can only parse context-free languages; in order to parse context-sensitive languages a <code>Monad</code> interface is needed.{{noteref}}
 
Intuitively, it is this ability to use the output from previous computations to decide what computations to run next that makes <code>Monad</code> more powerful than <code>Applicative</code>. The structure of an <code>Applicative</code> computation is fixed, whereas the structure of a <code>Monad</code> computation can change based on intermediate results. This also means that parsers built using an <code>Applicative</code> interface can only parse context-free languages; in order to parse context-sensitive languages a <code>Monad</code> interface is needed.{{noteref}}
   
 
To see the increased power of <code>Monad</code> from a different point of view, let’s see what happens if we try to implement <code>(>>=)</code> in terms of <code>fmap</code>, <code>pure</code>, and <code>(<*>)</code>. We are given a value <code>x</code> of type <code>m a</code>, and a function <code>k</code> of type <code>a -> m b</code>, so the only thing we can do is apply <code>k</code> to <code>x</code>. We can’t apply it directly, of course; we have to use <code>fmap</code> to lift it over the <code>m</code>. But what is the type of <code>fmap k</code>? Well, it’s <code>m a -> m (m b)</code>. So after we apply it to <code>x</code>, we are left with something of type <code>m (m b)</code>—but now we are stuck; what we really want is an <code>m b</code>, but there’s no way to get there from here. We can ''add'' <code>m</code>’s using <code>pure</code>, but we have no way to ''collapse'' multiple <code>m</code>’s into one.
 
To see the increased power of <code>Monad</code> from a different point of view, let’s see what happens if we try to implement <code>(>>=)</code> in terms of <code>fmap</code>, <code>pure</code>, and <code>(<*>)</code>. We are given a value <code>x</code> of type <code>m a</code>, and a function <code>k</code> of type <code>a -> m b</code>, so the only thing we can do is apply <code>k</code> to <code>x</code>. We can’t apply it directly, of course; we have to use <code>fmap</code> to lift it over the <code>m</code>. But what is the type of <code>fmap k</code>? Well, it’s <code>m a -> m (m b)</code>. So after we apply it to <code>x</code>, we are left with something of type <code>m (m b)</code>—but now we are stuck; what we really want is an <code>m b</code>, but there’s no way to get there from here. We can ''add'' <code>m</code>’s using <code>pure</code>, but we have no way to ''collapse'' multiple <code>m</code>’s into one.
   
{{note|1=You might hear some people claim that that the definition in terms of <code>return</code>, <code>fmap</code>, and <code>join</code> is the “math definition” and the definition in terms of <code>return</code> and <code>(>>=)</code> is something specific to Haskell. In fact, both definitions were known in the mathematics community long before Haskell picked up monads.}}
+
{{note|1=You might hear some people claim that the definition in terms of <code>return</code>, <code>fmap</code>, and <code>join</code> is the “math definition” and the definition in terms of <code>return</code> and <code>(>>=)</code> is something specific to Haskell. In fact, both definitions were known in the mathematics community long before Haskell picked up monads.}}
   
 
This ability to collapse multiple <code>m</code>’s is exactly the ability provided by the function <code>join :: m (m a) -> m a</code>, and it should come as no surprise that an alternative definition of <code>Monad</code> can be given in terms of <code>join</code>:
 
This ability to collapse multiple <code>m</code>’s is exactly the ability provided by the function <code>join :: m (m a) -> m a</code>, and it should come as no surprise that an alternative definition of <code>Monad</code> can be given in terms of <code>join</code>:
Line 508: Line 565:
 
==Utility functions==
 
==Utility functions==
   
The [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html <code>Control.Monad</code>] module provides a large number of convenient utility functions, all of which can be implemented in terms of the basic <code>Monad</code> operations (<code>return</code> and <code>(>>=)</code> in particular). We have already seen one of them, namely, <code>join</code>. We also mention some other noteworthy ones here; implementing these utility functions oneself is a good exercise. For a more detailed guide to these functions, with commentary and example code, see Henk-Jan van Tuyl’s [http://members.chello.nl/hjgtuyl/tourdemonad.html tour].
+
The [{{HackageDocs|base|Control-Monad}} <code>Control.Monad</code>] module provides a large number of convenient utility functions, all of which can be implemented in terms of the basic <code>Monad</code> operations (<code>return</code> and <code>(>>=)</code> in particular). We have already seen one of them, namely, <code>join</code>. We also mention some other noteworthy ones here; implementing these utility functions oneself is a good exercise. For a more detailed guide to these functions, with commentary and example code, see Henk-Jan van Tuyl’s [http://members.chello.nl/hjgtuyl/tourdemonad.html tour].
   
* <code>liftM :: Monad m => (a -> b) -> m a -> m b</code>. This should be familiar; of course, it is just <code>fmap</code>. The fact that we have both <code>fmap</code> and <code>liftM</code> is an unfortunate consequence of the fact that the <code>Monad</code> type class does not require a <code>Functor</code> instance, even though mathematically speaking, every monad is a functor. However, <code>fmap</code> and <code>liftM</code> are essentially interchangeable, since an instance of <code>Monad</code> also has to be instance of <code>Functor</code>.
+
* <code>liftM :: Monad m => (a -> b) -> m a -> m b</code>. This should be familiar; of course, it is just <code>fmap</code>. The fact that we have both <code>fmap</code> and <code>liftM</code> is a consequence of the fact that the <code>Monad</code> type class did not require a <code>Functor</code> instance until recently, even though mathematically speaking, every monad is a functor. If you are using GHC 7.10 or newer, you should avoid using <code>liftM</code> and just use <code>fmap</code> instead.
   
 
* <code>ap :: Monad m => m (a -> b) -> m a -> m b</code> should also be familiar: it is equivalent to <code>(<*>)</code>, justifying the claim that the <code>Monad</code> interface is strictly more powerful than <code>Applicative</code>. We can make any <code>Monad</code> into an instance of <code>Applicative</code> by setting <code>pure = return</code> and <code>(<*>) = ap</code>.
 
* <code>ap :: Monad m => m (a -> b) -> m a -> m b</code> should also be familiar: it is equivalent to <code>(<*>)</code>, justifying the claim that the <code>Monad</code> interface is strictly more powerful than <code>Applicative</code>. We can make any <code>Monad</code> into an instance of <code>Applicative</code> by setting <code>pure = return</code> and <code>(<*>) = ap</code>.
   
* <code>sequence :: Monad m => [m a] -> m [a]</code> takes a list of computations and combines them into one computation which collects a list of their results. It is again something of a historical accident that <code>sequence</code> has a <code>Monad</code> constraint, since it can actually be implemented only in terms of <code>Applicative</code>. There is an additional generalization of <code>sequence</code> to structures other than lists, which will be discussed in the [[#Traversable|section on <code>Traversable</code>]].
+
* <code>sequence :: Monad m => [m a] -> m [a]</code> takes a list of computations and combines them into one computation which collects a list of their results. It is again something of a historical accident that <code>sequence</code> has a <code>Monad</code> constraint, since it can actually be implemented only in terms of <code>Applicative</code> (see the exercise at the end of the Utility Functions section for Applicative). Note that the actual type of <code>sequence</code> is more general, and works over any <code>Traversable</code> rather than just lists; see the [[#Traversable|section on <code>Traversable</code>]].
   
* <code>replicateM :: Monad m => Int -> m a -> m [a]</code> is simply a combination of [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:replicate <code>replicate</code>] and <code>sequence</code>.
+
* <code>replicateM :: Monad m => Int -> m a -> m [a]</code> is simply a combination of [{{HackageDocs|base|Prelude}}#v:replicate <code>replicate</code>] and <code>sequence</code>.
   
* <code>when :: Monad m => Bool -> m () -> m ()</code> conditionally executes a computation, evaluating to its second argument if the test is <code>True</code>, and to <code>return ()</code> if the test is <code>False</code>. A collection of other sorts of monadic conditionals can be found in the [http://hackage.haskell.org/package/IfElse <code>IfElse</code> package].
 
  +
* <code>mapM :: Monad m => (a -> m b) -> [a] -> m [b]</code> maps its first argument over the second, and <code>sequence</code>s the results. The <code>forM</code> function is just <code>mapM</code> with its arguments reversed; it is called <code>forM</code> since it models generalized <code>for</code> loops: the list <code>[a]</code> provides the loop indices, and the function <code>a -> m b</code> specifies the “body” of the loop for each index. Again, these functions actually work over any <code>Traversable</code>, not just lists, and they can also be defined in terms of <code>Applicative</code>, not <code>Monad</code>: the analogue of <code>mapM</code> for <code>Applicative</code> is called <code>traverse</code>.
 
* <code>mapM :: Monad m => (a -> m b) -> [a] -> m [b]</code> maps its first argument over the second, and <code>sequence</code>s the results. The <code>forM</code> function is just <code>mapM</code> with its arguments reversed; it is called <code>forM</code> since it models generalized <code>for</code> loops: the list <code>[a]</code> provides the loop indices, and the function <code>a -> m b</code> specifies the “body” of the loop for each index.
 
   
 
* <code>(=<<) :: Monad m => (a -> m b) -> m a -> m b</code> is just <code>(>>=)</code> with its arguments reversed; sometimes this direction is more convenient since it corresponds more closely to function application.
 
* <code>(=<<) :: Monad m => (a -> m b) -> m a -> m b</code> is just <code>(>>=)</code> with its arguments reversed; sometimes this direction is more convenient since it corresponds more closely to function application.
   
 
* <code>(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c</code> is sort of like function composition, but with an extra <code>m</code> on the result type of each function, and the arguments swapped. We’ll have more to say about this operation later. There is also a flipped variant, <code>(<=<)</code>.
 
* <code>(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c</code> is sort of like function composition, but with an extra <code>m</code> on the result type of each function, and the arguments swapped. We’ll have more to say about this operation later. There is also a flipped variant, <code>(<=<)</code>.
 
* The <code>guard</code> function is for use with instances of <code>MonadPlus</code>, which is discussed at the end of the [[#Monoid|<code>Monoid</code> section]].
 
   
 
Many of these functions also have “underscored” variants, such as <code>sequence_</code> and <code>mapM_</code>; these variants throw away the results of the computations passed to them as arguments, using them only for their side effects.
 
Many of these functions also have “underscored” variants, such as <code>sequence_</code> and <code>mapM_</code>; these variants throw away the results of the computations passed to them as arguments, using them only for their side effects.
Line 540: Line 593:
 
m >>= return = m
 
m >>= return = m
 
m >>= (\x -> k x >>= h) = (m >>= k) >>= h
 
m >>= (\x -> k x >>= h) = (m >>= k) >>= h
 
fmap f xs = xs >>= return . f = liftM f xs
 
 
</haskell>
 
</haskell>
   
The first and second laws express the fact that <code>return</code> behaves nicely: if we inject a value <code>a</code> into a monadic context with <code>return</code>, and then bind to <code>k</code>, it is the same as just applying <code>k</code> to <code>a</code> in the first place; if we bind a computation <code>m</code> to <code>return</code>, nothing changes. The third law essentially says that <code>(>>=)</code> is associative, sort of. The last law ensures that <code>fmap</code> and <code>liftM</code> are the same for types which are instances of both <code>Functor</code> and <code>Monad</code>—which, as already noted, should be every instance of <code>Monad</code>.
+
The first and second laws express the fact that <code>return</code> behaves nicely: if we inject a value <code>a</code> into a monadic context with <code>return</code>, and then bind to <code>k</code>, it is the same as just applying <code>k</code> to <code>a</code> in the first place; if we bind a computation <code>m</code> to <code>return</code>, nothing changes. The third law essentially says that <code>(>>=)</code> is associative, sort of.
   
 
{{note|I like to pronounce this operator “fish”.}}
 
{{note|I like to pronounce this operator “fish”.}}
Line 603: Line 654:
 
</haskell>
 
</haskell>
   
but what happens if <code>foo</code> produces an empty list? Well, remember that ugly <code>fail</code> function in the <code>Monad</code> type class declaration? That’s what happens. See [http://www.haskell.org/onlinereport/exps.html#sect3.14 section 3.14 of the Haskell Report] for the full details. See also the discussion of <code>MonadPlus</code> and <code>MonadZero</code> in the [[#Other monoidal classes: Alternative, MonadPlus, ArrowPlus|section on other monoidal classes]].
+
but what happens if <code>foo</code> is an empty list? There is [https://hackage.haskell.org/package/base-4.14.0.0/docs/src/Control.Monad.Fail.html#fail an instance] of <code>MonadFail</code> for <code>[]</code>, and the <code>fail</code> function in the <code>MonadFail</code> instance will be used as the value for the <code>do</code>-expression. See also the discussion of <code>MonadPlus</code> and <code>MonadZero</code> in the [[#Other monoidal classes: Alternative, MonadPlus, ArrowPlus|section on other monoidal classes]].
   
 
A final note on intuition: <code>do</code> notation plays very strongly to the “computational context” point of view rather than the “container” point of view, since the binding notation <code>x <- m</code> is suggestive of “extracting” a single <code>x</code> from <code>m</code> and doing something with it. But <code>m</code> may represent some sort of a container, such as a list or a tree; the meaning of <code>x <- m</code> is entirely dependent on the implementation of <code>(>>=)</code>. For example, if <code>m</code> is a list, <code>x <- m</code> actually means that <code>x</code> will take on each value from the list in turn.
 
A final note on intuition: <code>do</code> notation plays very strongly to the “computational context” point of view rather than the “container” point of view, since the binding notation <code>x <- m</code> is suggestive of “extracting” a single <code>x</code> from <code>m</code> and doing something with it. But <code>m</code> may represent some sort of a container, such as a list or a tree; the meaning of <code>x <- m</code> is entirely dependent on the implementation of <code>(>>=)</code>. For example, if <code>m</code> is a list, <code>x <- m</code> actually means that <code>x</code> will take on each value from the list in turn.
  +
  +
====ApplicativeDo====
  +
  +
Sometimes, the full power of <code>Monad</code> is not needed to desugar <code>do</code>-notation. For example,
  +
  +
<haskell>
  +
do x <- foo1
  +
y <- foo2
  +
z <- foo3
  +
return (g x y z)
  +
</haskell>
  +
  +
would normally be desugared to <code>foo1 >>= \x -> foo2 >>= \y -> foo3 >>= \z -> return (g x y z)</code>, but this is equivalent to <code>g <$> foo1 <*> foo2 <*> foo3</code>. With the <code>ApplicativeDo</code> extension enabled (as of GHC 8.0), GHC tries hard to desugar <code>do</code>-blocks using <code>Applicative</code> operations wherever possible. This can sometimes lead to efficiency gains, even for types which also have <code>Monad</code> instances, since in general <code>Applicative</code> computations may be run in parallel, whereas monadic ones may not. For example, consider
  +
  +
<haskell>
  +
g :: Int -> Int -> M Int
  +
  +
-- These could be expensive
  +
bar, baz :: M Int
  +
  +
foo :: M Int
  +
foo = do
  +
x <- bar
  +
y <- baz
  +
g x y
  +
</haskell>
  +
  +
<code>foo</code> definitely depends on the <code>Monad</code> instance of <code>M</code>, since the effects generated by the whole computation may depend (via <code>g</code>) on the <code>Int</code> outputs of <code>bar</code> and <code>baz</code>. Nonetheless, with <code>ApplicativeDo</code> enabled, <code>foo</code> can be desugared as
  +
<haskell>
  +
join (g <$> bar <*> baz)
  +
</haskell>
  +
which may allow <code>bar</code> and <code>baz</code> to be computed in parallel, since they at least do not depend on each other.
  +
  +
The <code>ApplicativeDo</code> extension is described in [https://ghc.haskell.org/trac/ghc/wiki/ApplicativeDo this wiki page], and in more detail in [http://doi.org/10.1145/2976002.2976007 this Haskell Symposium paper].
  +
  +
====QualifiedDo====
  +
[https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0216-qualified-do.rst GHC Proposal #216] adds the QualifiedDo extension, which is available in GHC 9.0.1.
  +
  +
When <code>-XQualifiedDo</code> is activated, the syntax <code>[modid.]do</code> becomes available, where <code>modid</code> stands for some module name.
  +
  +
The <code>x <- u</code> statement now uses <code>(modid.>>=)</code>. For example
  +
  +
M.do { x <- u; stmts }
  +
  +
is like writing (without the new extension)
  +
  +
u M.>>= \x -> M.do { stmts }
  +
  +
Other monad methods are also covered, see the proposal for more details.
   
 
==Further reading==
 
==Further reading==
Line 635: Line 735:
 
There are many good reasons for eschewing <code>do</code> notation; some have gone so far as to [[Do_notation_considered_harmful|consider it harmful]].
 
There are many good reasons for eschewing <code>do</code> notation; some have gone so far as to [[Do_notation_considered_harmful|consider it harmful]].
   
Monads can be generalized in various ways; for an exposition of one possibility, see Robert Atkey’s paper on [http://homepages.inf.ed.ac.uk/ratkey/paramnotions-jfp.pdf parameterized monads], or Dan Piponi’s [http://blog.sigfpe.com/2009/02/beyond-monads.html Beyond Monads].
+
Monads can be generalized in various ways; for an exposition of one possibility, see Robert Atkey’s paper on [https://bentnib.org/paramnotions-jfp.pdf parameterized monads], or Dan Piponi’s [http://blog.sigfpe.com/2009/02/beyond-monads.html Beyond Monads].
   
For the categorically inclined, monads can be viewed as monoids ([http://blog.sigfpe.com/2008/11/from-monoids-to-monads.html From Monoids to Monads]) and also as closure operators [http://blog.plover.com/math/monad-closure.html Triples and Closure]. Derek Elkins’ article in [http://www.haskell.org/wikiupload/8/85/TMR-Issue13.pdf issue 13 of the Monad.Reader] contains an exposition of the category-theoretic underpinnings of some of the standard <code>Monad</code> instances, such as <code>State</code> and <code>Cont</code>. Jonathan Hill and Keith Clarke have [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.6497 an early paper explaining the connection between monads as they arise in category theory and as used in functional programming]. There is also a [http://okmij.org/ftp/Computation/IO-monad-history.html web page by Oleg Kiselyov] explaining the history of the IO monad.
+
For the categorically inclined, monads can be viewed as monoids ([http://blog.sigfpe.com/2008/11/from-monoids-to-monads.html From Monoids to Monads]) and also as closure operators ([http://blog.plover.com/math/monad-closure.html Triples and Closure]). Derek Elkins’ article in [http://www.haskell.org/wikiupload/8/85/TMR-Issue13.pdf issue 13 of the Monad.Reader] contains an exposition of the category-theoretic underpinnings of some of the standard <code>Monad</code> instances, such as <code>State</code> and <code>Cont</code>. Jonathan Hill and Keith Clarke have [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.6497 an early paper explaining the connection between monads as they arise in category theory and as used in functional programming]. There is also a [http://okmij.org/ftp/Computation/IO-monad-history.html web page by Oleg Kiselyov] explaining the history of the IO monad.
   
 
Links to many more research papers related to monads can be found under [[Research papers/Monads and arrows]].
 
Links to many more research papers related to monads can be found under [[Research papers/Monads and arrows]].
  +
  +
=MonadFail=
  +
  +
Some monads support a notion of ''failure'', without necessarily supporting the notion of ''recovery'' suggested by <code>MonadPlus</code>, and possibly including a primitive error reporting mechanism. This notion is expressed by the relatively unprincipled <code>MonadFail</code>. Since GHC 8.8, the <code>fail</code> method from <code>MonadFail</code> is used for pattern match failure in <code>do</code> bindings. But here are many monads, such as <code>Reader</code>, <code>State</code>, <code>Writer</code>, <code>RWST</code>, and <code>Cont</code> that simply do not support a legitimate <code>fail</code> method, so they have no <code>MonadFail</code> instance.
  +
  +
See the [https://gitlab.haskell.org/haskell/prime/-/wikis/libraries/proposals/monad-fail MonadFail proposal] for the history of the <code>fail</code> method.
  +
  +
==Definition==
  +
  +
<haskell>
  +
class Monad m => MonadFail m where
  +
fail :: String -> m a
  +
</haskell>
  +
  +
==Law==
  +
  +
<haskell>
  +
fail s >>= m = fail s
  +
</haskell>
   
 
=Monad transformers=
 
=Monad transformers=
Line 732: Line 851:
 
Much of the monad transformer library (originally [http://hackage.haskell.org/package/mtl <code>mtl</code>], now split between <code>mtl</code> and [http://hackage.haskell.org/package/transformers <code>transformers</code>]), including the <code>Reader</code>, <code>Writer</code>, <code>State</code>, and other monads, as well as the monad transformer framework itself, was inspired by Mark Jones’ classic paper [http://web.cecs.pdx.edu/~mpj/pubs/springschool.html Functional Programming with Overloading and Higher-Order Polymorphism]. It’s still very much worth a read—and highly readable—after almost fifteen years.
 
Much of the monad transformer library (originally [http://hackage.haskell.org/package/mtl <code>mtl</code>], now split between <code>mtl</code> and [http://hackage.haskell.org/package/transformers <code>transformers</code>]), including the <code>Reader</code>, <code>Writer</code>, <code>State</code>, and other monads, as well as the monad transformer framework itself, was inspired by Mark Jones’ classic paper [http://web.cecs.pdx.edu/~mpj/pubs/springschool.html Functional Programming with Overloading and Higher-Order Polymorphism]. It’s still very much worth a read—and highly readable—after almost fifteen years.
   
See [http://article.gmane.org/gmane.comp.lang.haskell.libraries/17139 Edward Kmett's mailing list message] for a description of the history and relationships among monad transformer packages (<code>mtl</code>, <code>transformers</code>, <code>monads-fd</code>, <code>monads-tf</code>).
+
See [http://archive.fo/wxSkj Edward Kmett's mailing list message] for a description of the history and relationships among monad transformer packages (<code>mtl</code>, <code>transformers</code>, <code>monads-fd</code>, <code>monads-tf</code>).
   
There are two excellent references on monad transformers. Martin Grabmüller’s [http://www.grabmueller.de/martin/www/pub/Transformers.en.html Monad Transformers Step by Step] is a thorough description, with running examples, of how to use monad transformers to elegantly build up computations with various effects. [http://cale.yi.org/index.php/How_To_Use_Monad_Transformers Cale Gibbard’s article] on how to use monad transformers is more practical, describing how to structure code using monad transformers to make writing it as painless as possible. Another good starting place for learning about monad transformers is a [http://blog.sigfpe.com/2006/05/grok-haskell-monad-transformers.html blog post by Dan Piponi].
+
There are two excellent references on monad transformers. Martin Grabmüller’s [https://github.com/mgrabmueller/TransformersStepByStep/blob/master/Transformers.lhs Monad Transformers Step by Step] is a thorough description, with running examples, of how to use monad transformers to elegantly build up computations with various effects. [http://cale.yi.org/index.php/How_To_Use_Monad_Transformers Cale Gibbard’s article] on how to use monad transformers is more practical, describing how to structure code using monad transformers to make writing it as painless as possible. Another good starting place for learning about monad transformers is a [http://blog.sigfpe.com/2006/05/grok-haskell-monad-transformers.html blog post by Dan Piponi].
   
 
The <code>ListT</code> transformer from the <code>transformers</code> package comes with the caveat that <code>ListT m</code> is only a monad when <code>m</code> is ''commutative'', that is, when <code>ma >>= \a -> mb >>= \b -> foo</code> is equivalent to <code>mb >>= \b -> ma >>= \a -> foo</code> (i.e. the order of <code>m</code>'s effects does not matter). For one explanation why, see Dan Piponi's blog post [http://blog.sigfpe.com/2006/11/why-isnt-listt-monad.html "Why isn't <code><nowiki>ListT []</nowiki></code> a monad"]. For more examples, as well as a design for a version of <code>ListT</code> which does not have this problem, see [http://www.haskell.org/haskellwiki/ListT_done_right <code>ListT</code> done right].
 
The <code>ListT</code> transformer from the <code>transformers</code> package comes with the caveat that <code>ListT m</code> is only a monad when <code>m</code> is ''commutative'', that is, when <code>ma >>= \a -> mb >>= \b -> foo</code> is equivalent to <code>mb >>= \b -> ma >>= \a -> foo</code> (i.e. the order of <code>m</code>'s effects does not matter). For one explanation why, see Dan Piponi's blog post [http://blog.sigfpe.com/2006/11/why-isnt-listt-monad.html "Why isn't <code><nowiki>ListT []</nowiki></code> a monad"]. For more examples, as well as a design for a version of <code>ListT</code> which does not have this problem, see [http://www.haskell.org/haskellwiki/ListT_done_right <code>ListT</code> done right].
Line 744: Line 863:
 
''Note: <code>MonadFix</code> is included here for completeness (and because it is interesting) but seems not to be used much. Skipping this section on a first read-through is perfectly OK (and perhaps even recommended).''
 
''Note: <code>MonadFix</code> is included here for completeness (and because it is interesting) but seems not to be used much. Skipping this section on a first read-through is perfectly OK (and perhaps even recommended).''
   
==<code>mdo</code>/<code>do rec</code> notation==
+
==<code>do rec</code> notation==
   
{{note|In GHC 7.6, the flag has been changed to <code>-XRecursiveDo</code>.}}
 
  +
The <code>MonadFix</code> class describes monads which support the special fixpoint operation <code>mfix :: (a -> m a) -> m a</code>, which allows the output of monadic computations to be defined via (effectful) recursion. This is [http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#recursive-do-notation supported in GHC] by a special “recursive do” notation, enabled by the <code>-XRecursiveDo</code> flag. Within a <code>do</code> block, one may have a nested <code>rec</code> block, like so:
The <code>MonadFix</code> class describes monads which support the special fixpoint operation <code>mfix :: (a -> m a) -> m a</code>, which allows the output of monadic computations to be defined via (effectful) recursion. This is [http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#recursive-do-notation supported in GHC] by a special “recursive do” notation, enabled by the <code>-XDoRec</code> flag{{noteref}}. Within a <code>do</code> block, one may have a nested <code>rec</code> block, like so:
 
 
<haskell>
 
<haskell>
 
do { x <- foo
 
do { x <- foo
Line 804: Line 922:
 
To see this from another point of view, we can consider three possibilities. First, if <code>f</code> outputs <code>Nothing</code> without looking at its argument, then <code>maybeFix f</code> clearly returns <code>Nothing</code>. Second, if <code>f</code> always outputs <code>Just x</code>, where <code>x</code> depends on its argument, then the recursion can proceed usefully: <code>fromJust ma</code> will be able to evaluate to <code>x</code>, thus feeding <code>f</code>'s output back to it as input. Third, if <code>f</code> tries to use its argument to decide whether to output <code>Just</code> or <code>Nothing</code>, then <code>maybeFix f</code> will not terminate: evaluating <code>f</code>'s argument requires evaluating <code>ma</code> to see whether it is <code>Just</code>, which requires evaluating <code>f (fromJust ma)</code>, which requires evaluating <code>ma</code>, ... and so on.
 
To see this from another point of view, we can consider three possibilities. First, if <code>f</code> outputs <code>Nothing</code> without looking at its argument, then <code>maybeFix f</code> clearly returns <code>Nothing</code>. Second, if <code>f</code> always outputs <code>Just x</code>, where <code>x</code> depends on its argument, then the recursion can proceed usefully: <code>fromJust ma</code> will be able to evaluate to <code>x</code>, thus feeding <code>f</code>'s output back to it as input. Third, if <code>f</code> tries to use its argument to decide whether to output <code>Just</code> or <code>Nothing</code>, then <code>maybeFix f</code> will not terminate: evaluating <code>f</code>'s argument requires evaluating <code>ma</code> to see whether it is <code>Just</code>, which requires evaluating <code>f (fromJust ma)</code>, which requires evaluating <code>ma</code>, ... and so on.
   
There are also instances of <code>MonadFix</code> for lists (which works analogously to the instance for <code>Maybe</code>), for <code>ST</code>, and for <code>IO</code>. The [http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/System-IO.html#fixIO instance for <code>IO</code>] is particularly amusing: it creates a new (empty) <code>MVar</code>, immediately reads its contents using <code>unsafeInterleaveIO</code> (which delays the actual reading lazily until the value is needed), uses the contents of the <code>MVar</code> to compute a new value, which it then writes back into the <code>MVar</code>. It almost seems, spookily, that <code>mfix</code> is sending a value back in time to itself through the <code>MVar</code> -- though of course what is really going on is that the reading is delayed just long enough (via <code>unsafeInterleaveIO</code>) to get the process bootstrapped.
+
There are also instances of <code>MonadFix</code> for lists (which works analogously to the instance for <code>Maybe</code>), for <code>ST</code>, and for <code>IO</code>. The [http://hackage.haskell.org/packages/archive/base/latest/doc/html/System-IO.html#fixIO instance for <code>IO</code>] is particularly amusing: it creates a new (empty) <code>MVar</code>, immediately reads its contents using <code>unsafeInterleaveIO</code> (which delays the actual reading lazily until the value is needed), uses the contents of the <code>MVar</code> to compute a new value, which it then writes back into the <code>MVar</code>. It almost seems, spookily, that <code>mfix</code> is sending a value back in time to itself through the <code>MVar</code> -- though of course what is really going on is that the reading is delayed just long enough (via <code>unsafeInterleaveIO</code>) to get the process bootstrapped.
   
 
{{Exercises|
 
{{Exercises|
Line 810: Line 928:
 
}}
 
}}
   
==GHC 7.6 changes==
 
  +
==<code>mdo</code> syntax==
   
GHC 7.6 reinstated the old <code>mdo</code> syntax, so the example at the start of this section can be written
+
The example at the start of this section can also be written
   
 
<haskell>
 
<haskell>
Line 823: Line 941:
 
</haskell>
 
</haskell>
   
which will be translated into the original example (assuming that, say, <code>bar</code> and <code>bob</code> refer to <code>y</code>. The difference is that <code>mdo</code> will analyze the code in order to find minimal recursive blocks, which will be placed in <code>rec</code> blocks, whereas <code>rec</code> blocks desugar directly into calls to <code>mfix</code> without any further analysis.
+
which will be translated into the original example (assuming that, say, <code>bar</code> and <code>bob</code> refer to <code>y</code>. The difference is that <code>mdo</code> will analyze the code in order to find minimal recursive blocks, which will be placed in <code>rec</code> blocks, whereas <code>rec</code> blocks desugar directly into calls to <code>mfix</code> without any further analysis.
  +
 
==Further reading==
 
==Further reading==
   
For more information (such as the precise desugaring rules for <code>rec</code> blocks), see Levent Erkök and John Launchbury's 2002 Haskell workshop paper, [http://sites.google.com/site/leventerkok/recdo.pdf?attredirects=0 A Recursive do for Haskell], or for full details, Levent Erkök’s thesis, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.15.1543&rep=rep1&type=pdf Value Recursion in Monadic Computations]. (Note, while reading, that <code>MonadFix</code> used to be called <code>MonadRec</code>.) You can also read the [http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#recursive-do-notation GHC user manual section on recursive do-notation].
+
For more information (such as the precise desugaring rules for <code>rec</code> blocks), see Levent Erkök and John Launchbury's 2002 Haskell workshop paper, [http://sites.google.com/site/leventerkok/recdo.pdf?attredirects=0 A Recursive do for Haskell], or for full details, Levent Erkök’s thesis, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.15.1543&rep=rep1&type=pdf Value Recursion in Monadic Computations]. (Note, while reading, that <code>MonadFix</code> used to be called <code>MonadRec</code>.) You can also read the [https://downloads.haskell.org/ghc/latest/docs/html/users_guide/glasgow_exts.html#extension-RecursiveDo GHC user manual section on recursive do-notation].
   
 
=Semigroup=
 
=Semigroup=
Line 839: Line 957:
 
==Definition==
 
==Definition==
   
Semigroups are not (yet?) defined in the base package, but the {{HackagePackage|id=semigroups}} package provides a standard definition.
 
  +
As of version 4.9 of the <code>base</code> package (which comes with GHC 8.0), semigroups are defined in the <code>Data.Semigroup</code> module. (If you are working with a previous version of base, or want to write a library that supports previous versions of base, you can use the <code>semigroups</code> package.)
   
The definition of the <code>Semigroup</code> type class ([http://hackage.haskell.org/packages/archive/semigroups/latest/doc/html/Data-Semigroup.html haddock]) is as follows:
+
The definition of the <code>Semigroup</code> type class ([https://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Semigroup.html haddock]) is as follows:
   
 
<haskell>
 
<haskell>
Line 848: Line 966:
   
 
sconcat :: NonEmpty a -> a
 
sconcat :: NonEmpty a -> a
sconcat = sconcat (a :| as) = go a as where
+
sconcat (a :| as) = go a as where
 
go b (c:cs) = b <> go c cs
 
go b (c:cs) = b <> go c cs
 
go b [] = b
 
go b [] = b
   
times1p :: Whole n => n -> a -> a
+
stimes :: Integral b => b -> a -> a
times1p = ...
+
stimes = ...
 
</haskell>
 
</haskell>
   
The really important method is <code>(<>)</code>, representing the associative binary operation. The other two methods have default implementations in terms of <code>(<>)</code>, and are included in the type class in case some instances can give more efficient implementations than the default. <code>sconcat</code> reduces a nonempty list using <code>(<>)</code>; <code>times1p n</code> is equivalent to (but more efficient than) <code>sconcat . replicate n</code>. See the [http://hackage.haskell.org/packages/archive/semigroups/latest/doc/html/Data-Semigroup.html haddock documentation] for more information on <code>sconcat</code> and <code>times1p</code>.
+
The really important method is <code>(<>)</code>, representing the associative binary operation. The other two methods have default implementations in terms of <code>(<>)</code>, and are included in the type class in case some instances can give more efficient implementations than the default.
  +
  +
<code>sconcat</code> reduces a nonempty list using <code>(<>)</code>. For most instances, this is the same as <code>foldr1 (<>)</code>, but it can be constant-time for idempotent semigroups.
  +
  +
<code>stimes n</code> is equivalent to (but sometimes considerably more efficient than) <code>sconcat . replicate n</code>. Its default definition uses multiplication by doubling (also known as exponentiation by squaring). For many semigroups, this is an important optimization; for some, such as lists, it is terrible and must be overridden.
  +
  +
See the [https://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Semigroup.html haddock documentation] for more information on <code>sconcat</code> and <code>stimes</code>.
   
 
==Laws==
 
==Laws==
Line 873: Line 991:
   
 
The definition of the <code>Monoid</code> type class (defined in
 
The definition of the <code>Monoid</code> type class (defined in
<code>Data.Monoid</code>; [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html haddock]) is:
+
<code>Data.Monoid</code>; [{{HackageDocs|base|Data-Monoid}} haddock]) is:
   
 
<haskell>
 
<haskell>
Line 894: Line 1,012:
 
The <code>Monoid</code> methods are rather unfortunately named; they are inspired
 
The <code>Monoid</code> methods are rather unfortunately named; they are inspired
 
by the list instance of <code>Monoid</code>, where indeed <code>mempty = []</code> and <code>mappend = (++)</code>, but this is misleading since many
 
by the list instance of <code>Monoid</code>, where indeed <code>mempty = []</code> and <code>mappend = (++)</code>, but this is misleading since many
monoids have little to do with appending (see these [http://thread.gmane.org/gmane.comp.lang.haskell.cafe/50590 Comments from OCaml Hacker Brian Hurt] on the Haskell-cafe mailing list). This was improved in GHC 7.4, where <code>(<>)</code> was added as an alias to <code>mappend</code>.
+
monoids have little to do with appending (see these [http://archive.fo/hkTOb Comments from OCaml Hacker Brian Hurt] on the Haskell-cafe mailing list). The situation is made somewhat better by <code>(<>)</code>, which is provided as an alias for <code>mappend</code>.
  +
  +
Note that the <code>(<>)</code> alias for <code>mappend</code> conflicts with the <code>Semigroup</code> method of the same name. For this reason, <code>Data.Semigroup</code> re-exports much of <code>Data.Monoid</code>; to use semigroups and monoids together, just import <code>Data.Semigroup</code>, and make sure all your types have both <code>Semigroup</code> and <code>Monoid</code> instances (and that <code>(<>) = mappend</code>).
   
 
==Laws==
 
==Laws==
Line 932: Line 1,050:
 
<li><code>Endo a</code> is a newtype wrapper for functions <code>a -> a</code>, which form a monoid under composition.</li>
 
<li><code>Endo a</code> is a newtype wrapper for functions <code>a -> a</code>, which form a monoid under composition.</li>
   
<li>There are several ways to “lift” <code>Monoid</code> instances to instances with additional structure. We have already seen that an instance for <code>a</code> can be lifted to an instance for <code>Maybe a</code>. There are also tuple instances: if <code>a</code> and <code>b</code> are instances of <code>Monoid</code>, then so is <code>(a,b)</code>, using the monoid operations for <code>a</code> and <code>b</code> in the obvious pairwise manner. Finally, if <code>a</code> is a <code>Monoid</code>, then so is the function type <code>e -> a</code> for any <code>e</code>; in particular, <code>g `mappend` h</code> is the function which applies both <code>g</code> and <code>h</code> to its argument and then combines the results using the underlying <code>Monoid</code> instance for <code>a</code>. This can be quite useful and elegant (see [http://thread.gmane.org/gmane.comp.lang.haskell.cafe/52416 example]).</li>
+
<li>There are several ways to “lift” <code>Monoid</code> instances to instances with additional structure. We have already seen that an instance for <code>a</code> can be lifted to an instance for <code>Maybe a</code>. There are also tuple instances: if <code>a</code> and <code>b</code> are instances of <code>Monoid</code>, then so is <code>(a,b)</code>, using the monoid operations for <code>a</code> and <code>b</code> in the obvious pairwise manner. Finally, if <code>a</code> is a <code>Monoid</code>, then so is the function type <code>e -> a</code> for any <code>e</code>; in particular, <code>g `mappend` h</code> is the function which applies both <code>g</code> and <code>h</code> to its argument and then combines the results using the underlying <code>Monoid</code> instance for <code>a</code>. This can be quite useful and elegant (see [http://archive.fo/dUbHK example]).</li>
   
 
<li>The type <code>Ordering = LT | EQ | GT</code> is a <code>Monoid</code>, defined in such a way that <code>mconcat (zipWith compare xs ys)</code> computes the lexicographic ordering of <code>xs</code> and <code>ys</code> (if <code>xs</code> and <code>ys</code> have the same length). In particular, <code>mempty = EQ</code>, and <code>mappend</code> evaluates to its leftmost non-<code>EQ</code> argument (or <code>EQ</code> if both arguments are <code>EQ</code>). This can be used together with the function instance of <code>Monoid</code> to do some clever things ([http://www.reddit.com/r/programming/comments/7cf4r/monoids_in_my_programming_language/c06adnx example]).</li>
 
<li>The type <code>Ordering = LT | EQ | GT</code> is a <code>Monoid</code>, defined in such a way that <code>mconcat (zipWith compare xs ys)</code> computes the lexicographic ordering of <code>xs</code> and <code>ys</code> (if <code>xs</code> and <code>ys</code> have the same length). In particular, <code>mempty = EQ</code>, and <code>mappend</code> evaluates to its leftmost non-<code>EQ</code> argument (or <code>EQ</code> if both arguments are <code>EQ</code>). This can be used together with the function instance of <code>Monoid</code> to do some clever things ([http://www.reddit.com/r/programming/comments/7cf4r/monoids_in_my_programming_language/c06adnx example]).</li>
Line 944: Line 1,062:
 
<haskell>
 
<haskell>
 
instance Monoid e => Applicative ((,) e) where
 
instance Monoid e => Applicative ((,) e) where
  +
pure :: Monoid e => a -> (e,a)
 
pure x = (mempty, x)
 
pure x = (mempty, x)
  +
  +
(<*>) :: Monoid e => (e,a -> b) -> (e,a) -> (e,b)
 
(u, f) <*> (v, x) = (u `mappend` v, f x)
 
(u, f) <*> (v, x) = (u `mappend` v, f x)
 
</haskell>
 
</haskell>
Line 952: Line 1,073:
 
<code>Monoid</code> also plays a key role in the <code>Foldable</code> type class (see section [[#Foldable|Foldable]]).
 
<code>Monoid</code> also plays a key role in the <code>Foldable</code> type class (see section [[#Foldable|Foldable]]).
   
==Other monoidal classes: Alternative, MonadPlus, ArrowPlus==
 
  +
==Further reading==
  +
  +
Monoids got a fair bit of attention in 2009, when
  +
[http://blog.enfranchisedmind.com/2009/01/random-thoughts-on-haskell/ a blog post by Brian Hurt]
  +
complained about the fact that the names of many Haskell type classes
  +
(<code>Monoid</code> in particular) are taken from abstract mathematics. This
  +
resulted in [http://archive.fo/hkTOb a long Haskell-cafe thread]
  +
arguing the point and discussing monoids in general.
  +
  +
{{note|May its name live forever.}}
  +
  +
However, this was quickly followed by several blog posts about
  +
<code>Monoid</code> {{noteref}}. First, Dan Piponi
  +
wrote a great introductory post, [http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]. This was quickly followed by
  +
Heinrich Apfelmus’ [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees], an accessible exposition of
  +
Hinze and Paterson’s [http://www.soi.city.ac.uk/%7Eross/papers/FingerTree.html classic paper on 2-3 finger trees], which makes very clever
  +
use of <code>Monoid</code> to implement an elegant and generic data structure.
  +
Dan Piponi then wrote two fascinating articles about using <code>Monoids</code>
  +
(and finger trees): [http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html Fast Incremental Regular Expressions] and [http://blog.sigfpe.com/2009/01/beyond-regular-expressions-more.html Beyond Regular Expressions]
  +
  +
In a similar vein, David Place’s article on improving <code>Data.Map</code> in
  +
order to compute incremental folds (see [http://www.haskell.org/wikiupload/6/6a/TMR-Issue11.pdf the Monad Reader issue 11])
  +
is also a
  +
good example of using <code>Monoid</code> to generalize a data structure.
  +
  +
Some other interesting examples of <code>Monoid</code> use include [http://www.reddit.com/r/programming/comments/7cf4r/monoids_in_my_programming_language/c06adnx building elegant list sorting combinators], [http://byorgey.wordpress.com/2008/04/17/collecting-unstructured-information-with-the-monoid-of-partial-knowledge/ collecting unstructured information], [http://izbicki.me/blog/gausian-distributions-are-monoids combining probability distributions], and a brilliant series of posts by Chung-Chieh Shan and Dylan Thurston using <code>Monoid</code>s to [http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers1/ elegantly solve a difficult combinatorial puzzle] (followed by [http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers2/ part 2], [http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers3/ part 3], [http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers4/ part 4]).
  +
  +
As unlikely as it sounds, monads can actually be viewed as a sort of
  +
monoid, with <code>join</code> playing the role of the binary operation and
  +
<code>return</code> the role of the identity; see [http://blog.sigfpe.com/2008/11/from-monoids-to-monads.html Dan Piponi’s blog post].
  +
  +
=Failure and choice: Alternative, MonadPlus, ArrowPlus=
  +
  +
Several classes (<code>Applicative</code>, <code>Monad</code>, <code>Arrow</code>) have "monoidal" subclasses, intended to model computations that support "failure" and "choice" (in some appropriate sense).
  +
  +
==Definition==
   
The <code>Alternative</code> type class ([http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Applicative.html#g:2 haddock])
+
The <code>Alternative</code> type class ([{{HackageDocs|base|Control-Applicative}}#g:2 haddock])
 
is for <code>Applicative</code> functors which also have
 
is for <code>Applicative</code> functors which also have
 
a monoid structure:
 
a monoid structure:
Line 962: Line 1,118:
 
empty :: f a
 
empty :: f a
 
(<|>) :: f a -> f a -> f a
 
(<|>) :: f a -> f a -> f a
  +
  +
some :: f a -> f [a]
  +
many :: f a -> f [a]
 
</haskell>
 
</haskell>
   
Of course, instances of <code>Alternative</code> should satisfy the monoid laws
 
  +
The basic intuition is that <code>empty</code> represents some sort of "failure", and <code>(<|>)</code> represents a choice between alternatives. (However, this intuition does not fully capture the nuance possible; see the section on Laws below.) Of course, <code>(<|>)</code> should be associative and <code>empty</code> should be the identity element for it.
  +
Instances of <code>Alternative</code> must implement <code>empty</code> and <code>(&lt;|&gt;)</code>; <code>some</code> and <code>many</code> have default implementations but are included in the class since specialized implementations may be more efficient than the default.
  +
  +
The default definitions of <code>some</code> and <code>many</code> are essentially given by
   
 
<haskell>
 
<haskell>
empty <|> x = x
 
  +
some v = (:) <$> v <*> many v
x <|> empty = x
 
  +
many v = some v <|> pure []
(x <|> y) <|> z = x <|> (y <|> z)
 
 
</haskell>
 
</haskell>
   
Likewise, <code>MonadPlus</code> ([http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html#t:MonadPlus haddock])
 
  +
(though for some reason, in actual fact they are not defined via mutual recursion). The intuition is that both keep running <code>v</code>, collecting its results into a list, until it fails; <code>some v</code> requires <code>v</code> to succeed at least once, whereas <code>many v</code> does not require it to succeed at all. That is, <code>many</code> represents 0 or more repetitions of <code>v</code>, whereas <code>some</code> represents 1 or more repetitions. Note that <code>some</code> and <code>many</code> do not make sense for all instances of <code>Alternative</code>; they are discussed further below.
  +
  +
Likewise, <code>MonadPlus</code> ([{{HackageDocs|base|Control-Monad}}#t:MonadPlus haddock])
 
is for <code>Monad</code>s with a monoid structure:
 
is for <code>Monad</code>s with a monoid structure:
   
Line 981: Line 1,144:
 
</haskell>
 
</haskell>
   
The <code>MonadPlus</code> documentation states that it is intended to model
 
  +
Finally, <code>ArrowZero</code> and <code>ArrowPlus</code> ([{{HackageDocs|base|Control-Arrow}}#t:ArrowZero haddock])
monads which also support “choice and failure”; in addition to the
 
  +
represent <code>Arrow</code>s ([[#Arrow|see below]]) with a
monoid laws, instances of <code>MonadPlus</code> are expected to satisfy
 
  +
monoid structure:
   
 
<haskell>
 
<haskell>
mzero >>= f = mzero
 
  +
class Arrow arr => ArrowZero arr where
v >> mzero = mzero
 
  +
zeroArrow :: b `arr` c
  +
  +
class ArrowZero arr => ArrowPlus arr where
  +
(<+>) :: (b `arr` c) -> (b `arr` c) -> (b `arr` c)
 
</haskell>
 
</haskell>
   
which explains the sense in which <code>mzero</code> denotes failure. Since
 
  +
==Instances==
<code>mzero</code> should be the identity for <code>mplus</code>, the computation <code>m1 `mplus` m2</code> succeeds (evaluates to something other than <code>mzero</code>) if
 
  +
either <code>m1</code> or <code>m2</code> does; so <code>mplus</code> represents choice. The <code>guard</code>
 
  +
Although this document typically discusses laws before presenting example instances, for <code>Alternative</code> and friends it is worth doing things the other way around, because there is some controversy over the laws and it helps to have some concrete examples in mind when discussing them. We mostly focus on <code>Alternative</code> in this section and the next; now that <code>Applicative</code> is a superclass of <code>Monad</code>, there is little reason to use <code>MonadPlus</code> any longer, and <code>ArrowPlus</code> is rather obscure.
function can also be used with instances of <code>MonadPlus</code>; it requires a
 
  +
condition to be satisfied and fails (using <code>mzero</code>) if it is not. A
 
  +
* <code>Maybe</code> is an instance of <code>Alternative</code>, where <code>empty</code> is <code>Nothing</code> and the choice operator <code>(<|>)</code> results in its first argument when it is <code>Just</code>, and otherwise results in its second argument. Hence folding over a list of <code>Maybe</code> with <code>(<|>)</code> (which can be done with <code>asum</code> from <code>Data.Foldable</code>) results in the first non-<code>Nothing</code> value in the list (or <code>Nothing</code> if there are none).
simple example of a <code>MonadPlus</code> instance is <code>[]</code>, which is exactly the
 
  +
same as the <code>Monoid</code> instance for <code>[]</code>: the empty list represents
 
  +
* <code>[]</code> is an instance, with <code>empty</code> given by the empty list, and <code>(<|>)</code> equal to <code>(++)</code>. It is worth pointing out that this is identical to the <code>Monoid</code> instance for <code>[a]</code>, whereas the <code>Alternative</code> and <code>Monoid</code> instances for <code>Maybe</code> are different: the <code>Monoid</code> instance for <code>Maybe a</code> requires a <code>Monoid</code> instance for <code>a</code>, and monoidally combines the contained values when presented with two <code>Just</code>s.
failure, and list concatenation represents choice. In general,
 
  +
however, a <code>MonadPlus</code> instance for a type need not be the same as its
 
  +
Let's think about the behavior of <code>some</code> and <code>many</code> for <code>Maybe</code> and <code>[]</code>. For <code>Maybe</code>, we have <code>some Nothing = (:) <$> Nothing <*> many Nothing = Nothing <*> many Nothing = Nothing</code>. Hence we also have <code>many Nothing = some Nothing <|> pure [] = Nothing <|> pure [] = pure [] = Just []</code>. Boring. But what about applying <code>some</code> and <code>many</code> to <code>Just</code>? In fact, <code>some (Just a)</code> and <code>many (Just a)</code> are both bottom! The problem is that since <code>Just a</code> is always "successful", the recursion will never terminate. In theory the result "should be" the infinite list <code>[a,a,a,...]</code> but it cannot even start producing any elements of this list, because there is no way for the <code>(<*>)</code> operator to yield any output until it knows that the result of the call to <code>many</code> will be <code>Just</code>.
<code>Monoid</code> instance; <code>Maybe</code> is an example of such a type. A great
 
  +
introduction to the <code>MonadPlus</code> type class, with interesting examples
 
  +
You can work out the behavior for <code>[]</code> yourself, but it ends up being quite similar: <code>some</code> and <code>many</code> yield boring results when applied to the empty list, and yield bottom when applied to any non-empty list.
of its use, is Doug Auclair’s ''MonadPlus: What a Super Monad!'' in [http://www.haskell.org/wikiupload/6/6a/TMR-Issue11.pdf the Monad.Reader issue 11].
 
  +
  +
In the end, <code>some</code> and <code>many</code> really only make sense when used with some sort of "stateful" <code>Applicative</code> instance, for which an action <code>v</code>, when run multiple times, can succeed some finite number of times and then fail. For example, parsers have this behavior, and indeed, parsers were the original motivating example for the <code>some</code> and <code>many</code> methods; more on this below.
  +
  +
* Since GHC 8.0 (that is, <code>base-4.9</code>), there is an instance of <code>Alternative</code> for <code>IO</code>. <code>empty</code> throws an I/O exception, and <code>(<|>)</code> works by first running its left-hand argument; if the left-hand argument throws an I/O exception, <code>(<|>)</code> catches the exception and then calls its second argument. (Note that other types of exceptions are not caught.) There are other, much better ways to handle I/O errors, but this is a quick and dirty way that may work for simple, one-off programs, such as expressions typed at the GHCi prompt. For example, if you want to read the contents of a file but use some default contents in case the file does not exist, you can just write <code>readFile "somefile.txt" <|> return "default file contents"</code>.
  +
  +
* <code>Concurrently</code> from the <code>async</code> package has an <code>Alternative</code> instance, for which <code>c1 <|> c2</code> races <code>c1</code> and <code>c2</code> in parallel, and returns the result of whichever finishes first. <code>empty</code> corresponds to the action that runs forever without returning a value.
  +
  +
* Practically any parser type (e.g. from <code>parsec</code>, <code>megaparsec</code>, <code>trifecta</code>, ...) has an <code>Alternative</code> instance, where <code>empty</code> is an unconditional parse failure, and <code>(<|>)</code> is left-biased choice. That is, <code>p1 <|> p2</code> first tries parsing with <code>p1</code>, and if <code>p1</code> fails then it tries <code>p2</code> instead.
  +
  +
<code>some</code> and <code>many</code> work particularly well with parser types having an <code>Applicative</code> instance: if <code>p</code> is a parser, then <code>some p</code> parses one or more consecutive occurrences of <code>p</code> (i.e. it will parse as many occurrences of <code>p</code> as possible and then stop), and <code>many p</code> parses zero or more occurrences.
  +
  +
==Laws==
  +
  +
Of course, instances of <code>Alternative</code> should satisfy the monoid laws
  +
  +
<haskell>
  +
empty <|> x = x
  +
x <|> empty = x
  +
(x <|> y) <|> z = x <|> (y <|> z)
  +
</haskell>
  +
  +
The documentation for <code>some</code> and <code>many</code> states that they should be the "least solution" (i.e. least in the definedness partial order) to their characterizing, mutually recursive default definitions. However, [https://www.reddit.com/r/haskell/comments/2j8bvl/laws_of_some_and_many/ this is controversial], and probably wasn't really thought out very carefully.
  +
  +
Since <code>Alternative</code> is a subclass of <code>Applicative</code>, a natural question is, "how should <code>empty</code> and <code>(<|>)</code> interact with <code>(<*>)</code> and <code>pure</code>?"
  +
  +
Almost everyone agrees on the ''left zero'' law (though see the discussion of the ''right zero'' law below):
  +
  +
<haskell>
  +
empty <*> f = empty
  +
</haskell>
  +
  +
After this is where it starts to get a bit hairy though. It turns out there are several other laws one might imagine adding, and different instances satisfy different laws.
  +
  +
* ''Right Zero'':<p>Another obvious law would be <haskell>f <*> empty = empty</haskell></p><p>This law is satisfied by most instances; however, it is not satisfied by <code>IO</code>. Once the effects in <code>f</code> have been executed, there is no way to roll them back if we later encounter an exception. Now consider the <code>Backwards</code> applicative transformer from the <code>transformers</code> package. If <code>f</code> is <code>Applicative</code>, then so is <code>Backwards f</code>; it works the same way but performs the actions of the arguments to <code>(<*>)</code> in the reverse order. There is also an instance <code>Alternative f => Alternative (Backwards f)</code>. If some <code>f</code> (such as <code>IO</code>) satisfies ''left zero'' but not ''right zero'', then <code>Backwards f</code> satisfies ''right zero'' but not ''left zero''! So even the ''left zero'' law is suspect. The point is that given the existence of <code>Backwards</code> we cannot privilege one direction or the other.</p>
  +
  +
  +
* ''Left Distribution'':<p><haskell>(a <|> b) <*> c = (a <*> c) <|> (b <*> c)</haskell></p><p>This distributivity law is satisfied by <code>[]</code> and <code>Maybe</code>, as you may verify. However, it is ''not'' satisfied by <code>IO</code> or most parsers. The reason is that <code>a</code> and <code>b</code> can have effects which influence execution of <code>c</code>, and the left-hand side may end up failing where the right-hand side succeeds.</p><p>For example, consider <code>IO</code>, and suppose that <code>a</code> always executes successfully, but <code>c</code> throws an I/O exception after <code>a</code> has run. Concretely, say, <code>a</code> might ensure that a certain file does not exist (deleting it if it does exist or doing nothing if it does not), and then <code>c</code> tries to read that file. In that case <code>(a <|> b) <*> c</code> will first delete the file, ignoring <code>b</code> since <code>a</code> is successful, and then throw an exception when <code>c</code> tries to read the file. On the other hand, <code>b</code> might ensure that the same file in question ''does'' exist. In that case <code>(a <*> c) <|> (b <*> c)</code> would succeed: after <code>(a <*> c)</code> throws an exception, it would be caught by <code>(<|>)</code>, and then <code>(b <*> c)</code> would be tried.</p><p>This law does not hold for parsers for a similar reason: <code>(a <|> b) <*> c</code> has to "commit" to parsing with <code>a</code> or <code>b</code> before running <code>c</code>, whereas <code>(a <*> c) <|> (b <*> c)</code> allows backtracking if <code>a <*> c</code> fails. In the particular case that <code>a</code> succeeds but <code>c</code> fails after <code>a</code> but not after <code>b</code>, these may give different results. For example, suppose <code>a</code> and <code>c</code> both expect to see two asterisks, but <code>b</code> expects to see only one. If there are only three asterisks in the input, <code>b <*> c</code> will be successful whereas <code>a <*> c</code> will not.</p>
  +
  +
* ''Right Distribution'':<p><haskell>a <*> (b <|> c) = (a <*> b) <|> (a <*> c)</haskell></p><p>This law is not satisfied by very many instances, but it's still worth discussing. In particular the law is still satisfied by <code>Maybe</code>. However, it is ''not'' satisfied by, for example, lists. The problem is that the results come out in a different order. For example, suppose <code>a = [(+1), (*10)]</code>, <code>b = [2]</code>, and <code>c = [3]</code>. Then the left-hand side yields <code>[3,4,20,30]</code>, whereas the right-hand side is <code>[3,20,4,30]</code>.</p><p><code>IO</code> does not satisfy it either, since, for example, <code>a</code> may succeed only the ''second'' time it is executed. Parsers, on the other hand, may or may not satisfy this law, depending on how they handle backtracking. Parsers for which <code>(<|>)</code> by itself does full backtracking will satisfy the law; but for many parser combinator libraries this is not the case, for efficiency reasons. For example, parsec fails this law: if <code>a</code> succeeds while consuming some input, and afterwards <code>b</code> fails without consuming any input, then the left-hand side may succeed while the right-hand side fails: after <code>(a <*> b)</code> fails, the right-hand side tries to re-run <code>a</code> without backtracking over the input the original <code>a</code> consumed.</p>
  +
  +
* ''Left Catch'':<p><haskell>(pure a) <|> x = pure a</haskell></p><p>Intuitively, this law states that <code>pure</code> should always represent a "successful" computation. It is satisfied by <code>Maybe</code>, <code>IO</code>, and parsers. However, it is not satisfied by lists, since lists collect ''all'' possible results: it corresponds to <code>[a] ++ x == [a]</code> which is obviously false.</p>
  +
  +
This, then, is the situation: we have a lot of instances of <code>Alternative</code> (and <code>MonadPlus</code>), with each instance satisfying some ''subset'' of these laws. Moreover, it's not always the ''same'' subset, so there is no obvious "default" set of laws to choose. For now at least, we just have to live with the situation. When using a particular instance of <code>Alternative</code> or <code>MonadPlus</code>, it's worth thinking carefully about which laws it satisfies.
  +
  +
==Utility functions==
  +
  +
There are a few <code>Alternative</code>-specific utility functions worth mentioning:
  +
  +
* <haskell>guard :: Alternative f => Bool -> f ()</haskell> checks the given condition, and evaluates to <code>pure ()</code> if the condition holds, and <code>empty</code> if not. This can be used to create a conditional failure point in the middle of a computation, where the computation only proceeds if a certain condition holds.
  +
  +
* <haskell>optional :: Alternative f => f a -> f (Maybe a)</haskell> reifies potential failure into the <code>Maybe</code> type: that is, <code>optional x</code> is a computation which always succeeds, returning <code>Nothing</code> if <code>x</code> fails and <code>Just a</code> if <code>x</code> successfully results in <code>a</code>. It is useful, for example, in the context of parsers, where it corresponds to a production which can occur zero or one times.
  +
  +
==Further reading==
   
 
There used to be a type class called <code>MonadZero</code> containing only
 
There used to be a type class called <code>MonadZero</code> containing only
Line 1,014: Line 1,232:
 
required.
 
required.
   
Finally, <code>ArrowZero</code> and <code>ArrowPlus</code> ([http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Arrow.html#t:ArrowZero haddock])
 
  +
A great introduction to the <code>MonadPlus</code> type class, with interesting examples of its use, is Doug Auclair’s ''MonadPlus: What a Super Monad!'' in [http://www.haskell.org/wikiupload/6/6a/TMR-Issue11.pdf the Monad.Reader issue 11].
represent <code>Arrow</code>s ([[#Arrow|see below]]) with a
 
monoid structure:
 
   
<haskell>
 
  +
Another interesting use of <code>MonadPlus</code> can be found in Christiansen et al, [http://www-ps.informatik.uni-kiel.de/~sad/icfp2016-preprint.pdf All Sorts of Permutations], from ICFP 2016.
class Arrow arr => ArrowZero arr where
 
zeroArrow :: b `arr` c
 
   
class ArrowZero arr => ArrowPlus arr where
 
  +
The [https://hackage.haskell.org/package/logict logict package] defines a type with prominent <code>Alternative</code> and <code>MonadPlus</code> instances that can be used to efficiently enumerate possibilities subject to constraints, ''i.e.'' logic programming; it's like the list monad on steroids.
(<+>) :: (b `arr` c) -> (b `arr` c) -> (b `arr` c)
 
</haskell>
 
 
==Further reading==
 
 
Monoids have gotten a fair bit of attention recently, ultimately due
 
to
 
[http://enfranchisedmind.com/blog/posts/random-thoughts-on-haskell/ a blog post by Brian Hurt], in which he
 
complained about the fact that the names of many Haskell type classes
 
(<code>Monoid</code> in particular) are taken from abstract mathematics. This
 
resulted in [http://thread.gmane.org/gmane.comp.lang.haskell.cafe/50590 a long Haskell-cafe thread]
 
arguing the point and discussing monoids in general.
 
 
{{note|May its name live forever.}}
 
 
However, this was quickly followed by several blog posts about
 
<code>Monoid</code> {{noteref}}. First, Dan Piponi
 
wrote a great introductory post, [http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]. This was quickly followed by
 
Heinrich Apfelmus’ [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees], an accessible exposition of
 
Hinze and Paterson’s [http://www.soi.city.ac.uk/%7Eross/papers/FingerTree.html classic paper on 2-3 finger trees], which makes very clever
 
use of <code>Monoid</code> to implement an elegant and generic data structure.
 
Dan Piponi then wrote two fascinating articles about using <code>Monoids</code>
 
(and finger trees): [http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html Fast Incremental Regular Expressions] and [http://blog.sigfpe.com/2009/01/beyond-regular-expressions-more.html Beyond Regular Expressions]
 
 
In a similar vein, David Place’s article on improving <code>Data.Map</code> in
 
order to compute incremental folds (see [http://www.haskell.org/wikiupload/6/6a/TMR-Issue11.pdf the Monad Reader issue 11])
 
is also a
 
good example of using <code>Monoid</code> to generalize a data structure.
 
 
Some other interesting examples of <code>Monoid</code> use include [http://www.reddit.com/r/programming/comments/7cf4r/monoids_in_my_programming_language/c06adnx building elegant list sorting combinators], [http://byorgey.wordpress.com/2008/04/17/collecting-unstructured-information-with-the-monoid-of-partial-knowledge/ collecting unstructured information], [http://izbicki.me/blog/gausian-distributions-are-monoids combining probability distributions], and a brilliant series of posts by Chung-Chieh Shan and Dylan Thurston using <code>Monoid</code>s to [http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers1/ elegantly solve a difficult combinatorial puzzle] (followed by [http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers2/ part 2], [http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers3/ part 3], [http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers4/ part 4]).
 
 
As unlikely as it sounds, monads can actually be viewed as a sort of
 
monoid, with <code>join</code> playing the role of the binary operation and
 
<code>return</code> the role of the identity; see [http://blog.sigfpe.com/2008/11/from-monoids-to-monads.html Dan Piponi’s blog post].
 
   
 
=Foldable=
 
=Foldable=
   
 
The <code>Foldable</code> class, defined in the <code>Data.Foldable</code>
 
The <code>Foldable</code> class, defined in the <code>Data.Foldable</code>
module ([https://hackage.haskell.org/package/base-4.8.1.0/docs/Data-Foldable.html haddock]), abstracts over containers which can be
+
module ([{{HackageDocs|base|Data-Foldable}} haddock]), abstracts over containers which can be
 
“folded” into a summary value. This allows such folding operations
 
“folded” into a summary value. This allows such folding operations
 
to be written in a container-agnostic way.
 
to be written in a container-agnostic way.
Line 1,073: Line 1,253:
 
fold :: Monoid m => t m -> m
 
fold :: Monoid m => t m -> m
 
foldMap :: Monoid m => (a -> m) -> t a -> m
 
foldMap :: Monoid m => (a -> m) -> t a -> m
 
 
foldr :: (a -> b -> b) -> b -> t a -> b
 
foldr :: (a -> b -> b) -> b -> t a -> b
foldl :: (a -> b -> a) -> a -> t b -> a
+
foldr' :: (a -> b -> b) -> b -> t a -> b
  +
foldl :: (b -> a -> b) -> b -> t a -> b
  +
foldl' :: (b -> a -> b) -> b -> t a -> b
 
foldr1 :: (a -> a -> a) -> t a -> a
 
foldr1 :: (a -> a -> a) -> t a -> a
 
foldl1 :: (a -> a -> a) -> t a -> a
 
foldl1 :: (a -> a -> a) -> t a -> a
  +
toList :: t a -> [a]
  +
null :: t a -> Bool
  +
length :: t a -> Int
  +
elem :: Eq a => a -> t a -> Bool
  +
maximum :: Ord a => t a -> a
  +
minimum :: Ord a => t a -> a
  +
sum :: Num a => t a -> a
  +
product :: Num a => t a -> a
 
</haskell>
 
</haskell>
   
Line 1,083: Line 1,270:
 
you only need to implement one method: your choice of <code>foldMap</code> or
 
you only need to implement one method: your choice of <code>foldMap</code> or
 
<code>foldr</code>. All the other methods have default implementations in terms
 
<code>foldr</code>. All the other methods have default implementations in terms
of these, and are presumably included in the class in case more
+
of these, and are included in the class in case more
 
efficient implementations can be provided.
 
efficient implementations can be provided.
   
Line 1,099: Line 1,286:
 
<haskell>
 
<haskell>
 
instance Foldable [] where
 
instance Foldable [] where
  +
foldMap :: Monoid m => (a -> m) -> [a] -> m
 
foldMap g = mconcat . map g
 
foldMap g = mconcat . map g
   
Line 1,104: Line 1,292:
   
 
instance Foldable Tree where
 
instance Foldable Tree where
  +
foldMap :: Monoid m => (a -> m) -> Tree a -> m
 
foldMap f Empty = mempty
 
foldMap f Empty = mempty
 
foldMap f (Leaf x) = f x
 
foldMap f (Leaf x) = f x
 
foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
 
foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
 
</haskell>
 
</haskell>
 
The <code>foldr</code> function has a type similar to the <code>foldr</code> found in the <code>Prelude</code>, but
 
more general, since the <code>foldr</code> in the <code>Prelude</code> works only on lists.
 
   
 
The <code>Foldable</code> module also provides instances for <code>Maybe</code> and <code>Array</code>;
 
The <code>Foldable</code> module also provides instances for <code>Maybe</code> and <code>Array</code>;
Line 1,117: Line 1,303:
   
 
{{Exercises|
 
{{Exercises|
  +
# Implement <code>fold</code> in terms of <code>foldMap</code>.
  +
# What would you need in order to implement <code>foldMap</code> in terms of <code>fold</code>?
  +
# Implement <code>foldMap</code> in terms of <code>foldr</code>.
  +
# Implement <code>foldr</code> in terms of <code>foldMap</code> (hint: use the <code>Endo</code> monoid).
 
# What is the type of <code>foldMap . foldMap</code>? Or <code>foldMap . foldMap . foldMap</code>, etc.? What do they do?
 
# What is the type of <code>foldMap . foldMap</code>? Or <code>foldMap . foldMap . foldMap</code>, etc.? What do they do?
 
}}
 
}}
Line 1,141: Line 1,331:
   
 
The <code>Foldable</code> module also provides a large number of predefined
 
The <code>Foldable</code> module also provides a large number of predefined
folds, many of which are generalized versions of <code>Prelude</code> functions of the
+
folds. These used to be generalized versions of <code>Prelude</code> functions of the
same name that only work on lists: <code>concat</code>, <code>concatMap</code>, <code>and</code>,
+
same name that only worked on lists; but [https://wiki.haskell.org/Foldable_Traversable_In_Prelude as of GHC 7.10], the generalized versions themselves are now exported from the Prelude: for example, <code>concat</code>, <code>concatMap</code>, <code>and</code>,
 
<code>or</code>, <code>any</code>, <code>all</code>, <code>sum</code>, <code>product</code>, <code>maximum</code>(<code>By</code>),
 
<code>or</code>, <code>any</code>, <code>all</code>, <code>sum</code>, <code>product</code>, <code>maximum</code>(<code>By</code>),
<code>minimum</code>(<code>By</code>), <code>elem</code>, <code>notElem</code>, and <code>find</code>.
+
<code>minimum</code>(<code>By</code>), <code>elem</code>, <code>notElem</code>, and <code>find</code>. For example, before GHC 7.10, <code>length</code> used to have type <code>length :: [a] -> Int</code>; now it has type <code>Foldable t => t a -> Int</code> (and is in fact the same as the <code>containerSize</code> function shown above).
   
 
The important function <code>toList</code> is also provided, which turns any <code>Foldable</code> structure into a list of its elements in left-right order; it works by folding with the list monoid.
 
The important function <code>toList</code> is also provided, which turns any <code>Foldable</code> structure into a list of its elements in left-right order; it works by folding with the list monoid.
Line 1,157: Line 1,347:
 
structure—that is, an <code>Alternative</code> or a <code>MonadPlus</code>—then we can
 
structure—that is, an <code>Alternative</code> or a <code>MonadPlus</code>—then we can
 
use the <code>asum</code> or <code>msum</code> functions, which can combine the results as
 
use the <code>asum</code> or <code>msum</code> functions, which can combine the results as
well. Consult the [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Foldable.html <code>Foldable</code> documentation] for
+
well. Consult the [{{HackageDocs|base|Data-Foldable}} <code>Foldable</code> documentation] for
 
more details on any of these functions.
 
more details on any of these functions.
   
Line 1,169: Line 1,359:
   
 
{{Exercises|
 
{{Exercises|
# Implement <code>toList :: Foldable f {{=}}> f a -> [a]</code>.
+
# Implement <code>toList :: Foldable f {{=}}> f a -> [a]</code> in terms of either <code>foldr</code> or <code>foldMap</code>.
  +
# Show how one could implement the generic version of <code>foldr</code> in terms of <code>toList</code>, assuming we had only the list-specific <code>foldr :: (a -> b -> b) -> b -> [a] -> b</code>.
 
# Pick some of the following functions to implement: <code>concat</code>, <code>concatMap</code>, <code>and</code>, <code>or</code>, <code>any</code>, <code>all</code>, <code>sum</code>, <code>product</code>, <code>maximum</code>(<code>By</code>), <code>minimum</code>(<code>By</code>), <code>elem</code>, <code>notElem</code>, and <code>find</code>. Figure out how they generalize to <code>Foldable</code> and come up with elegant implementations using <code>fold</code> or <code>foldMap</code> along with appropriate <code>Monoid</code> instances.
 
# Pick some of the following functions to implement: <code>concat</code>, <code>concatMap</code>, <code>and</code>, <code>or</code>, <code>any</code>, <code>all</code>, <code>sum</code>, <code>product</code>, <code>maximum</code>(<code>By</code>), <code>minimum</code>(<code>By</code>), <code>elem</code>, <code>notElem</code>, and <code>find</code>. Figure out how they generalize to <code>Foldable</code> and come up with elegant implementations using <code>fold</code> or <code>foldMap</code> along with appropriate <code>Monoid</code> instances.
  +
}}
  +
  +
==Utility functions==
  +
  +
* <code>asum :: (Alternative f, Foldable t) => t (f a) -> f a</code> takes a container full of computations and combines them using <code>(<|>)</code>.
  +
  +
* <code>sequenceA_ :: (Applicative f, Foldable t) => t (f a) -> f ()</code> takes a container full of computations and runs them in sequence, discarding the results (that is, they are used only for their effects). Since the results are discarded, the container only needs to be <code>Foldable</code>. (Compare with <code>sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)</code>, which requires a stronger <code>Traversable</code> constraint in order to be able to reconstruct a container of results having the same shape as the original container.)
  +
  +
* <code>traverse_ :: (Applicative f, Foldable t) => (a -> f b) -> t a -> f ()</code> applies the given function to each element in a foldable container and sequences the effects (but discards the results).
  +
  +
* <code>for_</code> is the same as <code>traverse_</code> but with its arguments flipped. This is the moral equivalent of a "foreach" loop in an imperative language.
  +
  +
* For historical reasons, there are also variants of all the above with overly-restrictive <code>Monad</code>(-like) constraints: <code>msum</code> is the same as <code>asum</code> specialized to <code>MonadPlus</code>, and <code>sequence_</code>, <code>mapM_</code>, and <code>forM_</code> respectively are <code>Monad</code> specializations of <code>sequenceA_</code>, <code>traverse_</code>, and <code>for_</code>.
  +
  +
{{Exercises|
  +
# Implement <code>traverse_</code> in terms of <code>sequenceA_</code> and vice versa. One of these will need an extra constraint. What is it?
 
}}
 
}}
   
 
==Foldable actually isn't==
 
==Foldable actually isn't==
   
The generic term "fold" is often used to refer to the more technical concept of [[Catamorphisms|catamorphism]]. Intuitively, given a way to summarize "one level of structure" (where recursive subterms have already been replaced with their summaries), a catamorphism can summarize an entire recursive structure. It is important to realize that <code>Foldable</code> does <i>not</i> correspond to catamorphisms, but to something weaker. In particular, <code>Foldable</code> allows observing only the left-right order of elements within a structure, not the actual structure itself. Put another way, every use of <code>Foldable</code> can be expressed in terms of <code>toList</code>. For example, <code>fold</code> itself is equivalent to <code>mconcat . toList</code>.
+
The generic term "fold" is often used to refer to the more technical concept of [[Catamorphisms|catamorphism]]. Intuitively, given a way to summarize "one level of structure" (where recursive subterms have already been replaced with their summaries), a catamorphism can summarize an entire recursive structure. It is important to realize that <code>Foldable</code> does <i>not</i> correspond to catamorphisms, but to something weaker. In particular, <code>Foldable</code> allows observing only the left-right traversal order of elements within a structure, not the actual structure itself. Put another way, every use of <code>Foldable</code> can be expressed in terms of <code>toList</code>. For example, <code>fold</code> itself is equivalent to <code>mconcat . toList</code>.
   
 
This is sufficient for many tasks, but not all. For example, consider trying to compute the depth of a <code>Tree</code>: try as we might, there is no way to implement it using <code>Foldable</code>. However, it <i>can</i> be implemented as a catamorphism.
 
This is sufficient for many tasks, but not all. For example, consider trying to compute the depth of a <code>Tree</code>: try as we might, there is no way to implement it using <code>Foldable</code>. However, it <i>can</i> be implemented as a catamorphism.
Line 1,187: Line 1,393:
 
An interesting use of <code>Foldable</code> (as well as <code>Traversable</code>) can be
 
An interesting use of <code>Foldable</code> (as well as <code>Traversable</code>) can be
 
found in Janis Voigtländer’s paper [http://doi.acm.org/10.1145/1480881.1480904 Bidirectionalization for free!].
 
found in Janis Voigtländer’s paper [http://doi.acm.org/10.1145/1480881.1480904 Bidirectionalization for free!].
  +
  +
For more on the relationship between <code>fold</code>, <code>foldMap</code>, and <code>foldr</code>, see [https://byorgey.wordpress.com/2012/11/05/foldr-is-made-of-monoids/ foldr is made of monoids].
  +
  +
There was [http://tojans.me/blog/2015/10/13/foldable-for-non-haskellers-haskells-controversial-ftp-proposal/ quite a bit of controversy] in the Haskell community about a [https://wiki.haskell.org/Foldable_Traversable_In_Prelude proposal to integrate <code>Foldable</code> (and <code>Traversable</code>) more tightly into the Prelude], known as the FTP. Some of the controversy centered around <code>Foldable</code> instances such as the one for <code>((,) a)</code>, which, together with generalized types for functions such as <code>length :: Foldable t => t a -> Int</code>, allow one to derive seemingly nonsensical results such as <code>length (2,3) = 1</code>. Here is a [https://www.youtube.com/watch?v=87re_yIQMDw humorous talk] poking fun at the situation.
   
 
=Traversable=
 
=Traversable=
Line 1,193: Line 1,403:
   
 
The <code>Traversable</code> type class, defined in the <code>Data.Traversable</code>
 
The <code>Traversable</code> type class, defined in the <code>Data.Traversable</code>
module ([http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Traversable.html haddock]), is:
+
module ([{{HackageDocs|base|Data-Traversable}} haddock]), is:
   
 
<haskell>
 
<haskell>
Line 1,203: Line 1,413:
 
</haskell>
 
</haskell>
   
As you can see, every <code>Traversable</code> is also a foldable functor. Like
+
As you can see, every <code>Traversable</code> is also a <code>Foldable</code> <code>Functor</code>. To make a <code>Traversable</code> instance, it suffices to implement either <code>traverse</code> or
<code>Foldable</code>, there is a lot in this type class, but making instances is
 
actually rather easy: one need only implement <code>traverse</code> or
 
 
<code>sequenceA</code>; the other methods all have default implementations in
 
<code>sequenceA</code>; the other methods all have default implementations in
terms of these functions. A good exercise is to figure out what the default
 
  +
terms of these. Note that <code>mapM</code> and <code>sequence</code> only exist for historical reasons; especially now that <code>Applicative</code> is a superclass of <code>Monad</code>, they are nothing more than copies of <code>traverse</code> and <code>sequenceA</code>, respectively, but with more restrictive types.
implementations should be: given either <code>traverse</code> or <code>sequenceA</code>, how
 
would you define the other three methods? (Hint for <code>mapM</code>:
 
<code>Control.Applicative</code> exports the <code>WrapMonad</code> newtype, which makes any
 
<code>Monad</code> into an <code>Applicative</code>. The <code>sequence</code> function can be implemented in terms
 
of <code>mapM</code>.)
 
   
 
==Intuition==
 
==Intuition==
   
The key method of the <code>Traversable</code> class, and the source of its
 
  +
unique power, is <code>sequenceA</code>. Consider its type:
 
  +
The key method of the <code>Traversable</code> class is <code>traverse</code>, which has the following type:
  +
<haskell>
  +
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
  +
</haskell>
  +
This leads us to view <code>Traversable</code> as a generalization of <code>Functor</code>. <code>traverse</code> is an "effectful <code>fmap</code>": it allows us to map over a structure of type <code>t a</code>, applying a function to every element of type <code>a</code> in order to produce a new structure of type <code>t b</code>; but along the way the function may have some effects (captured by the applicative functor <code>f</code>).
  +
  +
Alternatively, we may consider the <code>sequenceA</code> function. Consider its type:
 
<haskell>
 
<haskell>
 
sequenceA :: Applicative f => t (f a) -> f (t a)
 
sequenceA :: Applicative f => t (f a) -> f (t a)
Line 1,232: Line 1,443:
 
[http://web.cecs.pdx.edu/~mpj/pubs/springschool.html Mark Jones’ paper] for more details.
 
[http://web.cecs.pdx.edu/~mpj/pubs/springschool.html Mark Jones’ paper] for more details.
   
Alternatively, looking at the type of <code>traverse</code>,
 
  +
It turns out that given a <code>Functor</code> constraint on the type <code>t</code>, <code>traverse</code> and <code>sequenceA</code> are equivalent in power: either can be implemented in terms of the other.
<haskell>
 
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
 
</haskell>
 
leads us to view <code>Traversable</code> as a generalization of <code>Functor</code>. <code>traverse</code> is an "effectful <code>fmap</code>": it allows us to map over a structure of type <code>t a</code>, applying a function to every element of type <code>a</code> and in order to produce a new structure of type <code>t b</code>; but along the way the function may have some effects (captured by the applicative functor <code>f</code>).
 
   
 
{{Exercises|
 
{{Exercises|
Line 1,242: Line 1,449:
 
# Give a natural way to turn a list of trees into a tree of lists.
 
# Give a natural way to turn a list of trees into a tree of lists.
 
# What is the type of <code>traverse . traverse</code>? What does it do?
 
# What is the type of <code>traverse . traverse</code>? What does it do?
  +
# Implement <code>traverse</code> in terms of <code>sequenceA</code>, and vice versa.
 
}}
 
}}
   
Line 1,256: Line 1,464:
   
 
instance Traversable Tree where
 
instance Traversable Tree where
  +
traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
 
traverse g Empty = pure Empty
 
traverse g Empty = pure Empty
 
traverse g (Leaf x) = Leaf <$> g x
 
traverse g (Leaf x) = Leaf <$> g x
Line 1,263: Line 1,472:
   
 
instance Functor Tree where
 
instance Functor Tree where
  +
fmap :: (a -> b) -> Tree a -> Tree b
 
fmap g Empty = Empty
 
fmap g Empty = Empty
 
fmap g (Leaf x) = Leaf $ g x
 
fmap g (Leaf x) = Leaf $ g x
Line 1,271: Line 1,481:
   
 
It should be clear that the <code>Traversable</code> and <code>Functor</code> instances for
 
It should be clear that the <code>Traversable</code> and <code>Functor</code> instances for
<code>Tree</code> are almost identical; the only difference is that the <code>Functor</code>
+
<code>Tree</code> are structurally identical; the only difference is that the <code>Functor</code>
 
instance involves normal function application, whereas the
 
instance involves normal function application, whereas the
 
applications in the <code>Traversable</code> instance take place within an
 
applications in the <code>Traversable</code> instance take place within an
<code>Applicative</code> context, using <code>(<$>)</code> and <code>(<*>)</code>. In fact, this will
+
<code>Applicative</code> context, using <code>(<$>)</code> and <code>(<*>)</code>. This same pattern will hold for any type.
be
 
true for any type.
 
   
 
Any <code>Traversable</code> functor is also <code>Foldable</code>, and a <code>Functor</code>. We can see
 
Any <code>Traversable</code> functor is also <code>Foldable</code>, and a <code>Functor</code>. We can see
Line 1,282: Line 1,492:
   
 
The standard libraries provide a number of <code>Traversable</code> instances,
 
The standard libraries provide a number of <code>Traversable</code> instances,
including instances for <code>[]</code>, <code>Maybe</code>, <code>Map</code>, <code>Tree</code>, and <code>Sequence</code>.
+
including instances for <code>[]</code>, <code>ZipList</code>, <code>Maybe</code>, <code>((,) e)</code>, <code>Sum</code>, <code>Product</code>, <code>Either e</code>, <code>Map</code>, <code>Tree</code>, and <code>Sequence</code>.
 
Notably, <code>Set</code> is not <code>Traversable</code>, although it is <code>Foldable</code>.
 
Notably, <code>Set</code> is not <code>Traversable</code>, although it is <code>Foldable</code>.
   
 
{{Exercises|
 
{{Exercises|
 
# Implement <code>fmap</code> and <code>foldMap</code> using only the <code>Traversable</code> methods. (Note that the <code>Traversable</code> module provides these implementations as <code>fmapDefault</code> and <code>foldMapDefault</code>.)
 
# Implement <code>fmap</code> and <code>foldMap</code> using only the <code>Traversable</code> methods. (Note that the <code>Traversable</code> module provides these implementations as <code>fmapDefault</code> and <code>foldMapDefault</code>.)
  +
# Implement <code>Traversable</code> instances for <code>[]</code>, <code>Maybe</code>, <code>((,) e)</code>, and <code>Either e</code>.
  +
# Explain why <code>Set</code> is <code>Foldable</code> but not <code>Traversable</code>.
  +
# Show that <code>Traversable</code> functors compose: that is, implement an instance for <code>Traversable (Compose f g)</code> given <code>Traversable</code> instances for <code>f</code> and <code>g</code>.
 
}}
 
}}
   
Line 1,312: Line 1,525:
 
<code>Traversable</code> forms a core component of Edward Kmett's [http://hackage.haskell.org/package/lens lens library]. Watching [https://vimeo.com/56063074 Edward's talk on the subject] is a highly recommended way to gain better insight into <code>Traversable</code>, <code>Foldable</code>, <code>Applicative</code>, and many other things besides.
 
<code>Traversable</code> forms a core component of Edward Kmett's [http://hackage.haskell.org/package/lens lens library]. Watching [https://vimeo.com/56063074 Edward's talk on the subject] is a highly recommended way to gain better insight into <code>Traversable</code>, <code>Foldable</code>, <code>Applicative</code>, and many other things besides.
   
For references on the <code>Traversable</code> laws, see Russell O'Connor's [http://article.gmane.org/gmane.comp.lang.haskell.libraries/17778 mailing list post] (and subsequent thread).
 
  +
For references on the <code>Traversable</code> laws, see Russell O'Connor's [http://archive.fo/7XcVE mailing list post] (and subsequent thread), and [https://arxiv.org/abs/1202.2919 this paper by Jaskelioff and Rypacek] for a more in-depth discussion. Daniel Mlot also has [http://duplode.github.io/posts/traversable-a-remix.html this very nice blog post] explaining how <code>Traversable</code> arises by considering a variant on the usual Kleisli category of a monad, which also sheds light on where the <code>Traversable</code> laws come from.
  +
  +
[http://elvishjerricco.github.io/2017/03/23/applicative-sorting.html This blog post by Will Fancher] shows how to use <code>Traversable</code> along with a clever choice of <code>Applicative</code> to efficiently sort any <code>Traversable</code> container.
  +
  +
=Bifunctor=
  +
  +
Recall that a <code>Functor</code> is a type of kind <code>* -> *</code> where one can "map" a function over the type parameter. <code>(Either e)</code> is a <code>Functor</code> (with <code>fmap :: (a -> b) -> Either e a -> Either e b</code>), as is <code>((,) e)</code>. But there is something oddly asymmetric about these two examples: in principle, there is no reason we can't map over the <code>e</code> instead of the <code>a</code>, for example, like so: <code>lmap :: (e -> e') -> Either e a -> Either e' a</code>. This observation leads directly to the definition of <code>Bifunctor</code>, a class for types of kind <code>* -> * -> *</code> where one can functorially map over ''both'' type parameters.
  +
  +
==Definition==
  +
  +
Here is the type class declaration for <code>Bifunctor</code>, defined
  +
in <code>Data.Bifunctor</code> (since <code>base-4.8</code>, which came with GHC 7.10):
  +
  +
<haskell>
  +
class Bifunctor p where
  +
bimap :: (a -> b) -> (c -> d) -> p a c -> p b d
  +
  +
first :: (a -> b) -> p a c -> p b c
  +
second :: (b -> c) -> p a b -> p a c
  +
</haskell>
  +
  +
We can infer from the fact that <code>p</code> is applied to two type
  +
arguments that its kind must be <code>* -> * -> *</code>. The most
  +
fundamental method of the <code>Bifunctor</code> class is
  +
<code>bimap</code>, which allows mapping over both type arguments at
  +
once. For example,
  +
  +
<haskell>
  +
bimap (+1) length (4, [1,2,3]) = (5,3)
  +
</haskell>
  +
  +
<code>first</code> and <code>second</code> are also provided for
  +
mapping over only one type argument at a time. One is required to
  +
define either <code>bimap</code>, or both <code>first</code> and
  +
<code>second</code>, since default definitions are provided for each
  +
in terms of the others, namely:
  +
  +
<haskell>
  +
bimap f g = first f . second g
  +
  +
first f = bimap f id
  +
second g = bimap id g
  +
</haskell>
  +
  +
==Laws==
  +
  +
The laws for <code>Bifunctor</code> are entirely analogous to the laws
  +
for <code>Functor</code>. First, mapping with the identity function
  +
should have no effect:
  +
  +
<haskell>
  +
bimap id id = id
  +
first id = id
  +
second id = id
  +
</haskell>
  +
  +
Second, mapping with a composition should be the same as a composition
  +
of maps:
  +
  +
<haskell>
  +
bimap (f . g) (h . i) = bimap f h . bimap g i
  +
  +
first (f . g) = first f . first g
  +
second (f . g) = second f . second g
  +
</haskell>
  +
  +
These composition laws actually come "for free" (that is, by
  +
parametricity) once the identity laws are satisfied. One can also
  +
check that the default implementations of <code>first</code> and
  +
<code>second</code> will satisfy the requisite laws if and only if
  +
<code>bimap</code> does, and vice versa.
  +
  +
There is one additional law that relates <code>bimap</code>,
  +
<code>first</code>, and <code>second</code>, namely,
  +
  +
<haskell>
  +
bimap f g = first f . second g
  +
</haskell>
  +
  +
However, this law will hold automatically if one defines only
  +
<code>bimap</code>, or only <code>first</code> and
  +
<code>second</code>, using the default implementation for the others.
  +
So you only need to worry about this law if for some reason (''e.g.''
  +
efficiency) you define all three of the methods by hand.
  +
  +
One might wonder about the symmetric law <code>bimap f g = second g
  +
. first f</code>; it turns out that once <code>bimap f g = first f
  +
. second g</code> is satisfied, the symmetric version [https://byorgey.wordpress.com/2018/03/30/parametricity-for-bifunctor/ also follows from parametricity].
  +
  +
In summary, there are many laws that can be stated, but most of them
  +
follow automatically from default definitions or from parametricity.
  +
For example, if you define only <code>bimap</code>, then the only law
  +
you actually need to check is <code>bimap id id = id</code>; all the
  +
other laws come for free. Likewise, if you define only
  +
<code>first</code> and <code>second</code>, you only need to check
  +
that <code>first id = id</code> and <code>second id = id</code>.
  +
  +
==Instances==
  +
  +
* <code>(,)</code> and <code>Either</code> are instances in the evident way.
  +
  +
* Some larger tuple constructors are also instances; for example, the instance for <code>(,,)</code> maps over the last two components, leaving the first alone. Why anyone would ever want to use this is unclear.
  +
  +
* A value of type <code>Const a b</code> (to be discussed more in a later section) consists simply of a value of type <code>a</code>; <code>bimap f g</code> maps <code>f</code> over the <code>a</code> and ignores <code>g</code>.
   
 
=Category=
 
=Category=
Line 1,318: Line 1,634:
 
<code>Category</code> is a relatively recent addition to the Haskell standard libraries. It generalizes the notion of function composition to general “morphisms”.
 
<code>Category</code> is a relatively recent addition to the Haskell standard libraries. It generalizes the notion of function composition to general “morphisms”.
   
{{note|GHC 7.6.1 changed its rules regarding types and type variables. Now, any operator at the type level is treated as a type ''constructor'' rather than a type ''variable''; prior to GHC 7.6.1 it was possible to use <code>(~&gt;)</code> instead of <code>`arr`</code>. For more information, see [http://thread.gmane.org/gmane.comp.lang.haskell.glasgow.user/21350 the discussion on the GHC-users mailing list]. For a new approach to nice arrow notation that works with GHC 7.6.1, see [http://article.gmane.org/gmane.comp.lang.haskell.glasgow.user/22615 this message] and also [http://article.gmane.org/gmane.comp.lang.haskell.glasgow.user/22616 this message] from Edward Kmett, though for simplicity I haven't adopted it here.}}
+
{{note|GHC 7.6.1 changed its rules regarding types and type variables. Now, any operator at the type level is treated as a type ''constructor'' rather than a type ''variable''; prior to GHC 7.6.1 it was possible to use <code>(~&gt;)</code> instead of <code>`arr`</code>. For more information, see [http://archive.fo/weS2f the discussion on the GHC-users mailing list]. For a new approach to nice arrow notation that works with GHC 7.6.1, see [http://archive.fo/HhdvB this message] and also [http://archive.fo/iGx6W this message] from Edward Kmett, though for simplicity I haven't adopted it here.}}
 
The definition of the <code>Category</code> type class (from
 
The definition of the <code>Category</code> type class (from
<code>Control.Category</code>; [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Category.html haddock]) is shown below. For ease of reading, note that I have used an infix type variable <code>`arr`</code>, in parallel with the infix function type constructor <code>(->)</code>. {{noteref}} This syntax is not part of Haskell 2010. The second definition shown is the one used in the standard libraries. For the remainder of this document, I will use the infix type constructor <code>`arr`</code> for <code>Category</code> as well as <code>Arrow</code>.
+
<code>Control.Category</code>; [{{HackageDocs|base|Control-Category}} haddock]) is shown below. For ease of reading, note that I have used an infix type variable <code>`arr`</code>, in parallel with the infix function type constructor <code>(->)</code>. {{noteref}} This syntax is not part of Haskell 2010. The second definition shown is the one used in the standard libraries. For the remainder of this document, I will use the infix type constructor <code>`arr`</code> for <code>Category</code> as well as <code>Arrow</code>.
   
 
<haskell>
 
<haskell>
Line 1,333: Line 1,649:
 
</haskell>
 
</haskell>
   
Note that an instance of <code>Category</code> should be a type constructor which takes two type arguments, that is, something of kind <code>* -> * -> *</code>. It is instructive to imagine the type constructor variable <code>cat</code> replaced by the function constructor <code>(->)</code>: indeed, in this case we recover precisely the familiar identity function <code>id</code> and function composition operator <code>(.)</code> defined in the standard <code>Prelude</code>.
+
Note that an instance of <code>Category</code> should be a type which takes two type arguments, that is, something of kind <code>* -> * -> *</code>. It is instructive to imagine the type variable <code>cat</code> replaced by the function constructor <code>(->)</code>: indeed, in this case we recover precisely the familiar identity function <code>id</code> and function composition operator <code>(.)</code> defined in the standard <code>Prelude</code>.
   
 
Of course, the <code>Category</code> module provides exactly such an instance of
 
Of course, the <code>Category</code> module provides exactly such an instance of
Line 1,342: Line 1,658:
   
 
instance Monad m => Category (Kleisli m) where
 
instance Monad m => Category (Kleisli m) where
  +
id :: Kleisli m a a
 
id = Kleisli return
 
id = Kleisli return
  +
  +
(.) :: Kleisli m b c -> Kleisli m a b -> Kleisli m a c
 
Kleisli g . Kleisli h = Kleisli (h >=> g)
 
Kleisli g . Kleisli h = Kleisli (h >=> g)
 
</haskell>
 
</haskell>
   
The only law that <code>Category</code> instances should satisfy is that <code>id</code> and <code>(.)</code> should form a monoid—that is, <code>id</code> should be the identity of <code>(.)</code>, and <code>(.)</code> should be associative.
+
The only laws that <code>Category</code> instances should satisfy are that <code>id</code> should be the identity of <code>(.)</code>, and <code>(.)</code> should be associative. This is kind of like being a monoid, except that, unlike with monoids, not any two values can be composed with <code>(.)</code>---their types have to match up.
   
 
Finally, the <code>Category</code> module exports two additional operators:
 
Finally, the <code>Category</code> module exports two additional operators:
Line 1,372: Line 1,691:
   
 
The definition of the <code>Arrow</code> type class, from
 
The definition of the <code>Arrow</code> type class, from
<code>Control.Arrow</code> ([http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Arrow.html haddock]), is:
+
<code>Control.Arrow</code> ([{{HackageDocs|base|Control-Arrow}} haddock]), is:
   
 
<haskell>
 
<haskell>
Line 1,399: Line 1,718:
 
included in the <code>Arrow</code> class so that they can be overridden with more
 
included in the <code>Arrow</code> class so that they can be overridden with more
 
efficient implementations if desired.
 
efficient implementations if desired.
  +
  +
Note that <code>first</code> and <code>second</code> conflict with methods of the same name from <code>Data.Bifunctor</code>. If you want to use both for some reason, you will need to import one or both qualified. It used to be common to import <code>Control.Arrow</code> just to get the <code>(->)</code> instance for use in editing pairs using <code>first</code> or <code>second</code>; now it is recommended to import <code>Data.Bifunctor</code> for this purpose instead. (Notice that for the <code>(->)</code> instance of <code>Arrow</code> and the <code>(,)</code> instance of <code>Bifunctor</code>, <code>first</code> and <code>second</code> specialize to the same type.)
   
 
==Intuition==
 
==Intuition==
Line 1,424: Line 1,745:
 
<haskell>
 
<haskell>
 
instance Arrow (->) where
 
instance Arrow (->) where
  +
arr :: (b -> c) -> (b -> c)
 
arr g = g
 
arr g = g
  +
  +
first :: (b -> c) -> ((b,d) -> (c,d))
 
first g (x,y) = (g x, y)
 
first g (x,y) = (g x, y)
   
Line 1,430: Line 1,754:
   
 
instance Monad m => Arrow (Kleisli m) where
 
instance Monad m => Arrow (Kleisli m) where
  +
arr :: (b -> c) -> Kleisli m b c
 
arr f = Kleisli (return . f)
 
arr f = Kleisli (return . f)
  +
  +
first :: Kleisli m b c -> Kleisli m (b,d) (c,d)
 
first (Kleisli f) = Kleisli (\ ~(b,d) -> do c <- f b
 
first (Kleisli f) = Kleisli (\ ~(b,d) -> do c <- f b
 
return (c,d) )
 
return (c,d) )
Line 1,532: Line 1,859:
   
 
<haskell>
 
<haskell>
  +
class Arrow arr => ArrowApply arr where
  +
app :: (b `arr` c, b) `arr` c
  +
 
instance Monad m => ArrowApply (Kleisli m) where
 
instance Monad m => ArrowApply (Kleisli m) where
  +
app :: Kleisli m (Kleisli m b c, b) c
 
app = -- exercise
 
app = -- exercise
   
Line 1,538: Line 1,869:
   
 
instance ArrowApply a => Monad (ArrowMonad a) where
 
instance ArrowApply a => Monad (ArrowMonad a) where
  +
return :: b -> ArrowMonad a b
 
return = -- exercise
 
return = -- exercise
  +
  +
(>>=) :: ArrowMonad a a -> (a -> ArrowMonad a b) -> ArrowMonad a b
 
(ArrowMonad a) >>= k = -- exercise
 
(ArrowMonad a) >>= k = -- exercise
 
</haskell>
 
</haskell>
Line 1,622: Line 1,956:
 
(see [http://homepages.inf.ed.ac.uk/wadler/papers/arrows/arrows.pdf The arrow calculus]). There is also a precise technical sense in which [http://just-bottom.blogspot.de/2010/04/programming-with-effects-story-so-far.html <code>Arrow</code> can be seen as the intersection of <code>Applicative</code> and <code>Category</code>].
 
(see [http://homepages.inf.ed.ac.uk/wadler/papers/arrows/arrows.pdf The arrow calculus]). There is also a precise technical sense in which [http://just-bottom.blogspot.de/2010/04/programming-with-effects-story-so-far.html <code>Arrow</code> can be seen as the intersection of <code>Applicative</code> and <code>Category</code>].
   
Some examples of <code>Arrow</code>s include [http://www.haskell.org/yampa/ Yampa], the
+
Some examples of <code>Arrow</code>s include [https://wiki.haskell.org/Yampa Yampa], the
 
[http://www.fh-wedel.de/~si/HXmlToolbox/ Haskell XML Toolkit], and the functional GUI library [[Grapefruit]].
 
[http://www.fh-wedel.de/~si/HXmlToolbox/ Haskell XML Toolkit], and the functional GUI library [[Grapefruit]].
   
Line 1,668: Line 2,002:
 
-- position n onwards in the old Stream
 
-- position n onwards in the old Stream
 
instance Comonad Stream where
 
instance Comonad Stream where
  +
extract :: Stream a -> a
 
extract (Cons x _) = x
 
extract (Cons x _) = x
  +
  +
duplicate :: Stream a -> Stream (Stream a)
 
duplicate s@(Cons x xs) = Cons s (duplicate xs)
 
duplicate s@(Cons x xs) = Cons s (duplicate xs)
  +
  +
extend :: (Stream a -> b) -> Stream a -> Stream b
 
extend g s@(Cons x xs) = Cons (g s) (extend g xs)
 
extend g s@(Cons x xs) = Cons (g s) (extend g xs)
 
-- = fmap g (duplicate s)
 
-- = fmap g (duplicate s)

Latest revision as of 09:34, 10 December 2020

By Brent Yorgey, byorgey@gmail.com

Originally published 12 March 2009 in issue 13 of the Monad.Reader. Ported to the Haskell wiki in November 2011 by Geheimdienst.

This is now the official version of the Typeclassopedia and supersedes the version published in the Monad.Reader. Please help update and extend it by editing it yourself or by leaving comments, suggestions, and questions on the talk page.

Contents

Abstract

The standard Haskell libraries feature a number of type classes with algebraic or category-theoretic underpinnings. Becoming a fluent Haskell hacker requires intimate familiarity with them all, yet acquiring this familiarity often involves combing through a mountain of tutorials, blog posts, mailing list archives, and IRC logs.

The goal of this document is to serve as a starting point for the student of Haskell wishing to gain a firm grasp of its standard type classes. The essentials of each type class are introduced, with examples, commentary, and extensive references for further reading.

Introduction

Have you ever had any of the following thoughts?

  • What the heck is a monoid, and how is it different from a monad?
  • I finally figured out how to use Parsec with do-notation, and someone told me I should use something called Applicative instead. Um, what?
  • Someone in the #haskell IRC channel used (***), and when I asked Lambdabot to tell me its type, it printed out scary gobbledygook that didn’t even fit on one line! Then someone used fmap fmap fmap and my brain exploded.
  • When I asked how to do something I thought was really complicated, people started typing things like zip.ap fmap.(id &&& wtf) and the scary thing is that they worked! Anyway, I think those people must actually be robots because there’s no way anyone could come up with that in two seconds off the top of their head.

If you have, look no further! You, too, can write and understand concise, elegant, idiomatic Haskell code with the best of them.

There are two keys to an expert Haskell hacker’s wisdom:

  1. Understand the types.
  2. Gain a deep intuition for each type class and its relationship to other type classes, backed up by familiarity with many examples.

It’s impossible to overstate the importance of the first; the patient student of type signatures will uncover many profound secrets. Conversely, anyone ignorant of the types in their code is doomed to eternal uncertainty. “Hmm, it doesn’t compile ... maybe I’ll stick in an fmap here ... nope, let’s see ... maybe I need another (.) somewhere? ... um ...”

The second key—gaining deep intuition, backed by examples—is also important, but much more difficult to attain. A primary goal of this document is to set you on the road to gaining such intuition. However—

There is no royal road to Haskell. —Euclid

This document can only be a starting point, since good intuition comes from hard work, not from learning the right metaphor. Anyone who reads and understands all of it will still have an arduous journey ahead—but sometimes a good starting point makes a big difference.

It should be noted that this is not a Haskell tutorial; it is assumed that the reader is already familiar with the basics of Haskell, including the standard Prelude, the type system, data types, and type classes.

The type classes we will be discussing and their interrelationships (source code for this graph can be found here):

Typeclassopedia-diagram.png

Apply can be found in the semigroupoids package, and Comonad in the comonad package.

  • Solid arrows point from the general to the specific; that is, if there is an arrow from Foo to Bar it means that every Bar is (or should be, or can be made into) a Foo.
  • Dotted lines indicate some other sort of relationship.
  • Monad and ArrowApply are equivalent.
  • Apply and Comonad are greyed out since they are not actually (yet?) in the standard Haskell libraries .

One more note before we begin. The original spelling of “type class” is with two words, as evidenced by, for example, the Haskell 2010 Language Report, early papers on type classes like Type classes in Haskell and Type classes: exploring the design space, and Hudak et al.’s history of Haskell. However, as often happens with two-word phrases that see a lot of use, it has started to show up as one word (“typeclass”) or, rarely, hyphenated (“type-class”). When wearing my prescriptivist hat, I prefer “type class”, but realize (after changing into my descriptivist hat) that there's probably not much I can do about it.

Instances of List and Maybe illustrates these type classes with simple examples using List and Maybe. We now begin with the simplest type class of all: Functor.

Functor

The Functor class (haddock) is the most basic and ubiquitous type class in the Haskell libraries. A simple intuition is that a Functor represents a “container” of some sort, along with the ability to apply a function uniformly to every element in the container. For example, a list is a container of elements, and we can apply a function to every element of a list, using map. As another example, a binary tree is also a container of elements, and it’s not hard to come up with a way to recursively apply a function to every element in a tree.

Another intuition is that a Functor represents some sort of “computational context”. This intuition is generally more useful, but is more difficult to explain, precisely because it is so general. Some examples later should help to clarify the Functor-as-context point of view.

In the end, however, a Functor is simply what it is defined to be; doubtless there are many examples of Functor instances that don’t exactly fit either of the above intuitions. The wise student will focus their attention on definitions and examples, without leaning too heavily on any particular metaphor. Intuition will come, in time, on its own.

Definition

Here is the type class declaration for Functor:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

  (<$