<indexterm><primary>language, GHC</primary></indexterm>
<indexterm><primary>extensions, GHC</primary></indexterm>
As with all known Haskell systems, GHC implements some extensions to
-the language. They are all enabled by options; by default GHC
-understands only plain Haskell 98.
+the language. They can all be enabled or disabled by commandline flags
+or language pragmas. By default GHC understands the most recent Haskell
+version it supports, plus a handful of extensions.
</para>
<para>
<indexterm><primary>extensions</primary><secondary>options controlling</secondary>
</indexterm>
- <para>The language option flag control what variation of the language are
- permitted. Leaving out all of them gives you standard Haskell
- 98.</para>
-
- <para>Generally speaking, all the language options are introduced by "<option>-X</option>",
- e.g. <option>-XTemplateHaskell</option>.
- </para>
-
- <para> All the language options can be turned off by using the prefix "<option>No</option>";
- e.g. "<option>-XNoTemplateHaskell</option>".</para>
-
- <para> Language options recognised by Cabal can also be enabled using the <literal>LANGUAGE</literal> pragma,
- thus <literal>{-# LANGUAGE TemplateHaskell #-}</literal> (see <xref linkend="language-pragma"/>>). </para>
-
- <para>Turning on an option that enables special syntax
- <emphasis>might</emphasis> cause working Haskell 98 code to fail
- to compile, perhaps because it uses a variable name which has
- become a reserved word. So, together with each option below, we
- list the special syntax which is enabled by this option. We use
- notation and nonterminal names from the Haskell 98 lexical syntax
- (see the Haskell 98 Report). There are two classes of special
- syntax:</para>
+ <para>The language option flags control what variation of the language are
+ permitted.</para>
+ <para>Language options can be controlled in two ways:
<itemizedlist>
- <listitem>
- <para>New reserved words and symbols: character sequences
- which are no longer available for use as identifiers in the
- program.</para>
- </listitem>
- <listitem>
- <para>Other special syntax: sequences of characters that have
- a different meaning when this particular option is turned
- on.</para>
- </listitem>
- </itemizedlist>
-
- <para>We are only listing syntax changes here that might affect
- existing working programs (i.e. "stolen" syntax). Many of these
- extensions will also enable new context-free syntax, but in all
- cases programs written to use the new syntax would not be
- compilable without the option enabled.</para>
-
- <variablelist>
-
- <varlistentry>
- <term>
- <option>-fglasgow-exts</option>:
+ <listitem><para>Every language option can switched on by a command-line flag "<option>-X...</option>"
+ (e.g. <option>-XTemplateHaskell</option>), and switched off by the flag "<option>-XNo...</option>";
+ (e.g. <option>-XNoTemplateHaskell</option>).</para></listitem>
+ <listitem><para>
+ Language options recognised by Cabal can also be enabled using the <literal>LANGUAGE</literal> pragma,
+ thus <literal>{-# LANGUAGE TemplateHaskell #-}</literal> (see <xref linkend="language-pragma"/>). </para>
+ </listitem>
+ </itemizedlist></para>
+
+ <para>The flag <option>-fglasgow-exts</option>
<indexterm><primary><option>-fglasgow-exts</option></primary></indexterm>
- </term>
- <listitem>
- <para>This simultaneously enables all of the extensions to
- Haskell 98 described in <xref
- linkend="ghc-language-features"/>, except where otherwise
- noted. We are trying to move away from this portmanteau flag,
+ is equivalent to enabling the following extensions:
+ &what_glasgow_exts_does;
+ Enabling these options is the <emphasis>only</emphasis>
+ effect of <option>-fglasgow-exts</option>.
+ We are trying to move away from this portmanteau flag,
and towards enabling features individually.</para>
- <para>New reserved words: <literal>forall</literal> (only in
- types), <literal>mdo</literal>.</para>
-
- <para>Other syntax stolen:
- <replaceable>varid</replaceable>{<literal>#</literal>},
- <replaceable>char</replaceable><literal>#</literal>,
- <replaceable>string</replaceable><literal>#</literal>,
- <replaceable>integer</replaceable><literal>#</literal>,
- <replaceable>float</replaceable><literal>#</literal>,
- <replaceable>float</replaceable><literal>##</literal>,
- <literal>(#</literal>, <literal>#)</literal>,
- <literal>|)</literal>, <literal>{|</literal>.</para>
-
- <para>Implies these specific language options:
- <option>-XForeignFunctionInterface</option>,
- <option>-XImplicitParams</option>,
- <option>-XScopedTypeVariables</option>,
- <option>-XGADTs</option>,
- <option>-XTypeFamilies</option>. </para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>
- <option>-XForeignFunctionInterface</option>:
- <indexterm><primary><option>-XForeignFunctionInterface</option></primary></indexterm>
- </term>
- <listitem>
- <para>This option enables the language extension defined in the
- Haskell 98 Foreign Function Interface Addendum.</para>
-
- <para>New reserved words: <literal>foreign</literal>.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>
- <option>-XMonomorphismRestriction</option>,<option>-XMonoPatBinds</option>:
- </term>
- <listitem>
- <para> These two flags control how generalisation is done.
- See <xref linkend="monomorphism"/>.
- </para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>
- <option>-XExtendedDefaultRules</option>:
- <indexterm><primary><option>-XExtendedDefaultRules</option></primary></indexterm>
- </term>
- <listitem>
- <para> Use GHCi's extended default rules in a regular module (<xref linkend="extended-default-rules"/>).
- Independent of the <option>-fglasgow-exts</option>
- flag. </para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>
- <option>-XOverlappingInstances</option>
- <indexterm><primary><option>-XOverlappingInstances</option></primary></indexterm>
- </term>
- <term>
- <option>-XUndecidableInstances</option>
- <indexterm><primary><option>-XUndecidableInstances</option></primary></indexterm>
- </term>
- <term>
- <option>-XIncoherentInstances</option>
- <indexterm><primary><option>-XIncoherentInstances</option></primary></indexterm>
- </term>
- <term>
- <option>-fcontext-stack=N</option>
- <indexterm><primary><option>-fcontext-stack</option></primary></indexterm>
- </term>
- <listitem>
- <para> See <xref linkend="instance-decls"/>. Only relevant
- if you also use <option>-fglasgow-exts</option>.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>
- <option>-finline-phase</option>
- <indexterm><primary><option>-finline-phase</option></primary></indexterm>
- </term>
- <listitem>
- <para>See <xref linkend="rewrite-rules"/>. Only relevant if
- you also use <option>-fglasgow-exts</option>.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>
- <option>-XArrows</option>
- <indexterm><primary><option>-XArrows</option></primary></indexterm>
- </term>
- <listitem>
- <para>See <xref linkend="arrow-notation"/>. Independent of
- <option>-fglasgow-exts</option>.</para>
-
- <para>New reserved words/symbols: <literal>rec</literal>,
- <literal>proc</literal>, <literal>-<</literal>,
- <literal>>-</literal>, <literal>-<<</literal>,
- <literal>>>-</literal>.</para>
-
- <para>Other syntax stolen: <literal>(|</literal>,
- <literal>|)</literal>.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>
- <option>-XGenerics</option>
- <indexterm><primary><option>-XGenerics</option></primary></indexterm>
- </term>
- <listitem>
- <para>See <xref linkend="generic-classes"/>. Independent of
- <option>-fglasgow-exts</option>.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term><option>-XNoImplicitPrelude</option></term>
- <listitem>
- <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>Even though you have not imported the Prelude, most of
- the built-in syntax still refers to the built-in Haskell
- Prelude types and values, as specified by the Haskell
- Report. For example, the type <literal>[Int]</literal>
- still means <literal>Prelude.[] Int</literal>; tuples
- continue to refer to the standard Prelude tuples; the
- translation for list comprehensions continues to use
- <literal>Prelude.map</literal> etc.</para>
-
- <para>However, <option>-XNoImplicitPrelude</option> does
- change the handling of certain built-in syntax: see <xref
- linkend="rebindable-syntax"/>.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term><option>-XImplicitParams</option></term>
- <listitem>
- <para>Enables implicit parameters (see <xref
- linkend="implicit-parameters"/>). Currently also implied by
- <option>-fglasgow-exts</option>.</para>
-
- <para>Syntax stolen:
- <literal>?<replaceable>varid</replaceable></literal>,
- <literal>%<replaceable>varid</replaceable></literal>.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term><option>-XOverloadedStrings</option></term>
- <listitem>
- <para>Enables overloaded string literals (see <xref
- linkend="overloaded-strings"/>).</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term><option>-XScopedTypeVariables</option></term>
- <listitem>
- <para>Enables lexically-scoped type variables (see <xref
- linkend="scoped-type-variables"/>). Implied by
- <option>-fglasgow-exts</option>.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term><option>-XTemplateHaskell</option></term>
- <listitem>
- <para>Enables Template Haskell (see <xref
- linkend="template-haskell"/>). This flag must
- be given explicitly; it is no longer implied by
- <option>-fglasgow-exts</option>.</para>
-
- <para>Syntax stolen: <literal>[|</literal>,
- <literal>[e|</literal>, <literal>[p|</literal>,
- <literal>[d|</literal>, <literal>[t|</literal>,
- <literal>$(</literal>,
- <literal>$<replaceable>varid</replaceable></literal>.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term><option>-XQuasiQuotes</option></term>
- <listitem>
- <para>Enables quasiquotation (see <xref
- linkend="th-quasiquotation"/>).</para>
-
- <para>Syntax stolen:
- <literal>[:<replaceable>varid</replaceable>|</literal>.</para>
- </listitem>
- </varlistentry>
-
- </variablelist>
</sect1>
<!-- UNBOXED TYPES AND PRIMITIVE OPERATIONS -->
<sect1 id="primitives">
<title>Unboxed types and primitive operations</title>
-<para>GHC is built on a raft of primitive data types and operations.
+<para>GHC is built on a raft of primitive data types and operations;
+"primitive" in the sense that they cannot be defined in Haskell itself.
While you really can use this stuff to write fast code,
we generally find it a lot less painful, and more satisfying in the
long run, to use higher-level language features and libraries. With
unboxed version in any case. And if it isn't, we'd like to know
about it.</para>
-<para>We do not currently have good, up-to-date documentation about the
-primitives, perhaps because they are mainly intended for internal use.
-There used to be a long section about them here in the User Guide, but it
-became out of date, and wrong information is worse than none.</para>
-
-<para>The Real Truth about what primitive types there are, and what operations
-work over those types, is held in the file
-<filename>compiler/prelude/primops.txt.pp</filename>.
-This file is used directly to generate GHC's primitive-operation definitions, so
-it is always correct! It is also intended for processing into text.</para>
-
-<para>Indeed,
-the result of such processing is part of the description of the
- <ulink
- url="http://www.haskell.org/ghc/docs/papers/core.ps.gz">External
- Core language</ulink>.
-So that document is a good place to look for a type-set version.
-We would be very happy if someone wanted to volunteer to produce an XML
-back end to the program that processes <filename>primops.txt</filename> so that
-we could include the results here in the User Guide.</para>
-
-<para>What follows here is a brief summary of some main points.</para>
-
+<para>All these primitive data types and operations are exported by the
+library <literal>GHC.Prim</literal>, for which there is
+<ulink url="&libraryGhcPrimLocation;/GHC-Prim.html">detailed online documentation</ulink>.
+(This documentation is generated from the file <filename>compiler/prelude/primops.txt.pp</filename>.)
+</para>
+<para>
+If you want to mention any of the primitive data types or operations in your
+program, you must first import <literal>GHC.Prim</literal> to bring them
+into scope. Many of them have names ending in "#", and to mention such
+names you need the <option>-XMagicHash</option> extension (<xref linkend="magic-hash"/>).
+</para>
+
+<para>The primops make extensive use of <link linkend="glasgow-unboxed">unboxed types</link>
+and <link linkend="unboxed-tuples">unboxed tuples</link>, which
+we briefly summarise here. </para>
+
<sect2 id="glasgow-unboxed">
<title>Unboxed types
</title>
know and love—usually one instruction.
</para>
-<para> For some primitive types we have special syntax for literals.
-Anything that would be an integer lexeme followed by a
-<literal>#</literal> is an <literal>Int#</literal> literal, e.g.
-<literal>32#</literal> and <literal>-0x3A#</literal>. Likewise,
-any non-negative integer literal followed by
-<literal>##</literal> is a <literal>Word#</literal> literal.
-Likewise, any floating point literal followed by a
-<literal>#</literal> is a <literal>Float#</literal> literal, and
-followed by <literal>##</literal> is a
-<literal>Double#</literal>. Finally, a string literal followed by a
-<literal>#</literal>, e.g. <literal>"foo"#</literal>,
-is a <literal>Addr#</literal> literal.
-</para>
-
<para>
Primitive (unboxed) types cannot be defined in Haskell, and are
therefore built into the language and compiler. Primitive types are
always unlifted; that is, a value of a primitive type cannot be
-bottom. We use the convention that primitive types, values, and
-operations have a <literal>#</literal> suffix.
+bottom. We use the convention (but it is only a convention)
+that primitive types, values, and
+operations have a <literal>#</literal> suffix (see <xref linkend="magic-hash"/>).
+For some primitive types we have special syntax for literals, also
+described in the <link linkend="magic-hash">same section</link>.
</para>
<para>
in a <emphasis>recursive</emphasis> binding.
</para></listitem>
<listitem><para> You may bind unboxed variables in a (non-recursive,
-non-top-level) pattern binding, but any such variable causes the entire
-pattern-match
-to become strict. For example:
+non-top-level) pattern binding, but you must make any such pattern-match
+strict. For example, rather than:
<programlisting>
data Foo = Foo Int Int#
f x = let (Foo a b, w) = ..rhs.. in ..body..
</programlisting>
-Since <literal>b</literal> has type <literal>Int#</literal>, the entire pattern
-match
-is strict, and the program behaves as if you had written
+you must write:
<programlisting>
data Foo = Foo Int Int#
- f x = case ..rhs.. of { (Foo a b, w) -> ..body.. }
+ f x = let !(Foo a b, w) = ..rhs.. in ..body..
</programlisting>
+since <literal>b</literal> has type <literal>Int#</literal>.
</para>
</listitem>
</itemizedlist>
f x = let (# p,q #) = h x in ..body..
</programlisting>
If the types of <literal>p</literal> and <literal>q</literal> are not unboxed,
-the resulting binding is lazy like any other Haskell pattern binding. The
+the resulting binding is lazy like any other Haskell pattern binding. The
above example desugars like this:
<programlisting>
f x = let t = case h x o f{ (# p,q #) -> (p,q)
<sect1 id="syntax-extns">
<title>Syntactic extensions</title>
-
+
+ <sect2 id="unicode-syntax">
+ <title>Unicode syntax</title>
+ <para>The language
+ extension <option>-XUnicodeSyntax</option><indexterm><primary><option>-XUnicodeSyntax</option></primary></indexterm>
+ enables Unicode characters to be used to stand for certain ASCII
+ character sequences. The following alternatives are provided:</para>
+
+ <informaltable>
+ <tgroup cols="2" align="left" colsep="1" rowsep="1">
+ <thead>
+ <row>
+ <entry>ASCII</entry>
+ <entry>Unicode alternative</entry>
+ <entry>Code point</entry>
+ <entry>Name</entry>
+ </row>
+ </thead>
+
+<!--
+ to find the DocBook entities for these characters, find
+ the Unicode code point (e.g. 0x2237), and grep for it in
+ /usr/share/sgml/docbook/xml-dtd-*/ent/* (or equivalent on
+ your system. Some of these Unicode code points don't have
+ equivalent DocBook entities.
+ -->
+
+ <tbody>
+ <row>
+ <entry><literal>::</literal></entry>
+ <entry>::</entry> <!-- no special char, apparently -->
+ <entry>0x2237</entry>
+ <entry>PROPORTION</entry>
+ </row>
+ </tbody>
+ <tbody>
+ <row>
+ <entry><literal>=></literal></entry>
+ <entry>⇒</entry>
+ <entry>0x21D2</entry>
+ <entry>RIGHTWARDS DOUBLE ARROW</entry>
+ </row>
+ </tbody>
+ <tbody>
+ <row>
+ <entry><literal>forall</literal></entry>
+ <entry>∀</entry>
+ <entry>0x2200</entry>
+ <entry>FOR ALL</entry>
+ </row>
+ </tbody>
+ <tbody>
+ <row>
+ <entry><literal>-></literal></entry>
+ <entry>→</entry>
+ <entry>0x2192</entry>
+ <entry>RIGHTWARDS ARROW</entry>
+ </row>
+ </tbody>
+ <tbody>
+ <row>
+ <entry><literal><-</literal></entry>
+ <entry>←</entry>
+ <entry>0x2190</entry>
+ <entry>LEFTWARDS ARROW</entry>
+ </row>
+ </tbody>
+
+ <tbody>
+ <row>
+ <entry>-<</entry>
+ <entry>↢</entry>
+ <entry>0x2919</entry>
+ <entry>LEFTWARDS ARROW-TAIL</entry>
+ </row>
+ </tbody>
+
+ <tbody>
+ <row>
+ <entry>>-</entry>
+ <entry>↣</entry>
+ <entry>0x291A</entry>
+ <entry>RIGHTWARDS ARROW-TAIL</entry>
+ </row>
+ </tbody>
+
+ <tbody>
+ <row>
+ <entry>-<<</entry>
+ <entry></entry>
+ <entry>0x291B</entry>
+ <entry>LEFTWARDS DOUBLE ARROW-TAIL</entry>
+ </row>
+ </tbody>
+
+ <tbody>
+ <row>
+ <entry>>>-</entry>
+ <entry></entry>
+ <entry>0x291C</entry>
+ <entry>RIGHTWARDS DOUBLE ARROW-TAIL</entry>
+ </row>
+ </tbody>
+
+ <tbody>
+ <row>
+ <entry>*</entry>
+ <entry>★</entry>
+ <entry>0x2605</entry>
+ <entry>BLACK STAR</entry>
+ </row>
+ </tbody>
+
+ </tgroup>
+ </informaltable>
+ </sect2>
+
+ <sect2 id="magic-hash">
+ <title>The magic hash</title>
+ <para>The language extension <option>-XMagicHash</option> allows "#" as a
+ postfix modifier to identifiers. Thus, "x#" is a valid variable, and "T#" is
+ a valid type constructor or data constructor.</para>
+
+ <para>The hash sign does not change semantics at all. We tend to use variable
+ names ending in "#" for unboxed values or types (e.g. <literal>Int#</literal>),
+ but there is no requirement to do so; they are just plain ordinary variables.
+ Nor does the <option>-XMagicHash</option> extension bring anything into scope.
+ For example, to bring <literal>Int#</literal> into scope you must
+ import <literal>GHC.Prim</literal> (see <xref linkend="primitives"/>);
+ the <option>-XMagicHash</option> extension
+ then allows you to <emphasis>refer</emphasis> to the <literal>Int#</literal>
+ that is now in scope.</para>
+ <para> The <option>-XMagicHash</option> also enables some new forms of literals (see <xref linkend="glasgow-unboxed"/>):
+ <itemizedlist>
+ <listitem><para> <literal>'x'#</literal> has type <literal>Char#</literal></para> </listitem>
+ <listitem><para> <literal>"foo"#</literal> has type <literal>Addr#</literal></para> </listitem>
+ <listitem><para> <literal>3#</literal> has type <literal>Int#</literal>. In general,
+ any Haskell integer lexeme followed by a <literal>#</literal> is an <literal>Int#</literal> literal, e.g.
+ <literal>-0x3A#</literal> as well as <literal>32#</literal></para>.</listitem>
+ <listitem><para> <literal>3##</literal> has type <literal>Word#</literal>. In general,
+ any non-negative Haskell integer lexeme followed by <literal>##</literal>
+ is a <literal>Word#</literal>. </para> </listitem>
+ <listitem><para> <literal>3.2#</literal> has type <literal>Float#</literal>.</para> </listitem>
+ <listitem><para> <literal>3.2##</literal> has type <literal>Double#</literal></para> </listitem>
+ </itemizedlist>
+ </para>
+ </sect2>
+
<!-- ====================== HIERARCHICAL MODULES ======================= -->
+
<sect2 id="hierarchical-modules">
<title>Hierarchical Modules</title>
</programlisting>
<para>
-The auxiliary functions are
+The auxiliary functions are
</para>
<programlisting>
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.
+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.
+tends to become more and more indented.
</para>
<para>
</programlisting>
<para>
-The semantics should be clear enough. The qualifiers are matched in order.
+The semantics should be clear enough. The qualifiers 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.
+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
<programlisting>
type Typ
-
+
data TypView = Unit
| Arrow Typ Typ
The representation of Typ is held abstract, permitting implementations
to use a fancy representation (e.g., hash-consing to manage sharing).
-Without view patterns, using this signature a little inconvenient:
+Without view patterns, using this signature a little inconvenient:
<programlisting>
size :: Typ -> Integer
size t = case view t of
<para>
View patterns permit calling the view function inside the pattern and
-matching against the result:
+matching against the result:
<programlisting>
size (view -> Unit) = 1
size (view -> Arrow t1 t2) = size t1 + size t2
</para>
<para>
-More precisely, the scoping rules are:
+More precisely, the scoping rules are:
<itemizedlist>
<listitem>
<para>
example f (f -> 4) = True
</programlisting>
That is, the scoping is the same as it would be if the curried arguments
-were collected into a tuple.
+were collected into a tuple.
</para>
</listitem>
(y -> x) = e2 } in x
</programlisting>
-(We may lift this
-restriction in the future; the only cost is that type checking patterns
-would get a little more complicated.)
-
+(For some amplification on this design choice see
+<ulink url="http://hackage.haskell.org/trac/ghc/ticket/4061">Trac #4061</ulink>.)
</para>
</listitem>
<ulink url="http://www.haskell.org/onlinereport/">Haskell 98
Report</ulink>, add the following:
<programlisting>
-case v of { (e -> p) -> e1 ; _ -> e2 }
- =
+case v of { (e -> p) -> e1 ; _ -> e2 }
+ =
case (e v) of { p -> e1 ; _ -> e2 }
</programlisting>
That is, to match a variable <replaceable>v</replaceable> against a pattern
<literal>)</literal>, evaluate <literal>(</literal>
<replaceable>exp</replaceable> <replaceable> v</replaceable>
<literal>)</literal> and match the result against
-<replaceable>pat</replaceable>.
+<replaceable>pat</replaceable>.
</para></listitem>
<listitem><para> Efficiency: When the same view function is applied in
</sect2>
+ <!-- ===================== n+k patterns =================== -->
+
+<sect2 id="n-k-patterns">
+<title>n+k patterns</title>
+<indexterm><primary><option>-XNoNPlusKPatterns</option></primary></indexterm>
+
+<para>
+<literal>n+k</literal> pattern support is enabled by default. To disable
+it, you can use the <option>-XNoNPlusKPatterns</option> flag.
+</para>
+
+</sect2>
+
<!-- ===================== Recursive do-notation =================== -->
-<sect2 id="mdo-notation">
+<sect2 id="recursive-do-notation">
<title>The recursive do-notation
</title>
-<para> The recursive do-notation (also known as mdo-notation) is implemented as described in
-<ulink url="http://citeseer.ist.psu.edu/erk02recursive.html">A recursive do for Haskell</ulink>,
-by Levent Erkok, John Launchbury,
-Haskell Workshop 2002, pages: 29-37. Pittsburgh, Pennsylvania.
-This paper is essential reading for anyone making non-trivial use of mdo-notation,
-and we do not repeat it here.
-</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
+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, and this extension provides the necessary syntactic support.
+the do-notation. The <option>-XDoRec</option> flag provides the necessary syntactic support.
</para>
<para>
-Here is a simple (yet contrived) example:
-</para>
+Here is a simple (albeit contrived) example:
<programlisting>
-import Control.Monad.Fix
-
-justOnes = mdo xs <- Just (1:xs)
- return xs
+{-# 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>
-As you can guess <literal>justOnes</literal> will evaluate to <literal>Just [1,1,1,...</literal>.
+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 Control.Monad.Fix library introduces the <literal>MonadFix</literal> class. It's definition is:
+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>
-class Monad m => MonadFix m where
- mfix :: (a -> m a) -> m a
+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 function <literal>mfix</literal>
-dictates how the required recursion operation should be performed. For example,
-<literal>justOnes</literal> desugars as follows:
+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>
-justOnes = mfix (\xs' -> do { xs <- Just (1:xs'); return xs }
+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>
-For full details of the way in which mdo is typechecked and desugared, see
-the paper <ulink url="http://citeseer.ist.psu.edu/erk02recursive.html">A recursive do for Haskell</ulink>.
-In particular, GHC implements the segmentation technique described in Section 3.2 of the paper.
+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>
-If recursive bindings are required for a monad,
-then that monad must be declared an instance of the <literal>MonadFix</literal> class.
-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).
+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 important points in using the recursive-do notation:
+Here are some other 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>).
+It is enabled with the flag <literal>-XDoRec</literal>, which is in turn implied by
+<literal>-fglasgow-exts</literal>.
</para></listitem>
<listitem><para>
-It is enabled with the flag <literal>-XRecursiveDo</literal>, which is in turn implied by
-<literal>-fglasgow-exts</literal>.
+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>
-Unlike ordinary do-notation, but like <literal>let</literal> and <literal>where</literal> bindings,
-name shadowing is not allowed; that is, all the names bound in a single <literal>mdo</literal> must
-be distinct (Section 3.3 of the paper).
+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>
-Variables bound by a <literal>let</literal> statement in an <literal>mdo</literal>
-are monomorphic in the <literal>mdo</literal> (Section 3.1 of the paper). However
-GHC breaks the <literal>mdo</literal> into segments to enhance polymorphism,
-and improve termination (Section 3.2 of the paper).
+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>
-<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>
+<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>
example, the following zips together two lists:</para>
<programlisting>
- [ (x, y) | x <- xs | y <- ys ]
+ [ (x, y) | x <- xs | y <- ys ]
</programlisting>
<para>The behavior of parallel list comprehensions follows that of
<para>Given a parallel comprehension of the form: </para>
<programlisting>
- [ e | p1 <- e11, p2 <- e12, ...
- | q1 <- e21, q2 <- e22, ...
- ...
- ]
+ [ 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, ...]
- ...
- ]
+ [ 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">
<para>Generalised list comprehensions are a further enhancement to the
- list comprehension syntatic sugar to allow operations such as sorting
+ 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>Here is an example:
+<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)
, then sortWith by (sum salary)
, then take 5 ]
</programlisting>
-In this example, the list <literal>output</literal> would take on
+In this example, the list <literal>output</literal> would take on
the value:
-
+
<programlisting>
[("Yale", 60), ("Ed", 85), ("MS", 180)]
</programlisting>
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 it's use in the
+ 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>
</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
+ 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 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>
+ <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>
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]]
[(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
+ <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>
<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="../libraries/base/GHC-Exts.html"><literal>GHC.Exts</literal></ulink>. This
+ <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>
<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]
</para>
</sect2>
- <!-- ===================== REBINDABLE SYNTAX =================== -->
+ <!-- ===================== MONAD COMPREHENSIONS ===================== -->
-<sect2 id="rebindable-syntax">
-<title>Rebindable syntax</title>
+<sect2 id="monad-comprehensions">
+ <title>Monad comprehensions</title>
+ <indexterm><primary>monad comprehensions</primary></indexterm>
- <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>
+ 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>You may want to define your own numeric class
+ <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>-XNoImplicitPrelude</option> flag causes
+ 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>
+</para> </listitem>
<listitem><para>Fractional literals are handed in just the same way,
- except that the translation is
+ except that the translation is
<literal>fromRational (3.68::Rational)</literal>.
-</para> </listitem>
+</para> </listitem>
<listitem><para>The equality test in an overloaded numeric pattern
uses whatever <literal>(==)</literal> is in scope.
-</para> </listitem>
+</para> </listitem>
<listitem><para>The subtraction operation, and the
greater-than-or-equal test, in <literal>n+k</literal> patterns
</para></listitem>
<listitem>
+ <para>Conditionals (e.g. "<literal>if</literal> e1 <literal>then</literal> e2 <literal>else</literal> e3")
+ means "<literal>ifThenElse</literal> e1 e2 e3". However <literal>case</literal> expressions are unaffected.
+ </para></listitem>
+
+ <listitem>
<para>"Do" notation is translated using whatever
functions <literal>(>>=)</literal>,
<literal>(>>)</literal>, and <literal>fail</literal>,
to use this, ask!
</para></listitem>
</itemizedlist>
+<option>-XRebindableSyntax</option> implies <option>-XNoImplicitPrelude</option>.
+</para>
+<para>
In all cases (apart from arrow notation), the static semantics should be that of the desugared form,
-even if that is a little unexpected. For example, the
+even if that is a little unexpected. For example, the
static semantics of the literal <literal>368</literal>
is exactly that of <literal>fromInteger (368::Integer)</literal>; it's fine for
<literal>fromInteger</literal> to have any of the types:
fromInteger :: Integer -> Bool -> Bool
</programlisting>
</para>
-
+
<para>Be warned: this is an experimental facility, with
fewer checks than usual. Use <literal>-dcore-lint</literal>
to typecheck the desugared program. If Core Lint is happy
<title>Postfix operators</title>
<para>
-GHC allows a small extension to the syntax of left operator sections, which
-allows you to define postfix operators. The extension is this: the left section
+ The <option>-XPostfixOperators</option> flag enables a small
+extension to the syntax of left operator sections, which allows you to
+define postfix operators. The extension is this: the left section
<programlisting>
(e !)
</programlisting>
take only one argument, and that in turn allows you to write the function
postfix.
</para>
-<para>Since this extension goes beyond Haskell 98, it should really be enabled
-by a flag; but in fact it is enabled all the time. (No Haskell 98 programs
-change their behaviour, of course.)
-</para>
<para>The extension does not extend to the left-hand side of function
definitions; you must define such a function in prefix form.</para>
</sect2>
+<sect2 id="tuple-sections">
+<title>Tuple sections</title>
+
+<para>
+ The <option>-XTupleSections</option> flag enables Python-style partially applied
+ tuple constructors. For example, the following program
+<programlisting>
+ (, True)
+</programlisting>
+ is considered to be an alternative notation for the more unwieldy alternative
+<programlisting>
+ \x -> (x, True)
+</programlisting>
+You can omit any combination of arguments to the tuple, as in the following
+<programlisting>
+ (, "I", , , "Love", , 1337)
+</programlisting>
+which translates to
+<programlisting>
+ \a b c d -> (a, "I", b, c, "Love", d, 1337)
+</programlisting>
+</para>
+
+<para>
+ If you have <link linkend="unboxed-tuples">unboxed tuples</link> enabled, tuple sections
+ will also be available for them, like so
+<programlisting>
+ (# , True #)
+</programlisting>
+Because there is no unboxed unit tuple, the following expression
+<programlisting>
+ (# #)
+</programlisting>
+continues to stand for the unboxed singleton tuple data constructor.
+</para>
+
+</sect2>
+
<sect2 id="disambiguate-fields">
<title>Record field disambiguation</title>
<para>
import M
data T = MkT { x :: Int }
-
- ok1 (MkS { x = n }) = n+1 -- Unambiguous
+ ok1 (MkS { x = n }) = n+1 -- Unambiguous
ok2 n = MkT { x = n+1 } -- Unambiguous
bad1 k = k { x = 3 } -- Ambiguous
</para>
<para>
Haskell 98 regards all four as ambiguous, but with the
-<option>-fdisambiguate-record-fields</option> flag, GHC will accept
+<option>-XDisambiguateRecordFields</option> flag, GHC will accept
the former two. The rules are precisely the same as those for instance
-declarations in Haskell 98, where the method names on the left-hand side
+declarations in Haskell 98, where the method names on the left-hand side
of the method bindings in an instance declaration refer unambiguously
to the method of that class (provided they are in scope at all), even
if there are other variables in scope with the same name.
This reduces the clutter of qualified names when you import two
records from different modules that use the same field name.
</para>
+<para>
+Some details:
+<itemizedlist>
+<listitem><para>
+Field disambiguation can be combined with punning (see <xref linkend="record-puns"/>). For example:
+<programlisting>
+module Foo where
+ import M
+ x=True
+ ok3 (MkS { x }) = x+1 -- Uses both disambiguation and punning
+</programlisting>
+</para></listitem>
+
+<listitem><para>
+With <option>-XDisambiguateRecordFields</option> you can use <emphasis>unqualified</emphasis>
+field names even if the corresponding selector is only in scope <emphasis>qualified</emphasis>
+For example, assuming the same module <literal>M</literal> as in our earlier example, this is legal:
+<programlisting>
+module Foo where
+ import qualified M -- Note qualified
+
+ ok4 (M.MkS { x = n }) = n+1 -- Unambiguous
+</programlisting>
+Since the constructor <literal>MkS</literal> is only in scope qualified, you must
+name it <literal>M.MkS</literal>, but the field <literal>x</literal> does not need
+to be qualified even though <literal>M.x</literal> is in scope but <literal>x</literal>
+is not. (In effect, it is qualified by the constructor.)
+</para></listitem>
+</itemizedlist>
+</para>
+
</sect2>
<!-- ===================== Record puns =================== -->
to mean the same pattern as above. That is, in a record pattern, the
pattern <literal>a</literal> expands into the pattern <literal>a =
-a</literal> for the same name <literal>a</literal>.
-</para>
-
-<para>
-Note that puns and other patterns can be mixed in the same record:
-<programlisting>
-data C = C {a :: Int, b :: Int}
-f (C {a, b = 4}) = a
-</programlisting>
-and that puns can be used wherever record patterns occur (e.g. in
-<literal>let</literal> bindings or at the top-level).
+a</literal> for the same name <literal>a</literal>.
</para>
<para>
+Note that:
+<itemizedlist>
+<listitem><para>
Record punning can also be used in an expression, writing, for example,
<programlisting>
let a = 1 in C {a}
</programlisting>
-instead of
+instead of
<programlisting>
let a = 1 in C {a = a}
</programlisting>
-
-Note that this expansion is purely syntactic, so the record pun
+The expansion is purely syntactic, so the expanded right-hand side
expression refers to the nearest enclosing variable that is spelled the
same as the field name.
+</para></listitem>
+
+<listitem><para>
+Puns and other patterns can be mixed in the same record:
+<programlisting>
+data C = C {a :: Int, b :: Int}
+f (C {a, b = 4}) = a
+</programlisting>
+</para></listitem>
+
+<listitem><para>
+Puns can be used wherever record patterns occur (e.g. in
+<literal>let</literal> bindings or at the top-level).
+</para></listitem>
+
+<listitem><para>
+A pun on a qualified field name is expanded by stripping off the module qualifier.
+For example:
+<programlisting>
+f (C {M.a}) = a
+</programlisting>
+means
+<programlisting>
+f (M.C {M.a = a}) = a
+</programlisting>
+(This is useful if the field selector <literal>a</literal> for constructor <literal>M.C</literal>
+is only in scope in qualified form.)
+</para></listitem>
+</itemizedlist>
</para>
+
</sect2>
<!-- ===================== Record wildcards =================== -->
<para>
Record wildcards are enabled by the flag <literal>-XRecordWildCards</literal>.
+This flag implies <literal>-XDisambiguateRecordFields</literal>.
</para>
<para>
</para>
<para>
-Record wildcard syntax permits a (<literal>..</literal>) in a record
+Record wildcard syntax permits a "<literal>..</literal>" in a record
pattern, where each elided field <literal>f</literal> is replaced by the
pattern <literal>f = f</literal>. For example, the above pattern can be
written as
</para>
<para>
-Note that wildcards can be mixed with other patterns, including puns
+More details:
+<itemizedlist>
+<listitem><para>
+Wildcards can be mixed with other patterns, including puns
(<xref linkend="record-puns"/>); for example, in a pattern <literal>C {a
= 1, b, ..})</literal>. Additionally, record wildcards can be used
wherever record patterns occur, including in <literal>let</literal>
</programlisting>
defines <literal>b</literal>, <literal>c</literal>, and
<literal>d</literal>.
-</para>
+</para></listitem>
-<para>
+<listitem><para>
Record wildcards can also be used in expressions, writing, for example,
-
<programlisting>
let {a = 1; b = 2; c = 3; d = 4} in C {..}
</programlisting>
-
in place of
-
<programlisting>
let {a = 1; b = 2; c = 3; d = 4} in C {a=a, b=b, c=c, d=d}
</programlisting>
-
-Note that this expansion is purely syntactic, so the record wildcard
+The expansion is purely syntactic, so the record wildcard
expression refers to the nearest enclosing variables that are spelled
the same as the omitted field names.
+</para></listitem>
+
+<listitem><para>
+The "<literal>..</literal>" expands to the missing
+<emphasis>in-scope</emphasis> record fields, where "in scope"
+includes both unqualified and qualified-only.
+Any fields that are not in scope are not filled in. For example
+<programlisting>
+module M where
+ data R = R { a,b,c :: Int }
+module X where
+ import qualified M( R(a,b) )
+ f a b = R { .. }
+</programlisting>
+The <literal>{..}</literal> expands to <literal>{M.a=a,M.b=b}</literal>,
+omitting <literal>c</literal> since it is not in scope at all.
+</para></listitem>
+</itemizedlist>
</para>
</sect2>
<programlisting>
let f = ...
infixr 3 `f`
-in
+in
...
</programlisting>
and the fixity declaration applies wherever the binding is in scope.
For example, in a <literal>let</literal>, it applies in the right-hand
sides of other <literal>let</literal>-bindings and the body of the
<literal>let</literal>C. Or, in recursive <literal>do</literal>
-expressions (<xref linkend="mdo-notation"/>), the local fixity
+expressions (<xref linkend="recursive-do-notation"/>), the local fixity
declarations of a <literal>let</literal> statement scope over other
statements in the group, just as the bound name does.
</para>
<programlisting>
import "network" Network.Socket
</programlisting>
-
+
<para>would import the module <literal>Network.Socket</literal> from
the package <literal>network</literal> (any version). This may
be used to disambiguate an import when the same module is
the common case: modules occasionally move from one package to
another, rendering any package-qualified imports broken.</para>
</sect2>
+
+<sect2 id="syntax-stolen">
+<title>Summary of stolen syntax</title>
+
+ <para>Turning on an option that enables special syntax
+ <emphasis>might</emphasis> cause working Haskell 98 code to fail
+ to compile, perhaps because it uses a variable name which has
+ become a reserved word. This section lists the syntax that is
+ "stolen" by language extensions.
+ We use
+ notation and nonterminal names from the Haskell 98 lexical syntax
+ (see the Haskell 98 Report).
+ We only list syntax changes here that might affect
+ existing working programs (i.e. "stolen" syntax). Many of these
+ extensions will also enable new context-free syntax, but in all
+ cases programs written to use the new syntax would not be
+ compilable without the option enabled.</para>
+
+<para>There are two classes of special
+ syntax:
+
+ <itemizedlist>
+ <listitem>
+ <para>New reserved words and symbols: character sequences
+ which are no longer available for use as identifiers in the
+ program.</para>
+ </listitem>
+ <listitem>
+ <para>Other special syntax: sequences of characters that have
+ a different meaning when this particular option is turned
+ on.</para>
+ </listitem>
+ </itemizedlist>
+
+The following syntax is stolen:
+
+ <variablelist>
+ <varlistentry>
+ <term>
+ <literal>forall</literal>
+ <indexterm><primary><literal>forall</literal></primary></indexterm>
+ </term>
+ <listitem><para>
+ Stolen (in types) by: <option>-XExplicitForAll</option>, and hence by
+ <option>-XScopedTypeVariables</option>,
+ <option>-XLiberalTypeSynonyms</option>,
+ <option>-XRank2Types</option>,
+ <option>-XRankNTypes</option>,
+ <option>-XPolymorphicComponents</option>,
+ <option>-XExistentialQuantification</option>
+ </para></listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <literal>mdo</literal>
+ <indexterm><primary><literal>mdo</literal></primary></indexterm>
+ </term>
+ <listitem><para>
+ Stolen by: <option>-XRecursiveDo</option>,
+ </para></listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <literal>foreign</literal>
+ <indexterm><primary><literal>foreign</literal></primary></indexterm>
+ </term>
+ <listitem><para>
+ Stolen by: <option>-XForeignFunctionInterface</option>,
+ </para></listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <literal>rec</literal>,
+ <literal>proc</literal>, <literal>-<</literal>,
+ <literal>>-</literal>, <literal>-<<</literal>,
+ <literal>>>-</literal>, and <literal>(|</literal>,
+ <literal>|)</literal> brackets
+ <indexterm><primary><literal>proc</literal></primary></indexterm>
+ </term>
+ <listitem><para>
+ Stolen by: <option>-XArrows</option>,
+ </para></listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <literal>?<replaceable>varid</replaceable></literal>,
+ <literal>%<replaceable>varid</replaceable></literal>
+ <indexterm><primary>implicit parameters</primary></indexterm>
+ </term>
+ <listitem><para>
+ Stolen by: <option>-XImplicitParams</option>,
+ </para></listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <literal>[|</literal>,
+ <literal>[e|</literal>, <literal>[p|</literal>,
+ <literal>[d|</literal>, <literal>[t|</literal>,
+ <literal>$(</literal>,
+ <literal>$<replaceable>varid</replaceable></literal>
+ <indexterm><primary>Template Haskell</primary></indexterm>
+ </term>
+ <listitem><para>
+ Stolen by: <option>-XTemplateHaskell</option>,
+ </para></listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <literal>[:<replaceable>varid</replaceable>|</literal>
+ <indexterm><primary>quasi-quotation</primary></indexterm>
+ </term>
+ <listitem><para>
+ Stolen by: <option>-XQuasiQuotes</option>,
+ </para></listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <replaceable>varid</replaceable>{<literal>#</literal>},
+ <replaceable>char</replaceable><literal>#</literal>,
+ <replaceable>string</replaceable><literal>#</literal>,
+ <replaceable>integer</replaceable><literal>#</literal>,
+ <replaceable>float</replaceable><literal>#</literal>,
+ <replaceable>float</replaceable><literal>##</literal>,
+ <literal>(#</literal>, <literal>#)</literal>,
+ </term>
+ <listitem><para>
+ Stolen by: <option>-XMagicHash</option>,
+ </para></listitem>
+ </varlistentry>
+ </variablelist>
+</para>
+</sect2>
</sect1>
data T a -- T :: * -> *
</programlisting>
-<para>Syntactically, the declaration lacks the "= constrs" part. The
+<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="kinding"/>).</para>
Nevertheless, they can be useful when defining "phantom types".</para>
</sect2>
+<sect2 id="datatype-contexts">
+<title>Data type contexts</title>
+
+<para>Haskell allows datatypes to be given contexts, e.g.</para>
+
+<programlisting>
+data Eq a => Set a = NilSet | ConsSet a (Set a)
+</programlisting>
+
+<para>give constructors with types:</para>
+
+<programlisting>
+NilSet :: Set a
+ConsSet :: Eq a => a -> Set a -> Set a
+</programlisting>
+
+<para>In GHC this feature is an extension called
+<literal>DatatypeContexts</literal>, and on by default.</para>
+</sect2>
+
<sect2 id="infix-tycons">
<title>Infix type constructors, classes, and type variables</title>
type T (+) = Int + Int
f :: T Either
f = Left 3
-
+
liftA2 :: Arrow (~>)
=> (a -> b -> c) -> (e ~> a) -> (e ~> b) -> (e ~> c)
liftA2 = ...
<title>Liberalised type synonyms</title>
<para>
-Type synonyms are like macros at the type level, and
+Type synonyms are like macros at the type level, but Haskell 98 imposes many rules
+on individual synonym declarations.
+With the <option>-XLiberalTypeSynonyms</option> extension,
GHC does validity checking on types <emphasis>only after expanding type synonyms</emphasis>.
-That means that GHC can be very much more liberal about type synonyms than Haskell 98:
+That means that GHC can be very much more liberal about type synonyms than Haskell 98.
+
<itemizedlist>
<listitem> <para>You can write a <literal>forall</literal> (including overloading)
in a type synonym, thus:
</listitem>
<listitem><para>
-You can write an unboxed tuple in a type synonym:
+If you also use <option>-XUnboxedTuples</option>,
+you can write an unboxed tuple in a type synonym:
<programlisting>
type Pr = (# Int, Int #)
You can apply a type synonym to a forall type:
<programlisting>
type Foo a = a -> a -> Bool
-
+
f :: Foo (forall b. b->b)
</programlisting>
After expanding the synonym, <literal>f</literal> has the legal (in GHC) type:
<programlisting>
type Generic i o = forall x. i x -> o x
type Id x = x
-
+
foo :: Generic Id []
</programlisting>
After expanding the synonym, <literal>foo</literal> has the legal (in GHC) type:
<programlisting>
inc :: Counter a -> Counter a
inc (NewCounter x i d t) = NewCounter
- { _this = i x, _inc = i, _display = d, tag = t }
+ { _this = i x, _inc = i, _display = d, tag = t }
display :: Counter a -> IO ()
display NewCounter{ _this = x, _display = d } = d x
Now we can define counters with different underlying implementations:
<programlisting>
-counterA :: Counter String
+counterA :: Counter String
counterA = NewCounter
{ _this = 0, _inc = (1+), _display = print, tag = "A" }
-counterB :: Counter String
+counterB :: Counter String
counterB = NewCounter
{ _this = "", _inc = ('#':), _display = putStrLn, tag = "B" }
display (inc (inc counterB)) -- prints "##"
</programlisting>
-At the moment, record update syntax is only supported for Haskell 98 data types,
-so the following function does <emphasis>not</emphasis> work:
-
+Record update syntax is supported for existentials (and GADTs):
<programlisting>
--- This is invalid; use explicit NewCounter instead for now
setTag :: Counter a -> a -> Counter a
setTag obj t = obj{ tag = t }
</programlisting>
+The rule for record update is this: <emphasis>
+the types of the updated fields may
+mention only the universally-quantified type variables
+of the data constructor. For GADTs, the field may mention only types
+that appear as a simple type-variable argument in the constructor's result
+type</emphasis>. For example:
+<programlisting>
+data T a b where { T1 { f1::a, f2::b, f3::(b,c) } :: T a b } -- c is existential
+upd1 t x = t { f1=x } -- OK: upd1 :: T a b -> a' -> T a' b
+upd2 t x = t { f3=x } -- BAD (f3's type mentions c, which is
+ -- existentially quantified)
+data G a b where { G1 { g1::a, g2::c } :: G a [c] }
+upd3 g x = g { g1=x } -- OK: upd3 :: G a b -> c -> G c b
+upd4 g x = g { g2=x } -- BAD (f2's type mentions c, which is not a simple
+ -- type-variable argument in G1's result type)
+</programlisting>
</para>
</sect3>
<sect2 id="gadt-style">
<title>Declaring data types with explicit constructor signatures</title>
-<para>GHC allows you to declare an algebraic data type by
+<para>When the <literal>GADTSyntax</literal> extension is enabled,
+GHC allows you to declare an algebraic data type by
giving the type signatures of constructors explicitly. For example:
<programlisting>
data Maybe a where
Just :: a -> Maybe a
</programlisting>
The form is called a "GADT-style declaration"
-because Generalised Algebraic Data Types, described in <xref linkend="gadt"/>,
+because Generalised Algebraic Data Types, described in <xref linkend="gadt"/>,
can only be declared using this form.</para>
-<para>Notice that GADT-style syntax generalises existential types (<xref linkend="existential-quantification"/>).
+<para>Notice that GADT-style syntax generalises existential types (<xref linkend="existential-quantification"/>).
For example, these two declarations are equivalent:
<programlisting>
data Foo = forall a. MkFoo a (a -> Bool)
data Foo' where { MKFoo :: a -> (a->Bool) -> Foo' }
</programlisting>
</para>
-<para>Any data type that can be declared in standard Haskell-98 syntax
+<para>Any data type that can be declared in standard Haskell-98 syntax
can also be declared using GADT-style syntax.
The choice is largely stylistic, but GADT-style declarations differ in one important respect:
they treat class constraints on the data constructors differently.
insert a (MkSet as) | a `elem` as = MkSet as
| otherwise = MkSet (a:as)
</programlisting>
-A use of <literal>MkSet</literal> as a constructor (e.g. in the definition of <literal>makeSet</literal>)
+A use of <literal>MkSet</literal> as a constructor (e.g. in the definition of <literal>makeSet</literal>)
gives rise to a <literal>(Eq a)</literal>
constraint, as you would expect. The new feature is that pattern-matching on <literal>MkSet</literal>
(as in the definition of <literal>insert</literal>) makes <emphasis>available</emphasis> an <literal>(Eq a)</literal>
context. In implementation terms, the <literal>MkSet</literal> constructor has a hidden field that stores
the <literal>(Eq a)</literal> dictionary that is passed to <literal>MkSet</literal>; so
when pattern-matching that dictionary becomes available for the right-hand side of the match.
-In the example, the equality dictionary is used to satisfy the equality constraint
+In the example, the equality dictionary is used to satisfy the equality constraint
generated by the call to <literal>elem</literal>, so that the type of
<literal>insert</literal> itself has no <literal>Eq</literal> constraint.
</para>
plus :: NumInst a -> a -> a -> a
plus MkNumInst p q = p + q
</programlisting>
-Here, a value of type <literal>NumInst a</literal> is equivalent
+Here, a value of type <literal>NumInst a</literal> is equivalent
to an explicit <literal>(Num a)</literal> dictionary.
</para>
<para>
All this applies to constructors declared using the syntax of <xref linkend="existential-with-context"/>.
-For example, the <literal>NumInst</literal> data type above could equivalently be declared
+For example, the <literal>NumInst</literal> data type above could equivalently be declared
like this:
<programlisting>
- data NumInst a
+ data NumInst a
= Num a => MkNumInst (NumInst a)
</programlisting>
-Notice that, unlike the situation when declaring an existential, there is
+Notice that, unlike the situation when declaring an existential, there is
no <literal>forall</literal>, because the <literal>Num</literal> constrains the
-data type's universally quantified type variable <literal>a</literal>.
+data type's universally quantified type variable <literal>a</literal>.
A constructor may have both universal and existential type variables: for example,
the following two declarations are equivalent:
<programlisting>
- data T1 a
+ data T1 a
= forall b. (Num a, Eq b) => MkT1 a b
data T2 a where
MkT2 :: (Num a, Eq b) => a -> b -> T2 a
</programlisting>
</para>
-<para>All this behaviour contrasts with Haskell 98's peculiar treatment of
+<para>All this behaviour contrasts with Haskell 98's peculiar treatment of
contexts on a data type declaration (Section 4.2.1 of the Haskell 98 Report).
In Haskell 98 the definition
<programlisting>
data Eq a => Set' a = MkSet' [a]
</programlisting>
-gives <literal>MkSet'</literal> the same type as <literal>MkSet</literal> above. But instead of
+gives <literal>MkSet'</literal> the same type as <literal>MkSet</literal> above. But instead of
<emphasis>making available</emphasis> an <literal>(Eq a)</literal> constraint, pattern-matching
on <literal>MkSet'</literal> <emphasis>requires</emphasis> an <literal>(Eq a)</literal> constraint!
GHC faithfully implements this behaviour, odd though it is. But for GADT-style declarations,
<itemizedlist>
<listitem><para>
The result type of each data constructor must begin with the type constructor being defined.
-If the result type of all constructors
+If the result type of all constructors
has the form <literal>T a1 ... an</literal>, where <literal>a1 ... an</literal>
are distinct type variables, then the data type is <emphasis>ordinary</emphasis>;
otherwise is a <emphasis>generalised</emphasis> data type (<xref linkend="gadt"/>).
</para></listitem>
<listitem><para>
+As with other type signatures, you can give a single signature for several data constructors.
+In this example we give a single signature for <literal>T1</literal> and <literal>T2</literal>:
+<programlisting>
+ data T a where
+ T1,T2 :: a -> T a
+ T3 :: T a
+</programlisting>
+</para></listitem>
+
+<listitem><para>
The type signature of
-each constructor is independent, and is implicitly universally quantified as usual.
-Different constructors may have different universally-quantified type variables
-and different type-class constraints.
-For example, this is fine:
+each constructor is independent, and is implicitly universally quantified as usual.
+In particular, the type variable(s) in the "<literal>data T a where</literal>" header
+have no scope, and different constructors may have different universally-quantified type variables:
+<programlisting>
+ data T a where -- The 'a' has no scope
+ T1,T2 :: b -> T b -- Means forall b. b -> T b
+ T3 :: T a -- Means forall a. T a
+</programlisting>
+</para></listitem>
+
+<listitem><para>
+A constructor signature may mention type class constraints, which can differ for
+different constructors. For example, this is fine:
<programlisting>
data T a where
- T1 :: Eq b => b -> T b
+ T1 :: Eq b => b -> b -> T b
T2 :: (Show c, Ix c) => c -> [c] -> T c
</programlisting>
+When pattern matching, these constraints are made available to discharge constraints
+in the body of the match. For example:
+<programlisting>
+ f :: T a -> String
+ f (T1 x y) | x==y = "yes"
+ | otherwise = "no"
+ f (T2 a b) = show a
+</programlisting>
+Note that <literal>f</literal> is not overloaded; the <literal>Eq</literal> constraint arising
+from the use of <literal>==</literal> is discharged by the pattern match on <literal>T1</literal>
+and similarly the <literal>Show</literal> constraint arising from the use of <literal>show</literal>.
</para></listitem>
<listitem><para>
-Unlike a Haskell-98-style
-data type declaration, the type variable(s) in the "<literal>data Set a where</literal>" header
+Unlike a Haskell-98-style
+data type declaration, the type variable(s) in the "<literal>data Set a where</literal>" header
have no scope. Indeed, one can write a kind signature instead:
<programlisting>
data Set :: * -> * where ...
</programlisting>
or even a mixture of the two:
<programlisting>
- data Foo a :: (* -> *) -> * where ...
+ data Bar a :: (* -> *) -> * where ...
</programlisting>
The type variables (if given) may be explicitly kinded, so we could also write the header for <literal>Foo</literal>
like this:
<programlisting>
- data Foo a (b :: * -> *) where ...
+ data Bar a (b :: * -> *) where ...
</programlisting>
</para></listitem>
Just1 :: a -> Maybe1 a
} deriving( Eq, Ord )
- data Maybe2 a = Nothing2 | Just2 a
+ data Maybe2 a = Nothing2 | Just2 a
deriving( Eq, Ord )
</programlisting>
</para></listitem>
<listitem><para>
+The type signature may have quantified type variables that do not appear
+in the result type:
+<programlisting>
+ data Foo where
+ MkFoo :: a -> (a->Bool) -> Foo
+ Nil :: Foo
+</programlisting>
+Here the type variable <literal>a</literal> does not appear in the result type
+of either constructor.
+Although it is universally quantified in the type of the constructor, such
+a type variable is often called "existential".
+Indeed, the above declaration declares precisely the same type as
+the <literal>data Foo</literal> in <xref linkend="existential-quantification"/>.
+</para><para>
+The type may contain a class context too, of course:
+<programlisting>
+ data Showable where
+ MkShowable :: Show a => a -> Showable
+</programlisting>
+</para></listitem>
+
+<listitem><para>
You can use record syntax on a GADT-style data type declaration:
<programlisting>
data Person where
- Adult { name :: String, children :: [Person] } :: Person
- Child { name :: String } :: Person
+ Adult :: { name :: String, children :: [Person] } -> Person
+ Child :: Show a => { name :: !String, funny :: a } -> Person
</programlisting>
As usual, for every constructor that has a field <literal>f</literal>, the type of
field <literal>f</literal> must be the same (modulo alpha conversion).
-</para>
-<para>
-At the moment, record updates are not yet possible with GADT-style declarations,
-so support is limited to record construction, selection and pattern matching.
-For example
-<programlisting>
- aPerson = Adult { name = "Fred", children = [] }
+The <literal>Child</literal> constructor above shows that the signature
+may have a context, existentially-quantified variables, and strictness annotations,
+just as in the non-record case. (NB: the "type" that follows the double-colon
+is not really a type, because of the record syntax and strictness annotations.
+A "type" of this form can appear only in a constructor signature.)
+</para></listitem>
- shortName :: Person -> Bool
- hasChildren (Adult { children = kids }) = not (null kids)
- hasChildren (Child {}) = False
-</programlisting>
+<listitem><para>
+Record updates are allowed with GADT-style declarations,
+only fields that have the following property: the type of the field
+mentions no existential type variables.
</para></listitem>
-<listitem><para>
-As in the case of existentials declared using the Haskell-98-like record syntax
+<listitem><para>
+As in the case of existentials declared using the Haskell-98-like record syntax
(<xref linkend="existential-records"/>),
record-selector functions are generated only for those fields that have well-typed
-selectors.
+selectors.
Here is the example of that section, in GADT-style syntax:
<programlisting>
data Counter a where
<sect2 id="gadt">
<title>Generalised Algebraic Data Types (GADTs)</title>
-<para>Generalised Algebraic Data Types generalise ordinary algebraic data types
+<para>Generalised Algebraic Data Types generalise ordinary algebraic data types
by allowing constructors to have richer return types. Here is an example:
<programlisting>
data Term a where
Lit :: Int -> Term Int
Succ :: Term Int -> Term Int
- IsZero :: Term Int -> Term Bool
+ IsZero :: Term Int -> Term Bool
If :: Term Bool -> Term a -> Term a -> Term a
Pair :: Term a -> Term b -> Term (a,b)
</programlisting>
Notice that the return type of the constructors is not always <literal>Term a</literal>, as is the
-case with ordinary data types. This generality allows us to
+case with ordinary data types. This generality allows us to
write a well-typed <literal>eval</literal> function
for these <literal>Terms</literal>:
<programlisting>
eval (If b e1 e2) = if eval b then eval e1 else eval e2
eval (Pair e1 e2) = (eval e1, eval e2)
</programlisting>
-The key point about GADTs is that <emphasis>pattern matching causes type refinement</emphasis>.
+The key point about GADTs is that <emphasis>pattern matching causes type refinement</emphasis>.
For example, in the right hand side of the equation
<programlisting>
eval :: Term a -> a
eval (Lit i) = ...
</programlisting>
the type <literal>a</literal> is refined to <literal>Int</literal>. That's the whole point!
-A precise specification of the type rules is beyond what this user manual aspires to,
+A precise specification of the type rules is beyond what this user manual aspires to,
but the design closely follows that described in
the paper <ulink
url="http://research.microsoft.com/%7Esimonpj/papers/gadt/">Simple
unification-based type inference for GADTs</ulink>,
(ICFP 2006).
-The general principle is this: <emphasis>type refinement is only carried out
+The general principle is this: <emphasis>type refinement is only carried out
based on user-supplied type annotations</emphasis>.
-So if no type signature is supplied for <literal>eval</literal>, no type refinement happens,
+So if no type signature is supplied for <literal>eval</literal>, no type refinement happens,
and lots of obscure error messages will
occur. However, the refinement is quite general. For example, if we had:
<programlisting>
may use different notation to that implemented in GHC.
</para>
<para>
-The rest of this section outlines the extensions to GHC that support GADTs. The extension is enabled with
+The rest of this section outlines the extensions to GHC that support GADTs. The extension is enabled with
<option>-XGADTs</option>. The <option>-XGADTs</option> flag also sets <option>-XRelaxedPolyRec</option>.
<itemizedlist>
<listitem><para>
-A GADT can only be declared using GADT-style syntax (<xref linkend="gadt-style"/>);
+A GADT can only be declared using GADT-style syntax (<xref linkend="gadt-style"/>);
the old Haskell-98 syntax for data declarations always declares an ordinary data type.
The result type of each constructor must begin with the type constructor being defined,
-but for a GADT the arguments to the type constructor can be arbitrary monotypes.
+but for a GADT the arguments to the type constructor can be arbitrary monotypes.
For example, in the <literal>Term</literal> data
type above, the type of each constructor must end with <literal>Term ty</literal>, but
the <literal>ty</literal> need not be a type variable (e.g. the <literal>Lit</literal>
</para></listitem>
<listitem><para>
-It's is permitted to declare an ordinary algebraic data type using GADT-style syntax.
+It is permitted to declare an ordinary algebraic data type using GADT-style syntax.
What makes a GADT into a GADT is not the syntax, but rather the presence of data constructors
whose result type is not just <literal>T a b</literal>.
</para></listitem>
Lit { val :: Int } :: Term Int
Succ { num :: Term Int } :: Term Int
Pred { num :: Term Int } :: Term Int
- IsZero { arg :: Term Int } :: Term Bool
+ IsZero { arg :: Term Int } :: Term Bool
Pair { arg1 :: Term a
, arg2 :: Term b
} :: Term (a,b)
, fls :: Term a
} :: Term a
</programlisting>
-However, for GADTs there is the following additional constraint:
+However, for GADTs there is the following additional constraint:
every constructor that has a field <literal>f</literal> must have
the same result type (modulo alpha conversion)
-Hence, in the above example, we cannot merge the <literal>num</literal>
-and <literal>arg</literal> fields above into a
+Hence, in the above example, we cannot merge the <literal>num</literal>
+and <literal>arg</literal> fields above into a
single name. Although their field types are both <literal>Term Int</literal>,
their selector functions actually have different types:
</para></listitem>
<listitem><para>
-When pattern-matching against data constructors drawn from a GADT,
+When pattern-matching against data constructors drawn from a GADT,
for example in a <literal>case</literal> expression, the following rules apply:
<itemizedlist>
<listitem><para>The type of the scrutinee must be rigid.</para></listitem>
-<listitem><para>The type of the result of the <literal>case</literal> expression must be rigid.</para></listitem>
+<listitem><para>The type of the entire <literal>case</literal> expression must be rigid.</para></listitem>
<listitem><para>The type of any free variable mentioned in any of
the <literal>case</literal> alternatives must be rigid.</para></listitem>
</itemizedlist>
A type is "rigid" if it is completely known to the compiler at its binding site. The easiest
way to ensure that a variable a rigid type is to give it a type signature.
+For more precise details see <ulink url="http://research.microsoft.com/%7Esimonpj/papers/gadt">
+Simple unification-based type inference for GADTs
+</ulink>. The criteria implemented by GHC are given in the Appendix.
+
</para></listitem>
</itemizedlist>
instance Eq (f a) => Eq (T1 f a) where ...
instance Eq (f (f a)) => Eq (T2 f a) where ...
</programlisting>
-The first of these is obviously fine. The second is still fine, although less obviously.
+The first of these is obviously fine. The second is still fine, although less obviously.
The third is not Haskell 98, and risks losing termination of instances.
</para>
<para>
GHC takes a conservative position: it accepts the first two, but not the third. The rule is this:
-each constraint in the inferred instance context must consist only of type variables,
+each constraint in the inferred instance context must consist only of type variables,
with no repetitions.
</para>
<para>
</programlisting>
The syntax is identical to that of an ordinary instance declaration apart from (a) the keyword
<literal>deriving</literal>, and (b) the absence of the <literal>where</literal> part.
-You must supply a context (in the example the context is <literal>(Eq a)</literal>),
+Note the following points:
+<itemizedlist>
+<listitem><para>
+You must supply an explicit context (in the example the context is <literal>(Eq a)</literal>),
exactly as you would in an ordinary instance declaration.
-(In contrast the context is inferred in a <literal>deriving</literal> clause
-attached to a data type declaration.)
+(In contrast, in a <literal>deriving</literal> clause
+attached to a data type declaration, the context is inferred.)
+</para></listitem>
+<listitem><para>
A <literal>deriving instance</literal> declaration
must obey the same rules concerning form and termination as ordinary instance declarations,
controlled by the same flags; see <xref linkend="instance-decls"/>.
-</para>
-<para>
+</para></listitem>
+
+<listitem><para>
Unlike a <literal>deriving</literal>
declaration attached to a <literal>data</literal> declaration, the instance can be more specific
-than the data type (assuming you also use
+than the data type (assuming you also use
<literal>-XFlexibleInstances</literal>, <xref linkend="instance-rules"/>). Consider
for example
<programlisting>
</programlisting>
This will generate a derived instance for <literal>(Foo [a])</literal> and <literal>(Foo (Maybe a))</literal>,
but other types such as <literal>(Foo (Int,Bool))</literal> will not be an instance of <literal>Eq</literal>.
+</para></listitem>
+
+<listitem><para>
+Unlike a <literal>deriving</literal>
+declaration attached to a <literal>data</literal> declaration,
+GHC does not restrict the form of the data type. Instead, GHC simply generates the appropriate
+boilerplate code for the specified class, and typechecks it. If there is a type error, it is
+your problem. (GHC will show you the offending code if it has a type error.)
+The merit of this is that you can derive instances for GADTs and other exotic
+data types, providing only that the boilerplate code does indeed typecheck. For example:
+<programlisting>
+ data T a where
+ T1 :: T Int
+ T2 :: T Bool
+
+ deriving instance Show (T a)
+</programlisting>
+In this example, you cannot say <literal>... deriving( Show )</literal> on the
+data type declaration for <literal>T</literal>,
+because <literal>T</literal> is a GADT, but you <emphasis>can</emphasis> generate
+the instance declaration using stand-alone deriving.
</para>
+</listitem>
+<listitem>
<para>The stand-alone syntax is generalised for newtypes in exactly the same
way that ordinary <literal>deriving</literal> clauses are generalised (<xref linkend="newtype-deriving"/>).
For example:
</programlisting>
GHC always treats the <emphasis>last</emphasis> parameter of the instance
(<literal>Foo</literal> in this example) as the type whose instance is being derived.
-</para>
+</para></listitem>
+</itemizedlist></para>
</sect2>
<sect2 id="deriving-typeable">
-<title>Deriving clause for classes <literal>Typeable</literal> and <literal>Data</literal></title>
+<title>Deriving clause for extra classes (<literal>Typeable</literal>, <literal>Data</literal>, etc)</title>
<para>
-Haskell 98 allows the programmer to add "<literal>deriving( Eq, Ord )</literal>" to a data type
-declaration, to generate a standard instance declaration for classes specified in the <literal>deriving</literal> clause.
+Haskell 98 allows the programmer to add "<literal>deriving( Eq, Ord )</literal>" to a data type
+declaration, to generate a standard instance declaration for classes specified in the <literal>deriving</literal> clause.
In Haskell 98, the only classes that may appear in the <literal>deriving</literal> clause are the standard
-classes <literal>Eq</literal>, <literal>Ord</literal>,
+classes <literal>Eq</literal>, <literal>Ord</literal>,
<literal>Enum</literal>, <literal>Ix</literal>, <literal>Bounded</literal>, <literal>Read</literal>, and <literal>Show</literal>.
</para>
<para>
-GHC extends this list with two more classes that may be automatically derived
-(provided the <option>-XDeriveDataTypeable</option> flag is specified):
-<literal>Typeable</literal>, and <literal>Data</literal>. These classes are defined in the library
-modules <literal>Data.Typeable</literal> and <literal>Data.Generics</literal> respectively, and the
-appropriate class must be in scope before it can be mentioned in the <literal>deriving</literal> clause.
+GHC extends this list with several more classes that may be automatically derived:
+<itemizedlist>
+<listitem><para> With <option>-XDeriveDataTypeable</option>, you can derive instances of the classes
+<literal>Typeable</literal>, and <literal>Data</literal>, defined in the library
+modules <literal>Data.Typeable</literal> and <literal>Data.Generics</literal> respectively.
</para>
<para>An instance of <literal>Typeable</literal> can only be derived if the
data type has seven or fewer type parameters, all of kind <literal>*</literal>.
(Section 7.4 of the paper describes the multiple <literal>Typeable</literal> classes that
are used, and only <literal>Typeable1</literal> up to
<literal>Typeable7</literal> are provided in the library.)
-In other cases, there is nothing to stop the programmer writing a <literal>TypableX</literal>
+In other cases, there is nothing to stop the programmer writing a <literal>TypeableX</literal>
class, whose kind suits that of the data type constructor, and
then writing the data type instance by hand.
</para>
+</listitem>
+
+<listitem><para> With <option>-XDeriveGeneric</option>, you can derive
+instances of the class <literal>Generic</literal>, defined in
+<literal>GHC.Generics</literal>. You can use these to define generic functions,
+as described in <xref linkend="generic-programming"/>.
+</para></listitem>
+
+<listitem><para> With <option>-XDeriveFunctor</option>, you can derive instances of
+the class <literal>Functor</literal>,
+defined in <literal>GHC.Base</literal>.
+</para></listitem>
+
+<listitem><para> With <option>-XDeriveFoldable</option>, you can derive instances of
+the class <literal>Foldable</literal>,
+defined in <literal>Data.Foldable</literal>.
+</para></listitem>
+
+<listitem><para> With <option>-XDeriveTraversable</option>, you can derive instances of
+the class <literal>Traversable</literal>,
+defined in <literal>Data.Traversable</literal>.
+</para></listitem>
+</itemizedlist>
+In each case the appropriate class must be in scope before it
+can be mentioned in the <literal>deriving</literal> clause.
+</para>
</sect2>
<sect2 id="newtype-deriving">
example, if you define
<programlisting>
- newtype Dollars = Dollars Int
+ newtype Dollars = Dollars Int
</programlisting>
and you want to use arithmetic on <literal>Dollars</literal>, you have to
<sect3> <title> Generalising the deriving clause </title>
<para>
-GHC now permits such instances to be derived instead,
+GHC now permits such instances to be derived instead,
using the flag <option>-XGeneralizedNewtypeDeriving</option>,
-so one can write
+so one can write
<programlisting>
newtype Dollars = Dollars Int deriving (Eq,Show,Num)
</programlisting>
transformers, such that
<programlisting>
- instance Monad m => Monad (State s m)
+ instance Monad m => Monad (State s m)
instance Monad m => Monad (Failure m)
</programlisting>
-In Haskell 98, we can define a parsing monad by
+In Haskell 98, we can define a parsing monad by
<programlisting>
type Parser tok m a = State [tok] (Failure m) a
</programlisting>
newtype Parser tok m a = Parser (State [tok] (Failure m) a)
deriving Monad
</programlisting>
-In this case the derived instance declaration is of the form
+In this case the derived instance declaration is of the form
<programlisting>
- instance Monad (State [tok] (Failure m)) => Monad (Parser tok m)
+ instance Monad (State [tok] (Failure m)) => Monad (Parser tok m)
</programlisting>
Notice that, since <literal>Monad</literal> is a constructor class, the
clause. For example, given the class
<programlisting>
- class StateMonad s m | m -> s where ...
- instance Monad m => StateMonad s (State s m) where ...
+ class StateMonad s m | m -> s where ...
+ instance Monad m => StateMonad s (State s m) where ...
</programlisting>
-then we can derive an instance of <literal>StateMonad</literal> for <literal>Parser</literal>s by
+then we can derive an instance of <literal>StateMonad</literal> for <literal>Parser</literal>s by
<programlisting>
newtype Parser tok m a = Parser (State [tok] (Failure m) a)
deriving (Monad, StateMonad [tok])
declaration (after expansion of any type synonyms)
<programlisting>
- newtype T v1...vn = T' (t vk+1...vn) deriving (c1...cm)
+ newtype T v1...vn = T' (t vk+1...vn) deriving (c1...cm)
</programlisting>
-where
+where
<itemizedlist>
<listitem><para>
The <literal>ci</literal> are partial applications of
The type <literal>t</literal> is an arbitrary type.
</para></listitem>
<listitem><para>
- The type variables <literal>vk+1...vn</literal> do not occur in <literal>t</literal>,
+ The type variables <literal>vk+1...vn</literal> do not occur in <literal>t</literal>,
nor in the <literal>ci</literal>, and
</para></listitem>
<listitem><para>
- None of the <literal>ci</literal> is <literal>Read</literal>, <literal>Show</literal>,
+ None of the <literal>ci</literal> is <literal>Read</literal>, <literal>Show</literal>,
<literal>Typeable</literal>, or <literal>Data</literal>. These classes
should not "look through" the type or its constructor. You can still
- derive these classes for a newtype, but it happens in the usual way, not
- via this new mechanism.
+ derive these classes for a newtype, but it happens in the usual way, not
+ via this new mechanism.
</para></listitem>
</itemizedlist>
Then, for each <literal>ci</literal>, the derived instance
<programlisting>
instance ci t => ci (T v1...vk)
</programlisting>
-As an example which does <emphasis>not</emphasis> work, consider
+As an example which does <emphasis>not</emphasis> work, consider
<programlisting>
- newtype NonMonad m s = NonMonad (State s m s) deriving Monad
+ newtype NonMonad m s = NonMonad (State s m s) deriving Monad
</programlisting>
-Here we cannot derive the instance
+Here we cannot derive the instance
<programlisting>
- instance Monad (State s m) => Monad (NonMonad m)
+ instance Monad (State s m) => Monad (NonMonad m)
</programlisting>
because the type variable <literal>s</literal> occurs in <literal>State s m</literal>,
<literal>StateMonad</literal> class above were instead defined as
<programlisting>
- class StateMonad m s | m -> s where ...
+ class StateMonad m s | m -> s where ...
</programlisting>
then we would not have been able to derive an instance for the
instances is most interesting.
</para>
<para>Lastly, all of this applies only for classes other than
-<literal>Read</literal>, <literal>Show</literal>, <literal>Typeable</literal>,
+<literal>Read</literal>, <literal>Show</literal>, <literal>Typeable</literal>,
and <literal>Data</literal>, for which the built-in derivation applies (section
4.3.3. of the Haskell Report).
(For the standard classes <literal>Eq</literal>, <literal>Ord</literal>,
<sect3>
<title>Multi-parameter type classes</title>
<para>
-Multi-parameter type classes are permitted. For example:
+Multi-parameter type classes are permitted, with flag <option>-XMultiParamTypeClasses</option>.
+For example:
<programlisting>
</para>
</sect3>
-<sect3>
+<sect3 id="superclass-rules">
<title>The superclasses of a class declaration</title>
<para>
-There are no restrictions on the context in a class declaration
-(which introduces superclasses), except that the class hierarchy must
-be acyclic. So these class declarations are OK:
+In Haskell 98 the context of a class declaration (which introduces superclasses)
+must be simple; that is, each predicate must consist of a class applied to
+type variables. The flag <option>-XFlexibleContexts</option>
+(<xref linkend="flexible-contexts"/>)
+lifts this restriction,
+so that the only restriction on the context in a class declaration is
+that the class hierarchy must be acyclic. So these class declarations are OK:
<programlisting>
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
+contains the constraint <literal>Eq a</literal>, constrains only the
class type variable (in this case <literal>a</literal>).
GHC lifts this restriction (flag <option>-XConstrainedClassMethods</option>).
</para>
</sect3>
+
+
+<sect3 id="class-default-signatures">
+<title>Default signatures</title>
+
+<para>
+Haskell 98 allows you to define a default implementation when declaring a class:
+<programlisting>
+ class Enum a where
+ enum :: [a]
+ enum = []
+</programlisting>
+The type of the <literal>enum</literal> method is <literal>[a]</literal>, and
+this is also the type of the default method. You can lift this restriction
+and give another type to the default method using the flag
+<option>-XDefaultSignatures</option>. For instance, if you have written a
+generic implementation of enumeration in a class <literal>GEnum</literal>
+with method <literal>genum</literal> in terms of <literal>GHC.Generics</literal>,
+you can specify a default method that uses that generic implementation:
+<programlisting>
+ class Enum a where
+ enum :: [a]
+ default enum :: (Generic a, GEnum (Rep a)) => [a]
+ enum = map to genum
+</programlisting>
+We reuse the keyword <literal>default</literal> to signal that a signature
+applies to the default method only; when defining instances of the
+<literal>Enum</literal> class, the original type <literal>[a]</literal> of
+<literal>enum</literal> still applies. When giving an empty instance, however,
+the default implementation <literal>map to0 genum</literal> is filled-in,
+and type-checked with the type
+<literal>(Generic a, GEnum (Rep a)) => [a]</literal>.
+</para>
+
+<para>
+We use default signatures to simplify generic programming in GHC
+(<xref linkend="generic-programming"/>).
+</para>
+
+
+</sect3>
</sect2>
<sect2 id="functional-dependencies">
</title>
<para> Functional dependencies are implemented as described by Mark Jones
-in “<ulink url="http://citeseer.ist.psu.edu/jones00type.html">Type Classes with Functional Dependencies</ulink>”, Mark P. Jones,
-In Proceedings of the 9th European Symposium on Programming,
+in “<ulink url="http://citeseer.ist.psu.edu/jones00type.html">Type Classes with Functional Dependencies</ulink>”, Mark P. Jones,
+In Proceedings of the 9th European Symposium on Programming,
ESOP 2000, Berlin, Germany, March 2000, Springer-Verlag LNCS 1782,
.
</para>
<para>
-Functional dependencies are introduced by a vertical bar in the syntax of a
-class declaration; e.g.
+Functional dependencies are introduced by a vertical bar in the syntax of a
+class declaration; e.g.
<programlisting>
class (Monad m) => MonadState s m | m -> s where ...
<sect3><title>Rules for functional dependencies </title>
<para>
-In a class declaration, all of the class type variables must be reachable (in the sense
-mentioned in <xref linkend="type-restrictions"/>)
+In a class declaration, all of the class type variables must be reachable (in the sense
+mentioned in <xref linkend="flexible-contexts"/>)
from the free variables of each method type.
For example:
from the Hugs user manual, reproduced here (with minor changes) by kind
permission of Mark Jones.
</para>
-<para>
+<para>
Consider the following class, intended as part of a
library for collection types:
<programlisting>
can be used to represent collections of any equality type), bit sets (which can
be used to represent collections of characters), or hash tables (which can be
used to represent any collection whose elements have a hash function). Omitting
-standard implementation details, this would lead to the following declarations:
+standard implementation details, this would lead to the following declarations:
<programlisting>
instance Eq e => Collects e [e] where ...
instance Eq e => Collects e (e -> Bool) where ...
</programlisting>
All this looks quite promising; we have a class and a range of interesting
implementations. Unfortunately, there are some serious problems with the class
-declaration. First, the empty function has an ambiguous type:
+declaration. First, the empty function has an ambiguous type:
<programlisting>
empty :: Collects e ce => ce
</programlisting>
We can sidestep this specific problem by removing the empty member from the
class declaration. However, although the remaining members, insert and member,
do not have ambiguous types, we still run into problems when we try to use
-them. For example, consider the following two functions:
+them. For example, consider the following two functions:
<programlisting>
f x y = insert x . insert y
g = f True 'a'
</programlisting>
-for which GHC infers the following types:
+for which GHC infers the following types:
<programlisting>
f :: (Collects a c, Collects b c) => a -> b -> c -> c
g :: (Collects Bool c, Collects Char c) => c -> c
<para>
Faced with the problems described above, some Haskell programmers might be
-tempted to use something like the following version of the class declaration:
+tempted to use something like the following version of the class declaration:
<programlisting>
class Collects e c where
empty :: c e
used to form the collection type c e, and not over that collection type itself,
represented by ce in the original class declaration. This avoids the immediate
problems that we mentioned above: empty has type <literal>Collects e c => c
-e</literal>, which is not ambiguous.
+e</literal>, which is not ambiguous.
</para>
<para>
-The function f from the previous section has a more accurate type:
+The function f from the previous section has a more accurate type:
<programlisting>
f :: (Collects e c) => e -> e -> c e -> c e
</programlisting>
The function g from the previous section is now rejected with a type error as
we would hope because the type of f does not allow the two arguments to have
-different types.
+different types.
This, then, is an example of a multiple parameter class that does actually work
quite well in practice, without ambiguity problems.
There is, however, a catch. This version of the Collects class is nowhere near
in a manuscript [implparam], where they are identified as one point in a
general design space for systems of implicit parameterization.).
-To start with an abstract example, consider a declaration such as:
+To start with an abstract example, consider a declaration such as:
<programlisting>
class C a b where ...
</programlisting>
which tells us simply that C can be thought of as a binary relation on types
(or type constructors, depending on the kinds of a and b). Extra clauses can be
included in the definition of classes to add information about dependencies
-between parameters, as in the following examples:
+between parameters, as in the following examples:
<programlisting>
class D a b | a -> b where ...
class E a b | a -> b, b -> a where ...
definition of E above. Some dependencies that we can write in this notation are
redundant, and will be rejected because they don't serve any useful
purpose, and may instead indicate an error in the program. Examples of
-dependencies like this include <literal>a -> a </literal>,
-<literal>a -> a a </literal>,
+dependencies like this include <literal>a -> a </literal>,
+<literal>a -> a a </literal>,
<literal>a -> </literal>, etc. There can also be
-some redundancy if multiple dependencies are given, as in
-<literal>a->b</literal>,
+some redundancy if multiple dependencies are given, as in
+<literal>a->b</literal>,
<literal>b->c </literal>, <literal>a->c </literal>, and
in which some subset implies the remaining dependencies. Examples like this are
not treated as errors. Note that dependencies appear only in class
instances that are in scope at any given point in the program is consistent
with any declared dependencies. For example, the following pair of instance
declarations cannot appear together in the same scope because they violate the
-dependency for D, even though either one on its own would be acceptable:
+dependency for D, even though either one on its own would be acceptable:
<programlisting>
instance D Bool Int where ...
instance D Bool Char where ...
</programlisting>
-Note also that the following declaration is not allowed, even by itself:
+Note also that the following declaration is not allowed, even by itself:
<programlisting>
instance D [a] b where ...
</programlisting>
The problem here is that this instance would allow one particular choice of [a]
to be associated with more than one choice for b, which contradicts the
dependency specified in the definition of D. More generally, this means that,
-in any instance of the form:
+in any instance of the form:
<programlisting>
instance D t s where ...
</programlisting>
more general multiple parameter classes, without ambiguity problems, and with
the benefit of more accurate types. To illustrate this, we return to the
collection class example, and annotate the original definition of <literal>Collects</literal>
-with a simple dependency:
+with a simple dependency:
<programlisting>
class Collects e ce | ce -> e where
empty :: ce
Dependencies also help to produce more accurate types for user defined
functions, and hence to provide earlier detection of errors, and less cluttered
types for programmers to work with. Recall the previous definition for a
-function f:
+function f:
<programlisting>
f x y = insert x y = insert x . insert y
</programlisting>
-for which we originally obtained a type:
+for which we originally obtained a type:
<programlisting>
f :: (Collects a c, Collects b c) => a -> b -> c -> c
</programlisting>
Given the dependency information that we have for Collects, however, we can
deduce that a and b must be equal because they both appear as the second
parameter in a Collects constraint with the same first parameter c. Hence we
-can infer a shorter and more accurate type for f:
+can infer a shorter and more accurate type for f:
<programlisting>
f :: (Collects a c) => a -> a -> c -> c
</programlisting>
<sect2 id="instance-decls">
<title>Instance declarations</title>
-<sect3 id="instance-rules">
-<title>Relaxed rules for instance declarations</title>
-
<para>An instance declaration has the form
<screen>
instance ( <replaceable>assertion</replaceable><subscript>1</subscript>, ..., <replaceable>assertion</replaceable><subscript>n</subscript>) => <replaceable>class</replaceable> <replaceable>type</replaceable><subscript>1</subscript> ... <replaceable>type</replaceable><subscript>m</subscript> where ...
"<literal>=></literal>" is the <emphasis>head</emphasis> of the instance declaration.
</para>
+<sect3 id="flexible-instance-head">
+<title>Relaxed rules for the instance head</title>
+
<para>
In Haskell 98 the head of an instance declaration
must be of the form <literal>C (T a1 ... an)</literal>, where
-<literal>C</literal> is the class, <literal>T</literal> is a type constructor,
+<literal>C</literal> is the class, <literal>T</literal> is a data type constructor,
and the <literal>a1 ... an</literal> are distinct type variables.
-Furthermore, the assertions in the context of the instance declaration
+GHC relaxes these rules in two ways.
+<itemizedlist>
+<listitem>
+<para>
+The <option>-XFlexibleInstances</option> flag allows the head of the instance
+declaration to mention arbitrary nested types.
+For example, this becomes a legal instance declaration
+<programlisting>
+ instance C (Maybe Int) where ...
+</programlisting>
+See also the <link linkend="instance-overlap">rules on overlap</link>.
+</para></listitem>
+<listitem><para>
+With the <option>-XTypeSynonymInstances</option> flag, instance heads may use type
+synonyms. As always, using a type synonym is just shorthand for
+writing the RHS of the type synonym definition. For example:
+
+
+<programlisting>
+ type Point = (Int,Int)
+ instance C Point where ...
+ instance C [Point] where ...
+</programlisting>
+
+
+is legal. However, if you added
+
+
+<programlisting>
+ instance C (Int,Int) where ...
+</programlisting>
+
+
+as well, then the compiler will complain about the overlapping
+(actually, identical) instance declarations. As always, type synonyms
+must be fully applied. You cannot, for example, write:
+
+<programlisting>
+ type P a = [[a]]
+ instance Monad P where ...
+</programlisting>
+
+</para></listitem>
+</itemizedlist>
+</para>
+</sect3>
+
+<sect3 id="instance-rules">
+<title>Relaxed rules for instance contexts</title>
+
+<para>In Haskell 98, the assertions in the context of the instance declaration
must be of the form <literal>C a</literal> where <literal>a</literal>
is a type variable that occurs in the head.
</para>
+
<para>
-The <option>-XFlexibleInstances</option> flag loosens these restrictions
-considerably. Firstly, multi-parameter type classes are permitted. Secondly,
-the context and head of the instance declaration can each consist of arbitrary
+The <option>-XFlexibleContexts</option> flag relaxes this rule, as well
+as the corresponding rule for type signatures (see <xref linkend="flexible-contexts"/>).
+With this flag the context of the instance declaration can each consist of arbitrary
(well-kinded) assertions <literal>(C t1 ... tn)</literal> subject only to the
following rules:
<orderedlist>
<replaceable>tvs</replaceable><subscript>left</subscript> <literal>-></literal>
<replaceable>tvs</replaceable><subscript>right</subscript>, of the class,
every type variable in
-S(<replaceable>tvs</replaceable><subscript>right</subscript>) must appear in
+S(<replaceable>tvs</replaceable><subscript>right</subscript>) must appear in
S(<replaceable>tvs</replaceable><subscript>left</subscript>), where S is the
substitution mapping each type variable in the class declaration to the
corresponding type in the instance declaration.
</orderedlist>
These restrictions ensure that context reduction terminates: each reduction
step makes the problem smaller by at least one
-constructor. Both the Paterson Conditions and the Coverage Condition are lifted
-if you give the <option>-XUndecidableInstances</option>
+constructor. Both the Paterson Conditions and the Coverage Condition are lifted
+if you give the <option>-XUndecidableInstances</option>
flag (<xref linkend="undecidable-instances"/>).
You can find lots of background material about the reason for these
restrictions in the paper <ulink
instance Eq (S [a]) -- Structured type in head
-- Repeated type variable in head
- instance C4 a a => C4 [a] [a]
+ instance C4 a a => C4 [a] [a]
instance Stateful (ST s) (MutVar s)
-- Head can consist of type variables only
<programlisting>
-- Context assertion no smaller than head
instance C a => C a where ...
- -- (C b b) has more more occurrences of b than the head
+ -- (C b b) has more occurrences of b than the head
instance C b b => Foo [b] where ...
</programlisting>
</para>
<programlisting>
class HasConverter a b | a -> b where
convert :: a -> b
-
+
data Foo a = MkFoo a
instance (HasConverter a b,Show b) => Show (Foo a) where
<para>
Nevertheless, GHC allows you to experiment with more liberal rules. If you use
the experimental flag <option>-XUndecidableInstances</option>
-<indexterm><primary>-XUndecidableInstances</primary></indexterm>,
+<indexterm><primary>-XUndecidableInstances</primary></indexterm>,
both the Paterson Conditions and the Coverage Condition
(described in <xref linkend="instance-rules"/>) are lifted. Termination is ensured by having a
fixed-depth recursion stack. If you exceed the stack depth you get a
should be used to resolve a type-class constraint</emphasis>. This behaviour
can be modified by two flags: <option>-XOverlappingInstances</option>
<indexterm><primary>-XOverlappingInstances
-</primary></indexterm>
+</primary></indexterm>
and <option>-XIncoherentInstances</option>
<indexterm><primary>-XIncoherentInstances
</primary></indexterm>, as this section discusses. Both these
-flags are dynamic flags, and can be set on a per-module basis, using
+flags are dynamic flags, and can be set on a per-module basis, using
an <literal>OPTIONS_GHC</literal> pragma if desired (<xref linkend="source-file-options"/>).</para>
<para>
When GHC tries to resolve, say, the constraint <literal>C Int Bool</literal>,
instance context3 => C Int [a] where ... -- (C)
instance context4 => C Int [Int] where ... -- (D)
</programlisting>
-The instances (A) and (B) match the constraint <literal>C Int Bool</literal>,
+The instances (A) and (B) match the constraint <literal>C Int Bool</literal>,
but (C) and (D) do not. When matching, GHC takes
no account of the context of the instance declaration
(<literal>context1</literal> etc).
GHC's default behaviour is that <emphasis>exactly one instance must match the
-constraint it is trying to resolve</emphasis>.
+constraint it is trying to resolve</emphasis>.
It is fine for there to be a <emphasis>potential</emphasis> of overlap (by
-including both declarations (A) and (B), say); an error is only reported if a
+including both declarations (A) and (B), say); an error is only reported if a
particular constraint matches more than one.
</para>
Suppose that from the RHS of <literal>f</literal> we get the constraint
<literal>C Int [b]</literal>. But
GHC does not commit to instance (C), because in a particular
-call of <literal>f</literal>, <literal>b</literal> might be instantiate
+call of <literal>f</literal>, <literal>b</literal> might be instantiate
to <literal>Int</literal>, in which case instance (D) would be more specific still.
-So GHC rejects the program.
+So GHC rejects the program.
(If you add the flag <option>-XIncoherentInstances</option>,
-GHC will instead pick (C), without complaining about
+GHC will instead pick (C), without complaining about
the problem of subsequent instantiations.)
</para>
<para>
Notice that we gave a type signature to <literal>f</literal>, so GHC had to
-<emphasis>check</emphasis> that <literal>f</literal> has the specified type.
+<emphasis>check</emphasis> that <literal>f</literal> has the specified type.
Suppose instead we do not give a type signature, asking GHC to <emphasis>infer</emphasis>
it instead. In this case, GHC will refrain from
-simplifying the constraint <literal>C Int [Int]</literal> (for the same reason
+simplifying the constraint <literal>C Int [b]</literal> (for the same reason
as before) but, rather than rejecting the program, it will infer the type
<programlisting>
- f :: C Int b => [b] -> [b]
+ f :: C Int [b] => [b] -> [b]
</programlisting>
-That postpones the question of which instance to pick to the
+That postpones the question of which instance to pick to the
call site for <literal>f</literal>
by which time more is known about the type <literal>b</literal>.
+You can write this type signature yourself if you use the
+<link linkend="flexible-contexts"><option>-XFlexibleContexts</option></link>
+flag.
+</para>
+<para>
+Exactly the same situation can arise in instance declarations themselves. Suppose we have
+<programlisting>
+ class Foo a where
+ f :: a -> a
+ instance Foo [b] where
+ f x = ...
+</programlisting>
+and, as before, the constraint <literal>C Int [b]</literal> arises from <literal>f</literal>'s
+right hand side. GHC will reject the instance, complaining as before that it does not know how to resolve
+the constraint <literal>C Int [b]</literal>, because it matches more than one instance
+declaration. The solution is to postpone the choice by adding the constraint to the context
+of the instance declaration, thus:
+<programlisting>
+ instance C Int [b] => Foo [b] where
+ f x = ...
+</programlisting>
+(You need <link linkend="instance-rules"><option>-XFlexibleInstances</option></link> to do this.)
+</para>
+<para>
+Warning: overlapping instances must be used with care. They
+can give rise to incoherence (ie different instance choices are made
+in different parts of the program) even without <option>-XIncoherentInstances</option>. Consider:
+<programlisting>
+{-# LANGUAGE OverlappingInstances #-}
+module Help where
+
+ class MyShow a where
+ myshow :: a -> String
+
+ instance MyShow a => MyShow [a] where
+ myshow xs = concatMap myshow xs
+
+ showHelp :: MyShow a => [a] -> String
+ showHelp xs = myshow xs
+
+{-# LANGUAGE FlexibleInstances, OverlappingInstances #-}
+module Main where
+ import Help
+
+ data T = MkT
+
+ instance MyShow T where
+ myshow x = "Used generic instance"
+
+ instance MyShow [T] where
+ myshow xs = "Used more specific instance"
+
+ main = do { print (myshow [MkT]); print (showHelp [MkT]) }
+</programlisting>
+In function <literal>showHelp</literal> GHC sees no overlapping
+instances, and so uses the <literal>MyShow [a]</literal> instance
+without complaint. In the call to <literal>myshow</literal> in <literal>main</literal>,
+GHC resolves the <literal>MyShow [T]</literal> constraint using the overlapping
+instance declaration in module <literal>Main</literal>. As a result,
+the program prints
+<programlisting>
+ "Used more specific instance"
+ "Used generic instance"
+</programlisting>
+(An alternative possible behaviour, not currently implemented,
+would be to reject module <literal>Help</literal>
+on the grounds that a later instance declaration might overlap the local one.)
</para>
<para>
-The willingness to be overlapped or incoherent is a property of
+The willingness to be overlapped or incoherent is a property of
the <emphasis>instance declaration</emphasis> itself, controlled by the
-presence or otherwise of the <option>-XOverlappingInstances</option>
+presence or otherwise of the <option>-XOverlappingInstances</option>
and <option>-XIncoherentInstances</option> flags when that module is
-being defined. Neither flag is required in a module that imports and uses the
-instance declaration. Specifically, during the lookup process:
+being defined. Specifically, during the lookup process:
<itemizedlist>
<listitem><para>
-An instance declaration is ignored during the lookup process if (a) a more specific
-match is found, and (b) the instance declaration was compiled with
-<option>-XOverlappingInstances</option>. The flag setting for the
-more-specific instance does not matter.
+If the constraint being looked up matches two instance declarations IA and IB,
+and
+<itemizedlist>
+<listitem><para>IB is a substitution instance of IA (but not vice versa);
+that is, IB is strictly more specific than IA</para></listitem>
+<listitem><para>either IA or IB was compiled with <option>-XOverlappingInstances</option></para></listitem>
+</itemizedlist>
+then the less-specific instance IA is ignored.
</para></listitem>
<listitem><para>
Suppose an instance declaration does not match the constraint being looked up, but
-does unify with it, so that it might match when the constraint is further
+does <emphasis>unify</emphasis> with it, so that it might match when the constraint is further
instantiated. Usually GHC will regard this as a reason for not committing to
some other constraint. But if the instance declaration was compiled with
-<option>-XIncoherentInstances</option>, GHC will skip the "does-it-unify?"
+<option>-XIncoherentInstances</option>, GHC will skip the "does-it-unify?"
check for that declaration.
</para></listitem>
</itemizedlist>
-These rules make it possible for a library author to design a library that relies on
-overlapping instances without the library client having to know.
-</para>
-<para>
-If an instance declaration is compiled without
-<option>-XOverlappingInstances</option>,
-then that instance can never be overlapped. This could perhaps be
-inconvenient. Perhaps the rule should instead say that the
-<emphasis>overlapping</emphasis> instance declaration should be compiled in
-this way, rather than the <emphasis>overlapped</emphasis> one. Perhaps overlap
-at a usage site should be permitted regardless of how the instance declarations
-are compiled, if the <option>-XOverlappingInstances</option> flag is
-used at the usage site. (Mind you, the exact usage site can occasionally be
-hard to pin down.) We are interested to receive feedback on these points.
+These rules make it possible for a library author to design a library that relies on
+overlapping instances without the library client having to know.
</para>
<para>The <option>-XIncoherentInstances</option> flag implies the
<option>-XOverlappingInstances</option> flag, but not vice versa.
</para>
</sect3>
-<sect3>
-<title>Type synonyms in the instance head</title>
-<para>
-<emphasis>Unlike Haskell 98, instance heads may use type
-synonyms</emphasis>. (The instance "head" is the bit after the "=>" in an instance decl.)
-As always, using a type synonym is just shorthand for
-writing the RHS of the type synonym definition. For example:
+</sect2>
+
+<sect2 id="overloaded-strings">
+<title>Overloaded string literals
+</title>
+<para>
+GHC supports <emphasis>overloaded string literals</emphasis>. Normally a
+string literal has type <literal>String</literal>, but with overloaded string
+literals enabled (with <literal>-XOverloadedStrings</literal>)
+ a string literal has type <literal>(IsString a) => a</literal>.
+</para>
+<para>
+This means that the usual string syntax can be used, e.g., for packed strings
+and other variations of string like types. String literals behave very much
+like integer literals, i.e., they can be used in both expressions and patterns.
+If used in a pattern the literal with be replaced by an equality test, in the same
+way as an integer literal is.
+</para>
+<para>
+The class <literal>IsString</literal> is defined as:
<programlisting>
- type Point = (Int,Int)
- instance C Point where ...
- instance C [Point] where ...
+class IsString a where
+ fromString :: String -> a
+</programlisting>
+The only predefined instance is the obvious one to make strings work as usual:
+<programlisting>
+instance IsString [Char] where
+ fromString cs = cs
</programlisting>
+The class <literal>IsString</literal> is not in scope by default. If you want to mention
+it explicitly (for example, to give an instance declaration for it), you can import it
+from module <literal>GHC.Exts</literal>.
+</para>
+<para>
+Haskell's defaulting mechanism is extended to cover string literals, when <option>-XOverloadedStrings</option> is specified.
+Specifically:
+<itemizedlist>
+<listitem><para>
+Each type in a default declaration must be an
+instance of <literal>Num</literal> <emphasis>or</emphasis> of <literal>IsString</literal>.
+</para></listitem>
+
+<listitem><para>
+The standard defaulting rule (<ulink url="http://www.haskell.org/onlinereport/decls.html#sect4.3.4">Haskell Report, Section 4.3.4</ulink>)
+is extended thus: defaulting applies when all the unresolved constraints involve standard classes
+<emphasis>or</emphasis> <literal>IsString</literal>; and at least one is a numeric class
+<emphasis>or</emphasis> <literal>IsString</literal>.
+</para></listitem>
+</itemizedlist>
+</para>
+<para>
+A small example:
+<programlisting>
+module Main where
+import GHC.Exts( IsString(..) )
-is legal. However, if you added
+newtype MyString = MyString String deriving (Eq, Show)
+instance IsString MyString where
+ fromString = MyString
+
+greet :: MyString -> MyString
+greet "hello" = "world"
+greet other = other
+
+main = do
+ print $ greet "hello"
+ print $ greet "fool"
+</programlisting>
+</para>
+<para>
+Note that deriving <literal>Eq</literal> is necessary for the pattern matching
+to work since it gets translated into an equality comparison.
+</para>
+</sect2>
+
+</sect1>
+
+<sect1 id="type-families">
+<title>Type families</title>
+
+<para>
+ <firstterm>Indexed type families</firstterm> are a new GHC extension to
+ facilitate type-level
+ programming. Type families are a generalisation of <firstterm>associated
+ data types</firstterm>
+ (“<ulink url="http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html">Associated
+ Types with Class</ulink>”, M. Chakravarty, G. Keller, S. Peyton Jones,
+ and S. Marlow. In Proceedings of “The 32nd Annual ACM SIGPLAN-SIGACT
+ Symposium on Principles of Programming Languages (POPL'05)”, pages
+ 1-13, ACM Press, 2005) and <firstterm>associated type synonyms</firstterm>
+ (“<ulink url="http://www.cse.unsw.edu.au/~chak/papers/CKP05.html">Type
+ Associated Type Synonyms</ulink>”. M. Chakravarty, G. Keller, and
+ S. Peyton Jones.
+ In Proceedings of “The Tenth ACM SIGPLAN International Conference on
+ Functional Programming”, ACM Press, pages 241-253, 2005). Type families
+ themselves are described in the paper “<ulink
+ url="http://www.cse.unsw.edu.au/~chak/papers/SPCS08.html">Type
+ Checking with Open Type Functions</ulink>”, T. Schrijvers,
+ S. Peyton-Jones,
+ M. Chakravarty, and M. Sulzmann, in Proceedings of “ICFP 2008: The
+ 13th ACM SIGPLAN International Conference on Functional
+ Programming”, ACM Press, pages 51-62, 2008. Type families
+ essentially provide type-indexed data types and named functions on types,
+ which are useful for generic programming and highly parameterised library
+ interfaces as well as interfaces with enhanced static information, much like
+ dependent types. They might also be regarded as an alternative to functional
+ dependencies, but provide a more functional style of type-level programming
+ than the relational style of functional dependencies.
+</para>
+<para>
+ Indexed type families, or type families for short, are type constructors that
+ represent sets of types. Set members are denoted by supplying the type family
+ constructor with type parameters, which are called <firstterm>type
+ indices</firstterm>. The
+ difference between vanilla parametrised type constructors and family
+ constructors is much like between parametrically polymorphic functions and
+ (ad-hoc polymorphic) methods of type classes. Parametric polymorphic functions
+ behave the same at all type instances, whereas class methods can change their
+ behaviour in dependence on the class type parameters. Similarly, vanilla type
+ constructors imply the same data representation for all type instances, but
+ family constructors can have varying representation types for varying type
+ indices.
+</para>
+<para>
+ Indexed type families come in two flavours: <firstterm>data
+ families</firstterm> and <firstterm>type synonym
+ families</firstterm>. They are the indexed family variants of algebraic
+ data types and type synonyms, respectively. The instances of data families
+ can be data types and newtypes.
+</para>
+<para>
+ Type families are enabled by the flag <option>-XTypeFamilies</option>.
+ Additional information on the use of type families in GHC is available on
+ <ulink url="http://www.haskell.org/haskellwiki/GHC/Indexed_types">the
+ Haskell wiki page on type families</ulink>.
+</para>
+
+<sect2 id="data-families">
+ <title>Data families</title>
+
+ <para>
+ Data families appear in two flavours: (1) they can be defined on the
+ toplevel
+ or (2) they can appear inside type classes (in which case they are known as
+ associated types). The former is the more general variant, as it lacks the
+ requirement for the type-indexes to coincide with the class
+ parameters. However, the latter can lead to more clearly structured code and
+ compiler warnings if some type instances were - possibly accidentally -
+ omitted. In the following, we always discuss the general toplevel form first
+ and then cover the additional constraints placed on associated types.
+ </para>
+ <sect3 id="data-family-declarations">
+ <title>Data family declarations</title>
+ <para>
+ Indexed data families are introduced by a signature, such as
<programlisting>
- instance C (Int,Int) where ...
+data family GMap k :: * -> *
+</programlisting>
+ The special <literal>family</literal> distinguishes family from standard
+ data declarations. The result kind annotation is optional and, as
+ usual, defaults to <literal>*</literal> if omitted. An example is
+<programlisting>
+data family Array e
+</programlisting>
+ Named arguments can also be given explicit kind signatures if needed.
+ Just as with
+ [http://www.haskell.org/ghc/docs/latest/html/users_guide/gadt.html GADT
+ declarations] named arguments are entirely optional, so that we can
+ declare <literal>Array</literal> alternatively with
+<programlisting>
+data family Array :: * -> *
+</programlisting>
+ </para>
+
+ <sect4 id="assoc-data-family-decl">
+ <title>Associated data family declarations</title>
+ <para>
+ When a data family is declared as part of a type class, we drop
+ the <literal>family</literal> special. The <literal>GMap</literal>
+ declaration takes the following form
+<programlisting>
+class GMapKey k where
+ data GMap k :: * -> *
+ ...
+</programlisting>
+ In contrast to toplevel declarations, named arguments must be used for
+ all type parameters that are to be used as type-indexes. Moreover,
+ the argument names must be class parameters. Each class parameter may
+ only be used at most once per associated type, but some may be omitted
+ and they may be in an order other than in the class head. Hence, the
+ following contrived example is admissible:
+<programlisting>
+ class C a b c where
+ data T c a :: *
</programlisting>
+ </para>
+ </sect4>
+ </sect3>
+
+ <sect3 id="data-instance-declarations">
+ <title>Data instance declarations</title>
+
+ <para>
+ Instance declarations of data and newtype families are very similar to
+ standard data and newtype declarations. The only two differences are
+ that the keyword <literal>data</literal> or <literal>newtype</literal>
+ is followed by <literal>instance</literal> and that some or all of the
+ type arguments can be non-variable types, but may not contain forall
+ types or type synonym families. However, data families are generally
+ allowed in type parameters, and type synonyms are allowed as long as
+ they are fully applied and expand to a type that is itself admissible -
+ exactly as this is required for occurrences of type synonyms in class
+ instance parameters. For example, the <literal>Either</literal>
+ instance for <literal>GMap</literal> is
+<programlisting>
+data instance GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)
+</programlisting>
+ In this example, the declaration has only one variant. In general, it
+ can be any number.
+ </para>
+ <para>
+ Data and newtype instance declarations are only permitted when an
+ appropriate family declaration is in scope - just as a class instance declaration
+ requires the class declaration to be visible. Moreover, each instance
+ declaration has to conform to the kind determined by its family
+ declaration. This implies that the number of parameters of an instance
+ declaration matches the arity determined by the kind of the family.
+ </para>
+ <para>
+ A data family instance declaration can use the full expressiveness of
+ ordinary <literal>data</literal> or <literal>newtype</literal> declarations:
+ <itemizedlist>
+ <listitem><para> Although, a data family is <emphasis>introduced</emphasis> with
+ the keyword "<literal>data</literal>", a data family <emphasis>instance</emphasis> can
+ use either <literal>data</literal> or <literal>newtype</literal>. For example:
+<programlisting>
+data family T a
+data instance T Int = T1 Int | T2 Bool
+newtype instance T Char = TC Bool
+</programlisting>
+ </para></listitem>
+ <listitem><para> A <literal>data instance</literal> can use GADT syntax for the data constructors,
+ and indeed can define a GADT. For example:
+<programlisting>
+data family G a b
+data instance G [a] b where
+ G1 :: c -> G [Int] b
+ G2 :: G [a] Bool
+</programlisting>
+ </para></listitem>
+ <listitem><para> You can use a <literal>deriving</literal> clause on a
+ <literal>data instance</literal> or <literal>newtype instance</literal>
+ declaration.
+ </para></listitem>
+ </itemizedlist>
+ </para>
+ <para>
+ Even if type families are defined as toplevel declarations, functions
+ that perform different computations for different family instances may still
+ need to be defined as methods of type classes. In particular, the
+ following is not possible:
+<programlisting>
+data family T a
+data instance T Int = A
+data instance T Char = B
+foo :: T a -> Int
+foo A = 1 -- WRONG: These two equations together...
+foo B = 2 -- ...will produce a type error.
+</programlisting>
+Instead, you would have to write <literal>foo</literal> as a class operation, thus:
+<programlisting>
+class C a where
+ foo :: T a -> Int
+instance Foo Int where
+ foo A = 1
+instance Foo Char where
+ foo B = 2
+</programlisting>
+ (Given the functionality provided by GADTs (Generalised Algebraic Data
+ Types), it might seem as if a definition, such as the above, should be
+ feasible. However, type families are - in contrast to GADTs - are
+ <emphasis>open;</emphasis> i.e., new instances can always be added,
+ possibly in other
+ modules. Supporting pattern matching across different data instances
+ would require a form of extensible case construct.)
+ </para>
-as well, then the compiler will complain about the overlapping
-(actually, identical) instance declarations. As always, type synonyms
-must be fully applied. You cannot, for example, write:
+ <sect4 id="assoc-data-inst">
+ <title>Associated data instances</title>
+ <para>
+ When an associated data family instance is declared within a type
+ class instance, we drop the <literal>instance</literal> keyword in the
+ family instance. So, the <literal>Either</literal> instance
+ for <literal>GMap</literal> becomes:
+<programlisting>
+instance (GMapKey a, GMapKey b) => GMapKey (Either a b) where
+ data GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)
+ ...
+</programlisting>
+ The most important point about associated family instances is that the
+ type indexes corresponding to class parameters must be identical to
+ the type given in the instance head; here this is the first argument
+ of <literal>GMap</literal>, namely <literal>Either a b</literal>,
+ which coincides with the only class parameter. Any parameters to the
+ family constructor that do not correspond to class parameters, need to
+ be variables in every instance; here this is the
+ variable <literal>v</literal>.
+ </para>
+ <para>
+ Instances for an associated family can only appear as part of
+ instances declarations of the class in which the family was declared -
+ just as with the equations of the methods of a class. Also in
+ correspondence to how methods are handled, declarations of associated
+ types can be omitted in class instances. If an associated family
+ instance is omitted, the corresponding instance type is not inhabited;
+ i.e., only diverging expressions, such
+ as <literal>undefined</literal>, can assume the type.
+ </para>
+ </sect4>
+ <sect4 id="scoping-class-params">
+ <title>Scoping of class parameters</title>
+ <para>
+ In the case of multi-parameter type classes, the visibility of class
+ parameters in the right-hand side of associated family instances
+ depends <emphasis>solely</emphasis> on the parameters of the data
+ family. As an example, consider the simple class declaration
+<programlisting>
+class C a b where
+ data T a
+</programlisting>
+ Only one of the two class parameters is a parameter to the data
+ family. Hence, the following instance declaration is invalid:
+<programlisting>
+instance C [c] d where
+ data T [c] = MkT (c, d) -- WRONG!! 'd' is not in scope
+</programlisting>
+ Here, the right-hand side of the data instance mentions the type
+ variable <literal>d</literal> that does not occur in its left-hand
+ side. We cannot admit such data instances as they would compromise
+ type safety.
+ </para>
+ </sect4>
+ <sect4 id="family-class-inst">
+ <title>Type class instances of family instances</title>
+ <para>
+ Type class instances of instances of data families can be defined as
+ usual, and in particular data instance declarations can
+ have <literal>deriving</literal> clauses. For example, we can write
<programlisting>
- type P a = [[a]]
- instance Monad P where ...
+data GMap () v = GMapUnit (Maybe v)
+ deriving Show
</programlisting>
+ which implicitly defines an instance of the form
+<programlisting>
+instance Show v => Show (GMap () v) where ...
+</programlisting>
+ </para>
+ <para>
+ Note that class instances are always for
+ particular <emphasis>instances</emphasis> of a data family and never
+ for an entire family as a whole. This is for essentially the same
+ reasons that we cannot define a toplevel function that performs
+ pattern matching on the data constructors
+ of <emphasis>different</emphasis> instances of a single type family.
+ It would require a form of extensible case construct.
+ </para>
+ </sect4>
+
+ <sect4 id="data-family-overlap">
+ <title>Overlap of data instances</title>
+ <para>
+ The instance declarations of a data family used in a single program
+ may not overlap at all, independent of whether they are associated or
+ not. In contrast to type class instances, this is not only a matter
+ of consistency, but one of type safety.
+ </para>
+ </sect4>
+
+ </sect3>
+
+ <sect3 id="data-family-import-export">
+ <title>Import and export</title>
+
+ <para>
+ The association of data constructors with type families is more dynamic
+ than that is the case with standard data and newtype declarations. In
+ the standard case, the notation <literal>T(..)</literal> in an import or
+ export list denotes the type constructor and all the data constructors
+ introduced in its declaration. However, a family declaration never
+ introduces any data constructors; instead, data constructors are
+ introduced by family instances. As a result, which data constructors
+ are associated with a type family depends on the currently visible
+ instance declarations for that family. Consequently, an import or
+ export item of the form <literal>T(..)</literal> denotes the family
+ constructor and all currently visible data constructors - in the case of
+ an export item, these may be either imported or defined in the current
+ module. The treatment of import and export items that explicitly list
+ data constructors, such as <literal>GMap(GMapEither)</literal>, is
+ analogous.
+ </para>
+
+ <sect4 id="data-family-impexp-assoc">
+ <title>Associated families</title>
+ <para>
+ As expected, an import or export item of the
+ form <literal>C(..)</literal> denotes all of the class' methods and
+ associated types. However, when associated types are explicitly
+ listed as subitems of a class, we need some new syntax, as uppercase
+ identifiers as subitems are usually data constructors, not type
+ constructors. To clarify that we denote types here, each associated
+ type name needs to be prefixed by the keyword <literal>type</literal>.
+ So for example, when explicitly listing the components of
+ the <literal>GMapKey</literal> class, we write <literal>GMapKey(type
+ GMap, empty, lookup, insert)</literal>.
+ </para>
+ </sect4>
+ <sect4 id="data-family-impexp-examples">
+ <title>Examples</title>
+ <para>
+ Assuming our running <literal>GMapKey</literal> class example, let us
+ look at some export lists and their meaning:
+ <itemizedlist>
+ <listitem>
+ <para><literal>module GMap (GMapKey) where...</literal>: Exports
+ just the class name.</para>
+ </listitem>
+ <listitem>
+ <para><literal>module GMap (GMapKey(..)) where...</literal>:
+ Exports the class, the associated type <literal>GMap</literal>
+ and the member
+ functions <literal>empty</literal>, <literal>lookup</literal>,
+ and <literal>insert</literal>. None of the data constructors is
+ exported.</para>
+ </listitem>
+ <listitem>
+ <para><literal>module GMap (GMapKey(..), GMap(..))
+ where...</literal>: As before, but also exports all the data
+ constructors <literal>GMapInt</literal>,
+ <literal>GMapChar</literal>,
+ <literal>GMapUnit</literal>, <literal>GMapPair</literal>,
+ and <literal>GMapUnit</literal>.</para>
+ </listitem>
+ <listitem>
+ <para><literal>module GMap (GMapKey(empty, lookup, insert),
+ GMap(..)) where...</literal>: As before.</para>
+ </listitem>
+ <listitem>
+ <para><literal>module GMap (GMapKey, empty, lookup, insert, GMap(..))
+ where...</literal>: As before.</para>
+ </listitem>
+ </itemizedlist>
+ </para>
+ <para>
+ Finally, you can write <literal>GMapKey(type GMap)</literal> to denote
+ both the class <literal>GMapKey</literal> as well as its associated
+ type <literal>GMap</literal>. However, you cannot
+ write <literal>GMapKey(type GMap(..))</literal> — i.e.,
+ sub-component specifications cannot be nested. To
+ specify <literal>GMap</literal>'s data constructors, you have to list
+ it separately.
+ </para>
+ </sect4>
+
+ <sect4 id="data-family-impexp-instances">
+ <title>Instances</title>
+ <para>
+ Family instances are implicitly exported, just like class instances.
+ However, this applies only to the heads of instances, not to the data
+ constructors an instance defines.
+ </para>
+ </sect4>
-This design decision is independent of all the others, and easily
-reversed, but it makes sense to me.
+ </sect3>
-</para>
-</sect3>
+</sect2>
+<sect2 id="synonym-families">
+ <title>Synonym families</title>
-</sect2>
+ <para>
+ Type families appear in two flavours: (1) they can be defined on the
+ toplevel or (2) they can appear inside type classes (in which case they
+ are known as associated type synonyms). The former is the more general
+ variant, as it lacks the requirement for the type-indexes to coincide with
+ the class parameters. However, the latter can lead to more clearly
+ structured code and compiler warnings if some type instances were -
+ possibly accidentally - omitted. In the following, we always discuss the
+ general toplevel form first and then cover the additional constraints
+ placed on associated types.
+ </para>
-<sect2 id="overloaded-strings">
-<title>Overloaded string literals
-</title>
+ <sect3 id="type-family-declarations">
+ <title>Type family declarations</title>
-<para>
-GHC supports <emphasis>overloaded string literals</emphasis>. Normally a
-string literal has type <literal>String</literal>, but with overloaded string
-literals enabled (with <literal>-XOverloadedStrings</literal>)
- a string literal has type <literal>(IsString a) => a</literal>.
-</para>
-<para>
-This means that the usual string syntax can be used, e.g., for packed strings
-and other variations of string like types. String literals behave very much
-like integer literals, i.e., they can be used in both expressions and patterns.
-If used in a pattern the literal with be replaced by an equality test, in the same
-way as an integer literal is.
-</para>
-<para>
-The class <literal>IsString</literal> is defined as:
+ <para>
+ Indexed type families are introduced by a signature, such as
<programlisting>
-class IsString a where
- fromString :: String -> a
+type family Elem c :: *
</programlisting>
-The only predefined instance is the obvious one to make strings work as usual:
+ The special <literal>family</literal> distinguishes family from standard
+ type declarations. The result kind annotation is optional and, as
+ usual, defaults to <literal>*</literal> if omitted. An example is
<programlisting>
-instance IsString [Char] where
- fromString cs = cs
+type family Elem c
</programlisting>
-The class <literal>IsString</literal> is not in scope by default. If you want to mention
-it explicitly (for example, to give an instance declaration for it), you can import it
-from module <literal>GHC.Exts</literal>.
-</para>
-<para>
-Haskell's defaulting mechanism is extended to cover string literals, when <option>-XOverloadedStrings</option> is specified.
-Specifically:
-<itemizedlist>
-<listitem><para>
-Each type in a default declaration must be an
-instance of <literal>Num</literal> <emphasis>or</emphasis> of <literal>IsString</literal>.
-</para></listitem>
+ Parameters can also be given explicit kind signatures if needed. We
+ call the number of parameters in a type family declaration, the family's
+ arity, and all applications of a type family must be fully saturated
+ w.r.t. to that arity. This requirement is unlike ordinary type synonyms
+ and it implies that the kind of a type family is not sufficient to
+ determine a family's arity, and hence in general, also insufficient to
+ determine whether a type family application is well formed. As an
+ example, consider the following declaration:
+<programlisting>
+type family F a b :: * -> * -- F's arity is 2,
+ -- although its overall kind is * -> * -> * -> *
+</programlisting>
+ Given this declaration the following are examples of well-formed and
+ malformed types:
+<programlisting>
+F Char [Int] -- OK! Kind: * -> *
+F Char [Int] Bool -- OK! Kind: *
+F IO Bool -- WRONG: kind mismatch in the first argument
+F Bool -- WRONG: unsaturated application
+</programlisting>
+ </para>
-<listitem><para>
-The standard defaulting rule (<ulink url="http://www.haskell.org/onlinereport/decls.html#sect4.3.4">Haskell Report, Section 4.3.4</ulink>)
-is extended thus: defaulting applies when all the unresolved constraints involve standard classes
-<emphasis>or</emphasis> <literal>IsString</literal>; and at least one is a numeric class
-<emphasis>or</emphasis> <literal>IsString</literal>.
-</para></listitem>
-</itemizedlist>
-</para>
-<para>
-A small example:
+ <sect4 id="assoc-type-family-decl">
+ <title>Associated type family declarations</title>
+ <para>
+ When a type family is declared as part of a type class, we drop
+ the <literal>family</literal> special. The <literal>Elem</literal>
+ declaration takes the following form
<programlisting>
-module Main where
+class Collects ce where
+ type Elem ce :: *
+ ...
+</programlisting>
+ The argument names of the type family must be class parameters. Each
+ class parameter may only be used at most once per associated type, but
+ some may be omitted and they may be in an order other than in the
+ class head. Hence, the following contrived example is admissible:
+<programlisting>
+class C a b c where
+ type T c a :: *
+</programlisting>
+ These rules are exactly as for associated data families.
+ </para>
+ </sect4>
+ </sect3>
+
+ <sect3 id="type-instance-declarations">
+ <title>Type instance declarations</title>
+ <para>
+ Instance declarations of type families are very similar to standard type
+ synonym declarations. The only two differences are that the
+ keyword <literal>type</literal> is followed
+ by <literal>instance</literal> and that some or all of the type
+ arguments can be non-variable types, but may not contain forall types or
+ type synonym families. However, data families are generally allowed, and
+ type synonyms are allowed as long as they are fully applied and expand
+ to a type that is admissible - these are the exact same requirements as
+ for data instances. For example, the <literal>[e]</literal> instance
+ for <literal>Elem</literal> is
+<programlisting>
+type instance Elem [e] = e
+</programlisting>
+ </para>
+ <para>
+ Type family instance declarations are only legitimate when an
+ appropriate family declaration is in scope - just like class instances
+ require the class declaration to be visible. Moreover, each instance
+ declaration has to conform to the kind determined by its family
+ declaration, and the number of type parameters in an instance
+ declaration must match the number of type parameters in the family
+ declaration. Finally, the right-hand side of a type instance must be a
+ monotype (i.e., it may not include foralls) and after the expansion of
+ all saturated vanilla type synonyms, no synonyms, except family synonyms
+ may remain. Here are some examples of admissible and illegal type
+ instances:
+<programlisting>
+type family F a :: *
+type instance F [Int] = Int -- OK!
+type instance F String = Char -- OK!
+type instance F (F a) = a -- WRONG: type parameter mentions a type family
+type instance F (forall a. (a, b)) = b -- WRONG: a forall type appears in a type parameter
+type instance F Float = forall a.a -- WRONG: right-hand side may not be a forall type
+
+type family G a b :: * -> *
+type instance G Int = (,) -- WRONG: must be two type parameters
+type instance G Int Char Float = Double -- WRONG: must be two type parameters
+</programlisting>
+ </para>
-import GHC.Exts( IsString(..) )
+ <sect4 id="assoc-type-instance">
+ <title>Associated type instance declarations</title>
+ <para>
+ When an associated family instance is declared within a type class
+ instance, we drop the <literal>instance</literal> keyword in the family
+ instance. So, the <literal>[e]</literal> instance
+ for <literal>Elem</literal> becomes:
+<programlisting>
+instance (Eq (Elem [e])) => Collects ([e]) where
+ type Elem [e] = e
+ ...
+</programlisting>
+ The most important point about associated family instances is that the
+ type indexes corresponding to class parameters must be identical to the
+ type given in the instance head; here this is <literal>[e]</literal>,
+ which coincides with the only class parameter.
+ </para>
+ <para>
+ Instances for an associated family can only appear as part of instances
+ declarations of the class in which the family was declared - just as
+ with the equations of the methods of a class. Also in correspondence to
+ how methods are handled, declarations of associated types can be omitted
+ in class instances. If an associated family instance is omitted, the
+ corresponding instance type is not inhabited; i.e., only diverging
+ expressions, such as <literal>undefined</literal>, can assume the type.
+ </para>
+ </sect4>
+
+ <sect4 id="type-family-overlap">
+ <title>Overlap of type synonym instances</title>
+ <para>
+ The instance declarations of a type family used in a single program
+ may only overlap if the right-hand sides of the overlapping instances
+ coincide for the overlapping types. More formally, two instance
+ declarations overlap if there is a substitution that makes the
+ left-hand sides of the instances syntactically the same. Whenever
+ that is the case, the right-hand sides of the instances must also be
+ syntactically equal under the same substitution. This condition is
+ independent of whether the type family is associated or not, and it is
+ not only a matter of consistency, but one of type safety.
+ </para>
+ <para>
+ Here are two example to illustrate the condition under which overlap
+ is permitted.
+<programlisting>
+type instance F (a, Int) = [a]
+type instance F (Int, b) = [b] -- overlap permitted
-newtype MyString = MyString String deriving (Eq, Show)
-instance IsString MyString where
- fromString = MyString
+type instance G (a, Int) = [a]
+type instance G (Char, a) = [a] -- ILLEGAL overlap, as [Char] /= [Int]
+</programlisting>
+ </para>
+ </sect4>
+
+ <sect4 id="type-family-decidability">
+ <title>Decidability of type synonym instances</title>
+ <para>
+ In order to guarantee that type inference in the presence of type
+ families decidable, we need to place a number of additional
+ restrictions on the formation of type instance declarations (c.f.,
+ Definition 5 (Relaxed Conditions) of “<ulink
+ url="http://www.cse.unsw.edu.au/~chak/papers/SPCS08.html">Type
+ Checking with Open Type Functions</ulink>”). Instance
+ declarations have the general form
+<programlisting>
+type instance F t1 .. tn = t
+</programlisting>
+ where we require that for every type family application <literal>(G s1
+ .. sm)</literal> in <literal>t</literal>,
+ <orderedlist>
+ <listitem>
+ <para><literal>s1 .. sm</literal> do not contain any type family
+ constructors,</para>
+ </listitem>
+ <listitem>
+ <para>the total number of symbols (data type constructors and type
+ variables) in <literal>s1 .. sm</literal> is strictly smaller than
+ in <literal>t1 .. tn</literal>, and</para>
+ </listitem>
+ <listitem>
+ <para>for every type
+ variable <literal>a</literal>, <literal>a</literal> occurs
+ in <literal>s1 .. sm</literal> at most as often as in <literal>t1
+ .. tn</literal>.</para>
+ </listitem>
+ </orderedlist>
+ These restrictions are easily verified and ensure termination of type
+ inference. However, they are not sufficient to guarantee completeness
+ of type inference in the presence of, so called, ''loopy equalities'',
+ such as <literal>a ~ [F a]</literal>, where a recursive occurrence of
+ a type variable is underneath a family application and data
+ constructor application - see the above mentioned paper for details.
+ </para>
+ <para>
+ If the option <option>-XUndecidableInstances</option> is passed to the
+ compiler, the above restrictions are not enforced and it is on the
+ programmer to ensure termination of the normalisation of type families
+ during type inference.
+ </para>
+ </sect4>
+ </sect3>
+
+ <sect3 id-="equality-constraints">
+ <title>Equality constraints</title>
+ <para>
+ Type context can include equality constraints of the form <literal>t1 ~
+ t2</literal>, which denote that the types <literal>t1</literal>
+ and <literal>t2</literal> need to be the same. In the presence of type
+ families, whether two types are equal cannot generally be decided
+ locally. Hence, the contexts of function signatures may include
+ equality constraints, as in the following example:
+<programlisting>
+sumCollects :: (Collects c1, Collects c2, Elem c1 ~ Elem c2) => c1 -> c2 -> c2
+</programlisting>
+ where we require that the element type of <literal>c1</literal>
+ and <literal>c2</literal> are the same. In general, the
+ types <literal>t1</literal> and <literal>t2</literal> of an equality
+ constraint may be arbitrary monotypes; i.e., they may not contain any
+ quantifiers, independent of whether higher-rank types are otherwise
+ enabled.
+ </para>
+ <para>
+ Equality constraints can also appear in class and instance contexts.
+ The former enable a simple translation of programs using functional
+ dependencies into programs using family synonyms instead. The general
+ idea is to rewrite a class declaration of the form
+<programlisting>
+class C a b | a -> b
+</programlisting>
+ to
+<programlisting>
+class (F a ~ b) => C a b where
+ type F a
+</programlisting>
+ That is, we represent every functional dependency (FD) <literal>a1 .. an
+ -> b</literal> by an FD type family <literal>F a1 .. an</literal> and a
+ superclass context equality <literal>F a1 .. an ~ b</literal>,
+ essentially giving a name to the functional dependency. In class
+ instances, we define the type instances of FD families in accordance
+ with the class head. Method signatures are not affected by that
+ process.
+ </para>
+ <para>
+ NB: Equalities in superclass contexts are not fully implemented in
+ GHC 6.10.
+ </para>
+ </sect3>
+
+ <sect3 id-="ty-fams-in-instances">
+ <title>Type families and instance declarations</title>
+ <para>Type families require us to extend the rules for
+ the form of instance heads, which are given
+ in <xref linkend="flexible-instance-head"/>.
+ Specifically:
+<itemizedlist>
+ <listitem><para>Data type families may appear in an instance head</para></listitem>
+ <listitem><para>Type synonym families may not appear (at all) in an instance head</para></listitem>
+</itemizedlist>
+The reason for the latter restriction is that there is no way to check for. Consider
+<programlisting>
+ type family F a
+ type instance F Bool = Int
-greet :: MyString -> MyString
-greet "hello" = "world"
-greet other = other
+ class C a
-main = do
- print $ greet "hello"
- print $ greet "fool"
+ instance C Int
+ instance C (F a)
</programlisting>
+Now a constraint <literal>(C (F Bool))</literal> would match both instances.
+The situation is especially bad because the type instance for <literal>F Bool</literal>
+might be in another module, or even in a module that is not yet written.
</para>
-<para>
-Note that deriving <literal>Eq</literal> is necessary for the pattern matching
-to work since it gets translated into an equality comparison.
-</para>
+</sect3>
</sect2>
</sect1>
<sect1 id="other-type-extensions">
<title>Other type system extensions</title>
-<sect2 id="type-restrictions">
-<title>Type signatures</title>
+<sect2 id="explicit-foralls"><title>Explicit universal quantification (forall)</title>
+<para>
+Haskell type signatures are implicitly quantified. When the language option <option>-XExplicitForAll</option>
+is used, the keyword <literal>forall</literal>
+allows us to say exactly what this means. For example:
+</para>
+<para>
+<programlisting>
+ g :: b -> b
+</programlisting>
+means this:
+<programlisting>
+ g :: forall b. (b -> b)
+</programlisting>
+The two are treated identically.
+</para>
+<para>
+Of course <literal>forall</literal> becomes a keyword; you can't use <literal>forall</literal> as
+a type variable any more!
+</para>
+</sect2>
+
-<sect3 id="flexible-contexts"><title>The context of a type signature</title>
+<sect2 id="flexible-contexts"><title>The context of a type signature</title>
<para>
-Unlike Haskell 98, constraints in types do <emphasis>not</emphasis> have to be of
-the form <emphasis>(class type-variable)</emphasis> or
-<emphasis>(class (type-variable type-variable ...))</emphasis>. Thus,
+The <option>-XFlexibleContexts</option> flag lifts the Haskell 98 restriction
+that the type-class constraints in a type signature must have the
+form <emphasis>(class type-variable)</emphasis> or
+<emphasis>(class (type-variable type-variable ...))</emphasis>.
+With <option>-XFlexibleContexts</option>
these type signatures are perfectly OK
<programlisting>
g :: Eq [a] => ...
g :: Ord (T a ()) => ...
</programlisting>
+The flag <option>-XFlexibleContexts</option> also lifts the corresponding
+restriction on class declarations (<xref linkend="superclass-rules"/>) and instance declarations
+(<xref linkend="instance-rules"/>).
</para>
+
<para>
GHC imposes the following restrictions on the constraints in a type signature.
Consider the type:
language omits them; in Haskell 98, 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"/>).
+in GHC, you can give the foralls if you want. See <xref linkend="explicit-foralls"/>).
</para>
<para>
A type variable <literal>a</literal> is "reachable" if it appears
in the same constraint as either a type variable free in
-<literal>type</literal>, or another reachable type variable.
-A value with a type that does not obey
+<literal>type</literal>, or another reachable type variable.
+A value with a type that does not obey
this reachability restriction cannot be used without introducing
ambiguity; that is why the type is rejected.
Here, for example, is an illegal type:
</orderedlist>
</para>
-</sect3>
-
-
</sect2>
<sect2 id="implicit-parameters">
<title>Implicit parameters</title>
-<para> Implicit parameters are implemented as described in
-"Implicit parameters: dynamic scoping with static types",
+<para> Implicit parameters are implemented as described in
+"Implicit parameters: dynamic scoping with static types",
J Lewis, MB Shields, E Meijer, J Launchbury,
27th ACM Symposium on Principles of Programming Languages (POPL'00),
Boston, Jan 2000.
can support dynamic binding. Basically, we express the use of a
dynamically bound variable as a constraint on the type. These
constraints lead to types of the form <literal>(?x::t') => t</literal>, which says "this
-function uses a dynamically-bound variable <literal>?x</literal>
+function uses a dynamically-bound variable <literal>?x</literal>
of type <literal>t'</literal>". For
example, the following expresses the type of a sort function,
implicitly parameterized by a comparison function named <literal>cmp</literal>.
The dynamic binding constraints are just a new form of predicate in the type class system.
</para>
<para>
-An implicit parameter occurs in an expression using the special form <literal>?x</literal>,
+An implicit parameter occurs in an expression using the special form <literal>?x</literal>,
where <literal>x</literal> is
-any valid identifier (e.g. <literal>ord ?x</literal> is a valid expression).
+any valid identifier (e.g. <literal>ord ?x</literal> is a valid expression).
Use of this construct also introduces a new
-dynamic-binding constraint in the type of the expression.
+dynamic-binding constraint in the type of the expression.
For example, the following definition
shows how we can define an implicitly parameterized sort function in
terms of an explicitly parameterized <literal>sortBy</literal> function:
<para>
An implicit-parameter type constraint differs from other type class constraints in the
following way: All uses of a particular implicit parameter must have
-the same type. This means that the type of <literal>(?x, ?x)</literal>
-is <literal>(?x::a) => (a,a)</literal>, and not
+the same type. This means that the type of <literal>(?x, ?x)</literal>
+is <literal>(?x::a) => (a,a)</literal>, and not
<literal>(?x::a, ?x::b) => (a, b)</literal>, as would be the case for type
class constraints.
</para>
g s = show (read s)
</programlisting>
Here, <literal>g</literal> has an ambiguous type, and is rejected, but <literal>f</literal>
-is fine. The binding for <literal>?x</literal> at <literal>f</literal>'s call site is
+is fine. The binding for <literal>?x</literal> at <literal>f</literal>'s call site is
quite unambiguous, and fixes the type <literal>a</literal>.
</para>
</sect3>
</para>
<para>
A group of implicit-parameter bindings may occur anywhere a normal group of Haskell
-bindings can occur, except at top level. That is, they can occur in a <literal>let</literal>
-(including in a list comprehension, or do-notation, or pattern guards),
+bindings can occur, except at top level. That is, they can occur in a <literal>let</literal>
+(including in a list comprehension, or do-notation, or pattern guards),
or a <literal>where</literal> clause.
Note the following points:
<itemizedlist>
An implicit-parameter binding group must be a
collection of simple bindings to implicit-style variables (no
function-style bindings, and no type signatures); these bindings are
-neither polymorphic or recursive.
+neither polymorphic or recursive.
</para></listitem>
<listitem><para>
-You may not mix implicit-parameter bindings with ordinary bindings in a
+You may not mix implicit-parameter bindings with ordinary bindings in a
single <literal>let</literal>
expression; use two nested <literal>let</literal>s instead.
(In the case of <literal>where</literal> you are stuck, since you can't nest <literal>where</literal> clauses.)
Linear implicit parameters are just like ordinary implicit parameters,
except that they are "linear"; that is, they cannot be copied, and
must be explicitly "split" instead. Linear implicit parameters are
-written '<literal>%x</literal>' instead of '<literal>?x</literal>'.
+written '<literal>%x</literal>' instead of '<literal>?x</literal>'.
(The '/' in the '%' suggests the split!)
</para>
<para>
import GHC.Exts( Splittable )
data NameSupply = ...
-
+
splitNS :: NameSupply -> (NameSupply, NameSupply)
newName :: NameSupply -> Name
env' = extend env x x'
...more equations for f...
</programlisting>
-Notice that the implicit parameter %ns is consumed
+Notice that the implicit parameter %ns is consumed
<itemizedlist>
<listitem> <para> once by the call to <literal>newName</literal> </para> </listitem>
<listitem> <para> once by the recursive call to <literal>f</literal> </para></listitem>
<programlisting>
g :: (Splittable a, %ns :: a) => b -> (b,a,a)
</programlisting>
-The <literal>Splittable</literal> class is built into GHC. It's exported by module
+The <literal>Splittable</literal> class is built into GHC. It's exported by module
<literal>GHC.Exts</literal>.
</para>
<para>
Other points:
<itemizedlist>
-<listitem> <para> '<literal>?x</literal>' and '<literal>%x</literal>'
-are entirely distinct implicit parameters: you
+<listitem> <para> '<literal>?x</literal>' and '<literal>%x</literal>'
+are entirely distinct implicit parameters: you
can use them together and they won't interfere with each other. </para>
</listitem>
</programlisting>
But now the name supply is consumed in <emphasis>three</emphasis> places
(the two calls to newName,and the recursive call to f), so
-the result is utterly different. Urk! We don't even have
+the result is utterly different. Urk! We don't even have
the beta rule.
</para>
<para>
Yikes!
</para><para>
You may say that this is a good reason to dislike linear implicit parameters
-and you'd be right. That is why they are an experimental feature.
+and you'd be right. That is why they are an experimental feature.
</para>
</sect3>
<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,
+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:
</title>
<para>
-Haskell type signatures are implicitly quantified. The new keyword <literal>forall</literal>
-allows us to say exactly what this means. For example:
-</para>
-<para>
-<programlisting>
- g :: b -> b
-</programlisting>
-means this:
-<programlisting>
- g :: forall b. (b -> b)
-</programlisting>
-The two are treated identically.
-</para>
-
-<para>
-However, GHC's type system supports <emphasis>arbitrary-rank</emphasis>
+GHC's type system supports <emphasis>arbitrary-rank</emphasis>
explicit universal quantification in
-types.
+types.
For example, all the following types are legal:
<programlisting>
f1 :: forall a b. a -> b -> a
</itemizedlist>
</para></listitem>
</itemizedlist>
-Of course <literal>forall</literal> becomes a keyword; you can't use <literal>forall</literal> as
-a type variable any more!
</para>
<programlisting>
a1 :: T Int
a1 = T1 (\xy->x) 3
-
+
a2, a3 :: Swizzle
a2 = MkSwizzle sort
a3 = MkSwizzle reverse
-
+
a4 :: MonadT Maybe
a4 = let r x = Just x
b m k = case m of
that x's type has no foralls in it</emphasis>.
</para>
<para>
-What does it mean to "provide" an explicit type for x? You can do that by
+What does it mean to "provide" an explicit type for x? You can do that by
giving a type signature for x directly, using a pattern type signature
(<xref linkend="scoped-type-variables"/>), thus:
<programlisting>
<title>Implicit quantification</title>
<para>
-GHC performs implicit quantification as follows. <emphasis>At the top level (only) of
+GHC performs implicit quantification as follows. <emphasis>At the top level (only) of
user-written types, if and only if there is no explicit <literal>forall</literal>,
GHC finds all the type variables mentioned in the type that are not already
-in scope, and universally quantifies them.</emphasis> For example, the following pairs are
+in scope, and universally quantifies them.</emphasis> For example, the following pairs are
equivalent:
<programlisting>
f :: a -> a
<sect2 id="impredicative-polymorphism">
<title>Impredicative polymorphism
</title>
-<para>GHC supports <emphasis>impredicative polymorphism</emphasis>,
-enabled with <option>-XImpredicativeTypes</option>.
+<para>GHC supports <emphasis>impredicative polymorphism</emphasis>,
+enabled with <option>-XImpredicativeTypes</option>.
This means
that you can call a polymorphic function at a polymorphic type, and
parameterise data structures over polymorphic types. For example:
<para>The technical details of this extension are described in the paper
<ulink url="http://research.microsoft.com/%7Esimonpj/papers/boxy/">Boxy types:
type inference for higher-rank types and impredicativity</ulink>,
-which appeared at ICFP 2006.
+which appeared at ICFP 2006.
</para>
</sect2>
ys :: [a]
ys = reverse xs
</programlisting>
-The type signature for <literal>f</literal> brings the type variable <literal>a</literal> into scope; it scopes over
-the entire definition of <literal>f</literal>.
-In particular, it is in scope at the type signature for <varname>ys</varname>.
+The type signature for <literal>f</literal> brings the type variable <literal>a</literal> into scope,
+because of the explicit <literal>forall</literal> (<xref linkend="decl-type-sigs"/>).
+The type variables bound by a <literal>forall</literal> scope over
+the entire definition of the accompanying value declaration.
+In this example, the type variable <literal>a</literal> scopes over the whole
+definition of <literal>f</literal>, including over
+the type signature for <varname>ys</varname>.
In Haskell 98 it is not possible to declare
a type for <varname>ys</varname>; a major benefit of scoped type variables is that
it becomes possible to do so.
In Haskell, a programmer-written type signature is implicitly quantified over
its free type variables (<ulink
url="http://www.haskell.org/onlinereport/decls.html#sect4.1.2">Section
-4.1.2</ulink>
+4.1.2</ulink>
of the Haskell Report).
Lexically scoped type variables affect this implicit quantification rules
as follows: any type variable that is in scope is <emphasis>not</emphasis> universally
g (x:xs) = xs ++ [ x :: a ]
</programlisting>
This program will be rejected, because "<literal>a</literal>" does not scope
-over the definition of "<literal>f</literal>", so "<literal>x::a</literal>"
+over the definition of "<literal>g</literal>", so "<literal>x::a</literal>"
means "<literal>x::forall a. a</literal>" by Haskell's usual implicit
quantification rules.
</para></listitem>
-<listitem><para> The signature gives a type for a function binding or a bare variable binding,
+<listitem><para> The signature gives a type for a function binding or a bare variable binding,
not a pattern binding.
For example:
<programlisting>
f2 :: forall a. [a] -> [a]
f2 = \(x:xs) -> xs ++ [ x :: a ] -- OK
- f3 :: forall a. [a] -> [a]
+ f3 :: forall a. [a] -> [a]
Just f3 = Just (\(x:xs) -> xs ++ [ x :: a ]) -- Not OK!
</programlisting>
The binding for <literal>f3</literal> is a pattern binding, and so its type signature
<programlisting>
f = runST ( (op >>= \(x :: STRef s Int) -> g x) :: forall s. ST s Bool )
</programlisting>
-Here, the type signature <literal>forall a. ST s Bool</literal> brings the
-type variable <literal>s</literal> into scope, in the annotated expression
+Here, the type signature <literal>forall s. ST s Bool</literal> brings the
+type variable <literal>s</literal> into scope, in the annotated expression
<literal>(op >>= \(x :: STRef s Int) -> g x)</literal>.
</para>
<title>Pattern type signatures</title>
<para>
A type signature may occur in any pattern; this is a <emphasis>pattern type
-signature</emphasis>.
+signature</emphasis>.
For example:
<programlisting>
-- f and g assume that 'a' is already in scope
</programlisting>
Here, the pattern signatures for <literal>ys</literal> and <literal>zs</literal>
are fine, but the one for <literal>v</literal> is not because <literal>b</literal> is
-not in scope.
+not in scope.
</para>
<para>
However, in all patterns <emphasis>other</emphasis> than pattern bindings, a pattern
existentially-bound type variable.
</para>
<para>
-When a pattern type signature binds a type variable in this way, GHC insists that the
+When a pattern type signature binds a type variable in this way, GHC insists that the
type variable is bound to a <emphasis>rigid</emphasis>, or fully-known, type variable.
This means that any user-written type signature always stands for a completely known type.
</para>
could not name existentially-bound type variables in subsequent type signatures.
</para>
<para>
-This is (now) the <emphasis>only</emphasis> situation in which a pattern type
+This is (now) the <emphasis>only</emphasis> situation in which a pattern type
signature is allowed to mention a lexical variable that is not already in
scope.
For example, both <literal>f</literal> and <literal>g</literal> would be
</sect3>
-<!-- ==================== Commented out part about result type signatures
+<!-- ==================== Commented out part about result type signatures
<sect3 id="result-type-sigs">
<title>Result type signatures</title>
h xs = case xs of
(y:ys) :: a -> y
</programlisting>
-The final <literal>:: [a]</literal> after the patterns of <literal>f</literal> gives the type of
+The final <literal>:: [a]</literal> after the patterns of <literal>f</literal> gives the type of
the result of the function. Similarly, the body of the lambda in the RHS of
<literal>g</literal> is <literal>[Int]</literal>, and the RHS of the case
alternative in <literal>h</literal> is <literal>a</literal>.
<literal>let</literal> or <literal>where</literal>) should be sorted into
strongly-connected components, and then type-checked in dependency order
(<ulink url="http://www.haskell.org/onlinereport/decls.html#sect4.5.1">Haskell
-Report, Section 4.5.1</ulink>).
+Report, Section 4.5.1</ulink>).
As each group is type-checked, any binders of the group that
have
an explicit type signature are put in the type environment with the specified
polymorphic type,
-and all others are monomorphic until the group is generalised
+and all others are monomorphic until the group is generalised
(<ulink url="http://www.haskell.org/onlinereport/decls.html#sect4.5.2">Haskell Report, Section 4.5.2</ulink>).
</para>
<programlisting>
f :: Eq a => a -> Bool
f x = (x == x) || g True || g "Yes"
-
+
g y = (y <= y) || f True
</programlisting>
This is rejected by Haskell 98, but under Jones's scheme the definition for
</para>
<para>
-The same refined dependency analysis also allows the type signatures of
+The same refined dependency analysis also allows the type signatures of
mutually-recursive functions to have different contexts, something that is illegal in
Haskell 98 (Section 4.5.2, last sentence). With
<option>-XRelaxedPolyRec</option>
<programlisting>
f :: Eq a => a -> Bool
f x = (x == x) || g True
-
+
g :: Ord a => a -> Bool
g y = (y <= y) || f True
</programlisting>
</para>
</sect2>
-<sect2 id="type-families">
-<title>Type families
-</title>
-
+<sect2 id="mono-local-binds">
+<title>Monomorphic local bindings</title>
<para>
-GHC supports the definition of type families indexed by types. They may be
-seen as an extension of Haskell 98's class-based overloading of values to
-types. When type families are declared in classes, they are also known as
-associated types.
+We are actively thinking of simplifying GHC's type system, by <emphasis>not generalising local bindings</emphasis>.
+The rationale is described in the paper
+<ulink url="http://research.microsoft.com/~simonpj/papers/constraints/index.htm">Let should not be generalised</ulink>.
</para>
<para>
-There are two forms of type families: data families and type synonym families.
-Currently, only the former are fully implemented, while we are still working
-on the latter. As a result, the specification of the language extension is
-also still to some degree in flux. Hence, a more detailed description of
-the language extension and its use is currently available
-from <ulink url="http://www.haskell.org/haskellwiki/GHC/Indexed_types">the Haskell
-wiki page on type families</ulink>. The material will be moved to this user's
-guide when it has stabilised.
+The experimental new behaviour is enabled by the flag <option>-XMonoLocalBinds</option>. The effect is
+that local (that is, non-top-level) bindings without a type signature are not generalised at all. You can
+think of it as an extreme (but much more predictable) version of the Monomorphism Restriction.
+If you supply a type signature, then the flag has no effect.
</para>
-<para>
-Type families are enabled by the flag <option>-XTypeFamilies</option>.
-</para>
-
-
</sect2>
</sect1>
<!-- ==================== End of type system extensions ================= -->
-
+
<!-- ====================== TEMPLATE HASKELL ======================= -->
<sect1 id="template-haskell">
<title>Template Haskell</title>
<para>Template Haskell allows you to do compile-time meta-programming in
-Haskell.
+Haskell.
The background to
the main technical innovations is discussed in "<ulink
url="http://research.microsoft.com/~simonpj/papers/meta-haskell/">
Template Haskell at <ulink url="http://www.haskell.org/haskellwiki/Template_Haskell">
http://www.haskell.org/haskellwiki/Template_Haskell</ulink>, and that is the best place to look for
further details.
-You may also
+You may also
consult the <ulink
url="http://www.haskell.org/ghc/docs/latest/html/libraries/index.html">online
-Haskell library reference material</ulink>
+Haskell library reference material</ulink>
(look for module <literal>Language.Haskell.TH</literal>).
-Many changes to the original design are described in
+Many changes to the original design are described in
<ulink url="http://research.microsoft.com/~simonpj/papers/meta-haskell/notes2.ps">
Notes on Template Haskell version 2</ulink>.
Not all of these changes are in GHC, however.
</para>
-<para> The first example from that paper is set out below (<xref linkend="th-example"/>)
-as a worked example to help get you started.
+<para> The first example from that paper is set out below (<xref linkend="th-example"/>)
+as a worked example to help get you started.
</para>
<para>
-The documentation here describes the realisation of Template Haskell in GHC. It is not detailed enough to
+The documentation here describes the realisation of Template Haskell in GHC. It is not detailed enough to
understand Template Haskell; see the <ulink url="http://haskell.org/haskellwiki/Template_Haskell">
Wiki page</ulink>.
</para>
of "$" overrides its meaning as an infix operator, just as "M.x" overrides the meaning
of "." as an infix operator. If you want the infix operator, put spaces around it.
</para>
- <para> A splice can occur in place of
+ <para> A splice can occur in place of
<itemizedlist>
<listitem><para> an expression; the spliced expression must
have type <literal>Q Exp</literal></para></listitem>
- <listitem><para> a list of top-level declarations; the spliced expression must have type <literal>Q [Dec]</literal></para></listitem>
+ <listitem><para> an type; the spliced expression must
+ have type <literal>Q Typ</literal></para></listitem>
+ <listitem><para> a list of top-level declarations; the spliced expression
+ must have type <literal>Q [Dec]</literal></para></listitem>
</itemizedlist>
- </para>
- Inside a splice you can can only call functions defined in imported modules,
- not functions defined elsewhere in the same module.</listitem>
-
+ Note that pattern splices are not supported.
+ Inside a splice you can only call functions defined in imported modules,
+ not functions defined elsewhere in the same module.</para></listitem>
<listitem><para>
A expression quotation is written in Oxford brackets, thus:
<itemizedlist>
- <listitem><para> <literal>[| ... |]</literal>, where the "..." is an expression;
+ <listitem><para> <literal>[| ... |]</literal>, or <literal>[e| ... |]</literal>,
+ where the "..." is an expression;
the quotation has type <literal>Q Exp</literal>.</para></listitem>
<listitem><para> <literal>[d| ... |]</literal>, where the "..." is a list of top-level declarations;
the quotation has type <literal>Q [Dec]</literal>.</para></listitem>
<listitem><para> <literal>[t| ... |]</literal>, where the "..." is a type;
- the quotation has type <literal>Q Typ</literal>.</para></listitem>
+ the quotation has type <literal>Q Type</literal>.</para></listitem>
+ <listitem><para> <literal>[p| ... |]</literal>, where the "..." is a pattern;
+ the quotation has type <literal>Q Pat</literal>.</para></listitem>
</itemizedlist></para></listitem>
<listitem><para>
A quasi-quotation can appear in either a pattern context or an
expression context and is also written in Oxford brackets:
<itemizedlist>
- <listitem><para> <literal>[:<replaceable>varid</replaceable>| ... |]</literal>,
+ <listitem><para> <literal>[<replaceable>varid</replaceable>| ... |]</literal>,
where the "..." is an arbitrary string; a full description of the
quasi-quotation facility is given in <xref linkend="th-quasiquotation"/>.</para></listitem>
</itemizedlist></para></listitem>
<listitem><para> <literal>'f</literal> has type <literal>Name</literal>, and names the function <literal>f</literal>.
Similarly <literal>'C</literal> has type <literal>Name</literal> and names the data constructor <literal>C</literal>.
In general <literal>'</literal><replaceable>thing</replaceable> interprets <replaceable>thing</replaceable> in an expression context.
- </para></listitem>
+ </para></listitem>
<listitem><para> <literal>''T</literal> has type <literal>Name</literal>, and names the type constructor <literal>T</literal>.
That is, <literal>''</literal><replaceable>thing</replaceable> interprets <replaceable>thing</replaceable> in a type context.
- </para></listitem>
+ </para></listitem>
</itemizedlist>
These <literal>Names</literal> can be used to construct Template Haskell expressions, patterns, declarations etc. They
may also be given as an argument to the <literal>reify</literal> function.
</para>
</listitem>
-
+ <listitem><para> You may omit the <literal>$(...)</literal> in a top-level declaration splice.
+ Simply writing an expression (rather than a declaration) implies a splice. For example, you can write
+<programlisting>
+module Foo where
+import Bar
+
+f x = x
+
+$(deriveStuff 'f) -- Uses the $(...) notation
+
+g y = y+1
+
+deriveStuff 'g -- Omits the $(...)
+
+h z = z-1
+</programlisting>
+ This abbreviation makes top-level declaration slices quieter and less intimidating.
+ </para></listitem>
+
+
</itemizedlist>
(Compared to the original paper, there are many differences of detail.
The syntax for a declaration splice uses "<literal>$</literal>" not "<literal>splice</literal>".
The type of the enclosed expression must be <literal>Q [Dec]</literal>, not <literal>[Q Dec]</literal>.
-Type splices are not implemented, and neither are pattern splices or quotations.
+Pattern splices and quotations are not implemented.)
</sect2>
<listitem><para>
You can only run a function at compile time if it is imported
from another module <emphasis>that is not part of a mutually-recursive group of modules
- that includes the module currently being compiled</emphasis>. Furthermore, all of the modules of
+ that includes the module currently being compiled</emphasis>. Furthermore, all of the modules of
the mutually-recursive group must be reachable by non-SOURCE imports from the module where the
splice is to be run.</para>
<para>
</itemizedlist>
</para>
<para> Template Haskell works in any mode (<literal>--make</literal>, <literal>--interactive</literal>,
- or file-at-a-time). There used to be a restriction to the former two, but that restriction
+ or file-at-a-time). There used to be a restriction to the former two, but that restriction
has been lifted.
</para>
</sect2>
-
+
<sect2 id="th-example"> <title> A Template Haskell Worked Example </title>
<para>To help you get over the confidence barrier, try out this skeletal worked example.
First cut and paste the two modules below into "Main.hs" and "Printf.hs":</para>
<sect2>
<title>Using Template Haskell with Profiling</title>
<indexterm><primary>profiling</primary><secondary>with Template Haskell</secondary></indexterm>
-
+
<para>Template Haskell relies on GHC's built-in bytecode compiler and
interpreter to run the splice expressions. The bytecode interpreter
runs the compiled expression on top of the same runtime on which GHC
Nice to be Quoted: Quasiquoting for Haskell</ulink>" (Proc Haskell Workshop
2007). The example below shows how to write a quasiquoter for a simple
expression language.</para>
-
<para>
-In the example, the quasiquoter <literal>expr</literal> is bound to a value of
-type <literal>Language.Haskell.TH.Quote.QuasiQuoter</literal> which contains two
-functions for quoting expressions and patterns, respectively. The first argument
-to each quoter is the (arbitrary) string enclosed in the Oxford brackets. The
-context of the quasi-quotation statement determines which of the two parsers is
-called: if the quasi-quotation occurs in an expression context, the expression
-parser is called, and if it occurs in a pattern context, the pattern parser is
-called.</para>
+Here are the salient features
+<itemizedlist>
+<listitem><para>
+A quasi-quote has the form
+<literal>[<replaceable>quoter</replaceable>| <replaceable>string</replaceable> |]</literal>.
+<itemizedlist>
+<listitem><para>
+The <replaceable>quoter</replaceable> must be the (unqualified) name of an imported
+quoter; it cannot be an arbitrary expression.
+</para></listitem>
+<listitem><para>
+The <replaceable>quoter</replaceable> cannot be "<literal>e</literal>",
+"<literal>t</literal>", "<literal>d</literal>", or "<literal>p</literal>", since
+those overlap with Template Haskell quotations.
+</para></listitem>
+<listitem><para>
+There must be no spaces in the token
+<literal>[<replaceable>quoter</replaceable>|</literal>.
+</para></listitem>
+<listitem><para>
+The quoted <replaceable>string</replaceable>
+can be arbitrary, and may contain newlines.
+</para></listitem>
+</itemizedlist>
+</para></listitem>
+
+<listitem><para>
+A quasiquote may appear in place of
+<itemizedlist>
+<listitem><para>An expression</para></listitem>
+<listitem><para>A pattern</para></listitem>
+<listitem><para>A type</para></listitem>
+<listitem><para>A top-level declaration</para></listitem>
+</itemizedlist>
+(Only the first two are described in the paper.)
+</para></listitem>
+<listitem><para>
+A quoter is a value of type <literal>Language.Haskell.TH.Quote.QuasiQuoter</literal>,
+which is defined thus:
+<programlisting>
+data QuasiQuoter = QuasiQuoter { quoteExp :: String -> Q Exp,
+ quotePat :: String -> Q Pat,
+ quoteType :: String -> Q Type,
+ quoteDec :: String -> Q [Dec] }
+</programlisting>
+That is, a quoter is a tuple of four parsers, one for each of the contexts
+in which a quasi-quote can occur.
+</para></listitem>
+<listitem><para>
+A quasi-quote is expanded by applying the appropriate parser to the string
+enclosed by the Oxford brackets. The context of the quasi-quote (expression, pattern,
+type, declaration) determines which of the parsers is called.
+</para></listitem>
+</itemizedlist>
+</para>
<para>
-Note that in the example we make use of an antiquoted
+The example below shows quasi-quotation in action. The quoter <literal>expr</literal>
+is bound to a value of type <literal>QuasiQuoter</literal> defined in module <literal>Expr</literal>.
+The example makes use of an antiquoted
variable <literal>n</literal>, indicated by the syntax <literal>'int:n</literal>
(this syntax for anti-quotation was defined by the parser's
author, <emphasis>not</emphasis> by GHC). This binds <literal>n</literal> to the
pattern parser that returns a value of type <literal>Q Pat</literal>.
</para>
-<para>In general, a quasi-quote has the form
-<literal>[$<replaceable>quoter</replaceable>| <replaceable>string</replaceable> |]</literal>.
-The <replaceable>quoter</replaceable> must be the name of an imported quoter; it
-cannot be an arbitrary expression. The quoted <replaceable>string</replaceable>
-can be arbitrary, and may contain newlines.
-</para>
<para>
Quasiquoters must obey the same stage restrictions as Template Haskell, e.g., in
the example, <literal>expr</literal> cannot be defined
</para>
<programlisting>
-
-{- Main.hs -}
+{- ------------- file Main.hs --------------- -}
module Main where
import Expr
main :: IO ()
-main = do { print $ eval [$expr|1 + 2|]
+main = do { print $ eval [expr|1 + 2|]
; case IntExpr 1 of
- { [$expr|'int:n|] -> print n
+ { [expr|'int:n|] -> print n
; _ -> return ()
}
}
-{- Expr.hs -}
+{- ------------- file Expr.hs --------------- -}
module Expr where
import qualified Language.Haskell.TH as TH
-import Language.Haskell.TH.Quasi
+import Language.Haskell.TH.Quote
data Expr = IntExpr Integer
| AntiIntExpr String
opToFun MulOp = (*)
opToFun DivOp = div
-expr = QuasiQuoter parseExprExp parseExprPat
+expr = QuasiQuoter { quoteExp = parseExprExp, quotePat = parseExprPat }
-- Parse an Expr, returning its representation as
-- either a Q Exp or a Q Pat. See the referenced paper
</programlisting>
<para>Now run the compiler:
-</para>
<programlisting>
$ ghc --make -XQuasiQuotes Main.hs -o main
</programlisting>
+</para>
-<para>Run "main" and here is your output:</para>
-
+<para>Run "main" and here is your output:
<programlisting>
$ ./main
3
1
</programlisting>
-
+</para>
</sect2>
</sect1>
“Generalising Monads to Arrows”,
John Hughes, in <citetitle>Science of Computer Programming</citetitle> 37,
pp67–111, May 2000.
+The paper that introduced arrows: a friendly introduction, motivated with
+programming examples.
</para>
</listitem>
<para>
“<ulink url="http://www.soi.city.ac.uk/~ross/papers/notation.html">A New Notation for Arrows</ulink>”,
Ross Paterson, in <citetitle>ICFP</citetitle>, Sep 2001.
+Introduced the notation described here.
</para>
</listitem>
</para>
</listitem>
-</itemizedlist>
-and the arrows web page at
+<listitem>
+<para>
+“<ulink url="http://www.cs.chalmers.se/~rjmh/afp-arrows.pdf">Programming with Arrows</ulink>”,
+John Hughes, in <citetitle>5th International Summer School on
+Advanced Functional Programming</citetitle>,
+<citetitle>Lecture Notes in Computer Science</citetitle> vol. 3622,
+Springer, 2004.
+This paper includes another introduction to the notation,
+with practical examples.
+</para>
+</listitem>
+
+<listitem>
+<para>
+“<ulink url="http://www.haskell.org/ghc/docs/papers/arrow-rules.pdf">Type and Translation Rules for Arrow Notation in GHC</ulink>”,
+Ross Paterson and Simon Peyton Jones, September 16, 2004.
+A terse enumeration of the formal rules used
+(extracted from comments in the source code).
+</para>
+</listitem>
+
+<listitem>
+<para>
+The arrows web page at
<ulink url="http://www.haskell.org/arrows/"><literal>http://www.haskell.org/arrows/</literal></ulink>.
+</para>
+</listitem>
+
+</itemizedlist>
With the <option>-XArrows</option> flag, GHC supports the arrow
-notation described in the second of these papers.
+notation described in the second of these papers,
+translating it using combinators from the
+<ulink url="&libraryBaseLocation;/Control-Arrow.html"><literal>Control.Arrow</literal></ulink>
+module.
What follows is a brief introduction to the notation;
it won't make much sense unless you've read Hughes's paper.
-This notation is translated to ordinary Haskell,
-using combinators from the
-<ulink url="../libraries/base/Control-Arrow.html"><literal>Control.Arrow</literal></ulink>
-module.
</para>
<para>The extension adds a new kind of expression for defining arrows:
| proc <replaceable>apat</replaceable> -> <replaceable>cmd</replaceable>
</screen>
where <literal>proc</literal> is a new keyword.
-The variables of the pattern are bound in the body of the
+The variables of the pattern are bound in the body of the
<literal>proc</literal>-expression,
which is a new sort of thing called a <firstterm>command</firstterm>.
The syntax of commands is as follows:
<literal>y</literal>.
In the next line, the output is discarded.
The arrow <function>returnA</function> is defined in the
-<ulink url="../libraries/base/Control-Arrow.html"><literal>Control.Arrow</literal></ulink>
+<ulink url="&libraryBaseLocation;/Control-Arrow.html"><literal>Control.Arrow</literal></ulink>
module as <literal>arr id</literal>.
The above example is treated as an abbreviation for
<screen>
Note that variables not used later in the composition are projected out.
After simplification using rewrite rules (see <xref linkend="rewrite-rules"/>)
defined in the
-<ulink url="../libraries/base/Control-Arrow.html"><literal>Control.Arrow</literal></ulink>
+<ulink url="&libraryBaseLocation;/Control-Arrow.html"><literal>Control.Arrow</literal></ulink>
module, this reduces to
<screen>
arr (\ x -> (x+1, x)) >>>
<programlisting>
untilA :: ArrowChoice a => a e () -> a e Bool -> a e ()
untilA body cond = proc x ->
- if cond x then returnA -< ()
+ b <- cond -< x
+ if b then returnA -< ()
else do
body -< x
untilA body cond -< x
<para>
Although only GHC implements arrow notation directly,
there is also a preprocessor
-(available from the
+(available from the
<ulink url="http://www.haskell.org/arrows/">arrows web page</ulink>)
that translates arrow notation into Haskell 98
for use with other Haskell systems.
<listitem>
<para>
The module must import
-<ulink url="../libraries/base/Control-Arrow.html"><literal>Control.Arrow</literal></ulink>.
+<ulink url="&libraryBaseLocation;/Control-Arrow.html"><literal>Control.Arrow</literal></ulink>.
</para>
</listitem>
<indexterm><primary>Bang patterns</primary></indexterm>
</title>
<para>GHC supports an extension of pattern matching called <emphasis>bang
-patterns</emphasis>. Bang patterns are under consideration for Haskell Prime.
+patterns</emphasis>, written <literal>!<replaceable>pat</replaceable></literal>.
+Bang patterns are under consideration for Haskell Prime.
The <ulink
url="http://hackage.haskell.org/trac/haskell-prime/wiki/BangPatterns">Haskell
prime feature description</ulink> contains more discussion and examples
than the material below.
</para>
<para>
+The key change is the addition of a new rule to the
+<ulink url="http://haskell.org/onlinereport/exps.html#sect3.17.2">semantics of pattern matching in the Haskell 98 report</ulink>.
+Add new bullet 10, saying: Matching the pattern <literal>!</literal><replaceable>pat</replaceable>
+against a value <replaceable>v</replaceable> behaves as follows:
+<itemizedlist>
+<listitem><para>if <replaceable>v</replaceable> is bottom, the match diverges</para></listitem>
+<listitem><para>otherwise, <replaceable>pat</replaceable> is matched against <replaceable>v</replaceable> </para></listitem>
+</itemizedlist>
+</para>
+<para>
Bang patterns are enabled by the flag <option>-XBangPatterns</option>.
</para>
f2 (!x, y) = [x,y]
</programlisting>
Here, <literal>f2</literal> is strict in <literal>x</literal> but not in
-<literal>y</literal>.
+<literal>y</literal>.
A bang only really has an effect if it precedes a variable or wild-card pattern:
<programlisting>
f3 !(x,y) = [x,y]
f4 (x,y) = [x,y]
</programlisting>
-Here, <literal>f3</literal> and <literal>f4</literal> are identical; putting a bang before a pattern that
+Here, <literal>f3</literal> and <literal>f4</literal> are identical;
+putting a bang before a pattern that
forces evaluation anyway does nothing.
-</para><para>
+</para>
+<para>
+There is one (apparent) exception to this general rule that a bang only
+makes a difference when it precedes a variable or wild-card: a bang at the
+top level of a <literal>let</literal> or <literal>where</literal>
+binding makes the binding strict, regardless of the pattern.
+(We say "apparent" exception because the Right Way to think of it is that the bang
+at the top of a binding is not part of the <emphasis>pattern</emphasis>; rather it
+is part of the syntax of the <emphasis>binding</emphasis>,
+creating a "bang-pattern binding".)
+For example:
+<programlisting>
+let ![x,y] = e in b
+</programlisting>
+is a bang-pattern binding. Operationally, it behaves just like a case expression:
+<programlisting>
+case e of [x,y] -> b
+</programlisting>
+Like a case expression, a bang-pattern binding must be non-recursive, and
+is monomorphic.
+
+However, <emphasis>nested</emphasis> bangs in a pattern binding behave uniformly with all other forms of
+pattern matching. For example
+<programlisting>
+let (!x,[y]) = e in b
+</programlisting>
+is equivalent to this:
+<programlisting>
+let { t = case e of (x,[y]) -> x `seq` (x,y)
+ x = fst t
+ y = snd t }
+in b
+</programlisting>
+The binding is lazy, but when either <literal>x</literal> or <literal>y</literal> is
+evaluated by <literal>b</literal> the entire pattern is matched, including forcing the
+evaluation of <literal>x</literal>.
+</para>
+<para>
Bang patterns work in <literal>case</literal> expressions too, of course:
<programlisting>
g5 x = let y = f x in body
g6 x = case f x of { y -> body }
g7 x = case f x of { !y -> body }
</programlisting>
-The functions <literal>g5</literal> and <literal>g6</literal> mean exactly the same thing.
+The functions <literal>g5</literal> and <literal>g6</literal> mean exactly the same thing.
But <literal>g7</literal> evaluates <literal>(f x)</literal>, binds <literal>y</literal> to the
result, and then evaluates <literal>body</literal>.
-</para><para>
-Bang patterns work in <literal>let</literal> and <literal>where</literal>
-definitions too. For example:
-<programlisting>
-let ![x,y] = e in b
-</programlisting>
-is a strict pattern: operationally, it evaluates <literal>e</literal>, matches
-it against the pattern <literal>[x,y]</literal>, and then evaluates <literal>b</literal>
-The "<literal>!</literal>" should not be regarded as part of the pattern; after all,
-in a function argument <literal>![x,y]</literal> means the
-same as <literal>[x,y]</literal>. Rather, the "<literal>!</literal>"
-is part of the syntax of <literal>let</literal> bindings.
</para>
</sect2>
</programlisting>
The semantics of Haskell pattern matching is described in <ulink
url="http://www.haskell.org/onlinereport/exps.html#sect3.17.2">
-Section 3.17.2</ulink> of the Haskell Report. To this description add
+Section 3.17.2</ulink> of the Haskell Report. To this description add
one extra item 10, saying:
<itemizedlist><listitem><para>Matching
the pattern <literal>!pat</literal> against a value <literal>v</literal> behaves as follows:
= v `seq` case v of { pat -> e; _ -> e' }
</programlisting>
</para><para>
-That leaves let expressions, whose translation is given in
+That leaves let expressions, whose translation is given in
<ulink url="http://www.haskell.org/onlinereport/exps.html#sect3.12">Section
3.12</ulink>
of the Haskell Report.
-In the translation box, first apply
-the following transformation: for each pattern <literal>pi</literal> that is of
-form <literal>!qi = ei</literal>, transform it to <literal>(xi,!qi) = ((),ei)</literal>, and and replace <literal>e0</literal>
+In the translation box, first apply
+the following transformation: for each pattern <literal>pi</literal> that is of
+form <literal>!qi = ei</literal>, transform it to <literal>(xi,!qi) = ((),ei)</literal>, and replace <literal>e0</literal>
by <literal>(xi `seq` e0)</literal>. Then, when none of the left-hand-side patterns
have a bang at the top, apply the rules in the existing box.
</para>
<para>Pragmas all take the form
-<literal>{-# <replaceable>word</replaceable> ... #-}</literal>
+<literal>{-# <replaceable>word</replaceable> ... #-}</literal>
where <replaceable>word</replaceable> indicates the type of
pragma, and is followed optionally by information specific to that
<replaceable>word</replaceable>. The various values for
<replaceable>word</replaceable> that GHC understands are described
in the following sections; any pragma encountered with an
- unrecognised <replaceable>word</replaceable> is (silently)
+ unrecognised <replaceable>word</replaceable> is
ignored. The layout rule applies in pragmas, so the closing <literal>#-}</literal>
- should start in a column to the right of the opening <literal>{-#</literal>. </para>
+ should start in a column to the right of the opening <literal>{-#</literal>. </para>
- <para>Certain pragmas are <emphasis>file-header pragmas</emphasis>. A file-header
- pragma must precede the <literal>module</literal> keyword in the file.
+ <para>Certain pragmas are <emphasis>file-header pragmas</emphasis>:
+ <itemizedlist>
+ <listitem><para>
+ A file-header
+ pragma must precede the <literal>module</literal> keyword in the file.
+ </para></listitem>
+ <listitem><para>
There can be as many file-header pragmas as you please, and they can be
- preceded or followed by comments.</para>
+ preceded or followed by comments.
+ </para></listitem>
+ <listitem><para>
+ File-header pragmas are read once only, before
+ pre-processing the file (e.g. with cpp).
+ </para></listitem>
+ <listitem><para>
+ The file-header pragmas are: <literal>{-# LANGUAGE #-}</literal>,
+ <literal>{-# OPTIONS_GHC #-}</literal>, and
+ <literal>{-# INCLUDE #-}</literal>.
+ </para></listitem>
+ </itemizedlist>
+ </para>
<sect2 id="language-pragma">
<title>LANGUAGE pragma</title>
<indexterm><primary>LANGUAGE</primary><secondary>pragma</secondary></indexterm>
<indexterm><primary>pragma</primary><secondary>LANGUAGE</secondary></indexterm>
- <para>The <literal>LANGUAGE</literal> pragma allows language extensions to be enabled
+ <para>The <literal>LANGUAGE</literal> pragma allows language extensions to be enabled
in a portable way.
It is the intention that all Haskell compilers support the
<literal>LANGUAGE</literal> pragma with the same syntax, although not
</para>
<para>A list of all supported language extensions can be obtained by invoking
- <literal>ghc --supported-languages</literal> (see <xref linkend="modes"/>).</para>
+ <literal>ghc --supported-extensions</literal> (see <xref linkend="modes"/>).</para>
<para>Any extension from the <literal>Extension</literal> type defined in
<ulink
- url="../libraries/Cabal/Language-Haskell-Extension.html"><literal>Language.Haskell.Extension</literal></ulink>
+ url="&libraryCabalLocation;/Language-Haskell-Extension.html"><literal>Language.Haskell.Extension</literal></ulink>
may be used. GHC will report an error if any of the requested extensions are not supported.</para>
</sect2>
<sect2 id="include-pragma">
<title>INCLUDE pragma</title>
- <para>The <literal>INCLUDE</literal> pragma is for specifying the names
- of C header files that should be <literal>#include</literal>'d into
- the C source code generated by the compiler for the current module (if
- compiling via C). For example:</para>
-
-<programlisting>
-{-# INCLUDE "foo.h" #-}
-{-# INCLUDE <stdio.h> #-}</programlisting>
-
- <para><literal>INCLUDE</literal> is a file-header pragma (see <xref linkend="pragmas"/>).</para>
-
- <para>An <literal>INCLUDE</literal> pragma is the preferred alternative
- to the <option>-#include</option> option (<xref
- linkend="options-C-compiler" />), because the
- <literal>INCLUDE</literal> pragma is understood by other
- compilers. Yet another alternative is to add the include file to each
- <literal>foreign import</literal> declaration in your code, but we
- don't recommend using this approach with GHC.</para>
+ <para>The <literal>INCLUDE</literal> used to be necessary for
+ specifying header files to be included when using the FFI and
+ compiling via C. It is no longer required for GHC, but is
+ accepted (and ignored) for compatibility with other
+ compilers.</para>
</sect2>
<sect2 id="warning-deprecated-pragma">
(a) uses within the defining module, and
(b) uses in an export list.
The latter reduces spurious complaints within a library
- in which one module gathers together and re-exports
+ in which one module gathers together and re-exports
the exports of several others.
</para>
<para>You can suppress the warnings with the flag
<para>The major effect of an <literal>INLINE</literal> pragma
is to declare a function's “cost” to be very low.
The normal unfolding machinery will then be very keen to
- inline it. However, an <literal>INLINE</literal> pragma for a
+ inline it. However, an <literal>INLINE</literal> pragma for a
function "<literal>f</literal>" has a number of other effects:
<itemizedlist>
<listitem><para>
-No functions are inlined into <literal>f</literal>. Otherwise
-GHC might inline a big function into <literal>f</literal>'s right hand side,
-making <literal>f</literal> big; and then inline <literal>f</literal> blindly.
+While GHC is keen to inline the function, it does not do so
+blindly. For example, if you write
+<programlisting>
+map key_function xs
+</programlisting>
+there really isn't any point in inlining <literal>key_function</literal> to get
+<programlisting>
+map (\x -> <replaceable>body</replaceable>) xs
+</programlisting>
+In general, GHC only inlines the function if there is some reason (no matter
+how slight) to suppose that it is useful to do so.
+</para></listitem>
+
+<listitem><para>
+Moreover, GHC will only inline the function if it is <emphasis>fully applied</emphasis>,
+where "fully applied"
+means applied to as many arguments as appear (syntactically)
+on the LHS of the function
+definition. For example:
+<programlisting>
+comp1 :: (b -> c) -> (a -> b) -> a -> c
+{-# INLINE comp1 #-}
+comp1 f g = \x -> f (g x)
+
+comp2 :: (b -> c) -> (a -> b) -> a -> c
+{-# INLINE comp2 #-}
+comp2 f g x = f (g x)
+</programlisting>
+The two functions <literal>comp1</literal> and <literal>comp2</literal> have the
+same semantics, but <literal>comp1</literal> will be inlined when applied
+to <emphasis>two</emphasis> arguments, while <literal>comp2</literal> requires
+<emphasis>three</emphasis>. This might make a big difference if you say
+<programlisting>
+map (not `comp1` not) xs
+</programlisting>
+which will optimise better than the corresponding use of `comp2`.
</para></listitem>
+
<listitem><para>
-The float-in, float-out, and common-sub-expression transformations are not
-applied to the body of <literal>f</literal>.
+It is useful for GHC to optimise the definition of an
+INLINE function <literal>f</literal> just like any other non-INLINE function,
+in case the non-inlined version of <literal>f</literal> is
+ultimately called. But we don't want to inline
+the <emphasis>optimised</emphasis> version
+of <literal>f</literal>;
+a major reason for INLINE pragmas is to expose functions
+in <literal>f</literal>'s RHS that have
+rewrite rules, and it's no good if those functions have been optimised
+away.
+</para>
+<para>
+So <emphasis>GHC guarantees to inline precisely the code that you wrote</emphasis>, no more
+and no less. It does this by capturing a copy of the definition of the function to use
+for inlining (we call this the "inline-RHS"), which it leaves untouched,
+while optimising the ordinarily RHS as usual. For externally-visible functions
+the inline-RHS (not the optimised RHS) is recorded in the interface file.
</para></listitem>
<listitem><para>
An INLINE function is not worker/wrappered by strictness analysis.
It's going to be inlined wholesale instead.
</para></listitem>
</itemizedlist>
-All of these effects are aimed at ensuring that what gets inlined is
-exactly what you asked for, no more and no less.
</para>
<para>GHC ensures that inlining cannot go on forever: every mutually-recursive
group is cut by one or more <emphasis>loop breakers</emphasis> that is never inlined
{-# INLINE returnUs #-}
</programlisting>
- <para>See also the <literal>NOINLINE</literal> pragma (<xref
- linkend="noinline-pragma"/>).</para>
+ <para>See also the <literal>NOINLINE</literal> (<xref linkend="inlinable-pragma"/>)
+ and <literal>INLINABLE</literal> (<xref linkend="noinline-pragma"/>)
+ pragmas.</para>
<para>Note: the HBC compiler doesn't like <literal>INLINE</literal> pragmas,
so if you want your code to be HBC-compatible you'll have to surround
- the pragma with C pre-processor directives
+ the pragma with C pre-processor directives
<literal>#ifdef __GLASGOW_HASKELL__</literal>...<literal>#endif</literal>.</para>
</sect3>
+ <sect3 id="inlinable-pragma">
+ <title>INLINABLE pragma</title>
+
+<para>An <literal>{-# INLINABLE f #-}</literal> pragma on a
+function <literal>f</literal> has the following behaviour:
+<itemizedlist>
+<listitem><para>
+While <literal>INLINE</literal> says "please inline me", the <literal>INLINABLE</literal>
+says "feel free to inline me; use your
+discretion". In other words the choice is left to GHC, which uses the same
+rules as for pragma-free functions. Unlike <literal>INLINE</literal>, that decision is made at
+the <emphasis>call site</emphasis>, and
+will therefore be affected by the inlining threshold, optimisation level etc.
+</para></listitem>
+<listitem><para>
+Like <literal>INLINE</literal>, the <literal>INLINABLE</literal> pragma retains a
+copy of the original RHS for
+inlining purposes, and persists it in the interface file, regardless of
+the size of the RHS.
+</para></listitem>
+
+<listitem><para>
+One way to use <literal>INLINABLE</literal> is in conjunction with
+the special function <literal>inline</literal> (<xref linkend="special-ids"/>).
+The call <literal>inline f</literal> tries very hard to inline <literal>f</literal>.
+To make sure that <literal>f</literal> can be inlined,
+it is a good idea to mark the definition
+of <literal>f</literal> as <literal>INLINABLE</literal>,
+so that GHC guarantees to expose an unfolding regardless of how big it is.
+Moreover, by annotating <literal>f</literal> as <literal>INLINABLE</literal>,
+you ensure that <literal>f</literal>'s original RHS is inlined, rather than
+whatever random optimised version of <literal>f</literal> GHC's optimiser
+has produced.
+</para></listitem>
+
+<listitem><para>
+The <literal>INLINABLE</literal> pragma also works with <literal>SPECIALISE</literal>:
+if you mark function <literal>f</literal> as <literal>INLINABLE</literal>, then
+you can subsequently <literal>SPECIALISE</literal> in another module
+(see <xref linkend="specialize-pragma"/>).</para></listitem>
+
+<listitem><para>
+Unlike <literal>INLINE</literal>, it is OK to use
+an <literal>INLINABLE</literal> pragma on a recursive function.
+The principal reason do to so to allow later use of <literal>SPECIALISE</literal>
+</para></listitem>
+</itemizedlist>
+</para>
+
+ </sect3>
+
<sect3 id="noinline-pragma">
<title>NOINLINE pragma</title>
-
+
<indexterm><primary>NOINLINE</primary></indexterm>
<indexterm><primary>NOTINLINE</primary></indexterm>
portable).</para>
</sect3>
+ <sect3 id="conlike-pragma">
+ <title>CONLIKE modifier</title>
+ <indexterm><primary>CONLIKE</primary></indexterm>
+ <para>An INLINE or NOINLINE pragma may have a CONLIKE modifier,
+ which affects matching in RULEs (only). See <xref linkend="conlike"/>.
+ </para>
+ </sect3>
+
<sect3 id="phase-control">
<title>Phase control</title>
</sect3>
</sect2>
+ <sect2 id="annotation-pragmas">
+ <title>ANN pragmas</title>
+
+ <para>GHC offers the ability to annotate various code constructs with additional
+ data by using three pragmas. This data can then be inspected at a later date by
+ using GHC-as-a-library.</para>
+
+ <sect3 id="ann-pragma">
+ <title>Annotating values</title>
+
+ <indexterm><primary>ANN</primary></indexterm>
+
+ <para>Any expression that has both <literal>Typeable</literal> and <literal>Data</literal> instances may be attached to a top-level value
+ binding using an <literal>ANN</literal> pragma. In particular, this means you can use <literal>ANN</literal>
+ to annotate data constructors (e.g. <literal>Just</literal>) as well as normal values (e.g. <literal>take</literal>).
+ By way of example, to annotate the function <literal>foo</literal> with the annotation <literal>Just "Hello"</literal>
+ you would do this:</para>
+
+<programlisting>
+{-# ANN foo (Just "Hello") #-}
+foo = ...
+</programlisting>
+
+ <para>
+ A number of restrictions apply to use of annotations:
+ <itemizedlist>
+ <listitem><para>The binder being annotated must be at the top level (i.e. no nested binders)</para></listitem>
+ <listitem><para>The binder being annotated must be declared in the current module</para></listitem>
+ <listitem><para>The expression you are annotating with must have a type with <literal>Typeable</literal> and <literal>Data</literal> instances</para></listitem>
+ <listitem><para>The <ulink linkend="using-template-haskell">Template Haskell staging restrictions</ulink> apply to the
+ expression being annotated with, so for example you cannot run a function from the module being compiled.</para>
+
+ <para>To be precise, the annotation <literal>{-# ANN x e #-}</literal> is well staged if and only if <literal>$(e)</literal> would be
+ (disregarding the usual type restrictions of the splice syntax, and the usual restriction on splicing inside a splice - <literal>$([|1|])</literal> is fine as an annotation, albeit redundant).</para></listitem>
+ </itemizedlist>
+
+ If you feel strongly that any of these restrictions are too onerous, <ulink url="http://hackage.haskell.org/trac/ghc/wiki/MailingListsAndIRC">
+ please give the GHC team a shout</ulink>.
+ </para>
+
+ <para>However, apart from these restrictions, many things are allowed, including expressions which are not fully evaluated!
+ Annotation expressions will be evaluated by the compiler just like Template Haskell splices are. So, this annotation is fine:</para>
+
+<programlisting>
+{-# ANN f SillyAnnotation { foo = (id 10) + $([| 20 |]), bar = 'f } #-}
+f = ...
+</programlisting>
+ </sect3>
+
+ <sect3 id="typeann-pragma">
+ <title>Annotating types</title>
+
+ <indexterm><primary>ANN type</primary></indexterm>
+ <indexterm><primary>ANN</primary></indexterm>
+
+ <para>You can annotate types with the <literal>ANN</literal> pragma by using the <literal>type</literal> keyword. For example:</para>
+
+<programlisting>
+{-# ANN type Foo (Just "A `Maybe String' annotation") #-}
+data Foo = ...
+</programlisting>
+ </sect3>
+
+ <sect3 id="modann-pragma">
+ <title>Annotating modules</title>
+
+ <indexterm><primary>ANN module</primary></indexterm>
+ <indexterm><primary>ANN</primary></indexterm>
+
+ <para>You can annotate modules with the <literal>ANN</literal> pragma by using the <literal>module</literal> keyword. For example:</para>
+
+<programlisting>
+{-# ANN module (Just "A `Maybe String' annotation") #-}
+</programlisting>
+ </sect3>
+ </sect2>
+
<sect2 id="line-pragma">
<title>LINE pragma</title>
h :: Eq a => a -> a -> a
{-# SPECIALISE h :: (Eq a) => [a] -> [a] -> [a] #-}
</programlisting>
-The last of these examples will generate a
+The last of these examples will generate a
RULE with a somewhat-complex left-hand side (try it yourself), so it might not fire very
well. If you use this kind of specialisation, let us know how well it works.
</para>
+ <sect3 id="specialize-inline">
+ <title>SPECIALIZE INLINE</title>
+
<para>A <literal>SPECIALIZE</literal> pragma can optionally be followed with a
-<literal>INLINE</literal> or <literal>NOINLINE</literal> pragma, optionally
+<literal>INLINE</literal> or <literal>NOINLINE</literal> pragma, optionally
followed by a phase, as described in <xref linkend="inline-noinline-pragma"/>.
The <literal>INLINE</literal> pragma affects the specialised version of the
function (only), and applies even if the function is recursive. The motivating
unrolling of the indexing function.</para>
<para>Warning: you can make GHC diverge by using <literal>SPECIALISE INLINE</literal>
on an ordinarily-recursive function.</para>
+</sect3>
+
+<sect3><title>SPECIALIZE for imported functions</title>
+
+<para>
+Generally, you can only give a <literal>SPECIALIZE</literal> pragma
+for a function defined in the same module.
+However if a function <literal>f</literal> is given an <literal>INLINABLE</literal>
+pragma at its definition site, then it can subsequently be specialised by
+importing modules (see <xref linkend="inlinable-pragma"/>).
+For example
+<programlisting>
+module Map( lookup, blah blah ) where
+ lookup :: Ord key => [(key,a)] -> key -> Maybe a
+ lookup = ...
+ {-# INLINABLE lookup #-}
+
+module Client where
+ import Map( lookup )
+
+ data T = T1 | T2 deriving( Eq, Ord )
+ {-# SPECIALISE lookup :: [(T,a)] -> T -> Maybe a
+</programlisting>
+Here, <literal>lookup</literal> is declared <literal>INLINABLE</literal>, but
+it cannot be specialised for type <literal>T</literal> at its definition site,
+because that type does not exist yet. Instead a client module can define <literal>T</literal>
+and then specialise <literal>lookup</literal> at that type.
+</para>
+<para>
+Moreover, every module that imports <literal>Client</literal> (or imports a module
+that imports <literal>Client</literal>, transitively) will "see", and make use of,
+the specialised version of <literal>lookup</literal>. You don't need to put
+a <literal>SPECIALIZE</literal> pragma in every module.
+</para>
+<para>
+Moreover you often don't even need the <literal>SPECIALIZE</literal> pragma in the
+first place. When compiling a module M,
+GHC's optimiser (with -O) automatically considers each top-level
+overloaded function declared in M, and specialises it
+for the different types at which it is called in M. The optimiser
+<emphasis>also</emphasis> considers each <emphasis>imported</emphasis>
+<literal>INLINABLE</literal> overloaded function, and specialises it
+for the different types at which it is called in M.
+So in our example, it would be enough for <literal>lookup</literal> to
+be called at type <literal>T</literal>:
+<programlisting>
+module Client where
+ import Map( lookup )
+
+ data T = T1 | T2 deriving( Eq, Ord )
+
+ findT1 :: [(T,a)] -> Maybe a
+ findT1 m = lookup m T1 -- A call of lookup at type T
+</programlisting>
+However, sometimes there are no such calls, in which case the
+pragma can be useful.
+</para>
+</sect3>
+
+<sect3><title>Obsolete SPECIALIZE syntax</title>
<para>Note: In earlier versions of GHC, it was possible to provide your own
specialised function for a given type:
This feature has been removed, as it is now subsumed by the
<literal>RULES</literal> pragma (see <xref linkend="rule-spec"/>).</para>
+</sect3>
</sect2>
Same idea, except for instance declarations. For example:
<programlisting>
-instance (Eq a) => Eq (Foo a) where {
+instance (Eq a) => Eq (Foo a) where {
{-# SPECIALIZE instance Eq (Foo [(Int, Bar)]) #-}
... usual stuff ...
}
<title>UNPACK pragma</title>
<indexterm><primary>UNPACK</primary></indexterm>
-
+
<para>The <literal>UNPACK</literal> indicates to the compiler
that it should unpack the contents of a constructor field into
the constructor itself, removing a level of indirection. For
directly in the <function>T</function> constructor. The
unpacker can see through newtypes, too.</para>
- <para>If a field cannot be unpacked, you will not get a warning,
- so it might be an idea to check the generated code with
- <option>-ddump-simpl</option>.</para>
-
<para>See also the <option>-funbox-strict-fields</option> flag,
which essentially has the effect of adding
<literal>{-# UNPACK #-}</literal> to every strict
<para>
The programmer can specify rewrite rules as part of the source program
-(in a pragma). GHC applies these rewrite rules wherever it can, provided (a)
-the <option>-O</option> flag (<xref linkend="options-optimise"/>) is on,
-and (b) the <option>-fno-rewrite-rules</option> flag
-(<xref linkend="options-f"/>) is not specified, and (c) the
-<option>-fglasgow-exts</option> (<xref linkend="options-language"/>)
-flag is active.
-</para>
-
-<para>
+(in a pragma).
Here is an example:
<programlisting>
<para>
Use the debug flag <option>-ddump-simpl-stats</option> to see what rules fired.
If you need more information, then <option>-ddump-rule-firings</option> shows you
-each individual rule firing in detail.
+each individual rule firing and <option>-ddump-rule-rewrites</option> also shows what the code looks like before and after the rewrite.
</para>
<sect2>
<listitem>
<para>
- Rules are automatically exported from a module, just as instance declarations are.
+ All rules are implicitly exported from the module, and are therefore
+in force in any module that imports the module that defined the rule, directly
+or indirectly. (That is, if A imports B, which imports C, then C's rules are
+in force when compiling A.) The situation is very similar to that for instance
+declarations.
+</para>
+</listitem>
+
+<listitem>
+
+<para>
+Inside a RULE "<literal>forall</literal>" is treated as a keyword, regardless of
+any other flag settings. Furthermore, inside a RULE, the language extension
+<option>-XScopedTypeVariables</option> is automatically enabled; see
+<xref linkend="scoped-type-variables"/>.
</para>
</listitem>
+<listitem>
+<para>
+Like other pragmas, RULE pragmas are always checked for scope errors, and
+are typechecked. Typechecking means that the LHS and RHS of a rule are typechecked,
+and must have the same type. However, rules are only <emphasis>enabled</emphasis>
+if the <option>-fenable-rewrite-rules</option> flag is
+on (see <xref linkend="rule-semantics"/>).
+</para>
+</listitem>
</itemizedlist>
</para>
</sect2>
-<sect2>
+<sect2 id="rule-semantics">
<title>Semantics</title>
<para>
<itemizedlist>
<listitem>
-
<para>
-Rules are only applied if you use the <option>-O</option> flag.
+Rules are enabled (that is, used during optimisation)
+by the <option>-fenable-rewrite-rules</option> flag.
+This flag is implied by <option>-O</option>, and may be switched
+off (as usual) by <option>-fno-enable-rewrite-rules</option>.
+(NB: enabling <option>-fenable-rewrite-rules</option> without <option>-O</option>
+may not do what you expect, though, because without <option>-O</option> GHC
+ignores all optimisation information in interface files;
+see <option>-fignore-interface-pragmas</option>, <xref linkend="options-f"/>.)
+Note that <option>-fenable-rewrite-rules</option> is an <emphasis>optimisation</emphasis> flag, and
+has no effect on parsing or typechecking.
</para>
</listitem>
<listitem>
<para>
- The LHS and RHS of a rule are typechecked, and must have the
-same type.
-
-</para>
-</listitem>
-<listitem>
-
-<para>
GHC makes absolutely no attempt to verify that the LHS and RHS
of a rule have the same meaning. That is undecidable in general, and
infeasible in most interesting cases. The responsibility is entirely the programmer's!
</para>
</listitem>
-<listitem>
+</itemizedlist>
+
+</para>
+
+</sect2>
+
+<sect2 id="conlike">
+<title>How rules interact with INLINE/NOINLINE and CONLIKE pragmas</title>
<para>
Ordinary inlining happens at the same time as rule rewriting, which may lead to unexpected
results. Consider this (artificial) example
<programlisting>
f x = x
-{-# RULES "f" f True = False #-}
-
g y = f y
-
h z = g True
+
+{-# RULES "f" f True = False #-}
</programlisting>
Since <literal>f</literal>'s right-hand side is small, it is inlined into <literal>g</literal>,
to give
g y = y
</programlisting>
Now <literal>g</literal> is inlined into <literal>h</literal>, but <literal>f</literal>'s RULE has
-no chance to fire.
+no chance to fire.
If instead GHC had first inlined <literal>g</literal> into <literal>h</literal> then there
-would have been a better chance that <literal>f</literal>'s RULE might fire.
+would have been a better chance that <literal>f</literal>'s RULE might fire.
</para>
<para>
-The way to get predictable behaviour is to use a NOINLINE
-pragma on <literal>f</literal>, to ensure
+The way to get predictable behaviour is to use a NOINLINE
+pragma, or an INLINE[<replaceable>phase</replaceable>] pragma, on <literal>f</literal>, to ensure
that it is not inlined until its RULEs have had a chance to fire.
</para>
-</listitem>
-<listitem>
-
<para>
- All rules are implicitly exported from the module, and are therefore
-in force in any module that imports the module that defined the rule, directly
-or indirectly. (That is, if A imports B, which imports C, then C's rules are
-in force when compiling A.) The situation is very similar to that for instance
-declarations.
+GHC is very cautious about duplicating work. For example, consider
+<programlisting>
+f k z xs = let xs = build g
+ in ...(foldr k z xs)...sum xs...
+{-# RULES "foldr/build" forall k z g. foldr k z (build g) = g k z #-}
+</programlisting>
+Since <literal>xs</literal> is used twice, GHC does not fire the foldr/build rule. Rightly
+so, because it might take a lot of work to compute <literal>xs</literal>, which would be
+duplicated if the rule fired.
</para>
-</listitem>
-
-</itemizedlist>
-
+<para>
+Sometimes, however, this approach is over-cautious, and we <emphasis>do</emphasis> want the
+rule to fire, even though doing so would duplicate redex. There is no way that GHC can work out
+when this is a good idea, so we provide the CONLIKE pragma to declare it, thus:
+<programlisting>
+{-# INLINE[1] CONLIKE f #-}
+f x = <replaceable>blah</replaceable>
+</programlisting>
+CONLIKE is a modifier to an INLINE or NOINLINE pragma. It specifies that an application
+of f to one argument (in general, the number of arguments to the left of the '=' sign)
+should be considered cheap enough to duplicate, if such a duplication would make rule
+fire. (The name "CONLIKE" is short for "constructor-like", because constructors certainly
+have such a property.)
+The CONLIKE pragma is a modifier to INLINE/NOINLINE because it really only makes sense to match
+<literal>f</literal> on the LHS of a rule if you are sure that <literal>f</literal> is
+not going to be inlined before the rule has a chance to fire.
</para>
-
</sect2>
<sect2>
</sect2>
-<sect2>
-<title>Controlling what's going on</title>
+<sect2 id="controlling-rules">
+<title>Controlling what's going on in rewrite rules</title>
<para>
<listitem>
<para>
- Use <option>-ddump-rules</option> to see what transformation rules GHC is using.
+Use <option>-ddump-rules</option> to see the rules that are defined
+<emphasis>in this module</emphasis>.
+This includes rules generated by the specialisation pass, but excludes
+rules imported from other modules.
</para>
</listitem>
-<listitem>
+<listitem>
<para>
Use <option>-ddump-simpl-stats</option> to see what rules are being fired.
If you add <option>-dppr-debug</option> you get a more detailed listing.
</para>
</listitem>
+
<listitem>
+<para>
+ Use <option>-ddump-rule-firings</option> or <option>-ddump-rule-rewrites</option>
+to see in great detail what rules are being fired.
+If you add <option>-dppr-debug</option> you get a still more detailed listing.
+</para>
+</listitem>
+<listitem>
<para>
The definition of (say) <function>build</function> in <filename>GHC/Base.lhs</filename> looks like this:
<title>Special built-in functions</title>
<para>GHC has a few built-in functions with special behaviour. These
are now described in the module <ulink
-url="../libraries/base/GHC-Prim.html"><literal>GHC.Prim</literal></ulink>
-in the library documentation.</para>
+url="&libraryGhcPrimLocation;/GHC-Prim.html"><literal>GHC.Prim</literal></ulink>
+in the library documentation.
+In particular:
+<itemizedlist>
+<listitem><para>
+<ulink url="&libraryGhcPrimLocation;/GHC-Prim.html#v%3Ainline"><literal>inline</literal></ulink>
+allows control over inlining on a per-call-site basis.
+</para></listitem>
+<listitem><para>
+<ulink url="&libraryGhcPrimLocation;/GHC-Prim.html#v%3Alazy"><literal>lazy</literal></ulink>
+restrains the strictness analyser.
+</para></listitem>
+<listitem><para>
+<ulink url="&libraryGhcPrimLocation;/GHC-Prim.html#v%3AunsafeCoerce%23"><literal>unsafeCoerce#</literal></ulink>
+allows you to fool the type checker.
+</para></listitem>
+</itemizedlist>
+</para>
</sect1>
<title>Generic classes</title>
<para>
-The ideas behind this extension are described in detail in "Derivable type classes",
-Ralf Hinze and Simon Peyton Jones, Haskell Workshop, Montreal Sept 2000, pp94-105.
-An example will give the idea:
+GHC used to have an implementation of generic classes as defined in the paper
+"Derivable type classes", Ralf Hinze and Simon Peyton Jones, Haskell Workshop,
+Montreal Sept 2000, pp94-105. These have been removed and replaced by the more
+general <link linkend="generic-programming">support for generic programming</link>.
</para>
-<programlisting>
- import Generics
-
- class Bin a where
- toBin :: a -> [Int]
- fromBin :: [Int] -> (a, [Int])
-
- toBin {| Unit |} Unit = []
- toBin {| a :+: b |} (Inl x) = 0 : toBin x
- toBin {| a :+: b |} (Inr y) = 1 : toBin y
- toBin {| a :*: b |} (x :*: y) = toBin x ++ toBin y
-
- fromBin {| Unit |} bs = (Unit, bs)
- fromBin {| a :+: b |} (0:bs) = (Inl x, bs') where (x,bs') = fromBin bs
- fromBin {| a :+: b |} (1:bs) = (Inr y, bs') where (y,bs') = fromBin bs
- fromBin {| a :*: b |} bs = (x :*: y, bs'') where (x,bs' ) = fromBin bs
- (y,bs'') = fromBin bs'
-</programlisting>
-<para>
-This class declaration explains how <literal>toBin</literal> and <literal>fromBin</literal>
-work for arbitrary data types. They do so by giving cases for unit, product, and sum,
-which are defined thus in the library module <literal>Generics</literal>:
-</para>
-<programlisting>
- data Unit = Unit
- data a :+: b = Inl a | Inr b
- data a :*: b = a :*: b
-</programlisting>
-<para>
-Now you can make a data type into an instance of Bin like this:
-<programlisting>
- instance (Bin a, Bin b) => Bin (a,b)
- instance Bin a => Bin [a]
-</programlisting>
-That is, just leave off the "where" clause. Of course, you can put in the
-where clause and over-ride whichever methods you please.
-</para>
+</sect1>
- <sect2>
- <title> Using generics </title>
- <para>To use generics you need to</para>
- <itemizedlist>
- <listitem>
- <para>Use the flags <option>-fglasgow-exts</option> (to enable the extra syntax),
- <option>-XGenerics</option> (to generate extra per-data-type code),
- and <option>-package lang</option> (to make the <literal>Generics</literal> library
- available. </para>
- </listitem>
- <listitem>
- <para>Import the module <literal>Generics</literal> from the
- <literal>lang</literal> package. This import brings into
- scope the data types <literal>Unit</literal>,
- <literal>:*:</literal>, and <literal>:+:</literal>. (You
- don't need this import if you don't mention these types
- explicitly; for example, if you are simply giving instance
- declarations.)</para>
- </listitem>
- </itemizedlist>
- </sect2>
-<sect2> <title> Changes wrt the paper </title>
-<para>
-Note that the type constructors <literal>:+:</literal> and <literal>:*:</literal>
-can be written infix (indeed, you can now use
-any operator starting in a colon as an infix type constructor). Also note that
-the type constructors are not exactly as in the paper (Unit instead of 1, etc).
-Finally, note that the syntax of the type patterns in the class declaration
-uses "<literal>{|</literal>" and "<literal>|}</literal>" brackets; curly braces
-alone would ambiguous when they appear on right hand sides (an extension we
-anticipate wanting).
-</para>
-</sect2>
+<sect1 id="generic-programming">
+<title>Generic programming</title>
-<sect2> <title>Terminology and restrictions</title>
<para>
-Terminology. A "generic default method" in a class declaration
-is one that is defined using type patterns as above.
-A "polymorphic default method" is a default method defined as in Haskell 98.
-A "generic class declaration" is a class declaration with at least one
-generic default method.
+Using a combination of <option>-XDeriveGeneric</option>
+(<xref linkend="deriving-typeable"/>) and
+<option>-XDefaultSignatures</option> (<xref linkend="class-default-signatures"/>),
+you can easily do datatype-generic
+programming using the <literal>GHC.Generics</literal> framework. This section
+gives a very brief overview of how to do it. For more detail please refer to the
+<ulink url="http://www.haskell.org/haskellwiki/Generics">HaskellWiki page</ulink>
+or the original paper:
</para>
-<para>
-Restrictions:
<itemizedlist>
<listitem>
<para>
-Alas, we do not yet implement the stuff about constructor names and
-field labels.
+Jos� Pedro Magalh�es, Atze Dijkstra, Johan Jeuring, and Andres L�h.
+<ulink url="http://dreixel.net/research/pdf/gdmh.pdf">
+ A generic deriving mechanism for Haskell</ulink>.
+<citetitle>Proceedings of the third ACM Haskell symposium on Haskell</citetitle>
+(Haskell'2010), pp. 37-48, ACM, 2010.
</para>
</listitem>
+</itemizedlist>
-<listitem>
-<para>
-A generic class can have only one parameter; you can't have a generic
-multi-parameter class.
-</para>
-</listitem>
+<emphasis>Note</emphasis>: the current support for generic programming in GHC
+is preliminary. In particular, we only allow deriving instances for the
+<literal>Generic</literal> class. Support for deriving
+<literal>Generic1</literal> (and thus enabling generic functions of kind
+<literal>* -> *</literal> such as <literal>fmap</literal>) will come at a
+later stage.
-<listitem>
-<para>
-A default method must be defined entirely using type patterns, or entirely
-without. So this is illegal:
-<programlisting>
- class Foo a where
- op :: a -> (a, Bool)
- op {| Unit |} Unit = (Unit, True)
- op x = (x, False)
-</programlisting>
-However it is perfectly OK for some methods of a generic class to have
-generic default methods and others to have polymorphic default methods.
-</para>
-</listitem>
-<listitem>
-<para>
-The type variable(s) in the type pattern for a generic method declaration
-scope over the right hand side. So this is legal (note the use of the type variable ``p'' in a type signature on the right hand side:
-<programlisting>
- class Foo a where
- op :: a -> Bool
- op {| p :*: q |} (x :*: y) = op (x :: p)
- ...
-</programlisting>
-</para>
-</listitem>
+<sect2>
+<title>Deriving representations</title>
-<listitem>
<para>
-The type patterns in a generic default method must take one of the forms:
-<programlisting>
- a :+: b
- a :*: b
- Unit
-</programlisting>
-where "a" and "b" are type variables. Furthermore, all the type patterns for
-a single type constructor (<literal>:*:</literal>, say) must be identical; they
-must use the same type variables. So this is illegal:
+The first thing we need is generic representations. The
+<literal>GHC.Generics</literal> module defines a couple of primitive types
+that can be used to represent most Haskell datatypes:
+
<programlisting>
- class Foo a where
- op :: a -> Bool
- op {| a :+: b |} (Inl x) = True
- op {| p :+: q |} (Inr y) = False
+-- | Unit: used for constructors without arguments
+data U1 p = U1
+
+-- | Constants, additional parameters and recursion of kind *
+newtype K1 i c p = K1 { unK1 :: c }
+
+-- | Meta-information (constructor names, etc.)
+newtype M1 i c f p = M1 { unM1 :: f p }
+
+-- | Sums: encode choice between constructors
+infixr 5 :+:
+data (:+:) f g p = L1 (f p) | R1 (g p)
+
+-- | Products: encode multiple arguments to constructors
+infixr 6 :*:
+data (:*:) f g p = f p :*: g p
</programlisting>
-The type patterns must be identical, even in equations for different methods of the class.
-So this too is illegal:
+
+For example, a user-defined datatype of trees <literal>data UserTree a = Node a
+(UserTree a) (UserTree a) | Leaf</literal> gets the following representation:
+
<programlisting>
- class Foo a where
- op1 :: a -> Bool
- op1 {| a :*: b |} (x :*: y) = True
+instance Generic (UserTree a) where
+ -- Representation type
+ type Rep (UserTree a) =
+ M1 D D1UserTree (
+ M1 C C1_0UserTree (
+ M1 S NoSelector (K1 P a)
+ :*: M1 S NoSelector (K1 R (UserTree a))
+ :*: M1 S NoSelector (K1 R (UserTree a)))
+ :+: M1 C C1_1UserTree U1)
+
+ -- Conversion functions
+ from (Node x l r) = M1 (L1 (M1 (M1 (K1 x) :*: M1 (K1 l) :*: M1 (K1 r))))
+ from Leaf = M1 (R1 (M1 U1))
+ to (M1 (L1 (M1 (M1 (K1 x) :*: M1 (K1 l) :*: M1 (K1 r))))) = Node x l r
+ to (M1 (R1 (M1 U1))) = Leaf
- op2 :: a -> Bool
- op2 {| p :*: q |} (x :*: y) = False
+-- Meta-information
+data D1UserTree
+data C1_0UserTree
+data C1_1UserTree
+
+instance Datatype D1UserTree where
+ datatypeName _ = "UserTree"
+ moduleName _ = "Main"
+
+instance Constructor C1_0UserTree where
+ conName _ = "Node"
+
+instance Constructor C1_1UserTree where
+ conName _ = "Leaf"
</programlisting>
-(The reason for this restriction is that we gather all the equations for a particular type constructor
-into a single generic instance declaration.)
-</para>
-</listitem>
-<listitem>
-<para>
-A generic method declaration must give a case for each of the three type constructors.
+This representation is generated automatically if a
+<literal>deriving Generic</literal> clause is attached to the datatype.
+<link linkend="stand-alone-deriving">Standalone deriving</link> can also be
+used.
</para>
-</listitem>
+</sect2>
+
+<sect2>
+<title>Writing generic functions</title>
-<listitem>
<para>
-The type for a generic method can be built only from:
- <itemizedlist>
- <listitem> <para> Function arrows </para> </listitem>
- <listitem> <para> Type variables </para> </listitem>
- <listitem> <para> Tuples </para> </listitem>
- <listitem> <para> Arbitrary types not involving type variables </para> </listitem>
- </itemizedlist>
-Here are some example type signatures for generic methods:
+A generic function is defined by creating a class and giving instances for
+each of the representation types of <literal>GHC.Generics</literal>. As an
+example we show generic serialization:
<programlisting>
- op1 :: a -> Bool
- op2 :: Bool -> (a,Bool)
- op3 :: [Int] -> a -> a
- op4 :: [a] -> Bool
+data Bin = O | I
+
+class GSerialize f where
+ gput :: f a -> [Bin]
+
+instance GSerialize U1 where
+ gput U1 = []
+
+instance (GSerialize a, GSerialize b) => GSerialize (a :*: b) where
+ gput (a :*: b) = gput a ++ gput b
+
+instance (GSerialize a, GSerialize b) => GSerialize (a :+: b) where
+ gput (L1 x) = O : gput x
+ gput (R1 x) = I : gput x
+
+instance (GSerialize a) => GSerialize (M1 i c a) where
+ gput (M1 x) = gput x
+
+instance (Serialize a) => GSerialize (K1 i c a) where
+ gput (K1 x) = put x
</programlisting>
-Here, op1, op2, op3 are OK, but op4 is rejected, because it has a type variable
-inside a list.
-</para>
-<para>
-This restriction is an implementation restriction: we just haven't got around to
-implementing the necessary bidirectional maps over arbitrary type constructors.
-It would be relatively easy to add specific type constructors, such as Maybe and list,
-to the ones that are allowed.</para>
-</listitem>
-<listitem>
-<para>
-In an instance declaration for a generic class, the idea is that the compiler
-will fill in the methods for you, based on the generic templates. However it can only
-do so if
- <itemizedlist>
- <listitem>
- <para>
- The instance type is simple (a type constructor applied to type variables, as in Haskell 98).
- </para>
- </listitem>
- <listitem>
- <para>
- No constructor of the instance type has unboxed fields.
- </para>
- </listitem>
- </itemizedlist>
-(Of course, these things can only arise if you are already using GHC extensions.)
-However, you can still give an instance declarations for types which break these rules,
-provided you give explicit code to override any generic default methods.
+Typically this class will not be exported, as it only makes sense to have
+instances for the representation types.
</para>
-</listitem>
+</sect2>
-</itemizedlist>
-</para>
+<sect2>
+<title>Generic defaults</title>
<para>
-The option <option>-ddump-deriv</option> dumps incomprehensible stuff giving details of
-what the compiler does with generic declarations.
-</para>
+The only thing left to do now is to define a "front-end" class, which is
+exposed to the user:
+<programlisting>
+class Serialize a where
+ put :: a -> [Bin]
-</sect2>
+ default put :: (Generic a, GSerialize (Rep a)) => a -> [Bit]
+ put = gput . from
+</programlisting>
+Here we use a <link linkend="class-default-signatures">default signature</link>
+to specify that the user does not have to provide an implementation for
+<literal>put</literal>, as long as there is a <literal>Generic</literal>
+instance for the type to instantiate. For the <literal>UserTree</literal> type,
+for instance, the user can just write:
-<sect2> <title> Another example </title>
-<para>
-Just to finish with, here's another example I rather like:
<programlisting>
- class Tag a where
- nCons :: a -> Int
- nCons {| Unit |} _ = 1
- nCons {| a :*: b |} _ = 1
- nCons {| a :+: b |} _ = nCons (bot::a) + nCons (bot::b)
-
- tag :: a -> Int
- tag {| Unit |} _ = 1
- tag {| a :*: b |} _ = 1
- tag {| a :+: b |} (Inl x) = tag x
- tag {| a :+: b |} (Inr y) = nCons (bot::a) + tag y
+instance (Serialize a) => Serialize (UserTree a)
</programlisting>
+
+The default method for <literal>put</literal> is then used, corresponding to the
+generic implementation of serialization.
</para>
</sect2>
+
</sect1>
+
<sect1 id="monomorphism">
<title>Control over monomorphism</title>
<title>Switching off the dreaded Monomorphism Restriction</title>
<indexterm><primary><option>-XNoMonomorphismRestriction</option></primary></indexterm>
-<para>Haskell's monomorphism restriction (see
+<para>Haskell's monomorphism restriction (see
<ulink url="http://www.haskell.org/onlinereport/decls.html#sect4.5.5">Section
4.5.5</ulink>
of the Haskell Report)
<indexterm><primary><option>-XMonoPatBinds</option></primary></indexterm>
<para> As an experimental change, we are exploring the possibility of
- making pattern bindings monomorphic; that is, not generalised at all.
+ making pattern bindings monomorphic; that is, not generalised at all.
A pattern binding is a binding whose LHS has no function arguments,
and is not a simple variable. For example:
<programlisting>
<!-- Emacs stuff:
;;; Local Variables: ***
- ;;; mode: xml ***
;;; sgml-parent-document: ("users_guide.xml" "book" "chapter" "sect1") ***
;;; ispell-local-dictionary: "british" ***
;;; End: ***
projects / ghc-hetmet.git / blobdiff