+<sect1 id="syntax-extns">
+<title>Syntactic extensions</title>
+
+ <!-- ====================== HIERARCHICAL MODULES ======================= -->
+
+ <sect2 id="hierarchical-modules">
+ <title>Hierarchical Modules</title>
+
+ <para>GHC supports a small extension to the syntax of module
+ names: a module name is allowed to contain a dot
+ <literal>‘.’</literal>. This is also known as the
+ “hierarchical module namespace” extension, because
+ it extends the normally flat Haskell module namespace into a
+ more flexible hierarchy of modules.</para>
+
+ <para>This extension has very little impact on the language
+ itself; modules names are <emphasis>always</emphasis> fully
+ qualified, so you can just think of the fully qualified module
+ name as <quote>the module name</quote>. In particular, this
+ means that the full module name must be given after the
+ <literal>module</literal> keyword at the beginning of the
+ module; for example, the module <literal>A.B.C</literal> must
+ begin</para>
+
+<programlisting>module A.B.C</programlisting>
+
+
+ <para>It is a common strategy to use the <literal>as</literal>
+ keyword to save some typing when using qualified names with
+ hierarchical modules. For example:</para>
+
+<programlisting>
+import qualified Control.Monad.ST.Strict as ST
+</programlisting>
+
+ <para>Hierarchical modules have an impact on the way that GHC
+ searches for files. For a description, see <xref
+ linkend="finding-hierarchical-modules">.</para>
+
+ <para>GHC comes with a large collection of libraries arranged
+ hierarchically; see the accompanying library documentation.
+ There is an ongoing project to create and maintain a stable set
+ of <quote>core</quote> libraries used by several Haskell
+ compilers, and the libraries that GHC comes with represent the
+ current status of that project. For more details, see <ulink
+ url="http://www.haskell.org/~simonmar/libraries/libraries.html">Haskell
+ Libraries</ulink>.</para>
+
+ </sect2>
+
+ <!-- ====================== PATTERN GUARDS ======================= -->
+
+<sect2 id="pattern-guards">
+<title>Pattern guards</title>
+
+<para>
+<indexterm><primary>Pattern guards (Glasgow extension)</primary></indexterm>
+The discussion that follows is an abbreviated version of Simon Peyton Jones's original <ULink URL="http://research.microsoft.com/~simonpj/Haskell/guards.html">proposal</ULink>. (Note that the proposal was written before pattern guards were implemented, so refers to them as unimplemented.)
+</para>
+
+<para>
+Suppose we have an abstract data type of finite maps, with a
+lookup operation:
+
+<programlisting>
+lookup :: FiniteMap -> Int -> Maybe Int
+</programlisting>
+
+The lookup returns <function>Nothing</function> if the supplied key is not in the domain of the mapping, and <function>(Just v)</function> otherwise,
+where <VarName>v</VarName> is the value that the key maps to. Now consider the following definition:
+</para>
+
+<programlisting>
+clunky env var1 var2 | ok1 && ok2 = val1 + val2
+| otherwise = var1 + var2
+where
+ m1 = lookup env var1
+ m2 = lookup env var2
+ ok1 = maybeToBool m1
+ ok2 = maybeToBool m2
+ val1 = expectJust m1
+ val2 = expectJust m2
+</programlisting>
+
+<para>
+The auxiliary functions are
+</para>
+
+<programlisting>
+maybeToBool :: Maybe a -> Bool
+maybeToBool (Just x) = True
+maybeToBool Nothing = False
+
+expectJust :: Maybe a -> a
+expectJust (Just x) = x
+expectJust Nothing = error "Unexpected Nothing"
+</programlisting>
+
+<para>
+What is <function>clunky</function> doing? The guard <literal>ok1 &&
+ok2</literal> checks that both lookups succeed, using
+<function>maybeToBool</function> to convert the <function>Maybe</function>
+types to booleans. The (lazily evaluated) <function>expectJust</function>
+calls extract the values from the results of the lookups, and binds the
+returned values to <VarName>val1</VarName> and <VarName>val2</VarName>
+respectively. If either lookup fails, then clunky takes the
+<literal>otherwise</literal> case and returns the sum of its arguments.
+</para>
+
+<para>
+This is certainly legal Haskell, but it is a tremendously verbose and
+un-obvious way to achieve the desired effect. Arguably, a more direct way
+to write clunky would be to use case expressions:
+</para>
+
+<programlisting>
+clunky env var1 var1 = case lookup env var1 of
+ Nothing -> fail
+ Just val1 -> case lookup env var2 of
+ Nothing -> fail
+ Just val2 -> val1 + val2
+where
+ fail = val1 + val2
+</programlisting>
+
+<para>
+This is a bit shorter, but hardly better. Of course, we can rewrite any set
+of pattern-matching, guarded equations as case expressions; that is
+precisely what the compiler does when compiling equations! The reason that
+Haskell provides guarded equations is because they allow us to write down
+the cases we want to consider, one at a time, independently of each other.
+This structure is hidden in the case version. Two of the right-hand sides
+are really the same (<function>fail</function>), and the whole expression
+tends to become more and more indented.
+</para>
+
+<para>
+Here is how I would write clunky:
+</para>
+
+<programlisting>
+clunky env var1 var1
+ | Just val1 <- lookup env var1
+ , Just val2 <- lookup env var2
+ = val1 + val2
+...other equations for clunky...
+</programlisting>
+
+<para>
+The semantics should be clear enough. The qualifers are matched in order.
+For a <literal><-</literal> qualifier, which I call a pattern guard, the
+right hand side is evaluated and matched against the pattern on the left.
+If the match fails then the whole guard fails and the next equation is
+tried. If it succeeds, then the appropriate binding takes place, and the
+next qualifier is matched, in the augmented environment. Unlike list
+comprehensions, however, the type of the expression to the right of the
+<literal><-</literal> is the same as the type of the pattern to its
+left. The bindings introduced by pattern guards scope over all the
+remaining guard qualifiers, and over the right hand side of the equation.
+</para>
+
+<para>
+Just as with list comprehensions, boolean expressions can be freely mixed
+with among the pattern guards. For example:
+</para>
+
+<programlisting>
+f x | [y] <- x
+ , y > 3
+ , Just z <- h y
+ = ...
+</programlisting>
+
+<para>
+Haskell's current guards therefore emerge as a special case, in which the
+qualifier list has just one element, a boolean expression.
+</para>
+</sect2>
+
+ <!-- ===================== Recursive do-notation =================== -->
+
+<sect2 id="mdo-notation">
+<title>The recursive do-notation
+</title>
+
+<para> The recursive do-notation (also known as mdo-notation) is implemented as described in
+"A recursive do for Haskell",
+Levent Erkok, John Launchbury",
+Haskell Workshop 2002, pages: 29-37. Pittsburgh, Pennsylvania.
+</para>
+<para>
+The do-notation of Haskell 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, and this extension provides the necessary syntactic support.
+</para>
+<para>
+Here is a simple (yet contrived) example:
+</para>
+<programlisting>
+import Control.Monad.Fix
+
+justOnes = mdo xs <- Just (1:xs)
+ return xs
+</programlisting>
+<para>
+As you can guess <literal>justOnes</literal> will evaluate to <literal>Just [1,1,1,...</literal>.
+</para>
+
+<para>
+The Control.Monad.Fix library introduces the <literal>MonadFix</literal> class. It's definition is:
+</para>
+<programlisting>
+class Monad m => MonadFix m where
+ mfix :: (a -> m a) -> m a
+</programlisting>
+<para>
+The function <literal>mfix</literal>
+dictates how the required recursion operation should be performed. If recursive bindings are required for a monad,
+then that monad must be declared an instance of the <literal>MonadFix</literal> class.
+For details, see the above mentioned reference.
+</para>
+<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>
+<para>
+There are three important points in using the recursive-do notation:
+<itemizedlist>
+<listitem><para>
+The recursive version of the do-notation uses the keyword <literal>mdo</literal> (rather
+than <literal>do</literal>).
+</para></listitem>
+
+<listitem><para>
+You should <literal>import Control.Monad.Fix</literal>.
+(Note: Strictly speaking, this import is required only when you need to refer to the name
+<literal>MonadFix</literal> in your program, but the import is always safe, and the programmers
+are encouraged to always import this module when using the mdo-notation.)
+</para></listitem>
+
+<listitem><para>
+As with other extensions, ghc should be given the flag <literal>-fglasgow-exts</literal>
+</para></listitem>
+</itemizedlist>
+</para>
+
+<para>
+The web page: <ulink url="http://www.cse.ogi.edu/PacSoft/projects/rmb">http://www.cse.ogi.edu/PacSoft/projects/rmb</ulink>
+contains up to date information on recursive monadic bindings.
+</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>
+
+</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>
+
+<sect2 id="rebindable-syntax">
+<title>Rebindable syntax</title>
+
+
+ <para>GHC allows most kinds of built-in syntax to be rebound by
+ the user, to facilitate replacing the <literal>Prelude</literal>
+ with a home-grown version, for example.</para>
+
+ <para>You may want 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>-fno-implicit-prelude</option> flag causes
+ the following pieces of built-in syntax to refer to
+ <emphasis>whatever is in scope</emphasis>, not the Prelude
+ versions:</para>
+
+ <itemizedlist>
+ <listitem>
+ <para>Integer and fractional literals mean
+ "<literal>fromInteger 1</literal>" and
+ "<literal>fromRational 3.2</literal>", not the
+ Prelude-qualified versions; both in expressions and in
+ patterns. </para>
+ <para>However, the standard Prelude <literal>Eq</literal> class
+ is still used for the equality test necessary for literal patterns.</para>
+ </listitem>
+
+ <listitem>
+ <para>Negation (e.g. "<literal>- (f x)</literal>")
+ means "<literal>negate (f x)</literal>" (not
+ <literal>Prelude.negate</literal>).</para>
+ </listitem>
+
+ <listitem>
+ <para>In an n+k pattern, the standard Prelude
+ <literal>Ord</literal> class is still used for comparison,
+ but the necessary subtraction uses whatever
+ "<literal>(-)</literal>" is in scope (not
+ "<literal>Prelude.(-)</literal>").</para>
+ </listitem>
+
+ <listitem>
+ <para>"Do" notation is translated using whatever
+ functions <literal>(>>=)</literal>,
+ <literal>(>>)</literal>, <literal>fail</literal>, and
+ <literal>return</literal>, are in scope (not the Prelude
+ versions). List comprehensions, and parallel array
+ comprehensions, are unaffected. </para></listitem>
+ </itemizedlist>
+
+ <para>Be warned: this is an experimental facility, with fewer checks than
+ usual. In particular, it is essential that the functions GHC finds in scope
+ must have the appropriate types, namely:
+ <screen>
+ fromInteger :: forall a. (...) => Integer -> a
+ fromRational :: forall a. (...) => Rational -> a
+ negate :: forall a. (...) => a -> a
+ (-) :: forall a. (...) => a -> a -> a
+ (>>=) :: forall m a. (...) => m a -> (a -> m b) -> m b
+ (>>) :: forall m a. (...) => m a -> m b -> m b
+ return :: forall m a. (...) => a -> m a
+ fail :: forall m a. (...) => String -> m a
+ </screen>
+ (The (...) part can be any context including the empty context; that part
+ is up to you.)
+ If the functions don't have the right type, very peculiar things may
+ happen. Use <literal>-dcore-lint</literal> to
+ typecheck the desugared program. If Core Lint is happy you should be all right.</para>
+
+</sect2>
+</sect1>
+
+
+<!-- TYPE SYSTEM EXTENSIONS -->
+<sect1 id="type-extensions">
+<title>Type system extensions</title>
+
+<sect2 id="nullary-types">
+<title>Data types with no constructors</title>
+
+<para>With the <option>-fglasgow-exts</option> flag, GHC lets you declare
+a data type with no constructors. For example:</para>
+
+<programlisting>
+ data S -- S :: *
+ data T a -- T :: * -> *
+</programlisting>
+
+<para>Syntactically, the declaration lacks the "= constrs" part. The
+type can be parameterised over types of any kind, but if the kind is
+not <literal>*</literal> then an explicit kind annotation must be used
+(see <xref linkend="sec-kinding">).</para>
+
+<para>Such data types have only one value, namely bottom.
+Nevertheless, they can be useful when defining "phantom types".</para>
+</sect2>
+
+<sect2 id="infix-tycons">
+<title>Infix type constructors</title>
+
+<para>
+GHC allows type constructors to be operators, and to be written infix, very much
+like expressions. More specifically:
+<itemizedlist>
+<listitem><para>
+ A type constructor can be an operator, beginning with a colon; e.g. <literal>:*:</literal>.
+ The lexical syntax is the same as that for data constructors.
+ </para></listitem>
+<listitem><para>
+ Types can be written infix. For example <literal>Int :*: Bool</literal>.
+ </para></listitem>
+<listitem><para>
+ Back-quotes work
+ as for expressions, both for type constructors and type variables; e.g. <literal>Int `Either` Bool</literal>, or
+ <literal>Int `a` Bool</literal>. Similarly, parentheses work the same; e.g. <literal>(:*:) Int Bool</literal>.
+ </para></listitem>
+<listitem><para>
+ Fixities may be declared for type constructors just as for data constructors. However,
+ one cannot distinguish between the two in a fixity declaration; a fixity declaration
+ sets the fixity for a data constructor and the corresponding type constructor. For example:
+<screen>
+ infixl 7 T, :*:
+</screen>
+ sets the fixity for both type constructor <literal>T</literal> and data constructor <literal>T</literal>,
+ and similarly for <literal>:*:</literal>.
+ <literal>Int `a` Bool</literal>.
+ </para></listitem>
+<listitem><para>
+ Function arrow is <literal>infixr</literal> with fixity 0. (This might change; I'm not sure what it should be.)
+ </para></listitem>
+<listitem><para>
+ Data type and type-synonym declarations can be written infix. E.g.
+<screen>
+ data a :*: b = Foo a b
+ type a :+: b = Either a b
+</screen>
+ </para></listitem>
+<listitem><para>
+ The only thing that differs between operators in types and operators in expressions is that
+ ordinary non-constructor operators, such as <literal>+</literal> and <literal>*</literal>
+ are not allowed in types. Reason: the uniform thing to do would be to make them type
+ variables, but that's not very useful. A less uniform but more useful thing would be to
+ allow them to be type <emphasis>constructors</emphasis>. But that gives trouble in export
+ lists. So for now we just exclude them.
+ </para></listitem>
+
+</itemizedlist>
+</para>
+</sect2>
+
+<sect2 id="sec-kinding">
+<title>Explicitly-kinded quantification</title>
+
+<para>
+Haskell infers the kind of each type variable. Sometimes it is nice to be able
+to give the kind explicitly as (machine-checked) documentation,
+just as it is nice to give a type signature for a function. On some occasions,
+it is essential to do so. For example, in his paper "Restricted Data Types in Haskell" (Haskell Workshop 1999)
+John Hughes had to define the data type:
+<Screen>
+ data Set cxt a = Set [a]
+ | Unused (cxt a -> ())
+</Screen>
+The only use for the <literal>Unused</literal> constructor was to force the correct
+kind for the type variable <literal>cxt</literal>.
+</para>
+<para>
+GHC now instead allows you to specify the kind of a type variable directly, wherever
+a type variable is explicitly bound. Namely:
+<itemizedlist>
+<listitem><para><literal>data</literal> declarations:
+<Screen>
+ data Set (cxt :: * -> *) a = Set [a]
+</Screen></para></listitem>
+<listitem><para><literal>type</literal> declarations:
+<Screen>
+ type T (f :: * -> *) = f Int
+</Screen></para></listitem>
+<listitem><para><literal>class</literal> declarations:
+<Screen>
+ class (Eq a) => C (f :: * -> *) a where ...
+</Screen></para></listitem>
+<listitem><para><literal>forall</literal>'s in type signatures:
+<Screen>
+ f :: forall (cxt :: * -> *). Set cxt Int
+</Screen></para></listitem>
+</itemizedlist>
+</para>
+
+<para>
+The parentheses are required. Some of the spaces are required too, to
+separate the lexemes. If you write <literal>(f::*->*)</literal> you
+will get a parse error, because "<literal>::*->*</literal>" is a
+single lexeme in Haskell.
+</para>
+
+<para>
+As part of the same extension, you can put kind annotations in types
+as well. Thus:
+<Screen>
+ f :: (Int :: *) -> Int
+ g :: forall a. a -> (a :: *)
+</Screen>
+The syntax is
+<Screen>
+ atype ::= '(' ctype '::' kind ')
+</Screen>
+The parentheses are required.
+</para>
+</sect2>
+
+
+<sect2 id="class-method-types">
+<title>Class method types
+</title>
+<para>
+Haskell 98 prohibits class method types to mention constraints on the
+class type variable, thus:
+<programlisting>
+ class Seq s a where
+ fromList :: [a] -> s a
+ elem :: Eq a => a -> s a -> Bool
+</programlisting>
+The type of <literal>elem</literal> is illegal in Haskell 98, because it
+contains the constraint <literal>Eq a</literal>, constrains only the
+class type variable (in this case <literal>a</literal>).
+</para>
+<para>
+With the <option>-fglasgow-exts</option> GHC lifts this restriction.
+</para>
+
+</sect2>
+
+<sect2 id="multi-param-type-classes">
+<title>Multi-parameter type classes
+</title>
+
+<para>
+This section documents GHC's implementation of multi-parameter type
+classes. There's lots of background in the paper <ULink
+URL="http://research.microsoft.com/~simonpj/multi.ps.gz" >Type
+classes: exploring the design space</ULink > (Simon Peyton Jones, Mark
+Jones, Erik Meijer).
+</para>
+
+
+<sect3 id="type-restrictions">
+<title>Types</title>
+
+<para>
+GHC imposes the following restrictions on the form of a qualified
+type, whether declared in a type signature
+or inferred. Consider the type:
+
+<programlisting>
+ forall tv1..tvn (c1, ...,cn) => type
+</programlisting>
+
+(Here, I write the "foralls" explicitly, although the Haskell source
+language omits them; in Haskell 1.4, all the free type variables of an
+explicit source-language type signature are universally quantified,
+except for the class type variables in a class declaration. However,
+in GHC, you can give the foralls if you want. See <xref LinkEnd="universal-quantification">).
+</para>
+
+<para>
+
+<OrderedList>
+<listitem>
+
+<para>
+ <emphasis>Each universally quantified type variable
+<literal>tvi</literal> must be reachable from <literal>type</literal></emphasis>.
+
+A type variable is "reachable" if it it is functionally dependent
+(see <xref linkend="functional-dependencies">)
+on the type variables free in <literal>type</literal>.
+The reason for this is that a value with a type that does not obey
+this restriction could not be used without introducing
+ambiguity.
+Here, for example, is an illegal type:
+
+
+<programlisting>
+ forall a. Eq a => Int
+</programlisting>
+
+
+When a value with this type was used, the constraint <literal>Eq tv</literal>
+would be introduced where <literal>tv</literal> is a fresh type variable, and
+(in the dictionary-translation implementation) the value would be
+applied to a dictionary for <literal>Eq tv</literal>. The difficulty is that we
+can never know which instance of <literal>Eq</literal> to use because we never
+get any more information about <literal>tv</literal>.
+
+</para>
+</listitem>
+<listitem>
+
+<para>
+ <emphasis>Every constraint <literal>ci</literal> must mention at least one of the
+universally quantified type variables <literal>tvi</literal></emphasis>.
+
+For example, this type is OK because <literal>C a b</literal> mentions the
+universally quantified type variable <literal>b</literal>:
+
+
+<programlisting>
+ forall a. C a b => burble
+</programlisting>
+
+
+The next type is illegal because the constraint <literal>Eq b</literal> does not
+mention <literal>a</literal>:
+
+
+<programlisting>
+ forall a. Eq b => burble
+</programlisting>
+
+
+The reason for this restriction is milder than the other one. The
+excluded types are never useful or necessary (because the offending
+context doesn't need to be witnessed at this point; it can be floated
+out). Furthermore, floating them out increases sharing. Lastly,
+excluding them is a conservative choice; it leaves a patch of
+territory free in case we need it later.
+
+</para>
+</listitem>
+
+</OrderedList>
+
+</para>
+
+
+<para>
+Unlike Haskell 1.4, constraints in types do <emphasis>not</emphasis> have to be of
+the form <emphasis>(class type-variables)</emphasis>. Thus, these type signatures
+are perfectly OK
+</para>
+
+<para>
+
+<programlisting>
+ f :: Eq (m a) => [m a] -> [m a]
+ g :: Eq [a] => ...
+</programlisting>
+
+</para>
+
+<para>
+This choice recovers principal types, a property that Haskell 1.4 does not have.
+</para>
+
+</sect3>
+
+<sect3>
+<title>Class declarations</title>
+
+<para>
+
+<OrderedList>
+<listitem>
+
+<para>
+ <emphasis>Multi-parameter type classes are permitted</emphasis>. For example:
+
+
+<programlisting>
+ class Collection c a where
+ union :: c a -> c a -> c a
+ ...etc.
+</programlisting>
+
+
+
+</para>
+</listitem>
+<listitem>