+<para>
+The do-notation of Haskell 98 does not allow <emphasis>recursive bindings</emphasis>,
+that is, the variables bound in a do-expression are visible only in the textually following
+code block. Compare this to a let-expression, where bound variables are visible in the entire binding
+group. It turns out that several applications can benefit from recursive bindings in
+the do-notation. The <option>-XDoRec</option> flag provides the necessary syntactic support.
+</para>
+<para>
+Here is a simple (albeit contrived) example:
+<programlisting>
+{-# LANGUAGE DoRec #-}
+justOnes = do { rec { xs <- Just (1:xs) }
+ ; return (map negate xs) }
+</programlisting>
+As you can guess <literal>justOnes</literal> will evaluate to <literal>Just [-1,-1,-1,...</literal>.
+</para>
+<para>
+The background and motivation for recursive do-notation is described in
+<ulink url="http://sites.google.com/site/leventerkok/">A recursive do for Haskell</ulink>,
+by Levent Erkok, John Launchbury,
+Haskell Workshop 2002, pages: 29-37. Pittsburgh, Pennsylvania.
+The theory behind monadic value recursion is explained further in Erkok's thesis
+<ulink url="http://sites.google.com/site/leventerkok/erkok-thesis.pdf">Value Recursion in Monadic Computations</ulink>.
+However, note that GHC uses a different syntax than the one described in these documents.
+</para>
+
+<sect3>
+<title>Details of recursive do-notation</title>
+<para>
+The recursive do-notation is enabled with the flag <option>-XDoRec</option> or, equivalently,
+the LANGUAGE pragma <option>DoRec</option>. It introduces the single new keyword "<literal>rec</literal>",
+which wraps a mutually-recursive group of monadic statements,
+producing a single statement.
+</para>
+<para>Similar to a <literal>let</literal>
+statement, the variables bound in the <literal>rec</literal> are
+visible throughout the <literal>rec</literal> group, and below it.
+For example, compare
+<programlisting>
+do { a <- getChar do { a <- getChar
+ ; let { r1 = f a r2 ; rec { r1 <- f a r2
+ ; r2 = g r1 } ; r2 <- g r1 }
+ ; return (r1 ++ r2) } ; return (r1 ++ r2) }
+</programlisting>
+In both cases, <literal>r1</literal> and <literal>r2</literal> are
+available both throughout the <literal>let</literal> or <literal>rec</literal> block, and
+in the statements that follow it. The difference is that <literal>let</literal> is non-monadic,
+while <literal>rec</literal> is monadic. (In Haskell <literal>let</literal> is
+really <literal>letrec</literal>, of course.)
+</para>
+<para>
+The static and dynamic semantics of <literal>rec</literal> can be described as follows:
+<itemizedlist>
+<listitem><para>
+First,
+similar to let-bindings, the <literal>rec</literal> is broken into
+minimal recursive groups, a process known as <emphasis>segmentation</emphasis>.
+For example:
+<programlisting>
+rec { a <- getChar ===> a <- getChar
+ ; b <- f a c rec { b <- f a c
+ ; c <- f b a ; c <- f b a }
+ ; putChar c } putChar c
+</programlisting>
+The details of segmentation are described in Section 3.2 of
+<ulink url="http://sites.google.com/site/leventerkok/">A recursive do for Haskell</ulink>.
+Segmentation improves polymorphism, reduces the size of the recursive "knot", and, as the paper
+describes, also has a semantic effect (unless the monad satisfies the right-shrinking law).
+</para></listitem>
+<listitem><para>
+Then each resulting <literal>rec</literal> is desugared, using a call to <literal>Control.Monad.Fix.mfix</literal>.
+For example, the <literal>rec</literal> group in the preceding example is desugared like this:
+<programlisting>
+rec { b <- f a c ===> (b,c) <- mfix (\~(b,c) -> do { b <- f a c
+ ; c <- f b a } ; c <- f b a
+ ; return (b,c) })
+</programlisting>
+In general, the statment <literal>rec <replaceable>ss</replaceable></literal>
+is desugared to the statement
+<programlisting>
+<replaceable>vs</replaceable> <- mfix (\~<replaceable>vs</replaceable> -> do { <replaceable>ss</replaceable>; return <replaceable>vs</replaceable> })
+</programlisting>
+where <replaceable>vs</replaceable> is a tuple of the variables bound by <replaceable>ss</replaceable>.
+</para><para>
+The original <literal>rec</literal> typechecks exactly
+when the above desugared version would do so. For example, this means that
+the variables <replaceable>vs</replaceable> are all monomorphic in the statements
+following the <literal>rec</literal>, because they are bound by a lambda.
+</para>
+<para>
+The <literal>mfix</literal> function is defined in the <literal>MonadFix</literal>
+class, in <literal>Control.Monad.Fix</literal>, thus:
+<programlisting>
+class Monad m => MonadFix m where
+ mfix :: (a -> m a) -> m a
+</programlisting>
+</para>
+</listitem>
+</itemizedlist>
+</para>
+<para>
+Here are some other important points in using the recursive-do notation:
+<itemizedlist>
+<listitem><para>
+It is enabled with the flag <literal>-XDoRec</literal>, which is in turn implied by
+<literal>-fglasgow-exts</literal>.
+</para></listitem>
+
+<listitem><para>
+If recursive bindings are required for a monad,
+then that monad must be declared an instance of the <literal>MonadFix</literal> class.
+</para></listitem>
+
+<listitem><para>
+The following instances of <literal>MonadFix</literal> are automatically provided: List, Maybe, IO.
+Furthermore, the Control.Monad.ST and Control.Monad.ST.Lazy modules provide the instances of the MonadFix class
+for Haskell's internal state monad (strict and lazy, respectively).
+</para></listitem>
+
+<listitem><para>
+Like <literal>let</literal> and <literal>where</literal> bindings,
+name shadowing is not allowed within a <literal>rec</literal>;
+that is, all the names bound in a single <literal>rec</literal> must
+be distinct (Section 3.3 of the paper).
+</para></listitem>
+<listitem><para>
+It supports rebindable syntax (see <xref linkend="rebindable-syntax"/>).
+</para></listitem>
+</itemizedlist>
+</para>
+</sect3>
+
+<sect3 id="mdo-notation"> <title> Mdo-notation (deprecated) </title>
+
+<para> GHC used to support the flag <option>-XRecursiveDo</option>,
+which enabled the keyword <literal>mdo</literal>, precisely as described in
+<ulink url="http://sites.google.com/site/leventerkok/">A recursive do for Haskell</ulink>,
+but this is now deprecated. Instead of <literal>mdo { Q; e }</literal>, write
+<literal>do { rec Q; e }</literal>.
+</para>
+<para>
+Historical note: The old implementation of the mdo-notation (and most
+of the existing documents) used the name
+<literal>MonadRec</literal> for the class and the corresponding library.
+This name is not supported by GHC.
+</para>
+</sect3>
+
+</sect2>
+
+
+ <!-- ===================== PARALLEL LIST COMPREHENSIONS =================== -->
+
+ <sect2 id="parallel-list-comprehensions">
+ <title>Parallel List Comprehensions</title>
+ <indexterm><primary>list comprehensions</primary><secondary>parallel</secondary>
+ </indexterm>
+ <indexterm><primary>parallel list comprehensions</primary>
+ </indexterm>
+
+ <para>Parallel list comprehensions are a natural extension to list
+ comprehensions. List comprehensions can be thought of as a nice
+ syntax for writing maps and filters. Parallel comprehensions
+ extend this to include the zipWith family.</para>
+
+ <para>A parallel list comprehension has multiple independent
+ branches of qualifier lists, each separated by a `|' symbol. For
+ example, the following zips together two lists:</para>
+
+<programlisting>
+ [ (x, y) | x <- xs | y <- ys ]
+</programlisting>
+
+ <para>The behavior of parallel list comprehensions follows that of
+ zip, in that the resulting list will have the same length as the
+ shortest branch.</para>
+
+ <para>We can define parallel list comprehensions by translation to
+ regular comprehensions. Here's the basic idea:</para>
+
+ <para>Given a parallel comprehension of the form: </para>
+
+<programlisting>
+ [ e | p1 <- e11, p2 <- e12, ...
+ | q1 <- e21, q2 <- e22, ...
+ ...
+ ]
+</programlisting>
+
+ <para>This will be translated to: </para>
+
+<programlisting>
+ [ e | ((p1,p2), (q1,q2), ...) <- zipN [(p1,p2) | p1 <- e11, p2 <- e12, ...]
+ [(q1,q2) | q1 <- e21, q2 <- e22, ...]
+ ...
+ ]
+</programlisting>
+
+ <para>where `zipN' is the appropriate zip for the given number of
+ branches.</para>
+
+ </sect2>
+
+ <!-- ===================== TRANSFORM LIST COMPREHENSIONS =================== -->
+
+ <sect2 id="generalised-list-comprehensions">
+ <title>Generalised (SQL-Like) List Comprehensions</title>
+ <indexterm><primary>list comprehensions</primary><secondary>generalised</secondary>
+ </indexterm>
+ <indexterm><primary>extended list comprehensions</primary>
+ </indexterm>
+ <indexterm><primary>group</primary></indexterm>
+ <indexterm><primary>sql</primary></indexterm>
+
+
+ <para>Generalised list comprehensions are a further enhancement to the
+ list comprehension syntactic sugar to allow operations such as sorting
+ and grouping which are familiar from SQL. They are fully described in the
+ paper <ulink url="http://research.microsoft.com/~simonpj/papers/list-comp">
+ Comprehensive comprehensions: comprehensions with "order by" and "group by"</ulink>,
+ except that the syntax we use differs slightly from the paper.</para>
+<para>The extension is enabled with the flag <option>-XTransformListComp</option>.</para>
+<para>Here is an example:
+<programlisting>
+employees = [ ("Simon", "MS", 80)
+, ("Erik", "MS", 100)
+, ("Phil", "Ed", 40)
+, ("Gordon", "Ed", 45)
+, ("Paul", "Yale", 60)]
+
+output = [ (the dept, sum salary)
+| (name, dept, salary) <- employees
+, then group by dept
+, then sortWith by (sum salary)
+, then take 5 ]
+</programlisting>
+In this example, the list <literal>output</literal> would take on
+ the value:
+
+<programlisting>
+[("Yale", 60), ("Ed", 85), ("MS", 180)]
+</programlisting>
+</para>
+<para>There are three new keywords: <literal>group</literal>, <literal>by</literal>, and <literal>using</literal>.
+(The function <literal>sortWith</literal> is not a keyword; it is an ordinary
+function that is exported by <literal>GHC.Exts</literal>.)</para>
+
+<para>There are five new forms of comprehension qualifier,
+all introduced by the (existing) keyword <literal>then</literal>:
+ <itemizedlist>
+ <listitem>
+
+<programlisting>
+then f
+</programlisting>
+
+ This statement requires that <literal>f</literal> have the type <literal>
+ forall a. [a] -> [a]</literal>. You can see an example of its use in the
+ motivating example, as this form is used to apply <literal>take 5</literal>.
+
+ </listitem>
+
+
+ <listitem>
+<para>
+<programlisting>
+then f by e
+</programlisting>
+
+ This form is similar to the previous one, but allows you to create a function
+ which will be passed as the first argument to f. As a consequence f must have
+ the type <literal>forall a. (a -> t) -> [a] -> [a]</literal>. As you can see
+ from the type, this function lets f "project out" some information
+ from the elements of the list it is transforming.</para>
+
+ <para>An example is shown in the opening example, where <literal>sortWith</literal>
+ is supplied with a function that lets it find out the <literal>sum salary</literal>
+ for any item in the list comprehension it transforms.</para>
+
+ </listitem>
+
+
+ <listitem>
+
+<programlisting>
+then group by e using f
+</programlisting>
+
+ <para>This is the most general of the grouping-type statements. In this form,
+ f is required to have type <literal>forall a. (a -> t) -> [a] -> [[a]]</literal>.
+ As with the <literal>then f by e</literal> case above, the first argument
+ is a function supplied to f by the compiler which lets it compute e on every
+ element of the list being transformed. However, unlike the non-grouping case,
+ f additionally partitions the list into a number of sublists: this means that
+ at every point after this statement, binders occurring before it in the comprehension
+ refer to <emphasis>lists</emphasis> of possible values, not single values. To help understand
+ this, let's look at an example:</para>
+
+<programlisting>
+-- This works similarly to groupWith in GHC.Exts, but doesn't sort its input first
+groupRuns :: Eq b => (a -> b) -> [a] -> [[a]]
+groupRuns f = groupBy (\x y -> f x == f y)
+
+output = [ (the x, y)
+| x <- ([1..3] ++ [1..2])
+, y <- [4..6]
+, then group by x using groupRuns ]
+</programlisting>
+
+ <para>This results in the variable <literal>output</literal> taking on the value below:</para>
+
+<programlisting>
+[(1, [4, 5, 6]), (2, [4, 5, 6]), (3, [4, 5, 6]), (1, [4, 5, 6]), (2, [4, 5, 6])]
+</programlisting>
+
+ <para>Note that we have used the <literal>the</literal> function to change the type
+ of x from a list to its original numeric type. The variable y, in contrast, is left
+ unchanged from the list form introduced by the grouping.</para>
+
+ </listitem>
+
+ <listitem>
+
+<programlisting>
+then group by e
+</programlisting>
+
+ <para>This form of grouping is essentially the same as the one described above. However,
+ since no function to use for the grouping has been supplied it will fall back on the
+ <literal>groupWith</literal> function defined in
+ <ulink url="&libraryBaseLocation;/GHC-Exts.html"><literal>GHC.Exts</literal></ulink>. This
+ is the form of the group statement that we made use of in the opening example.</para>
+
+ </listitem>
+
+
+ <listitem>
+
+<programlisting>
+then group using f
+</programlisting>
+
+ <para>With this form of the group statement, f is required to simply have the type
+ <literal>forall a. [a] -> [[a]]</literal>, which will be used to group up the
+ comprehension so far directly. An example of this form is as follows:</para>
+
+<programlisting>
+output = [ x
+| y <- [1..5]
+, x <- "hello"
+, then group using inits]
+</programlisting>
+
+ <para>This will yield a list containing every prefix of the word "hello" written out 5 times:</para>
+
+<programlisting>
+["","h","he","hel","hell","hello","helloh","hellohe","hellohel","hellohell","hellohello","hellohelloh",...]
+</programlisting>
+
+ </listitem>
+</itemizedlist>
+</para>
+ </sect2>
+
+ <!-- ===================== MONAD COMPREHENSIONS ===================== -->
+
+<sect2 id="monad-comprehensions">
+ <title>Monad comprehensions</title>
+ <indexterm><primary>monad comprehensions</primary></indexterm>
+
+ <para>
+ Monad comprehensions generalise the list comprehension notation,
+ including parallel comprehensions
+ (<xref linkend="parallel-list-comprehensions"/>) and
+ transform comprehensions (<xref linkend="generalised-list-comprehensions"/>)
+ to work for any monad.
+ </para>
+
+ <para>Monad comprehensions support:</para>
+
+ <itemizedlist>
+ <listitem>
+ <para>
+ Bindings:
+ </para>
+
+<programlisting>
+[ x + y | x <- Just 1, y <- Just 2 ]
+</programlisting>
+
+ <para>
+ Bindings are translated with the <literal>(>>=)</literal> and
+ <literal>return</literal> functions to the usual do-notation:
+ </para>
+
+<programlisting>
+do x <- Just 1
+ y <- Just 2
+ return (x+y)
+</programlisting>
+
+ </listitem>
+ <listitem>
+ <para>
+ Guards:
+ </para>
+
+<programlisting>
+[ x | x <- [1..10], x <= 5 ]
+</programlisting>
+
+ <para>
+ Guards are translated with the <literal>guard</literal> function,
+ which requires a <literal>MonadPlus</literal> instance:
+ </para>
+
+<programlisting>
+do x <- [1..10]
+ guard (x <= 5)
+ return x
+</programlisting>
+
+ </listitem>
+ <listitem>
+ <para>
+ Transform statements (as with <literal>-XTransformListComp</literal>):
+ </para>
+
+<programlisting>
+[ x+y | x <- [1..10], y <- [1..x], then take 2 ]
+</programlisting>
+
+ <para>
+ This translates to:
+ </para>
+
+<programlisting>
+do (x,y) <- take 2 (do x <- [1..10]
+ y <- [1..x]
+ return (x,y))
+ return (x+y)
+</programlisting>
+
+ </listitem>
+ <listitem>
+ <para>
+ Group statements (as with <literal>-XTransformListComp</literal>):
+ </para>
+
+<programlisting>
+[ x | x <- [1,1,2,2,3], then group by x ]
+[ x | x <- [1,1,2,2,3], then group by x using GHC.Exts.groupWith ]
+[ x | x <- [1,1,2,2,3], then group using myGroup ]
+</programlisting>
+
+ <para>
+ The basic <literal>then group by e</literal> statement is
+ translated using the <literal>mgroupWith</literal> function, which
+ requires a <literal>MonadGroup</literal> instance, defined in
+ <ulink url="&libraryBaseLocation;/Control-Monad-Group.html"><literal>Control.Monad.Group</literal></ulink>:
+ </para>
+
+<programlisting>
+do x <- mgroupWith (do x <- [1,1,2,2,3]
+ return x)
+ return x
+</programlisting>
+
+ <para>
+ Note that the type of <literal>x</literal> is changed by the
+ grouping statement.
+ </para>
+
+ <para>
+ The grouping function can also be defined with the
+ <literal>using</literal> keyword.
+ </para>
+
+ </listitem>
+ <listitem>
+ <para>
+ Parallel statements (as with <literal>-XParallelListComp</literal>):
+ </para>
+
+<programlisting>
+[ (x+y) | x <- [1..10]
+ | y <- [11..20]
+ ]
+</programlisting>
+
+ <para>
+ Parallel statements are translated using the
+ <literal>mzip</literal> function, which requires a
+ <literal>MonadZip</literal> instance defined in
+ <ulink url="&libraryBaseLocation;/Control-Monad-Zip.html"><literal>Control.Monad.Zip</literal></ulink>:
+ </para>
+
+<programlisting>
+do (x,y) <- mzip (do x <- [1..10]
+ return x)
+ (do y <- [11..20]
+ return y)
+ return (x+y)
+</programlisting>
+
+ </listitem>
+ </itemizedlist>
+
+ <para>
+ All these features are enabled by default if the
+ <literal>MonadComprehensions</literal> extension is enabled. The types
+ and more detailed examples on how to use comprehensions are explained
+ in the previous chapters <xref
+ linkend="generalised-list-comprehensions"/> and <xref
+ linkend="parallel-list-comprehensions"/>. In general you just have
+ to replace the type <literal>[a]</literal> with the type
+ <literal>Monad m => m a</literal> for monad comprehensions.
+ </para>
+
+ <para>
+ Note: Even though most of these examples are using the list monad,
+ monad comprehensions work for any monad.
+ The <literal>base</literal> package offers all necessary instances for
+ lists, which make <literal>MonadComprehensions</literal> backward
+ compatible to built-in, transform and parallel list comprehensions.
+ </para>
+<para> More formally, the desugaring is as follows. We write <literal>D[ e | Q]</literal>
+to mean the desugaring of the monad comprehension <literal>[ e | Q]</literal>:
+<programlisting>
+Expressions: e
+Declarations: d
+Lists of qualifiers: Q,R,S
+
+-- Basic forms
+D[ e | ] = return e
+D[ e | p <- e, Q ] = e >>= \p -> D[ e | Q ]
+D[ e | e, Q ] = guard e >> \p -> D[ e | Q ]
+D[ e | let d, Q ] = let d in D[ e | Q ]
+
+-- Parallel comprehensions (iterate for multiple parallel branches)
+D[ e | (Q | R), S ] = mzip D[ Qv | Q ] D[ Rv | R ] >>= \(Qv,Rv) -> D[ e | S ]
+
+-- Transform comprehensions
+D[ e | Q then f, R ] = f D[ Qv | Q ] >>= \Qv -> D[ e | R ]
+
+D[ e | Q then f by b, R ] = f b D[ Qv | Q ] >>= \Qv -> D[ e | R ]
+
+D[ e | Q then group using f, R ] = f D[ Qv | Q ] >>= \ys ->
+ case (fmap selQv1 ys, ..., fmap selQvn ys) of
+ Qv -> D[ e | R ]
+
+D[ e | Q then group by b using f, R ] = f b D[ Qv | Q ] >>= \ys ->
+ case (fmap selQv1 ys, ..., fmap selQvn ys) of
+ Qv -> D[ e | R ]
+
+where Qv is the tuple of variables bound by Q (and used subsequently)
+ selQvi is a selector mapping Qv to the ith component of Qv
+
+Operator Standard binding Expected type
+--------------------------------------------------------------------
+return GHC.Base t1 -> m t2
+(>>=) GHC.Base m1 t1 -> (t2 -> m2 t3) -> m3 t3
+(>>) GHC.Base m1 t1 -> m2 t2 -> m3 t3
+guard Control.Monad t1 -> m t2
+fmap GHC.Base forall a b. (a->b) -> n a -> n b
+mgroupWith Control.Monad.Group forall a. (a -> t) -> m1 a -> m2 (n a)
+mzip Control.Monad.Zip forall a b. m a -> m b -> m (a,b)
+</programlisting>
+The comprehension should typecheck when its desugaring would typecheck.
+</para>
+<para>
+Monad comprehensions support rebindable syntax (<xref linkend="rebindable-syntax"/>).
+Without rebindable
+syntax, the operators from the "standard binding" module are used; with
+rebindable syntax, the operators are looked up in the current lexical scope.
+For example, parallel comprehensions will be typechecked and desugared
+using whatever "<literal>mzip</literal>" is in scope.
+</para>
+<para>
+The rebindable operators must have the "Expected type" given in the
+table above. These types are surprisingly general. For example, you can
+use a bind operator with the type
+<programlisting>
+(>>=) :: T x y a -> (a -> T y z b) -> T x z b
+</programlisting>
+In the case of transform comprehensions, notice that the groups are
+parameterised over some arbitrary type <literal>n</literal> (provided it
+has an <literal>fmap</literal>, as well as
+the comprehension being over an arbitrary monad.
+</para>
+</sect2>
+
+ <!-- ===================== REBINDABLE SYNTAX =================== -->
+
+<sect2 id="rebindable-syntax">
+<title>Rebindable syntax and the implicit Prelude import</title>
+
+ <para><indexterm><primary>-XNoImplicitPrelude
+ option</primary></indexterm> GHC normally imports
+ <filename>Prelude.hi</filename> files for you. If you'd
+ rather it didn't, then give it a
+ <option>-XNoImplicitPrelude</option> option. The idea is
+ that you can then import a Prelude of your own. (But don't
+ call it <literal>Prelude</literal>; the Haskell module
+ namespace is flat, and you must not conflict with any
+ Prelude module.)</para>
+
+ <para>Suppose you are importing a Prelude of your own
+ in order to define your own numeric class
+ hierarchy. It completely defeats that purpose if the
+ literal "1" means "<literal>Prelude.fromInteger
+ 1</literal>", which is what the Haskell Report specifies.
+ So the <option>-XRebindableSyntax</option>
+ flag causes
+ the following pieces of built-in syntax to refer to
+ <emphasis>whatever is in scope</emphasis>, not the Prelude
+ versions:
+ <itemizedlist>
+ <listitem>
+ <para>An integer literal <literal>368</literal> means
+ "<literal>fromInteger (368::Integer)</literal>", rather than
+ "<literal>Prelude.fromInteger (368::Integer)</literal>".
+</para> </listitem>
+
+ <listitem><para>Fractional literals are handed in just the same way,
+ except that the translation is
+ <literal>fromRational (3.68::Rational)</literal>.
+</para> </listitem>
+
+ <listitem><para>The equality test in an overloaded numeric pattern
+ uses whatever <literal>(==)</literal> is in scope.
+</para> </listitem>
+
+ <listitem><para>The subtraction operation, and the
+ greater-than-or-equal test, in <literal>n+k</literal> patterns
+ use whatever <literal>(-)</literal> and <literal>(>=)</literal> are in scope.
+ </para></listitem>
+
+ <listitem>
+ <para>Negation (e.g. "<literal>- (f x)</literal>")