<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. To use them, you'll need to give a <option>-fglasgow-exts</option>
-<indexterm><primary>-fglasgow-exts option</primary></indexterm> option.
+the language. They are all enabled by options; by default GHC
+understands only plain Haskell 98.
</para>
<para>
-Virtually all of the Glasgow extensions serve to give you access to
-the underlying facilities with which we implement Haskell. Thus, you
-can get at the Raw Iron, if you are willing to write some non-standard
-code at a more primitive level. You need not be “stuck” on
-performance because of the implementation costs of Haskell's
-“high-level” features—you can always code “under” them. In an extreme case, you can write all your time-critical code in C, and then just glue it together with Haskell!
+Some of the Glasgow extensions serve to give you access to the
+underlying facilities with which we implement Haskell. Thus, you can
+get at the Raw Iron, if you are willing to write some non-portable
+code at a more primitive level. You need not be “stuck”
+on performance because of the implementation costs of Haskell's
+“high-level” features—you can always code
+“under” them. In an extreme case, you can write all your
+time-critical code in C, and then just glue it together with Haskell!
</para>
<para>
sloshing <literal>MutableByteArray#</literal>s around your
program), you may wish to check if there are libraries that provide a
“Haskellised veneer” over the features you want. The
-separate libraries documentation describes all the libraries that come
-with GHC.
+separate <ulink url="../libraries/index.html">libraries
+documentation</ulink> describes all the libraries that come with GHC.
</para>
<!-- LANGUAGE OPTIONS -->
<indexterm><primary>extensions</primary><secondary>options controlling</secondary>
</indexterm>
- <para> These flags control what variation of the language are
+ <para>These flags control what variation of the language are
permitted. Leaving out all of them gives you standard Haskell
98.</para>
+ <para>NB. 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>
+
+ <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>
<listitem>
<para>This simultaneously enables all of the extensions to
Haskell 98 described in <xref
- linkend="ghc-language-features">, except where otherwise
+ linkend="ghc-language-features"/>, except where otherwise
noted. </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>
</listitem>
</varlistentry>
Haskell 98 Foreign Function Interface Addendum plus deprecated
syntax of previous versions of the FFI for backwards
compatibility.</para>
- </listitem>
- </varlistentry>
- <varlistentry>
- <term><option>-fwith</option>:</term>
- <indexterm><primary><option>-fwith</option></primary></indexterm>
- <listitem>
- <para>This option enables the deprecated <literal>with</literal>
- keyword for implicit parameters; it is merely provided for backwards
- compatibility.
- It is independent of the <option>-fglasgow-exts</option>
- flag. </para>
+ <para>New reserved words: <literal>foreign</literal>.</para>
</listitem>
</varlistentry>
<indexterm><primary><option>-fallow-undecidable-instances</option></primary></indexterm>
<indexterm><primary><option>-fcontext-stack</option></primary></indexterm>
<listitem>
- <para> See <xref LinkEnd="instance-decls">. Only relevant
+ <para> See <xref linkend="instance-decls"/>. Only relevant
if you also use <option>-fglasgow-exts</option>.</para>
</listitem>
</varlistentry>
<term><option>-finline-phase</option></term>
<indexterm><primary><option>-finline-phase</option></primary></indexterm>
<listitem>
- <para>See <xref LinkEnd="rewrite-rules">. Only relevant if
+ <para>See <xref linkend="rewrite-rules"/>. Only relevant if
you also use <option>-fglasgow-exts</option>.</para>
</listitem>
</varlistentry>
<term><option>-farrows</option></term>
<indexterm><primary><option>-farrows</option></primary></indexterm>
<listitem>
- <para>See <xref LinkEnd="arrow-notation">. Independent of
+ <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>
<term><option>-fgenerics</option></term>
<indexterm><primary><option>-fgenerics</option></primary></indexterm>
<listitem>
- <para>See <xref LinkEnd="generic-classes">. Independent of
+ <para>See <xref linkend="generic-classes"/>. Independent of
<option>-fglasgow-exts</option>.</para>
</listitem>
</varlistentry>
- <varlistentry>
- <term><option>-fno-implicit-prelude</option></term>
- <listitem>
- <para><indexterm><primary>-fno-implicit-prelude
- 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>-fno-implicit-prelude</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>-fno-implicit-prelude</option> does
- change the handling of certain built-in syntax: see
- <xref LinkEnd="rebindable-syntax">.</para>
+ <varlistentry>
+ <term><option>-fno-implicit-prelude</option></term>
+ <listitem>
+ <para><indexterm><primary>-fno-implicit-prelude
+ 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>-fno-implicit-prelude</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>-fno-implicit-prelude</option> does
+ change the handling of certain built-in syntax: see <xref
+ linkend="rebindable-syntax"/>.</para>
+ </listitem>
+ </varlistentry>
- </listitem>
- </varlistentry>
+ <varlistentry>
+ <term><option>-fth</option></term>
+ <listitem>
+ <para>Enables Template Haskell (see <xref
+ linkend="template-haskell"/>). Currently also 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>-fimplicit-params</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>
</variablelist>
</sect1>
<para>For details on how GHC searches for source and interface
files in the presence of hierarchical modules, see <xref
- linkend="search-path">.</para>
+ linkend="search-path"/>.</para>
<para>GHC comes with a large collection of libraries arranged
hierarchically; see the accompanying library documentation.
<para>
<indexterm><primary>Pattern guards (Glasgow extension)</primary></indexterm>
-The discussion that follows is an abbreviated version of Simon Peyton Jones's original <ULink URL="http://research.microsoft.com/~simonpj/Haskell/guards.html">proposal</ULink>. (Note that the proposal was written before pattern guards were implemented, so refers to them as unimplemented.)
+The discussion that follows is an abbreviated version of Simon Peyton Jones's original <ulink URL="http://research.microsoft.com/~simonpj/Haskell/guards.html">proposal</ulink>. (Note that the proposal was written before pattern guards were implemented, so refers to them as unimplemented.)
</para>
<para>
</programlisting>
The lookup returns <function>Nothing</function> if the supplied key is not in the domain of the mapping, and <function>(Just v)</function> otherwise,
-where <VarName>v</VarName> is the value that the key maps to. Now consider the following definition:
+where <varname>v</varname> is the value that the key maps to. Now consider the following definition:
</para>
<programlisting>
-clunky env var1 var2 | ok1 && ok2 = val1 + val2
+clunky env var1 var2 | ok1 && ok2 = val1 + val2
| otherwise = var1 + var2
where
m1 = lookup env var1
</programlisting>
<para>
-What is <function>clunky</function> doing? The guard <literal>ok1 &&
+What is <function>clunky</function> doing? The guard <literal>ok1 &&
ok2</literal> checks that both lookups succeed, using
<function>maybeToBool</function> to convert the <function>Maybe</function>
types to booleans. The (lazily evaluated) <function>expectJust</function>
calls extract the values from the results of the lookups, and binds the
-returned values to <VarName>val1</VarName> and <VarName>val2</VarName>
+returned values to <varname>val1</varname> and <varname>val2</varname>
respectively. If either lookup fails, then clunky takes the
<literal>otherwise</literal> case and returns the sum of its arguments.
</para>
</para>
<programlisting>
-f x | [y] <- x
+f x | [y] <- x
, y > 3
- , Just z <- h y
+ , Just z <- h y
= ...
</programlisting>
<programlisting>
import Control.Monad.Fix
-justOnes = mdo xs <- Just (1:xs)
+justOnes = mdo xs <- Just (1:xs)
return xs
</programlisting>
<para>
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>
<sect1 id="type-extensions">
<title>Type system extensions</title>
-<sect2 id="nullary-types">
+
+<sect2>
+<title>Data types and type synonyms</title>
+
+<sect3 id="nullary-types">
<title>Data types with no constructors</title>
<para>With the <option>-fglasgow-exts</option> flag, GHC lets you declare
<para>Syntactically, the declaration lacks the "= constrs" part. The
type can be parameterised over types of any kind, but if the kind is
not <literal>*</literal> then an explicit kind annotation must be used
-(see <xref linkend="sec-kinding">).</para>
+(see <xref linkend="sec-kinding"/>).</para>
<para>Such data types have only one value, namely bottom.
Nevertheless, they can be useful when defining "phantom types".</para>
-</sect2>
+</sect3>
-<sect2 id="infix-tycons">
+<sect3 id="infix-tycons">
<title>Infix type constructors</title>
<para>
</itemizedlist>
</para>
-</sect2>
+</sect3>
-<sect2 id="sec-kinding">
-<title>Explicitly-kinded quantification</title>
+<sect3 id="type-synonyms">
+<title>Liberalised type synonyms</title>
<para>
-Haskell infers the kind of each type variable. Sometimes it is nice to be able
-to give the kind explicitly as (machine-checked) documentation,
-just as it is nice to give a type signature for a function. On some occasions,
-it is essential to do so. For example, in his paper "Restricted Data Types in Haskell" (Haskell Workshop 1999)
-John Hughes had to define the data type:
-<Screen>
- data Set cxt a = Set [a]
- | Unused (cxt a -> ())
-</Screen>
-The only use for the <literal>Unused</literal> constructor was to force the correct
-kind for the type variable <literal>cxt</literal>.
-</para>
-<para>
-GHC now instead allows you to specify the kind of a type variable directly, wherever
-a type variable is explicitly bound. Namely:
+Type synonmys are like macros at the type level, and
+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:
<itemizedlist>
-<listitem><para><literal>data</literal> declarations:
-<Screen>
- data Set (cxt :: * -> *) a = Set [a]
-</Screen></para></listitem>
-<listitem><para><literal>type</literal> declarations:
-<Screen>
- type T (f :: * -> *) = f Int
-</Screen></para></listitem>
-<listitem><para><literal>class</literal> declarations:
-<Screen>
- class (Eq a) => C (f :: * -> *) a where ...
-</Screen></para></listitem>
-<listitem><para><literal>forall</literal>'s in type signatures:
-<Screen>
- f :: forall (cxt :: * -> *). Set cxt Int
-</Screen></para></listitem>
-</itemizedlist>
-</para>
+<listitem> <para>You can write a <literal>forall</literal> (including overloading)
+in a type synonym, thus:
+<programlisting>
+ type Discard a = forall b. Show b => a -> b -> (a, String)
-<para>
-The parentheses are required. Some of the spaces are required too, to
-separate the lexemes. If you write <literal>(f::*->*)</literal> you
-will get a parse error, because "<literal>::*->*</literal>" is a
-single lexeme in Haskell.
-</para>
+ f :: Discard a
+ f x y = (x, show y)
-<para>
-As part of the same extension, you can put kind annotations in types
-as well. Thus:
-<Screen>
- f :: (Int :: *) -> Int
- g :: forall a. a -> (a :: *)
-</Screen>
-The syntax is
-<Screen>
- atype ::= '(' ctype '::' kind ')
-</Screen>
-The parentheses are required.
+ g :: Discard Int -> (Int,Bool) -- A rank-2 type
+ g f = f Int True
+</programlisting>
</para>
-</sect2>
+</listitem>
+<listitem><para>
+You can write an unboxed tuple in a type synonym:
+<programlisting>
+ type Pr = (# Int, Int #)
-<sect2 id="class-method-types">
-<title>Class method types
-</title>
-<para>
-Haskell 98 prohibits class method types to mention constraints on the
-class type variable, thus:
+ h :: Int -> Pr
+ h x = (# x, x #)
+</programlisting>
+</para></listitem>
+
+<listitem><para>
+You can apply a type synonym to a forall type:
<programlisting>
- class Seq s a where
- fromList :: [a] -> s a
- elem :: Eq a => a -> s a -> Bool
+ type Foo a = a -> a -> Bool
+
+ f :: Foo (forall b. b->b)
</programlisting>
-The type of <literal>elem</literal> is illegal in Haskell 98, because it
-contains the constraint <literal>Eq a</literal>, constrains only the
-class type variable (in this case <literal>a</literal>).
+After expanding the synonym, <literal>f</literal> has the legal (in GHC) type:
+<programlisting>
+ f :: (forall b. b->b) -> (forall b. b->b) -> Bool
+</programlisting>
+</para></listitem>
+
+<listitem><para>
+You can apply a type synonym to a partially applied type synonym:
+<programlisting>
+ type Generic i o = forall x. i x -> o x
+ type Id x = x
+
+ foo :: Generic Id []
+</programlisting>
+After epxanding the synonym, <literal>foo</literal> has the legal (in GHC) type:
+<programlisting>
+ foo :: forall x. x -> [x]
+</programlisting>
+</para></listitem>
+
+</itemizedlist>
</para>
+
<para>
-With the <option>-fglasgow-exts</option> GHC lifts this restriction.
+GHC currently does kind checking before expanding synonyms (though even that
+could be changed.)
</para>
+<para>
+After expanding type synonyms, GHC does validity checking on types, looking for
+the following mal-formedness which isn't detected simply by kind checking:
+<itemizedlist>
+<listitem><para>
+Type constructor applied to a type involving for-alls.
+</para></listitem>
+<listitem><para>
+Unboxed tuple on left of an arrow.
+</para></listitem>
+<listitem><para>
+Partially-applied type synonym.
+</para></listitem>
+</itemizedlist>
+So, for example,
+this will be rejected:
+<programlisting>
+ type Pr = (# Int, Int #)
-</sect2>
+ h :: Pr -> Int
+ h x = ...
+</programlisting>
+because GHC does not allow unboxed tuples on the left of a function arrow.
+</para>
+</sect3>
-<sect2 id="multi-param-type-classes">
-<title>Multi-parameter type classes
+
+<sect3 id="existential-quantification">
+<title>Existentially quantified data constructors
</title>
<para>
-This section documents GHC's implementation of multi-parameter type
-classes. There's lots of background in the paper <ULink
-URL="http://research.microsoft.com/~simonpj/multi.ps.gz" >Type
-classes: exploring the design space</ULink > (Simon Peyton Jones, Mark
-Jones, Erik Meijer).
+The idea of using existential quantification in data type declarations
+was suggested by Laufer (I believe, thought doubtless someone will
+correct me), and implemented in Hope+. It's been in Lennart
+Augustsson's <command>hbc</command> Haskell compiler for several years, and
+proved very useful. Here's the idea. Consider the declaration:
</para>
-
-<sect3 id="type-restrictions">
-<title>Types</title>
-
<para>
-GHC imposes the following restrictions on the form of a qualified
-type, whether declared in a type signature
-or inferred. Consider the type:
<programlisting>
- forall tv1..tvn (c1, ...,cn) => type
+ data Foo = forall a. MkFoo a (a -> Bool)
+ | Nil
</programlisting>
-(Here, I write the "foralls" explicitly, although the Haskell source
-language omits them; in Haskell 1.4, all the free type variables of an
-explicit source-language type signature are universally quantified,
-except for the class type variables in a class declaration. However,
-in GHC, you can give the foralls if you want. See <xref LinkEnd="universal-quantification">).
</para>
<para>
-
-<OrderedList>
-<listitem>
+The data type <literal>Foo</literal> has two constructors with types:
+</para>
<para>
- <emphasis>Each universally quantified type variable
-<literal>tvi</literal> must be reachable from <literal>type</literal></emphasis>.
-
-A type variable is "reachable" if it it is functionally dependent
-(see <xref linkend="functional-dependencies">)
-on the type variables free in <literal>type</literal>.
-The reason for this is that a value with a type that does not obey
-this restriction could not be used without introducing
-ambiguity.
-Here, for example, is an illegal type:
-
<programlisting>
- forall a. Eq a => Int
+ MkFoo :: forall a. a -> (a -> Bool) -> Foo
+ Nil :: Foo
</programlisting>
-
-When a value with this type was used, the constraint <literal>Eq tv</literal>
-would be introduced where <literal>tv</literal> is a fresh type variable, and
-(in the dictionary-translation implementation) the value would be
-applied to a dictionary for <literal>Eq tv</literal>. The difficulty is that we
-can never know which instance of <literal>Eq</literal> to use because we never
-get any more information about <literal>tv</literal>.
-
</para>
-</listitem>
-<listitem>
<para>
- <emphasis>Every constraint <literal>ci</literal> must mention at least one of the
-universally quantified type variables <literal>tvi</literal></emphasis>.
-
-For example, this type is OK because <literal>C a b</literal> mentions the
-universally quantified type variable <literal>b</literal>:
+Notice that the type variable <literal>a</literal> in the type of <function>MkFoo</function>
+does not appear in the data type itself, which is plain <literal>Foo</literal>.
+For example, the following expression is fine:
+</para>
+<para>
<programlisting>
- forall a. C a b => burble
+ [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]
</programlisting>
+</para>
-The next type is illegal because the constraint <literal>Eq b</literal> does not
-mention <literal>a</literal>:
+<para>
+Here, <literal>(MkFoo 3 even)</literal> packages an integer with a function
+<function>even</function> that maps an integer to <literal>Bool</literal>; and <function>MkFoo 'c'
+isUpper</function> packages a character with a compatible function. These
+two things are each of type <literal>Foo</literal> and can be put in a list.
+</para>
+
+<para>
+What can we do with a value of type <literal>Foo</literal>?. In particular,
+what happens when we pattern-match on <function>MkFoo</function>?
+</para>
+<para>
<programlisting>
- forall a. Eq b => burble
+ f (MkFoo val fn) = ???
</programlisting>
-
-The reason for this restriction is milder than the other one. The
-excluded types are never useful or necessary (because the offending
-context doesn't need to be witnessed at this point; it can be floated
-out). Furthermore, floating them out increases sharing. Lastly,
-excluding them is a conservative choice; it leaves a patch of
-territory free in case we need it later.
-
-</para>
-</listitem>
-
-</OrderedList>
-
</para>
-
<para>
-Unlike Haskell 1.4, constraints in types do <emphasis>not</emphasis> have to be of
-the form <emphasis>(class type-variables)</emphasis>. Thus, these type signatures
-are perfectly OK
+Since all we know about <literal>val</literal> and <function>fn</function> is that they
+are compatible, the only (useful) thing we can do with them is to
+apply <function>fn</function> to <literal>val</literal> to get a boolean. For example:
</para>
<para>
<programlisting>
- f :: Eq (m a) => [m a] -> [m a]
- g :: Eq [a] => ...
+ f :: Foo -> Bool
+ f (MkFoo val fn) = fn val
</programlisting>
</para>
<para>
-This choice recovers principal types, a property that Haskell 1.4 does not have.
+What this allows us to do is to package heterogenous values
+together with a bunch of functions that manipulate them, and then treat
+that collection of packages in a uniform manner. You can express
+quite a bit of object-oriented-like programming this way.
</para>
-</sect3>
-
-<sect3>
-<title>Class declarations</title>
+<sect4 id="existential">
+<title>Why existential?
+</title>
<para>
+What has this to do with <emphasis>existential</emphasis> quantification?
+Simply that <function>MkFoo</function> has the (nearly) isomorphic type
+</para>
+
+<para>
+
+<programlisting>
+ MkFoo :: (exists a . (a, a -> Bool)) -> Foo
+</programlisting>
+
+</para>
+
+<para>
+But Haskell programmers can safely think of the ordinary
+<emphasis>universally</emphasis> quantified type given above, thereby avoiding
+adding a new existential quantification construct.
+</para>
+
+</sect4>
+
+<sect4>
+<title>Type classes</title>
+
+<para>
+An easy extension (implemented in <command>hbc</command>) is to allow
+arbitrary contexts before the constructor. For example:
+</para>
+
+<para>
+
+<programlisting>
+data Baz = forall a. Eq a => Baz1 a a
+ | forall b. Show b => Baz2 b (b -> b)
+</programlisting>
+
+</para>
+
+<para>
+The two constructors have the types you'd expect:
+</para>
+
+<para>
+
+<programlisting>
+Baz1 :: forall a. Eq a => a -> a -> Baz
+Baz2 :: forall b. Show b => b -> (b -> b) -> Baz
+</programlisting>
+
+</para>
+
+<para>
+But when pattern matching on <function>Baz1</function> the matched values can be compared
+for equality, and when pattern matching on <function>Baz2</function> the first matched
+value can be converted to a string (as well as applying the function to it).
+So this program is legal:
+</para>
+
+<para>
+
+<programlisting>
+ f :: Baz -> String
+ f (Baz1 p q) | p == q = "Yes"
+ | otherwise = "No"
+ f (Baz2 v fn) = show (fn v)
+</programlisting>
+
+</para>
+
+<para>
+Operationally, in a dictionary-passing implementation, the
+constructors <function>Baz1</function> and <function>Baz2</function> must store the
+dictionaries for <literal>Eq</literal> and <literal>Show</literal> respectively, and
+extract it on pattern matching.
+</para>
+
+<para>
+Notice the way that the syntax fits smoothly with that used for
+universal quantification earlier.
+</para>
+
+</sect4>
+
+<sect4>
+<title>Restrictions</title>
+
+<para>
+There are several restrictions on the ways in which existentially-quantified
+constructors can be use.
+</para>
+
+<para>
+
+<itemizedlist>
+<listitem>
+
+<para>
+ When pattern matching, each pattern match introduces a new,
+distinct, type for each existential type variable. These types cannot
+be unified with any other type, nor can they escape from the scope of
+the pattern match. For example, these fragments are incorrect:
+
+
+<programlisting>
+f1 (MkFoo a f) = a
+</programlisting>
+
+
+Here, the type bound by <function>MkFoo</function> "escapes", because <literal>a</literal>
+is the result of <function>f1</function>. One way to see why this is wrong is to
+ask what type <function>f1</function> has:
+
+
+<programlisting>
+ f1 :: Foo -> a -- Weird!
+</programlisting>
+
+
+What is this "<literal>a</literal>" in the result type? Clearly we don't mean
+this:
+
+
+<programlisting>
+ f1 :: forall a. Foo -> a -- Wrong!
+</programlisting>
+
+
+The original program is just plain wrong. Here's another sort of error
+
+
+<programlisting>
+ f2 (Baz1 a b) (Baz1 p q) = a==q
+</programlisting>
+
-<OrderedList>
+It's ok to say <literal>a==b</literal> or <literal>p==q</literal>, but
+<literal>a==q</literal> is wrong because it equates the two distinct types arising
+from the two <function>Baz1</function> constructors.
+
+
+</para>
+</listitem>
+<listitem>
+
+<para>
+You can't pattern-match on an existentially quantified
+constructor in a <literal>let</literal> or <literal>where</literal> group of
+bindings. So this is illegal:
+
+
+<programlisting>
+ f3 x = a==b where { Baz1 a b = x }
+</programlisting>
+
+Instead, use a <literal>case</literal> expression:
+
+<programlisting>
+ f3 x = case x of Baz1 a b -> a==b
+</programlisting>
+
+In general, you can only pattern-match
+on an existentially-quantified constructor in a <literal>case</literal> expression or
+in the patterns of a function definition.
+
+The reason for this restriction is really an implementation one.
+Type-checking binding groups is already a nightmare without
+existentials complicating the picture. Also an existential pattern
+binding at the top level of a module doesn't make sense, because it's
+not clear how to prevent the existentially-quantified type "escaping".
+So for now, there's a simple-to-state restriction. We'll see how
+annoying it is.
+
+</para>
+</listitem>
+<listitem>
+
+<para>
+You can't use existential quantification for <literal>newtype</literal>
+declarations. So this is illegal:
+
+
+<programlisting>
+ newtype T = forall a. Ord a => MkT a
+</programlisting>
+
+
+Reason: a value of type <literal>T</literal> must be represented as a
+pair of a dictionary for <literal>Ord t</literal> and a value of type
+<literal>t</literal>. That contradicts the idea that
+<literal>newtype</literal> should have no concrete representation.
+You can get just the same efficiency and effect by using
+<literal>data</literal> instead of <literal>newtype</literal>. If
+there is no overloading involved, then there is more of a case for
+allowing an existentially-quantified <literal>newtype</literal>,
+because the <literal>data</literal> version does carry an
+implementation cost, but single-field existentially quantified
+constructors aren't much use. So the simple restriction (no
+existential stuff on <literal>newtype</literal>) stands, unless there
+are convincing reasons to change it.
+
+
+</para>
+</listitem>
+<listitem>
+
+<para>
+ You can't use <literal>deriving</literal> to define instances of a
+data type with existentially quantified data constructors.
+
+Reason: in most cases it would not make sense. For example:#
+
+<programlisting>
+data T = forall a. MkT [a] deriving( Eq )
+</programlisting>
+
+To derive <literal>Eq</literal> in the standard way we would need to have equality
+between the single component of two <function>MkT</function> constructors:
+
+<programlisting>
+instance Eq T where
+ (MkT a) == (MkT b) = ???
+</programlisting>
+
+But <varname>a</varname> and <varname>b</varname> have distinct types, and so can't be compared.
+It's just about possible to imagine examples in which the derived instance
+would make sense, but it seems altogether simpler simply to prohibit such
+declarations. Define your own instances!
+</para>
+</listitem>
+
+</itemizedlist>
+
+</para>
+
+</sect4>
+</sect3>
+
+</sect2>
+
+
+
+<sect2 id="multi-param-type-classes">
+<title>Class declarations</title>
+
+<para>
+This section documents GHC's implementation of multi-parameter type
+classes. There's lots of background in the paper <ulink
+URL="http://research.microsoft.com/~simonpj/multi.ps.gz" >Type
+classes: exploring the design space</ulink > (Simon Peyton Jones, Mark
+Jones, Erik Meijer).
+</para>
+<para>
+There are the following constraints on class declarations:
+<orderedlist>
<listitem>
<para>
<para>
<emphasis>All of the class type variables must be reachable (in the sense
-mentioned in <xref linkend="type-restrictions">)
+mentioned in <xref linkend="type-restrictions"/>)
from the free varibles of each method type
</emphasis>. For example:
</para>
</listitem>
-</OrderedList>
+</orderedlist>
+</para>
+<sect3 id="class-method-types">
+<title>Class method types</title>
+<para>
+Haskell 98 prohibits class method types to mention constraints on the
+class type variable, thus:
+<programlisting>
+ class Seq s a where
+ fromList :: [a] -> s a
+ elem :: Eq a => a -> s a -> Bool
+</programlisting>
+The type of <literal>elem</literal> is illegal in Haskell 98, because it
+contains the constraint <literal>Eq a</literal>, constrains only the
+class type variable (in this case <literal>a</literal>).
+</para>
+<para>
+With the <option>-fglasgow-exts</option> GHC lifts this restriction.
</para>
</sect3>
-<sect3 id="instance-decls">
-<title>Instance declarations</title>
-
-<para>
+</sect2>
-<OrderedList>
-<listitem>
+<sect2 id="type-restrictions">
+<title>Type signatures</title>
+<sect3><title>The context of a type signature</title>
<para>
- <emphasis>Instance declarations may not overlap</emphasis>. The two instance
-declarations
-
-
+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,
+these type signatures are perfectly OK
<programlisting>
- instance context1 => C type1 where ...
- instance context2 => C type2 where ...
+ g :: Eq [a] => ...
+ g :: Ord (T a ()) => ...
</programlisting>
+</para>
+<para>
+GHC imposes the following restrictions on the constraints in a type signature.
+Consider the type:
+<programlisting>
+ forall tv1..tvn (c1, ...,cn) => type
+</programlisting>
+
+(Here, we write the "foralls" explicitly, although the Haskell source
+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"/>).
+</para>
+
+<para>
+
+<orderedlist>
+<listitem>
+
+<para>
+ <emphasis>Each universally quantified type variable
+<literal>tvi</literal> must be reachable from <literal>type</literal></emphasis>.
+
+A type variable <literal>a</literal> is "reachable" if it it appears
+in the same constraint as either a type variable free in in
+<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:
+
+
+<programlisting>
+ forall a. Eq a => Int
+</programlisting>
+
+
+When a value with this type was used, the constraint <literal>Eq tv</literal>
+would be introduced where <literal>tv</literal> is a fresh type variable, and
+(in the dictionary-translation implementation) the value would be
+applied to a dictionary for <literal>Eq tv</literal>. The difficulty is that we
+can never know which instance of <literal>Eq</literal> to use because we never
+get any more information about <literal>tv</literal>.
+</para>
+<para>
+Note
+that the reachability condition is weaker than saying that <literal>a</literal> is
+functionally dependendent on a type variable free in
+<literal>type</literal> (see <xref
+linkend="functional-dependencies"/>). The reason for this is there
+might be a "hidden" dependency, in a superclass perhaps. So
+"reachable" is a conservative approximation to "functionally dependent".
+For example, consider:
+<programlisting>
+ class C a b | a -> b where ...
+ class C a b => D a b where ...
+ f :: forall a b. D a b => a -> a
+</programlisting>
+This is fine, because in fact <literal>a</literal> does functionally determine <literal>b</literal>
+but that is not immediately apparent from <literal>f</literal>'s type.
+</para>
+</listitem>
+<listitem>
+
+<para>
+ <emphasis>Every constraint <literal>ci</literal> must mention at least one of the
+universally quantified type variables <literal>tvi</literal></emphasis>.
+
+For example, this type is OK because <literal>C a b</literal> mentions the
+universally quantified type variable <literal>b</literal>:
+
+
+<programlisting>
+ forall a. C a b => burble
+</programlisting>
+
+
+The next type is illegal because the constraint <literal>Eq b</literal> does not
+mention <literal>a</literal>:
+
+
+<programlisting>
+ forall a. Eq b => burble
+</programlisting>
+
+
+The reason for this restriction is milder than the other one. The
+excluded types are never useful or necessary (because the offending
+context doesn't need to be witnessed at this point; it can be floated
+out). Furthermore, floating them out increases sharing. Lastly,
+excluding them is a conservative choice; it leaves a patch of
+territory free in case we need it later.
+
+</para>
+</listitem>
+
+</orderedlist>
+
+</para>
+</sect3>
+
+<sect3 id="hoist">
+<title>For-all hoisting</title>
+<para>
+It is often convenient to use generalised type synonyms (see <xref linkend="type-synonyms"/>) at the right hand
+end of an arrow, thus:
+<programlisting>
+ type Discard a = forall b. a -> b -> a
+
+ g :: Int -> Discard Int
+ g x y z = x+y
+</programlisting>
+Simply expanding the type synonym would give
+<programlisting>
+ g :: Int -> (forall b. Int -> b -> Int)
+</programlisting>
+but GHC "hoists" the <literal>forall</literal> to give the isomorphic type
+<programlisting>
+ g :: forall b. Int -> Int -> b -> Int
+</programlisting>
+In general, the rule is this: <emphasis>to determine the type specified by any explicit
+user-written type (e.g. in a type signature), GHC expands type synonyms and then repeatedly
+performs the transformation:</emphasis>
+<programlisting>
+ <emphasis>type1</emphasis> -> forall a1..an. <emphasis>context2</emphasis> => <emphasis>type2</emphasis>
+==>
+ forall a1..an. <emphasis>context2</emphasis> => <emphasis>type1</emphasis> -> <emphasis>type2</emphasis>
+</programlisting>
+(In fact, GHC tries to retain as much synonym information as possible for use in
+error messages, but that is a usability issue.) This rule applies, of course, whether
+or not the <literal>forall</literal> comes from a synonym. For example, here is another
+valid way to write <literal>g</literal>'s type signature:
+<programlisting>
+ g :: Int -> Int -> forall b. b -> Int
+</programlisting>
+</para>
+<para>
+When doing this hoisting operation, GHC eliminates duplicate constraints. For
+example:
+<programlisting>
+ type Foo a = (?x::Int) => Bool -> a
+ g :: Foo (Foo Int)
+</programlisting>
+means
+<programlisting>
+ g :: (?x::Int) => Bool -> Bool -> Int
+</programlisting>
+</para>
+</sect3>
+
+
+</sect2>
+
+<sect2 id="instance-decls">
+<title>Instance declarations</title>
+
+<sect3>
+<title>Overlapping instances</title>
+<para>
+In general, <emphasis>instance declarations may not overlap</emphasis>. The two instance
+declarations
-"overlap" if <literal>type1</literal> and <literal>type2</literal> unify
+<programlisting>
+ instance context1 => C type1 where ...
+ instance context2 => C type2 where ...
+</programlisting>
+
+"overlap" if <literal>type1</literal> and <literal>type2</literal> unify.
+</para>
+<para>
However, if you give the command line option
<option>-fallow-overlapping-instances</option><indexterm><primary>-fallow-overlapping-instances
option</primary></indexterm> then overlapping instance declarations are permitted.
to look at ones that can't possibly be of use in the module currently
being compiled, in the interests of efficiency. (Perhaps we should
change that decision, at least for <literal>Main</literal>.)
-
</para>
-</listitem>
-<listitem>
-
-<para>
- <emphasis>There are no restrictions on the type in an instance
-<emphasis>head</emphasis>, except that at least one must not be a type variable</emphasis>.
-The instance "head" is the bit after the "=>" in an instance decl. For
-example, these are OK:
-
-
-<programlisting>
- instance C Int a where ...
-
- instance D (Int, Int) where ...
-
- instance E [[a]] where ...
-</programlisting>
-
-
-Note that instance heads <emphasis>may</emphasis> contain repeated type variables.
-For example, this is OK:
-
-
-<programlisting>
- instance Stateful (ST s) (MutVar s) where ...
-</programlisting>
+</sect3>
-See <xref linkend="undecidable-instances"> for an experimental
-extension to lift this restriction.
-</para>
-</listitem>
-<listitem>
+<sect3>
+<title>Type synonyms in the instance head</title>
<para>
- <emphasis>Unlike Haskell 1.4, instance heads may use type
-synonyms</emphasis>. As always, using a type synonym is just shorthand for
+<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:
reversed, but it makes sense to me.
</para>
-</listitem>
-<listitem>
+</sect3>
-<para>
-<emphasis>The types in an instance-declaration <emphasis>context</emphasis> must all
-be type variables</emphasis>. Thus
+<sect3 id="undecidable-instances">
+<title>Undecidable instances</title>
+<para>An instance declaration must normally obey the following rules:
+<orderedlist>
+<listitem><para>At least one of the types in the <emphasis>head</emphasis> of
+an instance declaration <emphasis>must not</emphasis> be a type variable.
+For example, these are OK:
<programlisting>
-instance C a b => Eq (a,b) where ...
-</programlisting>
-
-
-is OK, but
+ instance C Int a where ...
+ instance D (Int, Int) where ...
+ instance E [[a]] where ...
+</programlisting>
+but this is not:
<programlisting>
-instance C Int b => Foo b where ...
+ instance F a where ...
+</programlisting>
+Note that instance heads <emphasis>may</emphasis> contain repeated type variables.
+For example, this is OK:
+<programlisting>
+ instance Stateful (ST s) (MutVar s) where ...
</programlisting>
-
-
-is not OK. See <xref linkend="undecidable-instances"> for an experimental
-extension to lift this restriction.
-
-
-
</para>
</listitem>
-</OrderedList>
-</para>
-
-</sect3>
-
-</sect2>
-
-<sect2 id="undecidable-instances">
-<title>Undecidable instances</title>
-
-<para>The rules for instance declarations state that:
-<itemizedlist>
-<listitem><para>At least one of the types in the <emphasis>head</emphasis> of
-an instance declaration <emphasis>must not</emphasis> be a type variable.
-</para></listitem>
-<listitem><para>All of the types in the <emphasis>context</emphasis> of
+<listitem>
+<para>All of the types in the <emphasis>context</emphasis> of
an instance declaration <emphasis>must</emphasis> be type variables.
-</para></listitem>
-</itemizedlist>
+Thus
+<programlisting>
+instance C a b => Eq (a,b) where ...
+</programlisting>
+is OK, but
+<programlisting>
+instance C Int b => Foo b where ...
+</programlisting>
+is not OK.
+</para>
+</listitem>
+</orderedlist>
These restrictions ensure that
context reduction terminates: each reduction step removes one type
constructor. For example, the following would make the type checker
I'm on the lookout for a less brutal solution: a simple rule that preserves decidability while
allowing these idioms interesting idioms.
</para>
+</sect3>
+
+
</sect2>
<sect2 id="implicit-parameters">
-<title>Implicit parameters
-</title>
+<title>Implicit parameters</title>
<para> Implicit paramters are implemented as described in
"Implicit parameters: dynamic scoping with static types",
27th ACM Symposium on Principles of Programming Languages (POPL'00),
Boston, Jan 2000.
</para>
-<para>(Most of the following, stil rather incomplete, documentation is due to Jeff Lewis.)</para>
+
+<para>(Most of the following, stil rather incomplete, documentation is
+due to Jeff Lewis.)</para>
+
+<para>Implicit parameter support is enabled with the option
+<option>-fimplicit-params</option>.</para>
+
<para>
A variable is called <emphasis>dynamically bound</emphasis> when it is bound by the calling
context of a function and <emphasis>statically bound</emphasis> when bound by the callee's
<literal>cmp</literal>.
<programlisting>
min :: [a] -> a
- min = let ?cmp = (<=) in least
+ min = let ?cmp = (<=) in least
</programlisting>
</para>
<para>
</sect2>
<sect2 id="linear-implicit-parameters">
-<title>Linear implicit parameters
-</title>
+<title>Linear implicit parameters</title>
<para>
Linear implicit parameters are an idea developed by Koen Claessen,
Mark Shields, and Simon PJ. They address the long-standing
</sect2>
-<sect2 id="universal-quantification">
-<title>Arbitrary-rank polymorphism
-</title>
+
+<sect2 id="sec-kinding">
+<title>Explicitly-kinded quantification</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.
+Haskell infers the kind of each type variable. Sometimes it is nice to be able
+to give the kind explicitly as (machine-checked) documentation,
+just as it is nice to give a type signature for a function. On some occasions,
+it is essential to do so. For example, in his paper "Restricted Data Types in Haskell" (Haskell Workshop 1999)
+John Hughes had to define the data type:
+<screen>
+ data Set cxt a = Set [a]
+ | Unused (cxt a -> ())
+</screen>
+The only use for the <literal>Unused</literal> constructor was to force the correct
+kind for the type variable <literal>cxt</literal>.
</para>
-
<para>
-However, GHC's type system supports <emphasis>arbitrary-rank</emphasis>
-explicit universal quantification in
+GHC now instead allows you to specify the kind of a type variable directly, wherever
+a type variable is explicitly bound. Namely:
+<itemizedlist>
+<listitem><para><literal>data</literal> declarations:
+<screen>
+ data Set (cxt :: * -> *) a = Set [a]
+</screen></para></listitem>
+<listitem><para><literal>type</literal> declarations:
+<screen>
+ type T (f :: * -> *) = f Int
+</screen></para></listitem>
+<listitem><para><literal>class</literal> declarations:
+<screen>
+ class (Eq a) => C (f :: * -> *) a where ...
+</screen></para></listitem>
+<listitem><para><literal>forall</literal>'s in type signatures:
+<screen>
+ f :: forall (cxt :: * -> *). Set cxt Int
+</screen></para></listitem>
+</itemizedlist>
+</para>
+
+<para>
+The parentheses are required. Some of the spaces are required too, to
+separate the lexemes. If you write <literal>(f::*->*)</literal> you
+will get a parse error, because "<literal>::*->*</literal>" is a
+single lexeme in Haskell.
+</para>
+
+<para>
+As part of the same extension, you can put kind annotations in types
+as well. Thus:
+<screen>
+ f :: (Int :: *) -> Int
+ g :: forall a. a -> (a :: *)
+</screen>
+The syntax is
+<screen>
+ atype ::= '(' ctype '::' kind ')
+</screen>
+The parentheses are required.
+</para>
+</sect2>
+
+
+<sect2 id="universal-quantification">
+<title>Arbitrary-rank polymorphism
+</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>
+explicit universal quantification in
types.
For example, all the following types are legal:
<programlisting>
shows, the polymorphic type on the left of the function arrow can be overloaded.
</para>
<para>
-The functions <literal>f3</literal> and <literal>g3</literal> have rank-3 types;
-they have rank-2 types on the left of a function arrow.
+The function <literal>f3</literal> has a rank-3 type;
+it has rank-2 types on the left of a function arrow.
</para>
<para>
GHC allows types of arbitrary rank; you can nest <literal>forall</literal>s
including an operational type class context, is legal:
<itemizedlist>
<listitem> <para> On the left of a function arrow </para> </listitem>
-<listitem> <para> On the right of a function arrow (see <xref linkend="hoist">) </para> </listitem>
+<listitem> <para> On the right of a function arrow (see <xref linkend="hoist"/>) </para> </listitem>
<listitem> <para> As the argument of a constructor, or type of a field, in a data type declaration. For
-example, any of the <literal>f1,f2,f3,g1,g2,g3</literal> above would be valid
+example, any of the <literal>f1,f2,f3,g1,g2</literal> above would be valid
field type signatures.</para> </listitem>
<listitem> <para> As the type of an implicit parameter </para> </listitem>
-<listitem> <para> In a pattern type signature (see <xref linkend="scoped-type-variables">) </para> </listitem>
+<listitem> <para> In a pattern type signature (see <xref linkend="scoped-type-variables"/>) </para> </listitem>
</itemizedlist>
There is one place you cannot put a <literal>forall</literal>:
you cannot instantiate a type variable with a forall-type. So you cannot
types too. So if you write this:
<programlisting>
- data T a = MkT (Either a b) (b -> b)
-</programlisting>
-
-it's just as if you had written this:
-
-<programlisting>
- data T a = MkT (forall b. Either a b) (forall b. b -> b)
-</programlisting>
-
-That is, since the type variable <literal>b</literal> isn't in scope, it's
-implicitly universally quantified. (Arguably, it would be better
-to <emphasis>require</emphasis> explicit quantification on constructor arguments
-where that is what is wanted. Feedback welcomed.)
-</para>
-
-<para>
-You construct values of types <literal>T1, MonadT, Swizzle</literal> by applying
-the constructor to suitable values, just as usual. For example,
-</para>
-
-<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
- Just y -> k y
- Nothing -> Nothing
- in
- MkMonad r b
-
- mkTs :: (forall b. b -> b -> b) -> a -> [T a]
- mkTs f x y = [T1 f x, T1 f y]
-</programlisting>
-
-</para>
-
-<para>
-The type of the argument can, as usual, be more general than the type
-required, as <literal>(MkSwizzle reverse)</literal> shows. (<function>reverse</function>
-does not need the <literal>Ord</literal> constraint.)
-</para>
-
-<para>
-When you use pattern matching, the bound variables may now have
-polymorphic types. For example:
-</para>
-
-<para>
-
-<programlisting>
- f :: T a -> a -> (a, Char)
- f (T1 w k) x = (w k x, w 'c' 'd')
-
- g :: (Ord a, Ord b) => Swizzle -> [a] -> (a -> b) -> [b]
- g (MkSwizzle s) xs f = s (map f (s xs))
-
- h :: MonadT m -> [m a] -> m [a]
- h m [] = return m []
- h m (x:xs) = bind m x $ \y ->
- bind m (h m xs) $ \ys ->
- return m (y:ys)
-</programlisting>
-
-</para>
-
-<para>
-In the function <function>h</function> we use the record selectors <literal>return</literal>
-and <literal>bind</literal> to extract the polymorphic bind and return functions
-from the <literal>MonadT</literal> data structure, rather than using pattern
-matching.
-</para>
-</sect3>
-
-<sect3>
-<title>Type inference</title>
-
-<para>
-In general, type inference for arbitrary-rank types is undecideable.
-GHC uses an algorithm proposed by Odersky and Laufer ("Putting type annotations to work", POPL'96)
-to get a decidable algorithm by requiring some help from the programmer.
-We do not yet have a formal specification of "some help" but the rule is this:
-</para>
-<para>
-<emphasis>For a lambda-bound or case-bound variable, x, either the programmer
-provides an explicit polymorphic type for x, or GHC's type inference will assume
-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
-giving a type signature for x directly, using a pattern type signature
-(<xref linkend="scoped-type-variables">), thus:
-<programlisting>
- \ f :: (forall a. a->a) -> (f True, f 'c')
-</programlisting>
-Alternatively, you can give a type signature to the enclosing
-context, which GHC can "push down" to find the type for the variable:
-<programlisting>
- (\ f -> (f True, f 'c')) :: (forall a. a->a) -> (Bool,Char)
-</programlisting>
-Here the type signature on the expression can be pushed inwards
-to give a type signature for f. Similarly, and more commonly,
-one can give a type signature for the function itself:
-<programlisting>
- h :: (forall a. a->a) -> (Bool,Char)
- h f = (f True, f 'c')
-</programlisting>
-You don't need to give a type signature if the lambda bound variable
-is a constructor argument. Here is an example we saw earlier:
-<programlisting>
- f :: T a -> a -> (a, Char)
- f (T1 w k) x = (w k x, w 'c' 'd')
-</programlisting>
-Here we do not need to give a type signature to <literal>w</literal>, because
-it is an argument of constructor <literal>T1</literal> and that tells GHC all
-it needs to know.
-</para>
-
-</sect3>
-
-
-<sect3 id="implicit-quant">
-<title>Implicit quantification</title>
-
-<para>
-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
-equivalent:
-<programlisting>
- f :: a -> a
- f :: forall a. a -> a
-
- g (x::a) = let
- h :: a -> b -> b
- h x y = y
- in ...
- g (x::a) = let
- h :: forall b. a -> b -> b
- h x y = y
- in ...
-</programlisting>
-</para>
-<para>
-Notice that GHC does <emphasis>not</emphasis> find the innermost possible quantification
-point. For example:
-<programlisting>
- f :: (a -> a) -> Int
- -- MEANS
- f :: forall a. (a -> a) -> Int
- -- NOT
- f :: (forall a. a -> a) -> Int
-
-
- g :: (Ord a => a -> a) -> Int
- -- MEANS the illegal type
- g :: forall a. (Ord a => a -> a) -> Int
- -- NOT
- g :: (forall a. Ord a => a -> a) -> Int
-</programlisting>
-The latter produces an illegal type, which you might think is silly,
-but at least the rule is simple. If you want the latter type, you
-can write your for-alls explicitly. Indeed, doing so is strongly advised
-for rank-2 types.
-</para>
-</sect3>
-</sect2>
-
-<sect2 id="type-synonyms">
-<title>Liberalised type synonyms
-</title>
-
-<para>
-Type synonmys are like macros at the type level, and
-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:
-<itemizedlist>
-<listitem> <para>You can write a <literal>forall</literal> (including overloading)
-in a type synonym, thus:
-<programlisting>
- type Discard a = forall b. Show b => a -> b -> (a, String)
-
- f :: Discard a
- f x y = (x, show y)
-
- g :: Discard Int -> (Int,Bool) -- A rank-2 type
- g f = f Int True
-</programlisting>
-</para>
-</listitem>
-
-<listitem><para>
-You can write an unboxed tuple in a type synonym:
-<programlisting>
- type Pr = (# Int, Int #)
-
- h :: Int -> Pr
- h x = (# x, x #)
-</programlisting>
-</para></listitem>
-
-<listitem><para>
-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>
- f :: (forall b. b->b) -> (forall b. b->b) -> Bool
-</programlisting>
-</para></listitem>
-
-<listitem><para>
-You can apply a type synonym to a partially applied type synonym:
-<programlisting>
- type Generic i o = forall x. i x -> o x
- type Id x = x
-
- foo :: Generic Id []
-</programlisting>
-After epxanding the synonym, <literal>foo</literal> has the legal (in GHC) type:
-<programlisting>
- foo :: forall x. x -> [x]
-</programlisting>
-</para></listitem>
-
-</itemizedlist>
-</para>
-
-<para>
-GHC currently does kind checking before expanding synonyms (though even that
-could be changed.)
-</para>
-<para>
-After expanding type synonyms, GHC does validity checking on types, looking for
-the following mal-formedness which isn't detected simply by kind checking:
-<itemizedlist>
-<listitem><para>
-Type constructor applied to a type involving for-alls.
-</para></listitem>
-<listitem><para>
-Unboxed tuple on left of an arrow.
-</para></listitem>
-<listitem><para>
-Partially-applied type synonym.
-</para></listitem>
-</itemizedlist>
-So, for example,
-this will be rejected:
-<programlisting>
- type Pr = (# Int, Int #)
-
- h :: Pr -> Int
- h x = ...
-</programlisting>
-because GHC does not allow unboxed tuples on the left of a function arrow.
-</para>
-</sect2>
-
-<sect2 id="hoist">
-<title>For-all hoisting</title>
-<para>
-It is often convenient to use generalised type synonyms at the right hand
-end of an arrow, thus:
-<programlisting>
- type Discard a = forall b. a -> b -> a
-
- g :: Int -> Discard Int
- g x y z = x+y
-</programlisting>
-Simply expanding the type synonym would give
-<programlisting>
- g :: Int -> (forall b. Int -> b -> Int)
-</programlisting>
-but GHC "hoists" the <literal>forall</literal> to give the isomorphic type
-<programlisting>
- g :: forall b. Int -> Int -> b -> Int
-</programlisting>
-In general, the rule is this: <emphasis>to determine the type specified by any explicit
-user-written type (e.g. in a type signature), GHC expands type synonyms and then repeatedly
-performs the transformation:</emphasis>
-<programlisting>
- <emphasis>type1</emphasis> -> forall a1..an. <emphasis>context2</emphasis> => <emphasis>type2</emphasis>
-==>
- forall a1..an. <emphasis>context2</emphasis> => <emphasis>type1</emphasis> -> <emphasis>type2</emphasis>
-</programlisting>
-(In fact, GHC tries to retain as much synonym information as possible for use in
-error messages, but that is a usability issue.) This rule applies, of course, whether
-or not the <literal>forall</literal> comes from a synonym. For example, here is another
-valid way to write <literal>g</literal>'s type signature:
-<programlisting>
- g :: Int -> Int -> forall b. b -> Int
-</programlisting>
-</para>
-<para>
-When doing this hoisting operation, GHC eliminates duplicate constraints. For
-example:
-<programlisting>
- type Foo a = (?x::Int) => Bool -> a
- g :: Foo (Foo Int)
-</programlisting>
-means
-<programlisting>
- g :: (?x::Int) => Bool -> Bool -> Int
-</programlisting>
-</para>
-</sect2>
-
-
-<sect2 id="existential-quantification">
-<title>Existentially quantified data constructors
-</title>
-
-<para>
-The idea of using existential quantification in data type declarations
-was suggested by Laufer (I believe, thought doubtless someone will
-correct me), and implemented in Hope+. It's been in Lennart
-Augustsson's <Command>hbc</Command> Haskell compiler for several years, and
-proved very useful. Here's the idea. Consider the declaration:
-</para>
-
-<para>
-
-<programlisting>
- data Foo = forall a. MkFoo a (a -> Bool)
- | Nil
-</programlisting>
-
-</para>
-
-<para>
-The data type <literal>Foo</literal> has two constructors with types:
-</para>
-
-<para>
-
-<programlisting>
- MkFoo :: forall a. a -> (a -> Bool) -> Foo
- Nil :: Foo
-</programlisting>
-
-</para>
-
-<para>
-Notice that the type variable <literal>a</literal> in the type of <function>MkFoo</function>
-does not appear in the data type itself, which is plain <literal>Foo</literal>.
-For example, the following expression is fine:
-</para>
-
-<para>
-
-<programlisting>
- [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]
-</programlisting>
-
-</para>
-
-<para>
-Here, <literal>(MkFoo 3 even)</literal> packages an integer with a function
-<function>even</function> that maps an integer to <literal>Bool</literal>; and <function>MkFoo 'c'
-isUpper</function> packages a character with a compatible function. These
-two things are each of type <literal>Foo</literal> and can be put in a list.
-</para>
-
-<para>
-What can we do with a value of type <literal>Foo</literal>?. In particular,
-what happens when we pattern-match on <function>MkFoo</function>?
-</para>
-
-<para>
-
-<programlisting>
- f (MkFoo val fn) = ???
-</programlisting>
-
-</para>
-
-<para>
-Since all we know about <literal>val</literal> and <function>fn</function> is that they
-are compatible, the only (useful) thing we can do with them is to
-apply <function>fn</function> to <literal>val</literal> to get a boolean. For example:
-</para>
-
-<para>
-
-<programlisting>
- f :: Foo -> Bool
- f (MkFoo val fn) = fn val
-</programlisting>
-
-</para>
-
-<para>
-What this allows us to do is to package heterogenous values
-together with a bunch of functions that manipulate them, and then treat
-that collection of packages in a uniform manner. You can express
-quite a bit of object-oriented-like programming this way.
-</para>
-
-<sect3 id="existential">
-<title>Why existential?
-</title>
-
-<para>
-What has this to do with <emphasis>existential</emphasis> quantification?
-Simply that <function>MkFoo</function> has the (nearly) isomorphic type
-</para>
-
-<para>
-
-<programlisting>
- MkFoo :: (exists a . (a, a -> Bool)) -> Foo
-</programlisting>
-
-</para>
-
-<para>
-But Haskell programmers can safely think of the ordinary
-<emphasis>universally</emphasis> quantified type given above, thereby avoiding
-adding a new existential quantification construct.
-</para>
-
-</sect3>
-
-<sect3>
-<title>Type classes</title>
-
-<para>
-An easy extension (implemented in <Command>hbc</Command>) is to allow
-arbitrary contexts before the constructor. For example:
-</para>
-
-<para>
-
-<programlisting>
-data Baz = forall a. Eq a => Baz1 a a
- | forall b. Show b => Baz2 b (b -> b)
-</programlisting>
-
-</para>
-
-<para>
-The two constructors have the types you'd expect:
-</para>
-
-<para>
-
-<programlisting>
-Baz1 :: forall a. Eq a => a -> a -> Baz
-Baz2 :: forall b. Show b => b -> (b -> b) -> Baz
-</programlisting>
-
-</para>
-
-<para>
-But when pattern matching on <function>Baz1</function> the matched values can be compared
-for equality, and when pattern matching on <function>Baz2</function> the first matched
-value can be converted to a string (as well as applying the function to it).
-So this program is legal:
-</para>
-
-<para>
-
-<programlisting>
- f :: Baz -> String
- f (Baz1 p q) | p == q = "Yes"
- | otherwise = "No"
- f (Baz2 v fn) = show (fn v)
-</programlisting>
-
-</para>
-
-<para>
-Operationally, in a dictionary-passing implementation, the
-constructors <function>Baz1</function> and <function>Baz2</function> must store the
-dictionaries for <literal>Eq</literal> and <literal>Show</literal> respectively, and
-extract it on pattern matching.
-</para>
-
-<para>
-Notice the way that the syntax fits smoothly with that used for
-universal quantification earlier.
-</para>
-
-</sect3>
-
-<sect3>
-<title>Restrictions</title>
-
-<para>
-There are several restrictions on the ways in which existentially-quantified
-constructors can be use.
-</para>
-
-<para>
-
-<itemizedlist>
-<listitem>
-
-<para>
- When pattern matching, each pattern match introduces a new,
-distinct, type for each existential type variable. These types cannot
-be unified with any other type, nor can they escape from the scope of
-the pattern match. For example, these fragments are incorrect:
-
-
-<programlisting>
-f1 (MkFoo a f) = a
-</programlisting>
-
-
-Here, the type bound by <function>MkFoo</function> "escapes", because <literal>a</literal>
-is the result of <function>f1</function>. One way to see why this is wrong is to
-ask what type <function>f1</function> has:
-
-
-<programlisting>
- f1 :: Foo -> a -- Weird!
-</programlisting>
-
-
-What is this "<literal>a</literal>" in the result type? Clearly we don't mean
-this:
-
-
-<programlisting>
- f1 :: forall a. Foo -> a -- Wrong!
-</programlisting>
-
-
-The original program is just plain wrong. Here's another sort of error
-
-
-<programlisting>
- f2 (Baz1 a b) (Baz1 p q) = a==q
+ data T a = MkT (Either a b) (b -> b)
</programlisting>
+it's just as if you had written this:
-It's ok to say <literal>a==b</literal> or <literal>p==q</literal>, but
-<literal>a==q</literal> is wrong because it equates the two distinct types arising
-from the two <function>Baz1</function> constructors.
-
+<programlisting>
+ data T a = MkT (forall b. Either a b) (forall b. b -> b)
+</programlisting>
+That is, since the type variable <literal>b</literal> isn't in scope, it's
+implicitly universally quantified. (Arguably, it would be better
+to <emphasis>require</emphasis> explicit quantification on constructor arguments
+where that is what is wanted. Feedback welcomed.)
</para>
-</listitem>
-<listitem>
<para>
-You can't pattern-match on an existentially quantified
-constructor in a <literal>let</literal> or <literal>where</literal> group of
-bindings. So this is illegal:
+You construct values of types <literal>T1, MonadT, Swizzle</literal> by applying
+the constructor to suitable values, just as usual. For example,
+</para>
+<para>
<programlisting>
- f3 x = a==b where { Baz1 a b = x }
-</programlisting>
-
-Instead, use a <literal>case</literal> expression:
+ 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
+ Just y -> k y
+ Nothing -> Nothing
+ in
+ MkMonad r b
-<programlisting>
- f3 x = case x of Baz1 a b -> a==b
+ mkTs :: (forall b. b -> b -> b) -> a -> [T a]
+ mkTs f x y = [T1 f x, T1 f y]
</programlisting>
-In general, you can only pattern-match
-on an existentially-quantified constructor in a <literal>case</literal> expression or
-in the patterns of a function definition.
-
-The reason for this restriction is really an implementation one.
-Type-checking binding groups is already a nightmare without
-existentials complicating the picture. Also an existential pattern
-binding at the top level of a module doesn't make sense, because it's
-not clear how to prevent the existentially-quantified type "escaping".
-So for now, there's a simple-to-state restriction. We'll see how
-annoying it is.
+</para>
+<para>
+The type of the argument can, as usual, be more general than the type
+required, as <literal>(MkSwizzle reverse)</literal> shows. (<function>reverse</function>
+does not need the <literal>Ord</literal> constraint.)
</para>
-</listitem>
-<listitem>
<para>
-You can't use existential quantification for <literal>newtype</literal>
-declarations. So this is illegal:
+When you use pattern matching, the bound variables may now have
+polymorphic types. For example:
+</para>
+<para>
<programlisting>
- newtype T = forall a. Ord a => MkT a
-</programlisting>
-
+ f :: T a -> a -> (a, Char)
+ f (T1 w k) x = (w k x, w 'c' 'd')
-Reason: a value of type <literal>T</literal> must be represented as a pair
-of a dictionary for <literal>Ord t</literal> and a value of type <literal>t</literal>.
-That contradicts the idea that <literal>newtype</literal> should have no
-concrete representation. You can get just the same efficiency and effect
-by using <literal>data</literal> instead of <literal>newtype</literal>. If there is no
-overloading involved, then there is more of a case for allowing
-an existentially-quantified <literal>newtype</literal>, because the <literal>data</literal>
-because the <literal>data</literal> version does carry an implementation cost,
-but single-field existentially quantified constructors aren't much
-use. So the simple restriction (no existential stuff on <literal>newtype</literal>)
-stands, unless there are convincing reasons to change it.
+ g :: (Ord a, Ord b) => Swizzle -> [a] -> (a -> b) -> [b]
+ g (MkSwizzle s) xs f = s (map f (s xs))
+ h :: MonadT m -> [m a] -> m [a]
+ h m [] = return m []
+ h m (x:xs) = bind m x $ \y ->
+ bind m (h m xs) $ \ys ->
+ return m (y:ys)
+</programlisting>
</para>
-</listitem>
-<listitem>
<para>
- You can't use <literal>deriving</literal> to define instances of a
-data type with existentially quantified data constructors.
+In the function <function>h</function> we use the record selectors <literal>return</literal>
+and <literal>bind</literal> to extract the polymorphic bind and return functions
+from the <literal>MonadT</literal> data structure, rather than using pattern
+matching.
+</para>
+</sect3>
-Reason: in most cases it would not make sense. For example:#
+<sect3>
+<title>Type inference</title>
+<para>
+In general, type inference for arbitrary-rank types is undecideable.
+GHC uses an algorithm proposed by Odersky and Laufer ("Putting type annotations to work", POPL'96)
+to get a decidable algorithm by requiring some help from the programmer.
+We do not yet have a formal specification of "some help" but the rule is this:
+</para>
+<para>
+<emphasis>For a lambda-bound or case-bound variable, x, either the programmer
+provides an explicit polymorphic type for x, or GHC's type inference will assume
+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
+giving a type signature for x directly, using a pattern type signature
+(<xref linkend="scoped-type-variables"/>), thus:
<programlisting>
-data T = forall a. MkT [a] deriving( Eq )
+ \ f :: (forall a. a->a) -> (f True, f 'c')
+</programlisting>
+Alternatively, you can give a type signature to the enclosing
+context, which GHC can "push down" to find the type for the variable:
+<programlisting>
+ (\ f -> (f True, f 'c')) :: (forall a. a->a) -> (Bool,Char)
+</programlisting>
+Here the type signature on the expression can be pushed inwards
+to give a type signature for f. Similarly, and more commonly,
+one can give a type signature for the function itself:
+<programlisting>
+ h :: (forall a. a->a) -> (Bool,Char)
+ h f = (f True, f 'c')
+</programlisting>
+You don't need to give a type signature if the lambda bound variable
+is a constructor argument. Here is an example we saw earlier:
+<programlisting>
+ f :: T a -> a -> (a, Char)
+ f (T1 w k) x = (w k x, w 'c' 'd')
</programlisting>
+Here we do not need to give a type signature to <literal>w</literal>, because
+it is an argument of constructor <literal>T1</literal> and that tells GHC all
+it needs to know.
+</para>
-To derive <literal>Eq</literal> in the standard way we would need to have equality
-between the single component of two <function>MkT</function> constructors:
+</sect3>
+
+<sect3 id="implicit-quant">
+<title>Implicit quantification</title>
+
+<para>
+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
+equivalent:
<programlisting>
-instance Eq T where
- (MkT a) == (MkT b) = ???
-</programlisting>
+ f :: a -> a
+ f :: forall a. a -> a
-But <VarName>a</VarName> and <VarName>b</VarName> have distinct types, and so can't be compared.
-It's just about possible to imagine examples in which the derived instance
-would make sense, but it seems altogether simpler simply to prohibit such
-declarations. Define your own instances!
+ g (x::a) = let
+ h :: a -> b -> b
+ h x y = y
+ in ...
+ g (x::a) = let
+ h :: forall b. a -> b -> b
+ h x y = y
+ in ...
+</programlisting>
</para>
-</listitem>
+<para>
+Notice that GHC does <emphasis>not</emphasis> find the innermost possible quantification
+point. For example:
+<programlisting>
+ f :: (a -> a) -> Int
+ -- MEANS
+ f :: forall a. (a -> a) -> Int
+ -- NOT
+ f :: (forall a. a -> a) -> Int
-</itemizedlist>
+ g :: (Ord a => a -> a) -> Int
+ -- MEANS the illegal type
+ g :: forall a. (Ord a => a -> a) -> Int
+ -- NOT
+ g :: (forall a. Ord a => a -> a) -> Int
+</programlisting>
+The latter produces an illegal type, which you might think is silly,
+but at least the rule is simple. If you want the latter type, you
+can write your for-alls explicitly. Indeed, doing so is strongly advised
+for rank-2 types.
</para>
-
</sect3>
-
</sect2>
+
+
+
<sect2 id="scoped-type-variables">
<title>Scoped type variables
</title>
</para>
<para>
-The pattern <literal>(xs::[a])</literal> includes a type signature for <VarName>xs</VarName>.
+The pattern <literal>(xs::[a])</literal> includes a type signature for <varname>xs</varname>.
This brings the type variable <literal>a</literal> into scope; it scopes over
all the patterns and right hand sides for this equation for <function>f</function>.
-In particular, it is in scope at the type signature for <VarName>y</VarName>.
+In particular, it is in scope at the type signature for <varname>y</varname>.
</para>
<para>
Pattern type signatures are completely orthogonal to ordinary, separate
type signatures. The two can be used independently or together.
-At ordinary type signatures, such as that for <VarName>ys</VarName>, any type variables
+At ordinary type signatures, such as that for <varname>ys</varname>, any type variables
mentioned in the type signature <emphasis>that are not in scope</emphasis> are
implicitly universally quantified. (If there are no type variables in
scope, all type variables mentioned in the signature are universally
-quantified, which is just as in Haskell 98.) In this case, since <VarName>a</VarName>
-is in scope, it is not universally quantified, so the type of <VarName>ys</VarName> is
-the same as that of <VarName>xs</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
+quantified, which is just as in Haskell 98.) In this case, since <varname>a</varname>
+is in scope, it is not universally quantified, so the type of <varname>ys</varname> is
+the same as that of <varname>xs</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.
</para>
as the term variable(s) bound by the pattern. For example:
<programlisting>
let
- f (x::a) = <...rhs of f...>
+ f (x::a) = <...rhs of f...>
(p::b, q::b) = (1,2)
- in <...body of let...>
+ in <...body of let...>
</programlisting>
Here, the type variable <literal>a</literal> scopes over the right hand side of <literal>f</literal>,
just like <literal>x</literal> does; while the type variable <literal>b</literal> scopes over the
f x = x::a
</programlisting>
-It's illegal because <VarName>a</VarName> is not in scope in the body of <function>f</function>,
+It's illegal because <varname>a</varname> is not in scope in the body of <function>f</function>,
so the ordinary signature <literal>x::a</literal> is equivalent to <literal>x::forall a.a</literal>;
and that is an incorrect typing.
</sect2>
+<sect2 id="deriving-typeable">
+<title>Deriving clause for classes <literal>Typeable</literal> and <literal>Data</literal></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.
+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>,
+<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>-fglasgow-exts</option> flag is specified):
+<literal>Typeable</literal>, and <literal>Data</literal>. These classes are defined in the library
+modules <literal>Data.Dynamic</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.
+</para>
+</sect2>
+
<sect2 id="newtype-deriving">
<title>Generalised derived instances for newtypes</title>
<literal>S</literal> is a type constructor,
</para></listitem>
<listitem><para>
- <literal>t1...tk</literal> are types,
+ The <literal>t1...tk</literal> are types,
</para></listitem>
<listitem><para>
- <literal>vk+1...vn</literal> are type variables which do not occur in any of
+ The <literal>vk+1...vn</literal> are type variables which do not occur in any of
the <literal>ti</literal>, and
</para></listitem>
<listitem><para>
- the <literal>ci</literal> are partial applications of
+ The <literal>ci</literal> are partial applications of
classes of the form <literal>C t1'...tj'</literal>, where the arity of <literal>C</literal>
is exactly <literal>j+1</literal>. That is, <literal>C</literal> lacks exactly one type argument.
</para></listitem>
+<listitem><para>
+ 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.
+</para></listitem>
</itemizedlist>
Then, for each <literal>ci</literal>, the derived instance
declaration is:
the main technical innovations is discussed in "<ulink
url="http://research.microsoft.com/~simonpj/papers/meta-haskell">
Template Meta-programming for Haskell</ulink>" (Proc Haskell Workshop 2002).
+The details of the Template Haskell design are still in flux. Make sure you
+consult the <ulink url="http://www.haskell.org/ghc/docs/latest/html/libraries/index.html">online library reference material</ulink>
+(search for the type ExpQ).
+[Temporary: many changes to the original design are described in
+ <ulink url="http://research.microsoft.com/~simonpj/tmp/notes2.ps">"http://research.microsoft.com/~simonpj/tmp/notes2.ps"</ulink>.
+Not all of these changes are in GHC 6.2.]
</para>
<para> The first example from that paper is set out below as a worked example to help get you started.
Tim Sheard is going to expand it.)
</para>
-<sect2> <title> Syntax </title>
-<para>
- Template Haskell has the following new syntactic constructions. You need to use the flag
- <literal>-fglasgow-exts</literal> to switch these syntactic extensions on.
+ <sect2>
+ <title>Syntax</title>
+
+ <para> Template Haskell has the following new syntactic
+ constructions. You need to use the flag
+ <option>-fth</option><indexterm><primary><option>-fth</option></primary>
+ </indexterm>to switch these syntactic extensions on
+ (<option>-fth</option> is currently implied by
+ <option>-fglasgow-exts</option>, but you are encouraged to
+ specify it explicitly).</para>
<itemizedlist>
<listitem><para>
</itemizedlist>
-</para>
</sect2>
<sect2> <title> Using Template Haskell </title>
First cut and paste the two modules below into "Main.hs" and "Printf.hs":</para>
<programlisting>
+
{- Main.hs -}
module Main where
-- generated at compile time by "pr" and splices it into
-- the argument of "putStrLn".
main = putStrLn ( $(pr "Hello") )
-</programlisting>
-<programlisting>
+
{- Printf.hs -}
module Printf where
-- you intend to use it.
-- Import some Template Haskell syntax
-import Language.Haskell.THSyntax
+import Language.Haskell.TH.Syntax
-- Describe a format string
data Format = D | S | L String
-- Generate Haskell source code from a parsed representation
-- of the format string. This code will be spliced into
-- the module which calls "pr", at compile time.
-gen :: [Format] -> Expr
+gen :: [Format] -> ExpQ
gen [D] = [| \n -> show n |]
gen [S] = [| \s -> s |]
-gen [L s] = string s
+gen [L s] = stringE s
-- Here we generate the Haskell code for the splice
-- from an input format string.
-pr :: String -> Expr
+pr :: String -> ExpQ
pr s = gen (parse s)
</programlisting>
-<para>Now run the compiler (here we are using a "stage three" build of GHC, at a Cygwin prompt on Windows):
+<para>Now run the compiler (here we are a Cygwin prompt on Windows):
</para>
<programlisting>
-ghc/compiler/stage3/ghc-inplace --make -fglasgow-exts -package haskell-src main.hs -o main.exe
+$ ghc --make -fth main.hs -o main.exe
</programlisting>
-<para>Run "main.exe" and here is your output:
-</para>
+<para>Run "main.exe" and here is your output:</para>
<programlisting>
$ ./main
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="../base/Control.Arrow.html"><literal>Control.Arrow</literal></ulink>
+<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,
-of the form <literal>proc pat -> cmd</literal>,
+<para>The extension adds a new kind of expression for defining arrows:
+<screen>
+<replaceable>exp</replaceable><superscript>10</superscript> ::= ...
+ | 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
<literal>proc</literal>-expression,
which is a new sort of thing called a <firstterm>command</firstterm>.
The syntax of commands is as follows:
<screen>
-cmd ::= exp1 -< exp2
- | exp1 -<< exp2
- | do { cstmt1 .. cstmtn ; cmd }
- | let decls in cmd
- | if exp then cmd1 else cmd2
- | case exp of { calts }
- | cmd1 qop cmd2
- | (| aexp cmd1 .. cmdn |)
- | \ pat1 .. patn -> cmd
- | cmd aexp
- | ( cmd )
-
-cstmt ::= let decls
- | pat <- cmd
- | rec { cstmt1 .. cstmtn }
- | cmd
+<replaceable>cmd</replaceable> ::= <replaceable>exp</replaceable><superscript>10</superscript> -< <replaceable>exp</replaceable>
+ | <replaceable>exp</replaceable><superscript>10</superscript> -<< <replaceable>exp</replaceable>
+ | <replaceable>cmd</replaceable><superscript>0</superscript>
+</screen>
+with <replaceable>cmd</replaceable><superscript>0</superscript> up to
+<replaceable>cmd</replaceable><superscript>9</superscript> defined using
+infix operators as for expressions, and
+<screen>
+<replaceable>cmd</replaceable><superscript>10</superscript> ::= \ <replaceable>apat</replaceable> ... <replaceable>apat</replaceable> -> <replaceable>cmd</replaceable>
+ | let <replaceable>decls</replaceable> in <replaceable>cmd</replaceable>
+ | if <replaceable>exp</replaceable> then <replaceable>cmd</replaceable> else <replaceable>cmd</replaceable>
+ | case <replaceable>exp</replaceable> of { <replaceable>calts</replaceable> }
+ | do { <replaceable>cstmt</replaceable> ; ... <replaceable>cstmt</replaceable> ; <replaceable>cmd</replaceable> }
+ | <replaceable>fcmd</replaceable>
+
+<replaceable>fcmd</replaceable> ::= <replaceable>fcmd</replaceable> <replaceable>aexp</replaceable>
+ | ( <replaceable>cmd</replaceable> )
+ | (| <replaceable>aexp</replaceable> <replaceable>cmd</replaceable> ... <replaceable>cmd</replaceable> |)
+
+<replaceable>cstmt</replaceable> ::= let <replaceable>decls</replaceable>
+ | <replaceable>pat</replaceable> <- <replaceable>cmd</replaceable>
+ | rec { <replaceable>cstmt</replaceable> ; ... <replaceable>cstmt</replaceable> [;] }
+ | <replaceable>cmd</replaceable>
</screen>
+where <replaceable>calts</replaceable> are like <replaceable>alts</replaceable>
+except that the bodies are commands instead of expressions.
+</para>
+
+<para>
Commands produce values, but (like monadic computations)
may yield more than one value,
or none, and may do other things as well.
returnA
</screen>
Note that variables not used later in the composition are projected out.
-After simplification using rewrite rules (see <xref linkEnd="rewrite-rules">)
+After simplification using rewrite rules (see <xref linkend="rewrite-rules"/>)
defined in the
<ulink url="../base/Control.Arrow.html"><literal>Control.Arrow</literal></ulink>
module, this reduces to
</programlisting>
so we can use it to build commands:
<programlisting>
-expr' = proc x ->
+expr' = proc x -> do
returnA -< x
<+> do
symbol Plus -< ()
y <- term -< ()
expr' -< x - y
</programlisting>
+(The <literal>do</literal> on the first line is needed to prevent the first
+<literal><+> ...</literal> from being interpreted as part of the
+expression on the previous line.)
This is equivalent to
<programlisting>
expr' = (proc x -> returnA -< x)
For example, we could simulate <literal>do</literal>-notation by defining
<programlisting>
bind :: Arrow a => a e b -> a (e,b) c -> a e c
-u `bind` f = returnA &&& u >>> f
+u `bind` f = returnA &&& u >>> f
bind_ :: Arrow a => a e b -> a e c -> a e c
u `bind_` f = u `bind` (arr fst >>> f)
Although only GHC implements arrow notation directly,
there is also a preprocessor
(available from the
-<ulink url="http://www.haskell.org/arrows/">arrows web page></ulink>)
+<ulink url="http://www.haskell.org/arrows/">arrows web page</ulink>)
that translates arrow notation into Haskell 98
for use with other Haskell systems.
You would still want to check arrow programs with GHC;
<para>The DEPRECATED pragma lets you specify that a particular
function, class, or type, is deprecated. There are two
- forms.</para>
+ forms.
<itemizedlist>
<listitem>
message.</para>
</listitem>
</itemizedlist>
-
+ Any use of the deprecated item, or of anything from a deprecated
+ module, will be flagged with an appropriate message. However,
+ deprecations are not reported for
+ (a) uses of a deprecated function within its defining module, and
+ (b) uses of a deprecated function in an export list.
+ The latter reduces spurious complaints within a library
+ in which one module gathers together and re-exports
+ the exports of several others.
+ </para>
<para>You can suppress the warnings with the flag
<option>-fno-warn-deprecations</option>.</para>
</sect2>
</programlisting>
<para>See also the <literal>NOINLINE</literal> pragma (<xref
- linkend="noinline-pragma">).</para>
+ linkend="noinline-pragma"/>).</para>
</sect3>
<sect3 id="noinline-pragma">
</itemizedlist>
<para>The same phase-numbering control is available for RULES
- (<xref LinkEnd="rewrite-rules">).</para>
+ (<xref linkend="rewrite-rules"/>).</para>
</sect3>
</sect2>
<para>The <literal>OPTIONS</literal> pragma is used to specify
additional options that are given to the compiler when compiling
- this source file. See <xref linkend="source-file-options"> for
+ this source file. See <xref linkend="source-file-options"/> for
details.</para>
</sect2>
<title>RULES pragma</title>
<para>The RULES pragma lets you specify rewrite rules. It is
- described in <xref LinkEnd="rewrite-rules">.</para>
+ described in <xref linkend="rewrite-rules"/>.</para>
</sect2>
<sect2 id="specialize-pragma">
<para>A <literal>SPECIALIZE</literal> pragma for a function can
be put anywhere its type signature could be put.</para>
-<para>A <literal>SPECIALIZE</literal> has the effect of generating (a) a specialised
-version of the function and (b) a rewrite rule (see <xref linkend="rules">) that
-rewrites a call to the un-specialised function into a call to the specialised
-one. You can, instead, provide your own specialised function and your own rewrite rule.
-For example, suppose that:
-<programlisting>
- genericLookup :: Ord a => Table a b -> a -> b
- intLookup :: Table Int b -> Int -> b
-</programlisting>
-where <literal>intLookup</literal> is an implementation of <literal>genericLookup</literal>
-that works very fast for keys of type <literal>Int</literal>. Then you can write the rule
-<programlisting>
- {-# RULES "intLookup" genericLookup = intLookup #-}
-</programlisting>
-(see <xref linkend="rule-spec">). It is <emphasis>Your
- Responsibility</emphasis> to make sure that
- <function>intLookup</function> really behaves as a specialised
- version of <function>genericLookup</function>!!!</para>
+ <para>A <literal>SPECIALIZE</literal> has the effect of generating
+ (a) a specialised version of the function and (b) a rewrite rule
+ (see <xref linkend="rewrite-rules"/>) that rewrites a call to the
+ un-specialised function into a call to the specialised one.</para>
- <para>An example in which using <literal>RULES</literal> for
- specialisation will Win Big:
+ <para>In earlier versions of GHC, it was possible to provide your own
+ specialised function for a given type:
<programlisting>
- toDouble :: Real a => a -> Double
- toDouble = fromRational . toRational
-
- {-# RULES "toDouble/Int" toDouble = i2d #-}
- i2d (I# i) = D# (int2Double# i) -- uses Glasgow prim-op directly
+{-# SPECIALIZE hammeredLookup :: [(Int, value)] -> Int -> value = intLookup #-}
</programlisting>
- The <function>i2d</function> function is virtually one machine
- instruction; the default conversion—via an intermediate
- <literal>Rational</literal>—is obscenely expensive by
- comparison.</para>
+ This feature has been removed, as it is now subsumed by the
+ <literal>RULES</literal> pragma (see <xref linkend="rule-spec"/>).</para>
</sect2>
</sect2>
+ <sect2 id="unpack-pragma">
+ <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
+ example:</para>
+
+<programlisting>
+data T = T {-# UNPACK #-} !Float
+ {-# UNPACK #-} !Float
+</programlisting>
+
+ <para>will create a constructor <literal>T</literal> containing
+ two unboxed floats. This may not always be an optimisation: if
+ the <function>T</function> constructor is scrutinised and the
+ floats passed to a non-strict function for example, they will
+ have to be reboxed (this is done automatically by the
+ compiler).</para>
+
+ <para>Unpacking constructor fields should only be used in
+ conjunction with <option>-O</option>, in order to expose
+ unfoldings to the compiler so the reboxing can be removed as
+ often as possible. For example:</para>
+
+<programlisting>
+f :: T -> Float
+f (T f1 f2) = f1 + f2
+</programlisting>
+
+ <para>The compiler will avoid reboxing <function>f1</function>
+ and <function>f2</function> by inlining <function>+</function>
+ on floats, but only when <option>-O</option> is on.</para>
+
+ <para>Any single-constructor data is eligible for unpacking; for
+ example</para>
+
+<programlisting>
+data T = T {-# UNPACK #-} !(Int,Int)
+</programlisting>
+
+ <para>will store the two <literal>Int</literal>s directly in the
+ <function>T</function> constructor, by flattening the pair.
+ Multi-level unpacking is also supported:</para>
+
+<programlisting>
+data T = T {-# UNPACK #-} !S
+data S = S {-# UNPACK #-} !Int {-# UNPACK #-} !Int
+</programlisting>
+ <para>will store two unboxed <literal>Int#</literal>s
+ 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
+ constructor field.</para>
+ </sect2>
</sect1>
<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,
+the <option>-O</option> flag (<xref linkend="options-optimise"/>) is on,
and (b) the <option>-frules-off</option> flag
-(<xref LinkEnd="options-f">) is not specified.
+(<xref linkend="options-f"/>) is not specified.
</para>
<para>
<listitem>
<para>
-A rule may optionally have a phase-control number (see <xref LinkEnd="phase-control">),
+A rule may optionally have a phase-control number (see <xref linkend="phase-control"/>),
immediately after the name of the rule. Thus:
<programlisting>
{-# RULES
<para>
Matching is carried out on GHC's intermediate language, which includes
type abstractions and applications. So a rule only matches if the
-types match too. See <xref LinkEnd="rule-spec"> below.
+types match too. See <xref linkend="rule-spec"/> below.
</para>
</listitem>
<listitem>
</programlisting>
The expression <literal>s (t xs)</literal> does not match the rule <literal>"map/map"</literal>, but GHC
-will substitute for <VarName>s</VarName> and <VarName>t</VarName>, giving an expression which does match.
-If <VarName>s</VarName> or <VarName>t</VarName> was (a) used more than once, and (b) large or a redex, then it would
+will substitute for <varname>s</varname> and <varname>t</varname>, giving an expression which does match.
+If <varname>s</varname> or <varname>t</varname> was (a) used more than once, and (b) large or a redex, then it would
not be substituted, and the rule would not fire.
</para>
<para>
Rewrite rules can be used to get the same effect as a feature
-present in earlier version of GHC:
+present in earlier versions of GHC.
+For example, suppose that:
<programlisting>
- {-# SPECIALIZE fromIntegral :: Int8 -> Int16 = int8ToInt16 #-}
+genericLookup :: Ord a => Table a b -> a -> b
+intLookup :: Table Int b -> Int -> b
</programlisting>
-This told GHC to use <function>int8ToInt16</function> instead of <function>fromIntegral</function> whenever
-the latter was called with type <literal>Int8 -> Int16</literal>. That is, rather than
-specialising the original definition of <function>fromIntegral</function> the programmer is
-promising that it is safe to use <function>int8ToInt16</function> instead.
-</para>
-
-<para>
-This feature is no longer in GHC. But rewrite rules let you do the
-same thing:
+where <function>intLookup</function> is an implementation of
+<function>genericLookup</function> that works very fast for
+keys of type <literal>Int</literal>. You might wish
+to tell GHC to use <function>intLookup</function> instead of
+<function>genericLookup</function> whenever the latter was called with
+type <literal>Table Int b -> Int -> b</literal>.
+It used to be possible to write
<programlisting>
-{-# RULES
- "fromIntegral/Int8/Int16" fromIntegral = int8ToInt16
-#-}
+{-# SPECIALIZE genericLookup :: Table Int b -> Int -> b = intLookup #-}
</programlisting>
-This slightly odd-looking rule instructs GHC to replace <function>fromIntegral</function>
-by <function>int8ToInt16</function> <emphasis>whenever the types match</emphasis>. Speaking more operationally,
-GHC adds the type and dictionary applications to get the typed rule
+This feature is no longer in GHC, but rewrite rules let you do the same thing:
<programlisting>
-forall (d1::Integral Int8) (d2::Num Int16) .
- fromIntegral Int8 Int16 d1 d2 = int8ToInt16
+{-# RULES "genericLookup/Int" genericLookup = intLookup #-}
</programlisting>
-What is more,
-this rule does not need to be in the same file as fromIntegral,
-unlike the <literal>SPECIALISE</literal> pragmas which currently do (so that they
+This slightly odd-looking rule instructs GHC to replace
+<function>genericLookup</function> by <function>intLookup</function>
+<emphasis>whenever the types match</emphasis>.
+What is more, this rule does not need to be in the same
+file as <function>genericLookup</function>, unlike the
+<literal>SPECIALIZE</literal> pragmas which currently do (so that they
have an original definition available to specialise).
</para>
+<para>It is <emphasis>Your Responsibility</emphasis> to make sure that
+<function>intLookup</function> really behaves as a specialised version
+of <function>genericLookup</function>!!!</para>
+
+<para>An example in which using <literal>RULES</literal> for
+specialisation will Win Big:
+
+<programlisting>
+toDouble :: Real a => a -> Double
+toDouble = fromRational . toRational
+
+{-# RULES "toDouble/Int" toDouble = i2d #-}
+i2d (I# i) = D# (int2Double# i) -- uses Glasgow prim-op directly
+</programlisting>
+
+The <function>i2d</function> function is virtually one machine
+instruction; the default conversion—via an intermediate
+<literal>Rational</literal>—is obscenely expensive by
+comparison.
+</para>
+
</sect2>
<sect2>
<listitem>
<para>
- The defintion of (say) <function>build</function> in <FileName>GHC/Base.lhs</FileName> looks llike this:
+ The defintion of (say) <function>build</function> in <filename>GHC/Base.lhs</filename> looks llike this:
<programlisting>
build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
<para>
However, when external for is generated (via
<option>-fext-core</option>), there will be Notes attached to the
- expressions <function>show</function> and <VarName>x</VarName>.
+ expressions <function>show</function> and <varname>x</varname>.
The core function declaration for <function>f</function> is:
</para>
Here, we can see that the function <function>show</function> (which
has been expanded out to a case expression over the Show dictionary)
has a <literal>%note</literal> attached to it, as does the
- expression <VarName>eta</VarName> (which used to be called
- <VarName>x</VarName>).
+ expression <varname>eta</varname> (which used to be called
+ <varname>x</varname>).
</para>
</sect2>
;;; sgml-parent-document: ("users_guide.sgml" "book" "chapter" "sect1") ***
;;; End: ***
-->
+
projects / ghc-hetmet.git / blobdiff