View patterns, record wildcards, and record puns
[ghc-hetmet.git] / docs / users_guide / glasgow_exts.xml
1 <?xml version="1.0" encoding="iso-8859-1"?>
2 <para>
3 <indexterm><primary>language, GHC</primary></indexterm>
4 <indexterm><primary>extensions, GHC</primary></indexterm>
5 As with all known Haskell systems, GHC implements some extensions to
6 the language.  They are all enabled by options; by default GHC
7 understands only plain Haskell 98.
8 </para>
9
10 <para>
11 Some of the Glasgow extensions serve to give you access to the
12 underlying facilities with which we implement Haskell.  Thus, you can
13 get at the Raw Iron, if you are willing to write some non-portable
14 code at a more primitive level.  You need not be &ldquo;stuck&rdquo;
15 on performance because of the implementation costs of Haskell's
16 &ldquo;high-level&rdquo; features&mdash;you can always code
17 &ldquo;under&rdquo; them.  In an extreme case, you can write all your
18 time-critical code in C, and then just glue it together with Haskell!
19 </para>
20
21 <para>
22 Before you get too carried away working at the lowest level (e.g.,
23 sloshing <literal>MutableByteArray&num;</literal>s around your
24 program), you may wish to check if there are libraries that provide a
25 &ldquo;Haskellised veneer&rdquo; over the features you want.  The
26 separate <ulink url="../libraries/index.html">libraries
27 documentation</ulink> describes all the libraries that come with GHC.
28 </para>
29
30 <!-- LANGUAGE OPTIONS -->
31   <sect1 id="options-language">
32     <title>Language options</title>
33
34     <indexterm><primary>language</primary><secondary>option</secondary>
35     </indexterm>
36     <indexterm><primary>options</primary><secondary>language</secondary>
37     </indexterm>
38     <indexterm><primary>extensions</primary><secondary>options controlling</secondary>
39     </indexterm>
40
41     <para>The language option flag control what variation of the language are
42     permitted.  Leaving out all of them gives you standard Haskell
43     98.</para>
44
45     <para>Generally speaking, all the language options are introduced by "<option>-X</option>", 
46     e.g. <option>-XTemplateHaskell</option>.
47     </para>
48
49    <para> All the language options can be turned off by using the prefix "<option>No</option>"; 
50       e.g. "<option>-XNoTemplateHaskell</option>".</para>
51
52    <para> Language options recognised by Cabal can also be enabled using the <literal>LANGUAGE</literal> pragma,
53    thus <literal>{-# LANGUAGE TemplateHaskell #-}</literal> (see <xref linkend="language-pragma"/>>). </para>
54
55     <para>Turning on an option that enables special syntax
56     <emphasis>might</emphasis> cause working Haskell 98 code to fail
57     to compile, perhaps because it uses a variable name which has
58     become a reserved word.  So, together with each option below, we
59     list the special syntax which is enabled by this option.  We use
60     notation and nonterminal names from the Haskell 98 lexical syntax
61     (see the Haskell 98 Report).  There are two classes of special
62     syntax:</para>
63
64     <itemizedlist>
65       <listitem>
66         <para>New reserved words and symbols: character sequences
67         which are no longer available for use as identifiers in the
68         program.</para>
69       </listitem>
70       <listitem>
71         <para>Other special syntax: sequences of characters that have
72         a different meaning when this particular option is turned
73         on.</para>
74       </listitem>
75     </itemizedlist>
76
77     <para>We are only listing syntax changes here that might affect
78     existing working programs (i.e. "stolen" syntax).  Many of these
79     extensions will also enable new context-free syntax, but in all
80     cases programs written to use the new syntax would not be
81     compilable without the option enabled.</para>
82
83     <variablelist>
84
85       <varlistentry>
86         <term>
87           <option>-fglasgow-exts</option>:
88           <indexterm><primary><option>-fglasgow-exts</option></primary></indexterm>
89         </term>
90         <listitem>
91           <para>This simultaneously enables all of the extensions to
92           Haskell 98 described in <xref
93           linkend="ghc-language-features"/>, except where otherwise
94           noted. We are trying to move away from this portmanteau flag, 
95           and towards enabling features individaully.</para>
96
97           <para>New reserved words: <literal>forall</literal> (only in
98           types), <literal>mdo</literal>.</para>
99
100           <para>Other syntax stolen:
101               <replaceable>varid</replaceable>{<literal>&num;</literal>},
102               <replaceable>char</replaceable><literal>&num;</literal>,      
103               <replaceable>string</replaceable><literal>&num;</literal>,    
104               <replaceable>integer</replaceable><literal>&num;</literal>,    
105               <replaceable>float</replaceable><literal>&num;</literal>,    
106               <replaceable>float</replaceable><literal>&num;&num;</literal>,    
107               <literal>(&num;</literal>, <literal>&num;)</literal>,         
108               <literal>|)</literal>, <literal>{|</literal>.</para>
109
110           <para>Implies these specific language options: 
111             <option>-XForeignFunctionInterface</option>,
112             <option>-XImplicitParams</option>,
113             <option>-XScopedTypeVariables</option>,
114             <option>-XGADTs</option>, 
115             <option>-XTypeFamilies</option>. </para>
116         </listitem>
117       </varlistentry>
118
119       <varlistentry>
120         <term>
121           <option>-XForeignFunctionInterface</option>:
122           <indexterm><primary><option>-XForeignFunctionInterface</option></primary></indexterm>
123         </term>
124         <listitem>
125           <para>This option enables the language extension defined in the
126           Haskell 98 Foreign Function Interface Addendum.</para>
127
128           <para>New reserved words: <literal>foreign</literal>.</para>
129         </listitem>
130       </varlistentry>
131
132       <varlistentry>
133         <term>
134           <option>-XMonomorphismRestriction</option>,<option>-XMonoPatBinds</option>:
135         </term>
136         <listitem>
137           <para> These two flags control how generalisation is done.
138             See <xref linkend="monomorphism"/>.
139           </para>
140         </listitem>
141       </varlistentry>
142
143       <varlistentry>
144         <term>
145           <option>-XExtendedDefaultRules</option>:
146           <indexterm><primary><option>-XExtendedDefaultRules</option></primary></indexterm>
147         </term>
148         <listitem>
149           <para> Use GHCi's extended default rules in a regular module (<xref linkend="extended-default-rules"/>).
150           Independent of the <option>-fglasgow-exts</option>
151           flag. </para>
152         </listitem>
153       </varlistentry>
154
155       <varlistentry>
156         <term>
157           <option>-XOverlappingInstances</option>
158           <indexterm><primary><option>-XOverlappingInstances</option></primary></indexterm>
159         </term>
160         <term>
161           <option>-XUndecidableInstances</option>
162           <indexterm><primary><option>-XUndecidableInstances</option></primary></indexterm>
163         </term>
164         <term>
165           <option>-XIncoherentInstances</option>
166           <indexterm><primary><option>-XIncoherentInstances</option></primary></indexterm>
167         </term>
168         <term>
169           <option>-fcontext-stack=N</option>
170           <indexterm><primary><option>-fcontext-stack</option></primary></indexterm>
171         </term>
172         <listitem>
173           <para> See <xref linkend="instance-decls"/>.  Only relevant
174           if you also use <option>-fglasgow-exts</option>.</para>
175         </listitem>
176       </varlistentry>
177
178       <varlistentry>
179         <term>
180           <option>-finline-phase</option>
181           <indexterm><primary><option>-finline-phase</option></primary></indexterm>
182         </term>
183         <listitem>
184           <para>See <xref linkend="rewrite-rules"/>.  Only relevant if
185           you also use <option>-fglasgow-exts</option>.</para>
186         </listitem>
187       </varlistentry>
188
189       <varlistentry>
190         <term>
191           <option>-XArrows</option>
192           <indexterm><primary><option>-XArrows</option></primary></indexterm>
193         </term>
194         <listitem>
195           <para>See <xref linkend="arrow-notation"/>.  Independent of
196           <option>-fglasgow-exts</option>.</para>
197
198           <para>New reserved words/symbols: <literal>rec</literal>,
199           <literal>proc</literal>, <literal>-&lt;</literal>,
200           <literal>&gt;-</literal>, <literal>-&lt;&lt;</literal>,
201           <literal>&gt;&gt;-</literal>.</para>
202
203           <para>Other syntax stolen: <literal>(|</literal>,
204           <literal>|)</literal>.</para>
205         </listitem>
206       </varlistentry>
207
208       <varlistentry>
209         <term>
210           <option>-XGenerics</option>
211           <indexterm><primary><option>-XGenerics</option></primary></indexterm>
212         </term>
213         <listitem>
214           <para>See <xref linkend="generic-classes"/>.  Independent of
215           <option>-fglasgow-exts</option>.</para>
216         </listitem>
217       </varlistentry>
218
219       <varlistentry>
220         <term><option>-XNoImplicitPrelude</option></term>
221         <listitem>
222           <para><indexterm><primary>-XNoImplicitPrelude
223           option</primary></indexterm> GHC normally imports
224           <filename>Prelude.hi</filename> files for you.  If you'd
225           rather it didn't, then give it a
226           <option>-XNoImplicitPrelude</option> option.  The idea is
227           that you can then import a Prelude of your own.  (But don't
228           call it <literal>Prelude</literal>; the Haskell module
229           namespace is flat, and you must not conflict with any
230           Prelude module.)</para>
231
232           <para>Even though you have not imported the Prelude, most of
233           the built-in syntax still refers to the built-in Haskell
234           Prelude types and values, as specified by the Haskell
235           Report.  For example, the type <literal>[Int]</literal>
236           still means <literal>Prelude.[] Int</literal>; tuples
237           continue to refer to the standard Prelude tuples; the
238           translation for list comprehensions continues to use
239           <literal>Prelude.map</literal> etc.</para>
240
241           <para>However, <option>-XNoImplicitPrelude</option> does
242           change the handling of certain built-in syntax: see <xref
243           linkend="rebindable-syntax"/>.</para>
244         </listitem>
245       </varlistentry>
246
247       <varlistentry>
248         <term><option>-XImplicitParams</option></term>
249         <listitem>
250           <para>Enables implicit parameters (see <xref
251           linkend="implicit-parameters"/>).  Currently also implied by 
252           <option>-fglasgow-exts</option>.</para>
253
254           <para>Syntax stolen:
255           <literal>?<replaceable>varid</replaceable></literal>,
256           <literal>%<replaceable>varid</replaceable></literal>.</para>
257         </listitem>
258       </varlistentry>
259
260       <varlistentry>
261         <term><option>-XOverloadedStrings</option></term>
262         <listitem>
263           <para>Enables overloaded string literals (see <xref
264           linkend="overloaded-strings"/>).</para>
265         </listitem>
266       </varlistentry>
267
268       <varlistentry>
269         <term><option>-XScopedTypeVariables</option></term>
270         <listitem>
271           <para>Enables lexically-scoped type variables (see <xref
272           linkend="scoped-type-variables"/>).  Implied by
273           <option>-fglasgow-exts</option>.</para>
274         </listitem>
275       </varlistentry>
276
277       <varlistentry>
278         <term><option>-XTemplateHaskell</option></term>
279         <listitem>
280           <para>Enables Template Haskell (see <xref
281           linkend="template-haskell"/>).  This flag must
282           be given explicitly; it is no longer implied by
283           <option>-fglasgow-exts</option>.</para>
284
285           <para>Syntax stolen: <literal>[|</literal>,
286           <literal>[e|</literal>, <literal>[p|</literal>,
287           <literal>[d|</literal>, <literal>[t|</literal>,
288           <literal>$(</literal>,
289           <literal>$<replaceable>varid</replaceable></literal>.</para>
290         </listitem>
291       </varlistentry>
292
293     </variablelist>
294   </sect1>
295
296 <!-- UNBOXED TYPES AND PRIMITIVE OPERATIONS -->
297 <sect1 id="primitives">
298   <title>Unboxed types and primitive operations</title>
299
300 <para>GHC is built on a raft of primitive data types and operations.
301 While you really can use this stuff to write fast code,
302   we generally find it a lot less painful, and more satisfying in the
303   long run, to use higher-level language features and libraries.  With
304   any luck, the code you write will be optimised to the efficient
305   unboxed version in any case.  And if it isn't, we'd like to know
306   about it.</para>
307
308 <para>We do not currently have good, up-to-date documentation about the
309 primitives, perhaps because they are mainly intended for internal use.
310 There used to be a long section about them here in the User Guide, but it
311 became out of date, and wrong information is worse than none.</para>
312
313 <para>The Real Truth about what primitive types there are, and what operations
314 work over those types, is held in the file
315 <filename>fptools/ghc/compiler/prelude/primops.txt.pp</filename>.
316 This file is used directly to generate GHC's primitive-operation definitions, so
317 it is always correct!  It is also intended for processing into text.</para>
318
319 <para> Indeed,
320 the result of such processing is part of the description of the 
321  <ulink
322       url="http://haskell.cs.yale.edu/ghc/docs/papers/core.ps.gz">External
323          Core language</ulink>.
324 So that document is a good place to look for a type-set version.
325 We would be very happy if someone wanted to volunteer to produce an SGML
326 back end to the program that processes <filename>primops.txt</filename> so that
327 we could include the results here in the User Guide.</para>
328
329 <para>What follows here is a brief summary of some main points.</para>
330   
331 <sect2 id="glasgow-unboxed">
332 <title>Unboxed types
333 </title>
334
335 <para>
336 <indexterm><primary>Unboxed types (Glasgow extension)</primary></indexterm>
337 </para>
338
339 <para>Most types in GHC are <firstterm>boxed</firstterm>, which means
340 that values of that type are represented by a pointer to a heap
341 object.  The representation of a Haskell <literal>Int</literal>, for
342 example, is a two-word heap object.  An <firstterm>unboxed</firstterm>
343 type, however, is represented by the value itself, no pointers or heap
344 allocation are involved.
345 </para>
346
347 <para>
348 Unboxed types correspond to the &ldquo;raw machine&rdquo; types you
349 would use in C: <literal>Int&num;</literal> (long int),
350 <literal>Double&num;</literal> (double), <literal>Addr&num;</literal>
351 (void *), etc.  The <emphasis>primitive operations</emphasis>
352 (PrimOps) on these types are what you might expect; e.g.,
353 <literal>(+&num;)</literal> is addition on
354 <literal>Int&num;</literal>s, and is the machine-addition that we all
355 know and love&mdash;usually one instruction.
356 </para>
357
358 <para>
359 Primitive (unboxed) types cannot be defined in Haskell, and are
360 therefore built into the language and compiler.  Primitive types are
361 always unlifted; that is, a value of a primitive type cannot be
362 bottom.  We use the convention that primitive types, values, and
363 operations have a <literal>&num;</literal> suffix.
364 </para>
365
366 <para>
367 Primitive values are often represented by a simple bit-pattern, such
368 as <literal>Int&num;</literal>, <literal>Float&num;</literal>,
369 <literal>Double&num;</literal>.  But this is not necessarily the case:
370 a primitive value might be represented by a pointer to a
371 heap-allocated object.  Examples include
372 <literal>Array&num;</literal>, the type of primitive arrays.  A
373 primitive array is heap-allocated because it is too big a value to fit
374 in a register, and would be too expensive to copy around; in a sense,
375 it is accidental that it is represented by a pointer.  If a pointer
376 represents a primitive value, then it really does point to that value:
377 no unevaluated thunks, no indirections&hellip;nothing can be at the
378 other end of the pointer than the primitive value.
379 A numerically-intensive program using unboxed types can
380 go a <emphasis>lot</emphasis> faster than its &ldquo;standard&rdquo;
381 counterpart&mdash;we saw a threefold speedup on one example.
382 </para>
383
384 <para>
385 There are some restrictions on the use of primitive types:
386 <itemizedlist>
387 <listitem><para>The main restriction
388 is that you can't pass a primitive value to a polymorphic
389 function or store one in a polymorphic data type.  This rules out
390 things like <literal>[Int&num;]</literal> (i.e. lists of primitive
391 integers).  The reason for this restriction is that polymorphic
392 arguments and constructor fields are assumed to be pointers: if an
393 unboxed integer is stored in one of these, the garbage collector would
394 attempt to follow it, leading to unpredictable space leaks.  Or a
395 <function>seq</function> operation on the polymorphic component may
396 attempt to dereference the pointer, with disastrous results.  Even
397 worse, the unboxed value might be larger than a pointer
398 (<literal>Double&num;</literal> for instance).
399 </para>
400 </listitem>
401 <listitem><para> You cannot define a newtype whose representation type
402 (the argument type of the data constructor) is an unboxed type.  Thus,
403 this is illegal:
404 <programlisting>
405   newtype A = MkA Int#
406 </programlisting>
407 </para></listitem>
408 <listitem><para> You cannot bind a variable with an unboxed type
409 in a <emphasis>top-level</emphasis> binding.
410 </para></listitem>
411 <listitem><para> You cannot bind a variable with an unboxed type
412 in a <emphasis>recursive</emphasis> binding.
413 </para></listitem>
414 <listitem><para> You may bind unboxed variables in a (non-recursive,
415 non-top-level) pattern binding, but any such variable causes the entire
416 pattern-match
417 to become strict.  For example:
418 <programlisting>
419   data Foo = Foo Int Int#
420
421   f x = let (Foo a b, w) = ..rhs.. in ..body..
422 </programlisting>
423 Since <literal>b</literal> has type <literal>Int#</literal>, the entire pattern
424 match
425 is strict, and the program behaves as if you had written
426 <programlisting>
427   data Foo = Foo Int Int#
428
429   f x = case ..rhs.. of { (Foo a b, w) -> ..body.. }
430 </programlisting>
431 </para>
432 </listitem>
433 </itemizedlist>
434 </para>
435
436 </sect2>
437
438 <sect2 id="unboxed-tuples">
439 <title>Unboxed Tuples
440 </title>
441
442 <para>
443 Unboxed tuples aren't really exported by <literal>GHC.Exts</literal>,
444 they're available by default with <option>-fglasgow-exts</option>.  An
445 unboxed tuple looks like this:
446 </para>
447
448 <para>
449
450 <programlisting>
451 (# e_1, ..., e_n #)
452 </programlisting>
453
454 </para>
455
456 <para>
457 where <literal>e&lowbar;1..e&lowbar;n</literal> are expressions of any
458 type (primitive or non-primitive).  The type of an unboxed tuple looks
459 the same.
460 </para>
461
462 <para>
463 Unboxed tuples are used for functions that need to return multiple
464 values, but they avoid the heap allocation normally associated with
465 using fully-fledged tuples.  When an unboxed tuple is returned, the
466 components are put directly into registers or on the stack; the
467 unboxed tuple itself does not have a composite representation.  Many
468 of the primitive operations listed in <literal>primops.txt.pp</literal> return unboxed
469 tuples.
470 In particular, the <literal>IO</literal> and <literal>ST</literal> monads use unboxed
471 tuples to avoid unnecessary allocation during sequences of operations.
472 </para>
473
474 <para>
475 There are some pretty stringent restrictions on the use of unboxed tuples:
476 <itemizedlist>
477 <listitem>
478
479 <para>
480 Values of unboxed tuple types are subject to the same restrictions as
481 other unboxed types; i.e. they may not be stored in polymorphic data
482 structures or passed to polymorphic functions.
483
484 </para>
485 </listitem>
486 <listitem>
487
488 <para>
489 No variable can have an unboxed tuple type, nor may a constructor or function
490 argument have an unboxed tuple type.  The following are all illegal:
491
492
493 <programlisting>
494   data Foo = Foo (# Int, Int #)
495
496   f :: (# Int, Int #) -&#62; (# Int, Int #)
497   f x = x
498
499   g :: (# Int, Int #) -&#62; Int
500   g (# a,b #) = a
501
502   h x = let y = (# x,x #) in ...
503 </programlisting>
504 </para>
505 </listitem>
506 </itemizedlist>
507 </para>
508 <para>
509 The typical use of unboxed tuples is simply to return multiple values,
510 binding those multiple results with a <literal>case</literal> expression, thus:
511 <programlisting>
512   f x y = (# x+1, y-1 #)
513   g x = case f x x of { (# a, b #) -&#62; a + b }
514 </programlisting>
515 You can have an unboxed tuple in a pattern binding, thus
516 <programlisting>
517   f x = let (# p,q #) = h x in ..body..
518 </programlisting>
519 If the types of <literal>p</literal> and <literal>q</literal> are not unboxed,
520 the resulting binding is lazy like any other Haskell pattern binding.  The 
521 above example desugars like this:
522 <programlisting>
523   f x = let t = case h x o f{ (# p,q #) -> (p,q)
524             p = fst t
525             q = snd t
526         in ..body..
527 </programlisting>
528 Indeed, the bindings can even be recursive.
529 </para>
530
531 </sect2>
532 </sect1>
533
534
535 <!-- ====================== SYNTACTIC EXTENSIONS =======================  -->
536
537 <sect1 id="syntax-extns">
538 <title>Syntactic extensions</title>
539  
540     <!-- ====================== HIERARCHICAL MODULES =======================  -->
541
542     <sect2 id="hierarchical-modules">
543       <title>Hierarchical Modules</title>
544
545       <para>GHC supports a small extension to the syntax of module
546       names: a module name is allowed to contain a dot
547       <literal>&lsquo;.&rsquo;</literal>.  This is also known as the
548       &ldquo;hierarchical module namespace&rdquo; extension, because
549       it extends the normally flat Haskell module namespace into a
550       more flexible hierarchy of modules.</para>
551
552       <para>This extension has very little impact on the language
553       itself; modules names are <emphasis>always</emphasis> fully
554       qualified, so you can just think of the fully qualified module
555       name as <quote>the module name</quote>.  In particular, this
556       means that the full module name must be given after the
557       <literal>module</literal> keyword at the beginning of the
558       module; for example, the module <literal>A.B.C</literal> must
559       begin</para>
560
561 <programlisting>module A.B.C</programlisting>
562
563
564       <para>It is a common strategy to use the <literal>as</literal>
565       keyword to save some typing when using qualified names with
566       hierarchical modules.  For example:</para>
567
568 <programlisting>
569 import qualified Control.Monad.ST.Strict as ST
570 </programlisting>
571
572       <para>For details on how GHC searches for source and interface
573       files in the presence of hierarchical modules, see <xref
574       linkend="search-path"/>.</para>
575
576       <para>GHC comes with a large collection of libraries arranged
577       hierarchically; see the accompanying <ulink
578       url="../libraries/index.html">library
579       documentation</ulink>.  More libraries to install are available
580       from <ulink
581       url="http://hackage.haskell.org/packages/hackage.html">HackageDB</ulink>.</para>
582     </sect2>
583
584     <!-- ====================== PATTERN GUARDS =======================  -->
585
586 <sect2 id="pattern-guards">
587 <title>Pattern guards</title>
588
589 <para>
590 <indexterm><primary>Pattern guards (Glasgow extension)</primary></indexterm>
591 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.)
592 </para>
593
594 <para>
595 Suppose we have an abstract data type of finite maps, with a
596 lookup operation:
597
598 <programlisting>
599 lookup :: FiniteMap -> Int -> Maybe Int
600 </programlisting>
601
602 The lookup returns <function>Nothing</function> if the supplied key is not in the domain of the mapping, and <function>(Just v)</function> otherwise,
603 where <varname>v</varname> is the value that the key maps to.  Now consider the following definition:
604 </para>
605
606 <programlisting>
607 clunky env var1 var2 | ok1 &amp;&amp; ok2 = val1 + val2
608 | otherwise  = var1 + var2
609 where
610   m1 = lookup env var1
611   m2 = lookup env var2
612   ok1 = maybeToBool m1
613   ok2 = maybeToBool m2
614   val1 = expectJust m1
615   val2 = expectJust m2
616 </programlisting>
617
618 <para>
619 The auxiliary functions are 
620 </para>
621
622 <programlisting>
623 maybeToBool :: Maybe a -&gt; Bool
624 maybeToBool (Just x) = True
625 maybeToBool Nothing  = False
626
627 expectJust :: Maybe a -&gt; a
628 expectJust (Just x) = x
629 expectJust Nothing  = error "Unexpected Nothing"
630 </programlisting>
631
632 <para>
633 What is <function>clunky</function> doing? The guard <literal>ok1 &amp;&amp;
634 ok2</literal> checks that both lookups succeed, using
635 <function>maybeToBool</function> to convert the <function>Maybe</function>
636 types to booleans. The (lazily evaluated) <function>expectJust</function>
637 calls extract the values from the results of the lookups, and binds the
638 returned values to <varname>val1</varname> and <varname>val2</varname>
639 respectively.  If either lookup fails, then clunky takes the
640 <literal>otherwise</literal> case and returns the sum of its arguments.
641 </para>
642
643 <para>
644 This is certainly legal Haskell, but it is a tremendously verbose and
645 un-obvious way to achieve the desired effect.  Arguably, a more direct way
646 to write clunky would be to use case expressions:
647 </para>
648
649 <programlisting>
650 clunky env var1 var2 = case lookup env var1 of
651   Nothing -&gt; fail
652   Just val1 -&gt; case lookup env var2 of
653     Nothing -&gt; fail
654     Just val2 -&gt; val1 + val2
655 where
656   fail = var1 + var2
657 </programlisting>
658
659 <para>
660 This is a bit shorter, but hardly better.  Of course, we can rewrite any set
661 of pattern-matching, guarded equations as case expressions; that is
662 precisely what the compiler does when compiling equations! The reason that
663 Haskell provides guarded equations is because they allow us to write down
664 the cases we want to consider, one at a time, independently of each other. 
665 This structure is hidden in the case version.  Two of the right-hand sides
666 are really the same (<function>fail</function>), and the whole expression
667 tends to become more and more indented. 
668 </para>
669
670 <para>
671 Here is how I would write clunky:
672 </para>
673
674 <programlisting>
675 clunky env var1 var2
676   | Just val1 &lt;- lookup env var1
677   , Just val2 &lt;- lookup env var2
678   = val1 + val2
679 ...other equations for clunky...
680 </programlisting>
681
682 <para>
683 The semantics should be clear enough.  The qualifiers are matched in order. 
684 For a <literal>&lt;-</literal> qualifier, which I call a pattern guard, the
685 right hand side is evaluated and matched against the pattern on the left. 
686 If the match fails then the whole guard fails and the next equation is
687 tried.  If it succeeds, then the appropriate binding takes place, and the
688 next qualifier is matched, in the augmented environment.  Unlike list
689 comprehensions, however, the type of the expression to the right of the
690 <literal>&lt;-</literal> is the same as the type of the pattern to its
691 left.  The bindings introduced by pattern guards scope over all the
692 remaining guard qualifiers, and over the right hand side of the equation.
693 </para>
694
695 <para>
696 Just as with list comprehensions, boolean expressions can be freely mixed
697 with among the pattern guards.  For example:
698 </para>
699
700 <programlisting>
701 f x | [y] &lt;- x
702     , y > 3
703     , Just z &lt;- h y
704     = ...
705 </programlisting>
706
707 <para>
708 Haskell's current guards therefore emerge as a special case, in which the
709 qualifier list has just one element, a boolean expression.
710 </para>
711 </sect2>
712
713     <!-- ===================== View patterns ===================  -->
714
715 <sect2 id="view-patterns">
716 <title>View patterns
717 </title>
718
719 <para>
720 View patterns are enabled by the flag <literal>-XViewPatterns</literal>.
721 More information and examples of view patterns can be found on the
722 <ulink url="http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns">Wiki
723 page</ulink>.
724 </para>
725
726 <para>
727 View patterns are somewhat like pattern guards that can be nested inside
728 of other patterns.  They are a convenient way of pattern-matching
729 against values of abstract types. For example, in a programming language
730 implementation, we might represent the syntax of the types of the
731 language as follows:
732
733 <programlisting>
734 type Typ
735  
736 data TypView = Unit
737              | Arrow Typ Typ
738
739 view :: Type -> TypeView
740
741 -- additional operations for constructing Typ's ...
742 </programlisting>
743
744 The representation of Typ is held abstract, permitting implementations
745 to use a fancy representation (e.g., hash-consing to managage sharing).
746
747 Without view patterns, using this signature a little inconvenient: 
748 <programlisting>
749 size :: Typ -> Integer
750 size t = case view t of
751   Unit -> 1
752   Arrow t1 t2 -> size t1 + size t2
753 </programlisting>
754
755 It is necessary to iterate the case, rather than using an equational
756 function definition. And the situation is even worse when the matching
757 against <literal>t</literal> is buried deep inside another pattern.
758 </para>
759
760 <para>
761 View patterns permit calling the view function inside the pattern and
762 matching against the result: 
763 <programlisting>
764 size (view -> Unit) = 1
765 size (view -> Arrow t1 t2) = size t1 + size t2
766 </programlisting>
767
768 That is, we add a new form of pattern, written
769 <replaceable>expression</replaceable> <literal>-></literal>
770 <replaceable>pattern</replaceable> that means "apply the expression to
771 whatever we're trying to match against, and then match the result of
772 that application against the pattern". The expression can be any Haskell
773 expression of function type, and view patterns can be used wherever
774 patterns are used.
775 </para>
776
777 <para>
778 The semantics of a pattern <literal>(</literal>
779 <replaceable>exp</replaceable> <literal>-></literal>
780 <replaceable>pat</replaceable> <literal>)</literal> are as follows:
781
782 <itemizedlist>
783
784 <listitem> Scoping:
785
786 <para>The variables bound by the view pattern are the variables bound by
787 <replaceable>pat</replaceable>.
788 </para>
789
790 <para>
791 Any variables in <replaceable>exp</replaceable> are bound occurrences,
792 but variables bound "to the left" in a pattern are in scope.  This
793 feature permits, for example, one argument to a function to be used in
794 the view of another argument.  For example, the function
795 <literal>clunky</literal> from <xref linkend="pattern-guards" /> can be
796 written using view patterns as follows:
797
798 <programlisting>
799 clunky env (lookup env -> Just val1) (lookup env -> Just val2) = val1 + val2
800 ...other equations for clunky...
801 </programlisting>
802 </para>
803
804 <para>
805 More precisely, the scoping rules are: 
806 <itemizedlist>
807 <listitem>
808 <para>
809 In a single pattern, variables bound by patterns to the left of a view
810 pattern expression are in scope. For example:
811 <programlisting>
812 example :: Maybe ((String -> Integer,Integer), String) -> Bool
813 example Just ((f,_), f -> 4) = True
814 </programlisting>
815
816 Additionally, in function definitions, variables bound by matching earlier curried
817 arguments may be used in view pattern expressions in later arguments:
818 <programlisting>
819 example :: (String -> Integer) -> String -> Bool
820 example f (f -> 4) = True
821 </programlisting>
822 That is, the scoping is the same as it would be if the curried arguments
823 were collected into a tuple.  
824 </para>
825 </listitem>
826
827 <listitem>
828 <para>
829 In mutually recursive bindings, such as <literal>let</literal>,
830 <literal>where</literal>, or the top level, view patterns in one
831 declaration may not mention variables bound by other declarations.  That
832 is, each declaration must be self-contained.  For example, the following
833 program is not allowed:
834 <programlisting>
835 let {(x -> y) = e1 ;
836      (y -> x) = e2 } in x
837 </programlisting>
838
839 (We may lift this
840 restriction in the future; the only cost is that type checking patterns
841 would get a little more complicated.)  
842
843
844 </para>
845 </listitem>
846 </itemizedlist>
847
848 </para>
849 </listitem>
850
851 <listitem><para> Typing: If <replaceable>exp</replaceable> has type
852 <replaceable>T1</replaceable> <literal>-></literal>
853 <replaceable>T2</replaceable> and <replaceable>pat</replaceable> matches
854 a <replaceable>T2</replaceable>, then the whole view pattern matches a
855 <replaceable>T1</replaceable>.
856 </para></listitem>
857
858 <listitem><para> Matching: To the equations in Section 3.17.3 of the
859 <ulink url="http://www.haskell.org/onlinereport/">Haskell 98
860 Report</ulink>, add the following:
861 <programlisting>
862 case v of { (e -> p) -> e1 ; _ -> e2 } 
863  = 
864 case (e v) of { p -> e1 ; _ -> e2 }
865 </programlisting>
866 That is, to match a variable <replaceable>v</replaceable> against a pattern
867 <literal>(</literal> <replaceable>exp</replaceable>
868 <literal>-></literal> <replaceable>pat</replaceable>
869 <literal>)</literal>, evaluate <literal>(</literal>
870 <replaceable>exp</replaceable> <replaceable> v</replaceable>
871 <literal>)</literal> and match the result against
872 <replaceable>pat</replaceable>.  
873 </para></listitem>
874
875 <listitem><para> Efficiency: When the same view function is applied in
876 multiple branches of a function definition or a case expression (e.g.,
877 in <literal>size</literal> above), GHC makes an attempt to collect these
878 applications into a single nested case expression, so that the view
879 function is only applied once.  Pattern compilation in GHC follows the
880 matrix algorithm described in Chapter 4 of <ulink
881 url="http://research.microsoft.com/~simonpj/Papers/slpj-book-1987/">The
882 Implementation of Functional Programming Languages</ulink>.  When the
883 top rows of the first column of a matrix are all view patterns with the
884 "same" expression, these patterns are transformed into a single nested
885 case.  This includes, for example, adjacent view patterns that line up
886 in a tuple, as in
887 <programlisting>
888 f ((view -> A, p1), p2) = e1
889 f ((view -> B, p3), p4) = e2
890 </programlisting>
891 </para>
892
893 <para> The current notion of when two view pattern expressions are "the
894 same" is very restricted: it is not even full syntactic equality.
895 However, it does include variables, literals, applications, and tuples;
896 e.g., two instances of <literal>view ("hi", "there")</literal> will be
897 collected.  However, the current implementation does not compare up to
898 alpha-equivalence, so two instances of <literal>(x, view x ->
899 y)</literal> will not be coalesced.
900 </para>
901
902 </listitem>
903
904 </itemizedlist>
905 </para>
906
907 </sect2>
908
909     <!-- ===================== Recursive do-notation ===================  -->
910
911 <sect2 id="mdo-notation">
912 <title>The recursive do-notation
913 </title>
914
915 <para> The recursive do-notation (also known as mdo-notation) is implemented as described in
916 <ulink url="http://citeseer.ist.psu.edu/erk02recursive.html">A recursive do for Haskell</ulink>,
917 by Levent Erkok, John Launchbury,
918 Haskell Workshop 2002, pages: 29-37. Pittsburgh, Pennsylvania. 
919 This paper is essential reading for anyone making non-trivial use of mdo-notation,
920 and we do not repeat it here.
921 </para>
922 <para>
923 The do-notation of Haskell does not allow <emphasis>recursive bindings</emphasis>,
924 that is, the variables bound in a do-expression are visible only in the textually following 
925 code block. Compare this to a let-expression, where bound variables are visible in the entire binding
926 group. It turns out that several applications can benefit from recursive bindings in
927 the do-notation, and this extension provides the necessary syntactic support.
928 </para>
929 <para>
930 Here is a simple (yet contrived) example:
931 </para>
932 <programlisting>
933 import Control.Monad.Fix
934
935 justOnes = mdo xs &lt;- Just (1:xs)
936                return xs
937 </programlisting>
938 <para>
939 As you can guess <literal>justOnes</literal> will evaluate to <literal>Just [1,1,1,...</literal>.
940 </para>
941
942 <para>
943 The Control.Monad.Fix library introduces the <literal>MonadFix</literal> class. It's definition is:
944 </para>
945 <programlisting>
946 class Monad m => MonadFix m where
947    mfix :: (a -> m a) -> m a
948 </programlisting>
949 <para>
950 The function <literal>mfix</literal>
951 dictates how the required recursion operation should be performed.  For example, 
952 <literal>justOnes</literal> desugars as follows:
953 <programlisting>
954 justOnes = mfix (\xs' -&gt; do { xs &lt;- Just (1:xs'); return xs }
955 </programlisting>
956 For full details of the way in which mdo is typechecked and desugared, see 
957 the paper <ulink url="http://citeseer.ist.psu.edu/erk02recursive.html">A recursive do for Haskell</ulink>.
958 In particular, GHC implements the segmentation technique described in Section 3.2 of the paper.
959 </para>
960 <para>
961 If recursive bindings are required for a monad,
962 then that monad must be declared an instance of the <literal>MonadFix</literal> class.
963 The following instances of <literal>MonadFix</literal> are automatically provided: List, Maybe, IO. 
964 Furthermore, the Control.Monad.ST and Control.Monad.ST.Lazy modules provide the instances of the MonadFix class 
965 for Haskell's internal state monad (strict and lazy, respectively).
966 </para>
967 <para>
968 Here are some important points in using the recursive-do notation:
969 <itemizedlist>
970 <listitem><para>
971 The recursive version of the do-notation uses the keyword <literal>mdo</literal> (rather
972 than <literal>do</literal>).
973 </para></listitem>
974
975 <listitem><para>
976 It is enabled with the flag <literal>-XRecursiveDo</literal>, which is in turn implied by
977 <literal>-fglasgow-exts</literal>.
978 </para></listitem>
979
980 <listitem><para>
981 Unlike ordinary do-notation, but like <literal>let</literal> and <literal>where</literal> bindings,
982 name shadowing is not allowed; that is, all the names bound in a single <literal>mdo</literal> must
983 be distinct (Section 3.3 of the paper).
984 </para></listitem>
985
986 <listitem><para>
987 Variables bound by a <literal>let</literal> statement in an <literal>mdo</literal>
988 are monomorphic in the <literal>mdo</literal> (Section 3.1 of the paper).  However
989 GHC breaks the <literal>mdo</literal> into segments to enhance polymorphism,
990 and improve termination (Section 3.2 of the paper).
991 </para></listitem>
992 </itemizedlist>
993 </para>
994
995 <para>
996 The web page: <ulink url="http://www.cse.ogi.edu/PacSoft/projects/rmb">http://www.cse.ogi.edu/PacSoft/projects/rmb</ulink>
997 contains up to date information on recursive monadic bindings.
998 </para>
999
1000 <para>
1001 Historical note: The old implementation of the mdo-notation (and most
1002 of the existing documents) used the name
1003 <literal>MonadRec</literal> for the class and the corresponding library.
1004 This name is not supported by GHC.
1005 </para>
1006
1007 </sect2>
1008
1009
1010    <!-- ===================== PARALLEL LIST COMPREHENSIONS ===================  -->
1011
1012   <sect2 id="parallel-list-comprehensions">
1013     <title>Parallel List Comprehensions</title>
1014     <indexterm><primary>list comprehensions</primary><secondary>parallel</secondary>
1015     </indexterm>
1016     <indexterm><primary>parallel list comprehensions</primary>
1017     </indexterm>
1018
1019     <para>Parallel list comprehensions are a natural extension to list
1020     comprehensions.  List comprehensions can be thought of as a nice
1021     syntax for writing maps and filters.  Parallel comprehensions
1022     extend this to include the zipWith family.</para>
1023
1024     <para>A parallel list comprehension has multiple independent
1025     branches of qualifier lists, each separated by a `|' symbol.  For
1026     example, the following zips together two lists:</para>
1027
1028 <programlisting>
1029    [ (x, y) | x &lt;- xs | y &lt;- ys ] 
1030 </programlisting>
1031
1032     <para>The behavior of parallel list comprehensions follows that of
1033     zip, in that the resulting list will have the same length as the
1034     shortest branch.</para>
1035
1036     <para>We can define parallel list comprehensions by translation to
1037     regular comprehensions.  Here's the basic idea:</para>
1038
1039     <para>Given a parallel comprehension of the form: </para>
1040
1041 <programlisting>
1042    [ e | p1 &lt;- e11, p2 &lt;- e12, ... 
1043        | q1 &lt;- e21, q2 &lt;- e22, ... 
1044        ... 
1045    ] 
1046 </programlisting>
1047
1048     <para>This will be translated to: </para>
1049
1050 <programlisting>
1051    [ e | ((p1,p2), (q1,q2), ...) &lt;- zipN [(p1,p2) | p1 &lt;- e11, p2 &lt;- e12, ...] 
1052                                          [(q1,q2) | q1 &lt;- e21, q2 &lt;- e22, ...] 
1053                                          ... 
1054    ] 
1055 </programlisting>
1056
1057     <para>where `zipN' is the appropriate zip for the given number of
1058     branches.</para>
1059
1060   </sect2>
1061
1062    <!-- ===================== REBINDABLE SYNTAX ===================  -->
1063
1064 <sect2 id="rebindable-syntax">
1065 <title>Rebindable syntax</title>
1066
1067       <para>GHC allows most kinds of built-in syntax to be rebound by
1068       the user, to facilitate replacing the <literal>Prelude</literal>
1069       with a home-grown version, for example.</para>
1070
1071             <para>You may want to define your own numeric class
1072             hierarchy.  It completely defeats that purpose if the
1073             literal "1" means "<literal>Prelude.fromInteger
1074             1</literal>", which is what the Haskell Report specifies.
1075             So the <option>-XNoImplicitPrelude</option> flag causes
1076             the following pieces of built-in syntax to refer to
1077             <emphasis>whatever is in scope</emphasis>, not the Prelude
1078             versions:
1079
1080             <itemizedlist>
1081               <listitem>
1082                 <para>An integer literal <literal>368</literal> means
1083                 "<literal>fromInteger (368::Integer)</literal>", rather than
1084                 "<literal>Prelude.fromInteger (368::Integer)</literal>".
1085 </para> </listitem>         
1086
1087       <listitem><para>Fractional literals are handed in just the same way,
1088           except that the translation is 
1089               <literal>fromRational (3.68::Rational)</literal>.
1090 </para> </listitem>         
1091
1092           <listitem><para>The equality test in an overloaded numeric pattern
1093               uses whatever <literal>(==)</literal> is in scope.
1094 </para> </listitem>         
1095
1096           <listitem><para>The subtraction operation, and the
1097           greater-than-or-equal test, in <literal>n+k</literal> patterns
1098               use whatever <literal>(-)</literal> and <literal>(>=)</literal> are in scope.
1099               </para></listitem>
1100
1101               <listitem>
1102                 <para>Negation (e.g. "<literal>- (f x)</literal>")
1103                 means "<literal>negate (f x)</literal>", both in numeric
1104                 patterns, and expressions.
1105               </para></listitem>
1106
1107               <listitem>
1108           <para>"Do" notation is translated using whatever
1109               functions <literal>(>>=)</literal>,
1110               <literal>(>>)</literal>, and <literal>fail</literal>,
1111               are in scope (not the Prelude
1112               versions).  List comprehensions, mdo (<xref linkend="mdo-notation"/>), and parallel array
1113               comprehensions, are unaffected.  </para></listitem>
1114
1115               <listitem>
1116                 <para>Arrow
1117                 notation (see <xref linkend="arrow-notation"/>)
1118                 uses whatever <literal>arr</literal>,
1119                 <literal>(>>>)</literal>, <literal>first</literal>,
1120                 <literal>app</literal>, <literal>(|||)</literal> and
1121                 <literal>loop</literal> functions are in scope. But unlike the
1122                 other constructs, the types of these functions must match the
1123                 Prelude types very closely.  Details are in flux; if you want
1124                 to use this, ask!
1125               </para></listitem>
1126             </itemizedlist>
1127 In all cases (apart from arrow notation), the static semantics should be that of the desugared form,
1128 even if that is a little unexpected. For emample, the 
1129 static semantics of the literal <literal>368</literal>
1130 is exactly that of <literal>fromInteger (368::Integer)</literal>; it's fine for
1131 <literal>fromInteger</literal> to have any of the types:
1132 <programlisting>
1133 fromInteger :: Integer -> Integer
1134 fromInteger :: forall a. Foo a => Integer -> a
1135 fromInteger :: Num a => a -> Integer
1136 fromInteger :: Integer -> Bool -> Bool
1137 </programlisting>
1138 </para>
1139                 
1140              <para>Be warned: this is an experimental facility, with
1141              fewer checks than usual.  Use <literal>-dcore-lint</literal>
1142              to typecheck the desugared program.  If Core Lint is happy
1143              you should be all right.</para>
1144
1145 </sect2>
1146
1147 <sect2 id="postfix-operators">
1148 <title>Postfix operators</title>
1149
1150 <para>
1151 GHC allows a small extension to the syntax of left operator sections, which
1152 allows you to define postfix operators.  The extension is this:  the left section
1153 <programlisting>
1154   (e !)
1155 </programlisting> 
1156 is equivalent (from the point of view of both type checking and execution) to the expression
1157 <programlisting>
1158   ((!) e)
1159 </programlisting> 
1160 (for any expression <literal>e</literal> and operator <literal>(!)</literal>.
1161 The strict Haskell 98 interpretation is that the section is equivalent to
1162 <programlisting>
1163   (\y -> (!) e y)
1164 </programlisting> 
1165 That is, the operator must be a function of two arguments.  GHC allows it to
1166 take only one argument, and that in turn allows you to write the function
1167 postfix.
1168 </para>
1169 <para>Since this extension goes beyond Haskell 98, it should really be enabled
1170 by a flag; but in fact it is enabled all the time.  (No Haskell 98 programs
1171 change their behaviour, of course.)
1172 </para>
1173 <para>The extension does not extend to the left-hand side of function
1174 definitions; you must define such a function in prefix form.</para>
1175
1176 </sect2>
1177
1178 <sect2 id="disambiguate-fields">
1179 <title>Record field disambiguation</title>
1180 <para>
1181 In record construction and record pattern matching
1182 it is entirely unambiguous which field is referred to, even if there are two different
1183 data types in scope with a common field name.  For example:
1184 <programlisting>
1185 module M where
1186   data S = MkS { x :: Int, y :: Bool }
1187
1188 module Foo where
1189   import M
1190
1191   data T = MkT { x :: Int }
1192   
1193   ok1 (MkS { x = n }) = n+1   -- Unambiguous
1194
1195   ok2 n = MkT { x = n+1 }     -- Unambiguous
1196
1197   bad1 k = k { x = 3 }  -- Ambiguous
1198   bad2 k = x k          -- Ambiguous
1199 </programlisting>
1200 Even though there are two <literal>x</literal>'s in scope,
1201 it is clear that the <literal>x</literal> in the pattern in the
1202 definition of <literal>ok1</literal> can only mean the field
1203 <literal>x</literal> from type <literal>S</literal>. Similarly for
1204 the function <literal>ok2</literal>.  However, in the record update
1205 in <literal>bad1</literal> and the record selection in <literal>bad2</literal>
1206 it is not clear which of the two types is intended.
1207 </para>
1208 <para>
1209 Haskell 98 regards all four as ambiguous, but with the
1210 <option>-fdisambiguate-record-fields</option> flag, GHC will accept
1211 the former two.  The rules are precisely the same as those for instance
1212 declarations in Haskell 98, where the method names on the left-hand side 
1213 of the method bindings in an instance declaration refer unambiguously
1214 to the method of that class (provided they are in scope at all), even
1215 if there are other variables in scope with the same name.
1216 This reduces the clutter of qualified names when you import two
1217 records from different modules that use the same field name.
1218 </para>
1219 </sect2>
1220
1221     <!-- ===================== Record puns ===================  -->
1222
1223 <sect2 id="record-puns">
1224 <title>Record puns
1225 </title>
1226
1227 <para>
1228 Record puns are enabled by the flag <literal>-XRecordPuns</literal>.
1229 </para>
1230
1231 <para>
1232 When using records, it is common to write a pattern that binds a
1233 variable with the same name as a record field, such as:
1234
1235 <programlisting>
1236 data C = C {a :: Int}
1237 f (C {a = a}) = a
1238 </programlisting>
1239 </para>
1240
1241 <para>
1242 Record punning permits the variable name to be elided, so one can simply
1243 write
1244
1245 <programlisting>
1246 f (C {a}) = a
1247 </programlisting>
1248
1249 to mean the same pattern as above.  That is, in a record pattern, the
1250 pattern <literal>a</literal> expands into the pattern <literal>a =
1251 a</literal> for the same name <literal>a</literal>.  
1252 </para>
1253
1254 <para>
1255 Note that puns and other patterns can be mixed in the same record:
1256 <programlisting>
1257 data C = C {a :: Int, b :: Int}
1258 f (C {a, b = 4}) = a
1259 </programlisting>
1260 and that puns can be used wherever record patterns occur (e.g. in
1261 <literal>let</literal> bindings or at the top-level).  
1262 </para>
1263
1264 <para>
1265 Record punning can also be used in an expression, writing, for example,
1266 <programlisting>
1267 let a = 1 in C {a}
1268 </programlisting>
1269 instead of 
1270 <programlisting>
1271 let a = 1 in C {a = a}
1272 </programlisting>
1273
1274 Note that this expansion is purely syntactic, so the record pun
1275 expression refers to the nearest enclosing variable that is spelled the
1276 same as the field name.
1277 </para>
1278
1279 </sect2>
1280
1281     <!-- ===================== Record wildcards ===================  -->
1282
1283 <sect2 id="record-wildcards">
1284 <title>Record wildcards
1285 </title>
1286
1287 <para>
1288 Record wildcards are enabled by the flag <literal>-XRecordWildCards</literal>.
1289 </para>
1290
1291 <para>
1292 For records with many fields, it can be tiresome to write out each field
1293 individually in a record pattern, as in
1294 <programlisting>
1295 data C = C {a :: Int, b :: Int, c :: Int, d :: Int}
1296 f (C {a = 1, b = b, c = c, d = d}) = b + c + d
1297 </programlisting>
1298 </para>
1299
1300 <para>
1301 Record wildcard syntax permits a (<literal>..</literal>) in a record
1302 pattern, where each elided field <literal>f</literal> is replaced by the
1303 pattern <literal>f = f</literal>.  For example, the above pattern can be
1304 written as
1305 <programlisting>
1306 f (C {a = 1, ..}) = b + c + d
1307 </programlisting>
1308 </para>
1309
1310 <para>
1311 Note that wildcards can be mixed with other patterns, including puns
1312 (<xref linkend="record-puns"/>); for example, in a pattern <literal>C {a
1313 = 1, b, ..})</literal>.  Additionally, record wildcards can be used
1314 wherever record patterns occur, including in <literal>let</literal>
1315 bindings and at the top-level.  For example, the top-level binding
1316 <programlisting>
1317 C {a = 1, ..} = e
1318 </programlisting>
1319 defines <literal>b</literal>, <literal>c</literal>, and
1320 <literal>d</literal>.
1321 </para>
1322
1323 <para>
1324 Record wildcards can also be used in expressions, writing, for example,
1325
1326 <programlisting>
1327 let {a = 1; b = 2; c = 3; d = 4} in C {..}
1328 </programlisting>
1329
1330 in place of
1331
1332 <programlisting>
1333 let {a = 1; b = 2; c = 3; d = 4} in C {a=a, b=b, c=c, d=d}
1334 </programlisting>
1335
1336 Note that this expansion is purely syntactic, so the record wildcard
1337 expression refers to the nearest enclosing variables that are spelled
1338 the same as the omitted field names.
1339 </para>
1340
1341 </sect2>
1342
1343     <!-- ===================== Local fixity declarations ===================  -->
1344
1345 <sect2 id="local-fixity-declarations">
1346 <title>Local Fixity Declarations
1347 </title>
1348
1349 <para>A careful reading of the Haskell 98 Report reveals that fixity
1350 declarations (<literal>infix</literal>, <literal>infixl</literal>, and
1351 <literal>infixr</literal>) are permitted to appear inside local bindings
1352 such those introduced by <literal>let</literal> and
1353 <literal>where</literal>.  However, the Haskell Report does not specify
1354 the semantics of such bindings very precisely.
1355 </para>
1356
1357 <para>In GHC, a fixity declaration may accompany a local binding:
1358 <programlisting>
1359 let f = ...
1360     infixr 3 `f`
1361 in 
1362     ...
1363 </programlisting>
1364 and the fixity declaration applies wherever the binding is in scope.
1365 For example, in a <literal>let</literal>, it applies in the right-hand
1366 sides of other <literal>let</literal>-bindings and the body of the
1367 <literal>let</literal>C. Or, in recursive <literal>do</literal>
1368 expressions (<xref linkend="mdo-notation"/>), the local fixity
1369 declarations of aA <literal>let</literal> statement scope over other
1370 statements in the group, just as the bound name does.
1371 </para>
1372
1373 Moreover, a local fixity declatation *must* accompany a local binding of
1374 that name: it is not possible to revise the fixity of name bound
1375 elsewhere, as in
1376 <programlisting>
1377 let infixr 9 $ in ...
1378 </programlisting>
1379
1380 Because local fixity declarations are technically Haskell 98, no flag is
1381 necessary to enable them.
1382 </sect2>
1383
1384 </sect1>
1385
1386
1387 <!-- TYPE SYSTEM EXTENSIONS -->
1388 <sect1 id="data-type-extensions">
1389 <title>Extensions to data types and type synonyms</title>
1390
1391 <sect2 id="nullary-types">
1392 <title>Data types with no constructors</title>
1393
1394 <para>With the <option>-fglasgow-exts</option> flag, GHC lets you declare
1395 a data type with no constructors.  For example:</para>
1396
1397 <programlisting>
1398   data S      -- S :: *
1399   data T a    -- T :: * -> *
1400 </programlisting>
1401
1402 <para>Syntactically, the declaration lacks the "= constrs" part.  The 
1403 type can be parameterised over types of any kind, but if the kind is
1404 not <literal>*</literal> then an explicit kind annotation must be used
1405 (see <xref linkend="kinding"/>).</para>
1406
1407 <para>Such data types have only one value, namely bottom.
1408 Nevertheless, they can be useful when defining "phantom types".</para>
1409 </sect2>
1410
1411 <sect2 id="infix-tycons">
1412 <title>Infix type constructors, classes, and type variables</title>
1413
1414 <para>
1415 GHC allows type constructors, classes, and type variables to be operators, and
1416 to be written infix, very much like expressions.  More specifically:
1417 <itemizedlist>
1418 <listitem><para>
1419   A type constructor or class can be an operator, beginning with a colon; e.g. <literal>:*:</literal>.
1420   The lexical syntax is the same as that for data constructors.
1421   </para></listitem>
1422 <listitem><para>
1423   Data type and type-synonym declarations can be written infix, parenthesised
1424   if you want further arguments.  E.g.
1425 <screen>
1426   data a :*: b = Foo a b
1427   type a :+: b = Either a b
1428   class a :=: b where ...
1429
1430   data (a :**: b) x = Baz a b x
1431   type (a :++: b) y = Either (a,b) y
1432 </screen>
1433   </para></listitem>
1434 <listitem><para>
1435   Types, and class constraints, can be written infix.  For example
1436   <screen>
1437         x :: Int :*: Bool
1438         f :: (a :=: b) => a -> b
1439   </screen>
1440   </para></listitem>
1441 <listitem><para>
1442   A type variable can be an (unqualified) operator e.g. <literal>+</literal>.
1443   The lexical syntax is the same as that for variable operators, excluding "(.)",
1444   "(!)", and "(*)".  In a binding position, the operator must be
1445   parenthesised.  For example:
1446 <programlisting>
1447    type T (+) = Int + Int
1448    f :: T Either
1449    f = Left 3
1450  
1451    liftA2 :: Arrow (~>)
1452           => (a -> b -> c) -> (e ~> a) -> (e ~> b) -> (e ~> c)
1453    liftA2 = ...
1454 </programlisting>
1455   </para></listitem>
1456 <listitem><para>
1457   Back-quotes work
1458   as for expressions, both for type constructors and type variables;  e.g. <literal>Int `Either` Bool</literal>, or
1459   <literal>Int `a` Bool</literal>.  Similarly, parentheses work the same; e.g.  <literal>(:*:) Int Bool</literal>.
1460   </para></listitem>
1461 <listitem><para>
1462   Fixities may be declared for type constructors, or classes, just as for data constructors.  However,
1463   one cannot distinguish between the two in a fixity declaration; a fixity declaration
1464   sets the fixity for a data constructor and the corresponding type constructor.  For example:
1465 <screen>
1466   infixl 7 T, :*:
1467 </screen>
1468   sets the fixity for both type constructor <literal>T</literal> and data constructor <literal>T</literal>,
1469   and similarly for <literal>:*:</literal>.
1470   <literal>Int `a` Bool</literal>.
1471   </para></listitem>
1472 <listitem><para>
1473   Function arrow is <literal>infixr</literal> with fixity 0.  (This might change; I'm not sure what it should be.)
1474   </para></listitem>
1475
1476 </itemizedlist>
1477 </para>
1478 </sect2>
1479
1480 <sect2 id="type-synonyms">
1481 <title>Liberalised type synonyms</title>
1482
1483 <para>
1484 Type synonyms are like macros at the type level, and
1485 GHC does validity checking on types <emphasis>only after expanding type synonyms</emphasis>.
1486 That means that GHC can be very much more liberal about type synonyms than Haskell 98:
1487 <itemizedlist>
1488 <listitem> <para>You can write a <literal>forall</literal> (including overloading)
1489 in a type synonym, thus:
1490 <programlisting>
1491   type Discard a = forall b. Show b => a -> b -> (a, String)
1492
1493   f :: Discard a
1494   f x y = (x, show y)
1495
1496   g :: Discard Int -> (Int,String)    -- A rank-2 type
1497   g f = f 3 True
1498 </programlisting>
1499 </para>
1500 </listitem>
1501
1502 <listitem><para>
1503 You can write an unboxed tuple in a type synonym:
1504 <programlisting>
1505   type Pr = (# Int, Int #)
1506
1507   h :: Int -> Pr
1508   h x = (# x, x #)
1509 </programlisting>
1510 </para></listitem>
1511
1512 <listitem><para>
1513 You can apply a type synonym to a forall type:
1514 <programlisting>
1515   type Foo a = a -> a -> Bool
1516  
1517   f :: Foo (forall b. b->b)
1518 </programlisting>
1519 After expanding the synonym, <literal>f</literal> has the legal (in GHC) type:
1520 <programlisting>
1521   f :: (forall b. b->b) -> (forall b. b->b) -> Bool
1522 </programlisting>
1523 </para></listitem>
1524
1525 <listitem><para>
1526 You can apply a type synonym to a partially applied type synonym:
1527 <programlisting>
1528   type Generic i o = forall x. i x -> o x
1529   type Id x = x
1530   
1531   foo :: Generic Id []
1532 </programlisting>
1533 After expanding the synonym, <literal>foo</literal> has the legal (in GHC) type:
1534 <programlisting>
1535   foo :: forall x. x -> [x]
1536 </programlisting>
1537 </para></listitem>
1538
1539 </itemizedlist>
1540 </para>
1541
1542 <para>
1543 GHC currently does kind checking before expanding synonyms (though even that
1544 could be changed.)
1545 </para>
1546 <para>
1547 After expanding type synonyms, GHC does validity checking on types, looking for
1548 the following mal-formedness which isn't detected simply by kind checking:
1549 <itemizedlist>
1550 <listitem><para>
1551 Type constructor applied to a type involving for-alls.
1552 </para></listitem>
1553 <listitem><para>
1554 Unboxed tuple on left of an arrow.
1555 </para></listitem>
1556 <listitem><para>
1557 Partially-applied type synonym.
1558 </para></listitem>
1559 </itemizedlist>
1560 So, for example,
1561 this will be rejected:
1562 <programlisting>
1563   type Pr = (# Int, Int #)
1564
1565   h :: Pr -> Int
1566   h x = ...
1567 </programlisting>
1568 because GHC does not allow  unboxed tuples on the left of a function arrow.
1569 </para>
1570 </sect2>
1571
1572
1573 <sect2 id="existential-quantification">
1574 <title>Existentially quantified data constructors
1575 </title>
1576
1577 <para>
1578 The idea of using existential quantification in data type declarations
1579 was suggested by Perry, and implemented in Hope+ (Nigel Perry, <emphasis>The Implementation
1580 of Practical Functional Programming Languages</emphasis>, PhD Thesis, University of
1581 London, 1991). It was later formalised by Laufer and Odersky
1582 (<emphasis>Polymorphic type inference and abstract data types</emphasis>,
1583 TOPLAS, 16(5), pp1411-1430, 1994).
1584 It's been in Lennart
1585 Augustsson's <command>hbc</command> Haskell compiler for several years, and
1586 proved very useful.  Here's the idea.  Consider the declaration:
1587 </para>
1588
1589 <para>
1590
1591 <programlisting>
1592   data Foo = forall a. MkFoo a (a -> Bool)
1593            | Nil
1594 </programlisting>
1595
1596 </para>
1597
1598 <para>
1599 The data type <literal>Foo</literal> has two constructors with types:
1600 </para>
1601
1602 <para>
1603
1604 <programlisting>
1605   MkFoo :: forall a. a -> (a -> Bool) -> Foo
1606   Nil   :: Foo
1607 </programlisting>
1608
1609 </para>
1610
1611 <para>
1612 Notice that the type variable <literal>a</literal> in the type of <function>MkFoo</function>
1613 does not appear in the data type itself, which is plain <literal>Foo</literal>.
1614 For example, the following expression is fine:
1615 </para>
1616
1617 <para>
1618
1619 <programlisting>
1620   [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]
1621 </programlisting>
1622
1623 </para>
1624
1625 <para>
1626 Here, <literal>(MkFoo 3 even)</literal> packages an integer with a function
1627 <function>even</function> that maps an integer to <literal>Bool</literal>; and <function>MkFoo 'c'
1628 isUpper</function> packages a character with a compatible function.  These
1629 two things are each of type <literal>Foo</literal> and can be put in a list.
1630 </para>
1631
1632 <para>
1633 What can we do with a value of type <literal>Foo</literal>?.  In particular,
1634 what happens when we pattern-match on <function>MkFoo</function>?
1635 </para>
1636
1637 <para>
1638
1639 <programlisting>
1640   f (MkFoo val fn) = ???
1641 </programlisting>
1642
1643 </para>
1644
1645 <para>
1646 Since all we know about <literal>val</literal> and <function>fn</function> is that they
1647 are compatible, the only (useful) thing we can do with them is to
1648 apply <function>fn</function> to <literal>val</literal> to get a boolean.  For example:
1649 </para>
1650
1651 <para>
1652
1653 <programlisting>
1654   f :: Foo -> Bool
1655   f (MkFoo val fn) = fn val
1656 </programlisting>
1657
1658 </para>
1659
1660 <para>
1661 What this allows us to do is to package heterogenous values
1662 together with a bunch of functions that manipulate them, and then treat
1663 that collection of packages in a uniform manner.  You can express
1664 quite a bit of object-oriented-like programming this way.
1665 </para>
1666
1667 <sect3 id="existential">
1668 <title>Why existential?
1669 </title>
1670
1671 <para>
1672 What has this to do with <emphasis>existential</emphasis> quantification?
1673 Simply that <function>MkFoo</function> has the (nearly) isomorphic type
1674 </para>
1675
1676 <para>
1677
1678 <programlisting>
1679   MkFoo :: (exists a . (a, a -> Bool)) -> Foo
1680 </programlisting>
1681
1682 </para>
1683
1684 <para>
1685 But Haskell programmers can safely think of the ordinary
1686 <emphasis>universally</emphasis> quantified type given above, thereby avoiding
1687 adding a new existential quantification construct.
1688 </para>
1689
1690 </sect3>
1691
1692 <sect3>
1693 <title>Type classes</title>
1694
1695 <para>
1696 An easy extension is to allow
1697 arbitrary contexts before the constructor.  For example:
1698 </para>
1699
1700 <para>
1701
1702 <programlisting>
1703 data Baz = forall a. Eq a => Baz1 a a
1704          | forall b. Show b => Baz2 b (b -> b)
1705 </programlisting>
1706
1707 </para>
1708
1709 <para>
1710 The two constructors have the types you'd expect:
1711 </para>
1712
1713 <para>
1714
1715 <programlisting>
1716 Baz1 :: forall a. Eq a => a -> a -> Baz
1717 Baz2 :: forall b. Show b => b -> (b -> b) -> Baz
1718 </programlisting>
1719
1720 </para>
1721
1722 <para>
1723 But when pattern matching on <function>Baz1</function> the matched values can be compared
1724 for equality, and when pattern matching on <function>Baz2</function> the first matched
1725 value can be converted to a string (as well as applying the function to it).
1726 So this program is legal:
1727 </para>
1728
1729 <para>
1730
1731 <programlisting>
1732   f :: Baz -> String
1733   f (Baz1 p q) | p == q    = "Yes"
1734                | otherwise = "No"
1735   f (Baz2 v fn)            = show (fn v)
1736 </programlisting>
1737
1738 </para>
1739
1740 <para>
1741 Operationally, in a dictionary-passing implementation, the
1742 constructors <function>Baz1</function> and <function>Baz2</function> must store the
1743 dictionaries for <literal>Eq</literal> and <literal>Show</literal> respectively, and
1744 extract it on pattern matching.
1745 </para>
1746
1747 <para>
1748 Notice the way that the syntax fits smoothly with that used for
1749 universal quantification earlier.
1750 </para>
1751
1752 </sect3>
1753
1754 <sect3 id="existential-records">
1755 <title>Record Constructors</title>
1756
1757 <para>
1758 GHC allows existentials to be used with records syntax as well.  For example:
1759
1760 <programlisting>
1761 data Counter a = forall self. NewCounter
1762     { _this    :: self
1763     , _inc     :: self -> self
1764     , _display :: self -> IO ()
1765     , tag      :: a
1766     }
1767 </programlisting>
1768 Here <literal>tag</literal> is a public field, with a well-typed selector
1769 function <literal>tag :: Counter a -> a</literal>.  The <literal>self</literal>
1770 type is hidden from the outside; any attempt to apply <literal>_this</literal>,
1771 <literal>_inc</literal> or <literal>_display</literal> as functions will raise a
1772 compile-time error.  In other words, <emphasis>GHC defines a record selector function
1773 only for fields whose type does not mention the existentially-quantified variables</emphasis>.
1774 (This example used an underscore in the fields for which record selectors
1775 will not be defined, but that is only programming style; GHC ignores them.)
1776 </para>
1777
1778 <para>
1779 To make use of these hidden fields, we need to create some helper functions:
1780
1781 <programlisting>
1782 inc :: Counter a -> Counter a
1783 inc (NewCounter x i d t) = NewCounter
1784     { _this = i x, _inc = i, _display = d, tag = t } 
1785
1786 display :: Counter a -> IO ()
1787 display NewCounter{ _this = x, _display = d } = d x
1788 </programlisting>
1789
1790 Now we can define counters with different underlying implementations:
1791
1792 <programlisting>
1793 counterA :: Counter String 
1794 counterA = NewCounter
1795     { _this = 0, _inc = (1+), _display = print, tag = "A" }
1796
1797 counterB :: Counter String 
1798 counterB = NewCounter
1799     { _this = "", _inc = ('#':), _display = putStrLn, tag = "B" }
1800
1801 main = do
1802     display (inc counterA)         -- prints "1"
1803     display (inc (inc counterB))   -- prints "##"
1804 </programlisting>
1805
1806 At the moment, record update syntax is only supported for Haskell 98 data types,
1807 so the following function does <emphasis>not</emphasis> work:
1808
1809 <programlisting>
1810 -- This is invalid; use explicit NewCounter instead for now
1811 setTag :: Counter a -> a -> Counter a
1812 setTag obj t = obj{ tag = t }
1813 </programlisting>
1814
1815 </para>
1816
1817 </sect3>
1818
1819
1820 <sect3>
1821 <title>Restrictions</title>
1822
1823 <para>
1824 There are several restrictions on the ways in which existentially-quantified
1825 constructors can be use.
1826 </para>
1827
1828 <para>
1829
1830 <itemizedlist>
1831 <listitem>
1832
1833 <para>
1834  When pattern matching, each pattern match introduces a new,
1835 distinct, type for each existential type variable.  These types cannot
1836 be unified with any other type, nor can they escape from the scope of
1837 the pattern match.  For example, these fragments are incorrect:
1838
1839
1840 <programlisting>
1841 f1 (MkFoo a f) = a
1842 </programlisting>
1843
1844
1845 Here, the type bound by <function>MkFoo</function> "escapes", because <literal>a</literal>
1846 is the result of <function>f1</function>.  One way to see why this is wrong is to
1847 ask what type <function>f1</function> has:
1848
1849
1850 <programlisting>
1851   f1 :: Foo -> a             -- Weird!
1852 </programlisting>
1853
1854
1855 What is this "<literal>a</literal>" in the result type? Clearly we don't mean
1856 this:
1857
1858
1859 <programlisting>
1860   f1 :: forall a. Foo -> a   -- Wrong!
1861 </programlisting>
1862
1863
1864 The original program is just plain wrong.  Here's another sort of error
1865
1866
1867 <programlisting>
1868   f2 (Baz1 a b) (Baz1 p q) = a==q
1869 </programlisting>
1870
1871
1872 It's ok to say <literal>a==b</literal> or <literal>p==q</literal>, but
1873 <literal>a==q</literal> is wrong because it equates the two distinct types arising
1874 from the two <function>Baz1</function> constructors.
1875
1876
1877 </para>
1878 </listitem>
1879 <listitem>
1880
1881 <para>
1882 You can't pattern-match on an existentially quantified
1883 constructor in a <literal>let</literal> or <literal>where</literal> group of
1884 bindings. So this is illegal:
1885
1886
1887 <programlisting>
1888   f3 x = a==b where { Baz1 a b = x }
1889 </programlisting>
1890
1891 Instead, use a <literal>case</literal> expression:
1892
1893 <programlisting>
1894   f3 x = case x of Baz1 a b -> a==b
1895 </programlisting>
1896
1897 In general, you can only pattern-match
1898 on an existentially-quantified constructor in a <literal>case</literal> expression or
1899 in the patterns of a function definition.
1900
1901 The reason for this restriction is really an implementation one.
1902 Type-checking binding groups is already a nightmare without
1903 existentials complicating the picture.  Also an existential pattern
1904 binding at the top level of a module doesn't make sense, because it's
1905 not clear how to prevent the existentially-quantified type "escaping".
1906 So for now, there's a simple-to-state restriction.  We'll see how
1907 annoying it is.
1908
1909 </para>
1910 </listitem>
1911 <listitem>
1912
1913 <para>
1914 You can't use existential quantification for <literal>newtype</literal>
1915 declarations.  So this is illegal:
1916
1917
1918 <programlisting>
1919   newtype T = forall a. Ord a => MkT a
1920 </programlisting>
1921
1922
1923 Reason: a value of type <literal>T</literal> must be represented as a
1924 pair of a dictionary for <literal>Ord t</literal> and a value of type
1925 <literal>t</literal>.  That contradicts the idea that
1926 <literal>newtype</literal> should have no concrete representation.
1927 You can get just the same efficiency and effect by using
1928 <literal>data</literal> instead of <literal>newtype</literal>.  If
1929 there is no overloading involved, then there is more of a case for
1930 allowing an existentially-quantified <literal>newtype</literal>,
1931 because the <literal>data</literal> version does carry an
1932 implementation cost, but single-field existentially quantified
1933 constructors aren't much use.  So the simple restriction (no
1934 existential stuff on <literal>newtype</literal>) stands, unless there
1935 are convincing reasons to change it.
1936
1937
1938 </para>
1939 </listitem>
1940 <listitem>
1941
1942 <para>
1943  You can't use <literal>deriving</literal> to define instances of a
1944 data type with existentially quantified data constructors.
1945
1946 Reason: in most cases it would not make sense. For example:;
1947
1948 <programlisting>
1949 data T = forall a. MkT [a] deriving( Eq )
1950 </programlisting>
1951
1952 To derive <literal>Eq</literal> in the standard way we would need to have equality
1953 between the single component of two <function>MkT</function> constructors:
1954
1955 <programlisting>
1956 instance Eq T where
1957   (MkT a) == (MkT b) = ???
1958 </programlisting>
1959
1960 But <varname>a</varname> and <varname>b</varname> have distinct types, and so can't be compared.
1961 It's just about possible to imagine examples in which the derived instance
1962 would make sense, but it seems altogether simpler simply to prohibit such
1963 declarations.  Define your own instances!
1964 </para>
1965 </listitem>
1966
1967 </itemizedlist>
1968
1969 </para>
1970
1971 </sect3>
1972 </sect2>
1973
1974 <!-- ====================== Generalised algebraic data types =======================  -->
1975
1976 <sect2 id="gadt-style">
1977 <title>Declaring data types with explicit constructor signatures</title>
1978
1979 <para>GHC allows you to declare an algebraic data type by 
1980 giving the type signatures of constructors explicitly.  For example:
1981 <programlisting>
1982   data Maybe a where
1983       Nothing :: Maybe a
1984       Just    :: a -> Maybe a
1985 </programlisting>
1986 The form is called a "GADT-style declaration"
1987 because Generalised Algebraic Data Types, described in <xref linkend="gadt"/>, 
1988 can only be declared using this form.</para>
1989 <para>Notice that GADT-style syntax generalises existential types (<xref linkend="existential-quantification"/>).  
1990 For example, these two declarations are equivalent:
1991 <programlisting>
1992   data Foo = forall a. MkFoo a (a -> Bool)
1993   data Foo' where { MKFoo :: a -> (a->Bool) -> Foo' }
1994 </programlisting>
1995 </para>
1996 <para>Any data type that can be declared in standard Haskell-98 syntax 
1997 can also be declared using GADT-style syntax.
1998 The choice is largely stylistic, but GADT-style declarations differ in one important respect:
1999 they treat class constraints on the data constructors differently.
2000 Specifically, if the constructor is given a type-class context, that
2001 context is made available by pattern matching.  For example:
2002 <programlisting>
2003   data Set a where
2004     MkSet :: Eq a => [a] -> Set a
2005
2006   makeSet :: Eq a => [a] -> Set a
2007   makeSet xs = MkSet (nub xs)
2008
2009   insert :: a -> Set a -> Set a
2010   insert a (MkSet as) | a `elem` as = MkSet as
2011                       | otherwise   = MkSet (a:as)
2012 </programlisting>
2013 A use of <literal>MkSet</literal> as a constructor (e.g. in the definition of <literal>makeSet</literal>) 
2014 gives rise to a <literal>(Eq a)</literal>
2015 constraint, as you would expect.  The new feature is that pattern-matching on <literal>MkSet</literal>
2016 (as in the definition of <literal>insert</literal>) makes <emphasis>available</emphasis> an <literal>(Eq a)</literal>
2017 context.  In implementation terms, the <literal>MkSet</literal> constructor has a hidden field that stores
2018 the <literal>(Eq a)</literal> dictionary that is passed to <literal>MkSet</literal>; so
2019 when pattern-matching that dictionary becomes available for the right-hand side of the match.
2020 In the example, the equality dictionary is used to satisfy the equality constraint 
2021 generated by the call to <literal>elem</literal>, so that the type of
2022 <literal>insert</literal> itself has no <literal>Eq</literal> constraint.
2023 </para>
2024 <para>This behaviour contrasts with Haskell 98's peculiar treament of 
2025 contexts on a data type declaration (Section 4.2.1 of the Haskell 98 Report).
2026 In Haskell 98 the defintion
2027 <programlisting>
2028   data Eq a => Set' a = MkSet' [a]
2029 </programlisting>
2030 gives <literal>MkSet'</literal> the same type as <literal>MkSet</literal> above.  But instead of 
2031 <emphasis>making available</emphasis> an <literal>(Eq a)</literal> constraint, pattern-matching
2032 on <literal>MkSet'</literal> <emphasis>requires</emphasis> an <literal>(Eq a)</literal> constraint!
2033 GHC faithfully implements this behaviour, odd though it is.  But for GADT-style declarations,
2034 GHC's behaviour is much more useful, as well as much more intuitive.</para>
2035 <para>
2036 For example, a possible application of GHC's behaviour is to reify dictionaries:
2037 <programlisting>
2038    data NumInst a where
2039      MkNumInst :: Num a => NumInst a
2040
2041    intInst :: NumInst Int
2042    intInst = MkNumInst
2043
2044    plus :: NumInst a -> a -> a -> a
2045    plus MkNumInst p q = p + q
2046 </programlisting>
2047 Here, a value of type <literal>NumInst a</literal> is equivalent 
2048 to an explicit <literal>(Num a)</literal> dictionary.
2049 </para>
2050
2051 <para>
2052 The rest of this section gives further details about GADT-style data
2053 type declarations.
2054
2055 <itemizedlist>
2056 <listitem><para>
2057 The result type of each data constructor must begin with the type constructor being defined.
2058 If the result type of all constructors 
2059 has the form <literal>T a1 ... an</literal>, where <literal>a1 ... an</literal>
2060 are distinct type variables, then the data type is <emphasis>ordinary</emphasis>;
2061 otherwise is a <emphasis>generalised</emphasis> data type (<xref linkend="gadt"/>).
2062 </para></listitem>
2063
2064 <listitem><para>
2065 The type signature of
2066 each constructor is independent, and is implicitly universally quantified as usual. 
2067 Different constructors may have different universally-quantified type variables
2068 and different type-class constraints.  
2069 For example, this is fine:
2070 <programlisting>
2071   data T a where
2072     T1 :: Eq b => b -> T b
2073     T2 :: (Show c, Ix c) => c -> [c] -> T c
2074 </programlisting>
2075 </para></listitem>
2076
2077 <listitem><para>
2078 Unlike a Haskell-98-style 
2079 data type declaration, the type variable(s) in the "<literal>data Set a where</literal>" header 
2080 have no scope.  Indeed, one can write a kind signature instead:
2081 <programlisting>
2082   data Set :: * -> * where ...
2083 </programlisting>
2084 or even a mixture of the two:
2085 <programlisting>
2086   data Foo a :: (* -> *) -> * where ...
2087 </programlisting>
2088 The type variables (if given) may be explicitly kinded, so we could also write the header for <literal>Foo</literal>
2089 like this:
2090 <programlisting>
2091   data Foo a (b :: * -> *) where ...
2092 </programlisting>
2093 </para></listitem>
2094
2095
2096 <listitem><para>
2097 You can use strictness annotations, in the obvious places
2098 in the constructor type:
2099 <programlisting>
2100   data Term a where
2101       Lit    :: !Int -> Term Int
2102       If     :: Term Bool -> !(Term a) -> !(Term a) -> Term a
2103       Pair   :: Term a -> Term b -> Term (a,b)
2104 </programlisting>
2105 </para></listitem>
2106
2107 <listitem><para>
2108 You can use a <literal>deriving</literal> clause on a GADT-style data type
2109 declaration.   For example, these two declarations are equivalent
2110 <programlisting>
2111   data Maybe1 a where {
2112       Nothing1 :: Maybe1 a ;
2113       Just1    :: a -> Maybe1 a
2114     } deriving( Eq, Ord )
2115
2116   data Maybe2 a = Nothing2 | Just2 a 
2117        deriving( Eq, Ord )
2118 </programlisting>
2119 </para></listitem>
2120
2121 <listitem><para>
2122 You can use record syntax on a GADT-style data type declaration:
2123
2124 <programlisting>
2125   data Person where
2126       Adult { name :: String, children :: [Person] } :: Person
2127       Child { name :: String } :: Person
2128 </programlisting>
2129 As usual, for every constructor that has a field <literal>f</literal>, the type of
2130 field <literal>f</literal> must be the same (modulo alpha conversion).
2131 </para>
2132 <para>
2133 At the moment, record updates are not yet possible with GADT-style declarations, 
2134 so support is limited to record construction, selection and pattern matching.
2135 For exmaple
2136 <programlisting>
2137   aPerson = Adult { name = "Fred", children = [] }
2138
2139   shortName :: Person -> Bool
2140   hasChildren (Adult { children = kids }) = not (null kids)
2141   hasChildren (Child {})                  = False
2142 </programlisting>
2143 </para></listitem>
2144
2145 <listitem><para> 
2146 As in the case of existentials declared using the Haskell-98-like record syntax 
2147 (<xref linkend="existential-records"/>),
2148 record-selector functions are generated only for those fields that have well-typed
2149 selectors.  
2150 Here is the example of that section, in GADT-style syntax:
2151 <programlisting>
2152 data Counter a where
2153     NewCounter { _this    :: self
2154                , _inc     :: self -> self
2155                , _display :: self -> IO ()
2156                , tag      :: a
2157                }
2158         :: Counter a
2159 </programlisting>
2160 As before, only one selector function is generated here, that for <literal>tag</literal>.
2161 Nevertheless, you can still use all the field names in pattern matching and record construction.
2162 </para></listitem>
2163 </itemizedlist></para>
2164 </sect2>
2165
2166 <sect2 id="gadt">
2167 <title>Generalised Algebraic Data Types (GADTs)</title>
2168
2169 <para>Generalised Algebraic Data Types generalise ordinary algebraic data types 
2170 by allowing constructors to have richer return types.  Here is an example:
2171 <programlisting>
2172   data Term a where
2173       Lit    :: Int -> Term Int
2174       Succ   :: Term Int -> Term Int
2175       IsZero :: Term Int -> Term Bool   
2176       If     :: Term Bool -> Term a -> Term a -> Term a
2177       Pair   :: Term a -> Term b -> Term (a,b)
2178 </programlisting>
2179 Notice that the return type of the constructors is not always <literal>Term a</literal>, as is the
2180 case with ordinary data types.  This generality allows us to 
2181 write a well-typed <literal>eval</literal> function
2182 for these <literal>Terms</literal>:
2183 <programlisting>
2184   eval :: Term a -> a
2185   eval (Lit i)      = i
2186   eval (Succ t)     = 1 + eval t
2187   eval (IsZero t)   = eval t == 0
2188   eval (If b e1 e2) = if eval b then eval e1 else eval e2
2189   eval (Pair e1 e2) = (eval e1, eval e2)
2190 </programlisting>
2191 The key point about GADTs is that <emphasis>pattern matching causes type refinement</emphasis>.  
2192 For example, in the right hand side of the equation
2193 <programlisting>
2194   eval :: Term a -> a
2195   eval (Lit i) =  ...
2196 </programlisting>
2197 the type <literal>a</literal> is refined to <literal>Int</literal>.  That's the whole point!
2198 A precise specification of the type rules is beyond what this user manual aspires to, 
2199 but the design closely follows that described in
2200 the paper <ulink
2201 url="http://research.microsoft.com/%7Esimonpj/papers/gadt/index.htm">Simple
2202 unification-based type inference for GADTs</ulink>,
2203 (ICFP 2006).
2204 The general principle is this: <emphasis>type refinement is only carried out 
2205 based on user-supplied type annotations</emphasis>.
2206 So if no type signature is supplied for <literal>eval</literal>, no type refinement happens, 
2207 and lots of obscure error messages will
2208 occur.  However, the refinement is quite general.  For example, if we had:
2209 <programlisting>
2210   eval :: Term a -> a -> a
2211   eval (Lit i) j =  i+j
2212 </programlisting>
2213 the pattern match causes the type <literal>a</literal> to be refined to <literal>Int</literal> (because of the type
2214 of the constructor <literal>Lit</literal>), and that refinement also applies to the type of <literal>j</literal>, and
2215 the result type of the <literal>case</literal> expression.  Hence the addition <literal>i+j</literal> is legal.
2216 </para>
2217 <para>
2218 These and many other examples are given in papers by Hongwei Xi, and
2219 Tim Sheard. There is a longer introduction
2220 <ulink url="http://haskell.org/haskellwiki/GADT">on the wiki</ulink>,
2221 and Ralf Hinze's
2222 <ulink url="http://www.informatik.uni-bonn.de/~ralf/publications/With.pdf">Fun with phantom types</ulink> also has a number of examples. Note that papers
2223 may use different notation to that implemented in GHC.
2224 </para>
2225 <para>
2226 The rest of this section outlines the extensions to GHC that support GADTs.   The extension is enabled with 
2227 <option>-XGADTs</option>.
2228 <itemizedlist>
2229 <listitem><para>
2230 A GADT can only be declared using GADT-style syntax (<xref linkend="gadt-style"/>); 
2231 the old Haskell-98 syntax for data declarations always declares an ordinary data type.
2232 The result type of each constructor must begin with the type constructor being defined,
2233 but for a GADT the arguments to the type constructor can be arbitrary monotypes.  
2234 For example, in the <literal>Term</literal> data
2235 type above, the type of each constructor must end with <literal>Term ty</literal>, but
2236 the <literal>ty</literal> may not be a type variable (e.g. the <literal>Lit</literal>
2237 constructor).
2238 </para></listitem>
2239
2240 <listitem><para>
2241 You cannot use a <literal>deriving</literal> clause for a GADT; only for
2242 an ordianary data type.
2243 </para></listitem>
2244
2245 <listitem><para>
2246 As mentioned in <xref linkend="gadt-style"/>, record syntax is supported.
2247 For example:
2248 <programlisting>
2249   data Term a where
2250       Lit    { val  :: Int }      :: Term Int
2251       Succ   { num  :: Term Int } :: Term Int
2252       Pred   { num  :: Term Int } :: Term Int
2253       IsZero { arg  :: Term Int } :: Term Bool  
2254       Pair   { arg1 :: Term a
2255              , arg2 :: Term b
2256              }                    :: Term (a,b)
2257       If     { cnd  :: Term Bool
2258              , tru  :: Term a
2259              , fls  :: Term a
2260              }                    :: Term a
2261 </programlisting>
2262 However, for GADTs there is the following additional constraint: 
2263 every constructor that has a field <literal>f</literal> must have
2264 the same result type (modulo alpha conversion)
2265 Hence, in the above example, we cannot merge the <literal>num</literal> 
2266 and <literal>arg</literal> fields above into a 
2267 single name.  Although their field types are both <literal>Term Int</literal>,
2268 their selector functions actually have different types:
2269
2270 <programlisting>
2271   num :: Term Int -> Term Int
2272   arg :: Term Bool -> Term Int
2273 </programlisting>
2274 </para></listitem>
2275
2276 </itemizedlist>
2277 </para>
2278
2279 </sect2>
2280 </sect1>
2281
2282 <!-- ====================== End of Generalised algebraic data types =======================  -->
2283
2284 <sect1 id="deriving">
2285 <title>Extensions to the "deriving" mechanism</title>
2286
2287 <sect2 id="deriving-inferred">
2288 <title>Inferred context for deriving clauses</title>
2289
2290 <para>
2291 The Haskell Report is vague about exactly when a <literal>deriving</literal> clause is
2292 legal.  For example:
2293 <programlisting>
2294   data T0 f a = MkT0 a         deriving( Eq )
2295   data T1 f a = MkT1 (f a)     deriving( Eq )
2296   data T2 f a = MkT2 (f (f a)) deriving( Eq )
2297 </programlisting>
2298 The natural generated <literal>Eq</literal> code would result in these instance declarations:
2299 <programlisting>
2300   instance Eq a         => Eq (T0 f a) where ...
2301   instance Eq (f a)     => Eq (T1 f a) where ...
2302   instance Eq (f (f a)) => Eq (T2 f a) where ...
2303 </programlisting>
2304 The first of these is obviously fine. The second is still fine, although less obviously. 
2305 The third is not Haskell 98, and risks losing termination of instances.
2306 </para>
2307 <para>
2308 GHC takes a conservative position: it accepts the first two, but not the third.  The  rule is this:
2309 each constraint in the inferred instance context must consist only of type variables, 
2310 with no repititions.
2311 </para>
2312 <para>
2313 This rule is applied regardless of flags.  If you want a more exotic context, you can write
2314 it yourself, using the <link linkend="stand-alone-deriving">standalone deriving mechanism</link>.
2315 </para>
2316 </sect2>
2317
2318 <sect2 id="stand-alone-deriving">
2319 <title>Stand-alone deriving declarations</title>
2320
2321 <para>
2322 GHC now allows stand-alone <literal>deriving</literal> declarations, enabled by <literal>-XStandaloneDeriving</literal>:
2323 <programlisting>
2324   data Foo a = Bar a | Baz String
2325
2326   deriving instance Eq a => Eq (Foo a)
2327 </programlisting>
2328 The syntax is identical to that of an ordinary instance declaration apart from (a) the keyword
2329 <literal>deriving</literal>, and (b) the absence of the <literal>where</literal> part.
2330 You must supply a context (in the example the context is <literal>(Eq a)</literal>), 
2331 exactly as you would in an ordinary instance declaration.
2332 (In contrast the context is inferred in a <literal>deriving</literal> clause 
2333 attached to a data type declaration.) These <literal>deriving instance</literal>
2334 rules obey the same rules concerning form and termination as ordinary instance declarations,
2335 controlled by the same flags; see <xref linkend="instance-decls"/>. </para>
2336
2337 <para>The stand-alone syntax is generalised for newtypes in exactly the same
2338 way that ordinary <literal>deriving</literal> clauses are generalised (<xref linkend="newtype-deriving"/>).
2339 For example:
2340 <programlisting>
2341   newtype Foo a = MkFoo (State Int a)
2342
2343   deriving instance MonadState Int Foo
2344 </programlisting>
2345 GHC always treats the <emphasis>last</emphasis> parameter of the instance
2346 (<literal>Foo</literal> in this exmample) as the type whose instance is being derived.
2347 </para>
2348
2349 </sect2>
2350
2351
2352 <sect2 id="deriving-typeable">
2353 <title>Deriving clause for classes <literal>Typeable</literal> and <literal>Data</literal></title>
2354
2355 <para>
2356 Haskell 98 allows the programmer to add "<literal>deriving( Eq, Ord )</literal>" to a data type 
2357 declaration, to generate a standard instance declaration for classes specified in the <literal>deriving</literal> clause.  
2358 In Haskell 98, the only classes that may appear in the <literal>deriving</literal> clause are the standard
2359 classes <literal>Eq</literal>, <literal>Ord</literal>, 
2360 <literal>Enum</literal>, <literal>Ix</literal>, <literal>Bounded</literal>, <literal>Read</literal>, and <literal>Show</literal>.
2361 </para>
2362 <para>
2363 GHC extends this list with two more classes that may be automatically derived 
2364 (provided the <option>-XDeriveDataTypeable</option> flag is specified):
2365 <literal>Typeable</literal>, and <literal>Data</literal>.  These classes are defined in the library
2366 modules <literal>Data.Typeable</literal> and <literal>Data.Generics</literal> respectively, and the
2367 appropriate class must be in scope before it can be mentioned in the <literal>deriving</literal> clause.
2368 </para>
2369 <para>An instance of <literal>Typeable</literal> can only be derived if the
2370 data type has seven or fewer type parameters, all of kind <literal>*</literal>.
2371 The reason for this is that the <literal>Typeable</literal> class is derived using the scheme
2372 described in
2373 <ulink url="http://research.microsoft.com/%7Esimonpj/papers/hmap/gmap2.ps">
2374 Scrap More Boilerplate: Reflection, Zips, and Generalised Casts
2375 </ulink>.
2376 (Section 7.4 of the paper describes the multiple <literal>Typeable</literal> classes that
2377 are used, and only <literal>Typeable1</literal> up to
2378 <literal>Typeable7</literal> are provided in the library.)
2379 In other cases, there is nothing to stop the programmer writing a <literal>TypableX</literal>
2380 class, whose kind suits that of the data type constructor, and
2381 then writing the data type instance by hand.
2382 </para>
2383 </sect2>
2384
2385 <sect2 id="newtype-deriving">
2386 <title>Generalised derived instances for newtypes</title>
2387
2388 <para>
2389 When you define an abstract type using <literal>newtype</literal>, you may want
2390 the new type to inherit some instances from its representation. In
2391 Haskell 98, you can inherit instances of <literal>Eq</literal>, <literal>Ord</literal>,
2392 <literal>Enum</literal> and <literal>Bounded</literal> by deriving them, but for any
2393 other classes you have to write an explicit instance declaration. For
2394 example, if you define
2395
2396 <programlisting> 
2397   newtype Dollars = Dollars Int 
2398 </programlisting> 
2399
2400 and you want to use arithmetic on <literal>Dollars</literal>, you have to
2401 explicitly define an instance of <literal>Num</literal>:
2402
2403 <programlisting> 
2404   instance Num Dollars where
2405     Dollars a + Dollars b = Dollars (a+b)
2406     ...
2407 </programlisting>
2408 All the instance does is apply and remove the <literal>newtype</literal>
2409 constructor. It is particularly galling that, since the constructor
2410 doesn't appear at run-time, this instance declaration defines a
2411 dictionary which is <emphasis>wholly equivalent</emphasis> to the <literal>Int</literal>
2412 dictionary, only slower!
2413 </para>
2414
2415
2416 <sect3> <title> Generalising the deriving clause </title>
2417 <para>
2418 GHC now permits such instances to be derived instead, 
2419 using the flag <option>-XGeneralizedNewtypeDeriving</option>,
2420 so one can write 
2421 <programlisting> 
2422   newtype Dollars = Dollars Int deriving (Eq,Show,Num)
2423 </programlisting> 
2424
2425 and the implementation uses the <emphasis>same</emphasis> <literal>Num</literal> dictionary
2426 for <literal>Dollars</literal> as for <literal>Int</literal>. Notionally, the compiler
2427 derives an instance declaration of the form
2428
2429 <programlisting> 
2430   instance Num Int => Num Dollars
2431 </programlisting> 
2432
2433 which just adds or removes the <literal>newtype</literal> constructor according to the type.
2434 </para>
2435 <para>
2436
2437 We can also derive instances of constructor classes in a similar
2438 way. For example, suppose we have implemented state and failure monad
2439 transformers, such that
2440
2441 <programlisting> 
2442   instance Monad m => Monad (State s m) 
2443   instance Monad m => Monad (Failure m)
2444 </programlisting> 
2445 In Haskell 98, we can define a parsing monad by 
2446 <programlisting> 
2447   type Parser tok m a = State [tok] (Failure m) a
2448 </programlisting> 
2449
2450 which is automatically a monad thanks to the instance declarations
2451 above. With the extension, we can make the parser type abstract,
2452 without needing to write an instance of class <literal>Monad</literal>, via
2453
2454 <programlisting> 
2455   newtype Parser tok m a = Parser (State [tok] (Failure m) a)
2456                          deriving Monad
2457 </programlisting>
2458 In this case the derived instance declaration is of the form 
2459 <programlisting> 
2460   instance Monad (State [tok] (Failure m)) => Monad (Parser tok m) 
2461 </programlisting> 
2462
2463 Notice that, since <literal>Monad</literal> is a constructor class, the
2464 instance is a <emphasis>partial application</emphasis> of the new type, not the
2465 entire left hand side. We can imagine that the type declaration is
2466 "eta-converted" to generate the context of the instance
2467 declaration.
2468 </para>
2469 <para>
2470
2471 We can even derive instances of multi-parameter classes, provided the
2472 newtype is the last class parameter. In this case, a ``partial
2473 application'' of the class appears in the <literal>deriving</literal>
2474 clause. For example, given the class
2475
2476 <programlisting> 
2477   class StateMonad s m | m -> s where ... 
2478   instance Monad m => StateMonad s (State s m) where ... 
2479 </programlisting> 
2480 then we can derive an instance of <literal>StateMonad</literal> for <literal>Parser</literal>s by 
2481 <programlisting> 
2482   newtype Parser tok m a = Parser (State [tok] (Failure m) a)
2483                          deriving (Monad, StateMonad [tok])
2484 </programlisting>
2485
2486 The derived instance is obtained by completing the application of the
2487 class to the new type:
2488
2489 <programlisting> 
2490   instance StateMonad [tok] (State [tok] (Failure m)) =>
2491            StateMonad [tok] (Parser tok m)
2492 </programlisting>
2493 </para>
2494 <para>
2495
2496 As a result of this extension, all derived instances in newtype
2497  declarations are treated uniformly (and implemented just by reusing
2498 the dictionary for the representation type), <emphasis>except</emphasis>
2499 <literal>Show</literal> and <literal>Read</literal>, which really behave differently for
2500 the newtype and its representation.
2501 </para>
2502 </sect3>
2503
2504 <sect3> <title> A more precise specification </title>
2505 <para>
2506 Derived instance declarations are constructed as follows. Consider the
2507 declaration (after expansion of any type synonyms)
2508
2509 <programlisting> 
2510   newtype T v1...vn = T' (t vk+1...vn) deriving (c1...cm) 
2511 </programlisting> 
2512
2513 where 
2514  <itemizedlist>
2515 <listitem><para>
2516   The <literal>ci</literal> are partial applications of
2517   classes of the form <literal>C t1'...tj'</literal>, where the arity of <literal>C</literal>
2518   is exactly <literal>j+1</literal>.  That is, <literal>C</literal> lacks exactly one type argument.
2519 </para></listitem>
2520 <listitem><para>
2521   The <literal>k</literal> is chosen so that <literal>ci (T v1...vk)</literal> is well-kinded.
2522 </para></listitem>
2523 <listitem><para>
2524   The type <literal>t</literal> is an arbitrary type.
2525 </para></listitem>
2526 <listitem><para>
2527   The type variables <literal>vk+1...vn</literal> do not occur in <literal>t</literal>, 
2528   nor in the <literal>ci</literal>, and
2529 </para></listitem>
2530 <listitem><para>
2531   None of the <literal>ci</literal> is <literal>Read</literal>, <literal>Show</literal>, 
2532                 <literal>Typeable</literal>, or <literal>Data</literal>.  These classes
2533                 should not "look through" the type or its constructor.  You can still
2534                 derive these classes for a newtype, but it happens in the usual way, not 
2535                 via this new mechanism.  
2536 </para></listitem>
2537 </itemizedlist>
2538 Then, for each <literal>ci</literal>, the derived instance
2539 declaration is:
2540 <programlisting> 
2541   instance ci t => ci (T v1...vk)
2542 </programlisting>
2543 As an example which does <emphasis>not</emphasis> work, consider 
2544 <programlisting> 
2545   newtype NonMonad m s = NonMonad (State s m s) deriving Monad 
2546 </programlisting> 
2547 Here we cannot derive the instance 
2548 <programlisting> 
2549   instance Monad (State s m) => Monad (NonMonad m) 
2550 </programlisting> 
2551
2552 because the type variable <literal>s</literal> occurs in <literal>State s m</literal>,
2553 and so cannot be "eta-converted" away. It is a good thing that this
2554 <literal>deriving</literal> clause is rejected, because <literal>NonMonad m</literal> is
2555 not, in fact, a monad --- for the same reason. Try defining
2556 <literal>>>=</literal> with the correct type: you won't be able to.
2557 </para>
2558 <para>
2559
2560 Notice also that the <emphasis>order</emphasis> of class parameters becomes
2561 important, since we can only derive instances for the last one. If the
2562 <literal>StateMonad</literal> class above were instead defined as
2563
2564 <programlisting> 
2565   class StateMonad m s | m -> s where ... 
2566 </programlisting>
2567
2568 then we would not have been able to derive an instance for the
2569 <literal>Parser</literal> type above. We hypothesise that multi-parameter
2570 classes usually have one "main" parameter for which deriving new
2571 instances is most interesting.
2572 </para>
2573 <para>Lastly, all of this applies only for classes other than
2574 <literal>Read</literal>, <literal>Show</literal>, <literal>Typeable</literal>, 
2575 and <literal>Data</literal>, for which the built-in derivation applies (section
2576 4.3.3. of the Haskell Report).
2577 (For the standard classes <literal>Eq</literal>, <literal>Ord</literal>,
2578 <literal>Ix</literal>, and <literal>Bounded</literal> it is immaterial whether
2579 the standard method is used or the one described here.)
2580 </para>
2581 </sect3>
2582 </sect2>
2583 </sect1>
2584
2585
2586 <!-- TYPE SYSTEM EXTENSIONS -->
2587 <sect1 id="type-class-extensions">
2588 <title>Class and instances declarations</title>
2589
2590 <sect2 id="multi-param-type-classes">
2591 <title>Class declarations</title>
2592
2593 <para>
2594 This section, and the next one, documents GHC's type-class extensions.
2595 There's lots of background in the paper <ulink
2596 url="http://research.microsoft.com/~simonpj/Papers/type-class-design-space" >Type
2597 classes: exploring the design space</ulink > (Simon Peyton Jones, Mark
2598 Jones, Erik Meijer).
2599 </para>
2600 <para>
2601 All the extensions are enabled by the <option>-fglasgow-exts</option> flag.
2602 </para>
2603
2604 <sect3>
2605 <title>Multi-parameter type classes</title>
2606 <para>
2607 Multi-parameter type classes are permitted. For example:
2608
2609
2610 <programlisting>
2611   class Collection c a where
2612     union :: c a -> c a -> c a
2613     ...etc.
2614 </programlisting>
2615
2616 </para>
2617 </sect3>
2618
2619 <sect3>
2620 <title>The superclasses of a class declaration</title>
2621
2622 <para>
2623 There are no restrictions on the context in a class declaration
2624 (which introduces superclasses), except that the class hierarchy must
2625 be acyclic.  So these class declarations are OK:
2626
2627
2628 <programlisting>
2629   class Functor (m k) => FiniteMap m k where
2630     ...
2631
2632   class (Monad m, Monad (t m)) => Transform t m where
2633     lift :: m a -> (t m) a
2634 </programlisting>
2635
2636
2637 </para>
2638 <para>
2639 As in Haskell 98, The class hierarchy must be acyclic.  However, the definition
2640 of "acyclic" involves only the superclass relationships.  For example,
2641 this is OK:
2642
2643
2644 <programlisting>
2645   class C a where {
2646     op :: D b => a -> b -> b
2647   }
2648
2649   class C a => D a where { ... }
2650 </programlisting>
2651
2652
2653 Here, <literal>C</literal> is a superclass of <literal>D</literal>, but it's OK for a
2654 class operation <literal>op</literal> of <literal>C</literal> to mention <literal>D</literal>.  (It
2655 would not be OK for <literal>D</literal> to be a superclass of <literal>C</literal>.)
2656 </para>
2657 </sect3>
2658
2659
2660
2661
2662 <sect3 id="class-method-types">
2663 <title>Class method types</title>
2664
2665 <para>
2666 Haskell 98 prohibits class method types to mention constraints on the
2667 class type variable, thus:
2668 <programlisting>
2669   class Seq s a where
2670     fromList :: [a] -> s a
2671     elem     :: Eq a => a -> s a -> Bool
2672 </programlisting>
2673 The type of <literal>elem</literal> is illegal in Haskell 98, because it
2674 contains the constraint <literal>Eq a</literal>, constrains only the 
2675 class type variable (in this case <literal>a</literal>).
2676 GHC lifts this restriction.
2677 </para>
2678
2679
2680 </sect3>
2681 </sect2>
2682
2683 <sect2 id="functional-dependencies">
2684 <title>Functional dependencies
2685 </title>
2686
2687 <para> Functional dependencies are implemented as described by Mark Jones
2688 in &ldquo;<ulink url="http://www.cse.ogi.edu/~mpj/pubs/fundeps.html">Type Classes with Functional Dependencies</ulink>&rdquo;, Mark P. Jones, 
2689 In Proceedings of the 9th European Symposium on Programming, 
2690 ESOP 2000, Berlin, Germany, March 2000, Springer-Verlag LNCS 1782,
2691 .
2692 </para>
2693 <para>
2694 Functional dependencies are introduced by a vertical bar in the syntax of a 
2695 class declaration;  e.g. 
2696 <programlisting>
2697   class (Monad m) => MonadState s m | m -> s where ...
2698
2699   class Foo a b c | a b -> c where ...
2700 </programlisting>
2701 There should be more documentation, but there isn't (yet).  Yell if you need it.
2702 </para>
2703
2704 <sect3><title>Rules for functional dependencies </title>
2705 <para>
2706 In a class declaration, all of the class type variables must be reachable (in the sense 
2707 mentioned in <xref linkend="type-restrictions"/>)
2708 from the free variables of each method type.
2709 For example:
2710
2711 <programlisting>
2712   class Coll s a where
2713     empty  :: s
2714     insert :: s -> a -> s
2715 </programlisting>
2716
2717 is not OK, because the type of <literal>empty</literal> doesn't mention
2718 <literal>a</literal>.  Functional dependencies can make the type variable
2719 reachable:
2720 <programlisting>
2721   class Coll s a | s -> a where
2722     empty  :: s
2723     insert :: s -> a -> s
2724 </programlisting>
2725
2726 Alternatively <literal>Coll</literal> might be rewritten
2727
2728 <programlisting>
2729   class Coll s a where
2730     empty  :: s a
2731     insert :: s a -> a -> s a
2732 </programlisting>
2733
2734
2735 which makes the connection between the type of a collection of
2736 <literal>a</literal>'s (namely <literal>(s a)</literal>) and the element type <literal>a</literal>.
2737 Occasionally this really doesn't work, in which case you can split the
2738 class like this:
2739
2740
2741 <programlisting>
2742   class CollE s where
2743     empty  :: s
2744
2745   class CollE s => Coll s a where
2746     insert :: s -> a -> s
2747 </programlisting>
2748 </para>
2749 </sect3>
2750
2751
2752 <sect3>
2753 <title>Background on functional dependencies</title>
2754
2755 <para>The following description of the motivation and use of functional dependencies is taken
2756 from the Hugs user manual, reproduced here (with minor changes) by kind
2757 permission of Mark Jones.
2758 </para>
2759 <para> 
2760 Consider the following class, intended as part of a
2761 library for collection types:
2762 <programlisting>
2763    class Collects e ce where
2764        empty  :: ce
2765        insert :: e -> ce -> ce
2766        member :: e -> ce -> Bool
2767 </programlisting>
2768 The type variable e used here represents the element type, while ce is the type
2769 of the container itself. Within this framework, we might want to define
2770 instances of this class for lists or characteristic functions (both of which
2771 can be used to represent collections of any equality type), bit sets (which can
2772 be used to represent collections of characters), or hash tables (which can be
2773 used to represent any collection whose elements have a hash function). Omitting
2774 standard implementation details, this would lead to the following declarations: 
2775 <programlisting>
2776    instance Eq e => Collects e [e] where ...
2777    instance Eq e => Collects e (e -> Bool) where ...
2778    instance Collects Char BitSet where ...
2779    instance (Hashable e, Collects a ce)
2780               => Collects e (Array Int ce) where ...
2781 </programlisting>
2782 All this looks quite promising; we have a class and a range of interesting
2783 implementations. Unfortunately, there are some serious problems with the class
2784 declaration. First, the empty function has an ambiguous type: 
2785 <programlisting>
2786    empty :: Collects e ce => ce
2787 </programlisting>
2788 By "ambiguous" we mean that there is a type variable e that appears on the left
2789 of the <literal>=&gt;</literal> symbol, but not on the right. The problem with
2790 this is that, according to the theoretical foundations of Haskell overloading,
2791 we cannot guarantee a well-defined semantics for any term with an ambiguous
2792 type.
2793 </para>
2794 <para>
2795 We can sidestep this specific problem by removing the empty member from the
2796 class declaration. However, although the remaining members, insert and member,
2797 do not have ambiguous types, we still run into problems when we try to use
2798 them. For example, consider the following two functions: 
2799 <programlisting>
2800    f x y = insert x . insert y
2801    g     = f True 'a'
2802 </programlisting>
2803 for which GHC infers the following types: 
2804 <programlisting>
2805    f :: (Collects a c, Collects b c) => a -> b -> c -> c
2806    g :: (Collects Bool c, Collects Char c) => c -> c
2807 </programlisting>
2808 Notice that the type for f allows the two parameters x and y to be assigned
2809 different types, even though it attempts to insert each of the two values, one
2810 after the other, into the same collection. If we're trying to model collections
2811 that contain only one type of value, then this is clearly an inaccurate
2812 type. Worse still, the definition for g is accepted, without causing a type
2813 error. As a result, the error in this code will not be flagged at the point
2814 where it appears. Instead, it will show up only when we try to use g, which
2815 might even be in a different module.
2816 </para>
2817
2818 <sect4><title>An attempt to use constructor classes</title>
2819
2820 <para>
2821 Faced with the problems described above, some Haskell programmers might be
2822 tempted to use something like the following version of the class declaration: 
2823 <programlisting>
2824    class Collects e c where
2825       empty  :: c e
2826       insert :: e -> c e -> c e
2827       member :: e -> c e -> Bool
2828 </programlisting>
2829 The key difference here is that we abstract over the type constructor c that is
2830 used to form the collection type c e, and not over that collection type itself,
2831 represented by ce in the original class declaration. This avoids the immediate
2832 problems that we mentioned above: empty has type <literal>Collects e c => c
2833 e</literal>, which is not ambiguous. 
2834 </para>
2835 <para>
2836 The function f from the previous section has a more accurate type: 
2837 <programlisting>
2838    f :: (Collects e c) => e -> e -> c e -> c e
2839 </programlisting>
2840 The function g from the previous section is now rejected with a type error as
2841 we would hope because the type of f does not allow the two arguments to have
2842 different types. 
2843 This, then, is an example of a multiple parameter class that does actually work
2844 quite well in practice, without ambiguity problems.
2845 There is, however, a catch. This version of the Collects class is nowhere near
2846 as general as the original class seemed to be: only one of the four instances
2847 for <literal>Collects</literal>
2848 given above can be used with this version of Collects because only one of
2849 them---the instance for lists---has a collection type that can be written in
2850 the form c e, for some type constructor c, and element type e.
2851 </para>
2852 </sect4>
2853
2854 <sect4><title>Adding functional dependencies</title>
2855
2856 <para>
2857 To get a more useful version of the Collects class, Hugs provides a mechanism
2858 that allows programmers to specify dependencies between the parameters of a
2859 multiple parameter class (For readers with an interest in theoretical
2860 foundations and previous work: The use of dependency information can be seen
2861 both as a generalization of the proposal for `parametric type classes' that was
2862 put forward by Chen, Hudak, and Odersky, or as a special case of Mark Jones's
2863 later framework for "improvement" of qualified types. The
2864 underlying ideas are also discussed in a more theoretical and abstract setting
2865 in a manuscript [implparam], where they are identified as one point in a
2866 general design space for systems of implicit parameterization.).
2867
2868 To start with an abstract example, consider a declaration such as: 
2869 <programlisting>
2870    class C a b where ...
2871 </programlisting>
2872 which tells us simply that C can be thought of as a binary relation on types
2873 (or type constructors, depending on the kinds of a and b). Extra clauses can be
2874 included in the definition of classes to add information about dependencies
2875 between parameters, as in the following examples: 
2876 <programlisting>
2877    class D a b | a -> b where ...
2878    class E a b | a -> b, b -> a where ...
2879 </programlisting>
2880 The notation <literal>a -&gt; b</literal> used here between the | and where
2881 symbols --- not to be
2882 confused with a function type --- indicates that the a parameter uniquely
2883 determines the b parameter, and might be read as "a determines b." Thus D is
2884 not just a relation, but actually a (partial) function. Similarly, from the two
2885 dependencies that are included in the definition of E, we can see that E
2886 represents a (partial) one-one mapping between types.
2887 </para>
2888 <para>
2889 More generally, dependencies take the form <literal>x1 ... xn -&gt; y1 ... ym</literal>,
2890 where x1, ..., xn, and y1, ..., yn are type variables with n&gt;0 and
2891 m&gt;=0, meaning that the y parameters are uniquely determined by the x
2892 parameters. Spaces can be used as separators if more than one variable appears
2893 on any single side of a dependency, as in <literal>t -&gt; a b</literal>. Note that a class may be
2894 annotated with multiple dependencies using commas as separators, as in the
2895 definition of E above. Some dependencies that we can write in this notation are
2896 redundant, and will be rejected because they don't serve any useful
2897 purpose, and may instead indicate an error in the program. Examples of
2898 dependencies like this include  <literal>a -&gt; a </literal>,  
2899 <literal>a -&gt; a a </literal>,  
2900 <literal>a -&gt; </literal>, etc. There can also be
2901 some redundancy if multiple dependencies are given, as in  
2902 <literal>a-&gt;b</literal>, 
2903  <literal>b-&gt;c </literal>,  <literal>a-&gt;c </literal>, and
2904 in which some subset implies the remaining dependencies. Examples like this are
2905 not treated as errors. Note that dependencies appear only in class
2906 declarations, and not in any other part of the language. In particular, the
2907 syntax for instance declarations, class constraints, and types is completely
2908 unchanged.
2909 </para>
2910 <para>
2911 By including dependencies in a class declaration, we provide a mechanism for
2912 the programmer to specify each multiple parameter class more precisely. The
2913 compiler, on the other hand, is responsible for ensuring that the set of
2914 instances that are in scope at any given point in the program is consistent
2915 with any declared dependencies. For example, the following pair of instance
2916 declarations cannot appear together in the same scope because they violate the
2917 dependency for D, even though either one on its own would be acceptable: 
2918 <programlisting>
2919    instance D Bool Int where ...
2920    instance D Bool Char where ...
2921 </programlisting>
2922 Note also that the following declaration is not allowed, even by itself: 
2923 <programlisting>
2924    instance D [a] b where ...
2925 </programlisting>
2926 The problem here is that this instance would allow one particular choice of [a]
2927 to be associated with more than one choice for b, which contradicts the
2928 dependency specified in the definition of D. More generally, this means that,
2929 in any instance of the form: 
2930 <programlisting>
2931    instance D t s where ...
2932 </programlisting>
2933 for some particular types t and s, the only variables that can appear in s are
2934 the ones that appear in t, and hence, if the type t is known, then s will be
2935 uniquely determined.
2936 </para>
2937 <para>
2938 The benefit of including dependency information is that it allows us to define
2939 more general multiple parameter classes, without ambiguity problems, and with
2940 the benefit of more accurate types. To illustrate this, we return to the
2941 collection class example, and annotate the original definition of <literal>Collects</literal>
2942 with a simple dependency: 
2943 <programlisting>
2944    class Collects e ce | ce -> e where
2945       empty  :: ce
2946       insert :: e -> ce -> ce
2947       member :: e -> ce -> Bool
2948 </programlisting>
2949 The dependency <literal>ce -&gt; e</literal> here specifies that the type e of elements is uniquely
2950 determined by the type of the collection ce. Note that both parameters of
2951 Collects are of kind *; there are no constructor classes here. Note too that
2952 all of the instances of Collects that we gave earlier can be used
2953 together with this new definition.
2954 </para>
2955 <para>
2956 What about the ambiguity problems that we encountered with the original
2957 definition? The empty function still has type Collects e ce => ce, but it is no
2958 longer necessary to regard that as an ambiguous type: Although the variable e
2959 does not appear on the right of the => symbol, the dependency for class
2960 Collects tells us that it is uniquely determined by ce, which does appear on
2961 the right of the => symbol. Hence the context in which empty is used can still
2962 give enough information to determine types for both ce and e, without
2963 ambiguity. More generally, we need only regard a type as ambiguous if it
2964 contains a variable on the left of the => that is not uniquely determined
2965 (either directly or indirectly) by the variables on the right.
2966 </para>
2967 <para>
2968 Dependencies also help to produce more accurate types for user defined
2969 functions, and hence to provide earlier detection of errors, and less cluttered
2970 types for programmers to work with. Recall the previous definition for a
2971 function f: 
2972 <programlisting>
2973    f x y = insert x y = insert x . insert y
2974 </programlisting>
2975 for which we originally obtained a type: 
2976 <programlisting>
2977    f :: (Collects a c, Collects b c) => a -> b -> c -> c
2978 </programlisting>
2979 Given the dependency information that we have for Collects, however, we can
2980 deduce that a and b must be equal because they both appear as the second
2981 parameter in a Collects constraint with the same first parameter c. Hence we
2982 can infer a shorter and more accurate type for f: 
2983 <programlisting>
2984    f :: (Collects a c) => a -> a -> c -> c
2985 </programlisting>
2986 In a similar way, the earlier definition of g will now be flagged as a type error.
2987 </para>
2988 <para>
2989 Although we have given only a few examples here, it should be clear that the
2990 addition of dependency information can help to make multiple parameter classes
2991 more useful in practice, avoiding ambiguity problems, and allowing more general
2992 sets of instance declarations.
2993 </para>
2994 </sect4>
2995 </sect3>
2996 </sect2>
2997
2998 <sect2 id="instance-decls">
2999 <title>Instance declarations</title>
3000
3001 <sect3 id="instance-rules">
3002 <title>Relaxed rules for instance declarations</title>
3003
3004 <para>An instance declaration has the form
3005 <screen>
3006   instance ( <replaceable>assertion</replaceable><subscript>1</subscript>, ..., <replaceable>assertion</replaceable><subscript>n</subscript>) =&gt; <replaceable>class</replaceable> <replaceable>type</replaceable><subscript>1</subscript> ... <replaceable>type</replaceable><subscript>m</subscript> where ...
3007 </screen>
3008 The part before the "<literal>=&gt;</literal>" is the
3009 <emphasis>context</emphasis>, while the part after the
3010 "<literal>=&gt;</literal>" is the <emphasis>head</emphasis> of the instance declaration.
3011 </para>
3012
3013 <para>
3014 In Haskell 98 the head of an instance declaration
3015 must be of the form <literal>C (T a1 ... an)</literal>, where
3016 <literal>C</literal> is the class, <literal>T</literal> is a type constructor,
3017 and the <literal>a1 ... an</literal> are distinct type variables.
3018 Furthermore, the assertions in the context of the instance declaration
3019 must be of the form <literal>C a</literal> where <literal>a</literal>
3020 is a type variable that occurs in the head.
3021 </para>
3022 <para>
3023 The <option>-fglasgow-exts</option> flag loosens these restrictions
3024 considerably.  Firstly, multi-parameter type classes are permitted.  Secondly,
3025 the context and head of the instance declaration can each consist of arbitrary
3026 (well-kinded) assertions <literal>(C t1 ... tn)</literal> subject only to the
3027 following rules:
3028 <orderedlist>
3029 <listitem><para>
3030 The Paterson Conditions: for each assertion in the context
3031 <orderedlist>
3032 <listitem><para>No type variable has more occurrences in the assertion than in the head</para></listitem>
3033 <listitem><para>The assertion has fewer constructors and variables (taken together
3034       and counting repetitions) than the head</para></listitem>
3035 </orderedlist>
3036 </para></listitem>
3037
3038 <listitem><para>The Coverage Condition.  For each functional dependency,
3039 <replaceable>tvs</replaceable><subscript>left</subscript> <literal>-&gt;</literal>
3040 <replaceable>tvs</replaceable><subscript>right</subscript>,  of the class,
3041 every type variable in
3042 S(<replaceable>tvs</replaceable><subscript>right</subscript>) must appear in 
3043 S(<replaceable>tvs</replaceable><subscript>left</subscript>), where S is the
3044 substitution mapping each type variable in the class declaration to the
3045 corresponding type in the instance declaration.
3046 </para></listitem>
3047 </orderedlist>
3048 These restrictions ensure that context reduction terminates: each reduction
3049 step makes the problem smaller by at least one
3050 constructor.  Both the Paterson Conditions and the Coverage Condition are lifted 
3051 if you give the <option>-fallow-undecidable-instances</option> 
3052 flag (<xref linkend="undecidable-instances"/>).
3053 You can find lots of background material about the reason for these
3054 restrictions in the paper <ulink
3055 url="http://research.microsoft.com/%7Esimonpj/papers/fd%2Dchr/">
3056 Understanding functional dependencies via Constraint Handling Rules</ulink>.
3057 </para>
3058 <para>
3059 For example, these are OK:
3060 <programlisting>
3061   instance C Int [a]          -- Multiple parameters
3062   instance Eq (S [a])         -- Structured type in head
3063
3064       -- Repeated type variable in head
3065   instance C4 a a => C4 [a] [a] 
3066   instance Stateful (ST s) (MutVar s)
3067
3068       -- Head can consist of type variables only
3069   instance C a
3070   instance (Eq a, Show b) => C2 a b
3071
3072       -- Non-type variables in context
3073   instance Show (s a) => Show (Sized s a)
3074   instance C2 Int a => C3 Bool [a]
3075   instance C2 Int a => C3 [a] b
3076 </programlisting>
3077 But these are not:
3078 <programlisting>
3079       -- Context assertion no smaller than head
3080   instance C a => C a where ...
3081       -- (C b b) has more more occurrences of b than the head
3082   instance C b b => Foo [b] where ...
3083 </programlisting>
3084 </para>
3085
3086 <para>
3087 The same restrictions apply to instances generated by
3088 <literal>deriving</literal> clauses.  Thus the following is accepted:
3089 <programlisting>
3090   data MinHeap h a = H a (h a)
3091     deriving (Show)
3092 </programlisting>
3093 because the derived instance
3094 <programlisting>
3095   instance (Show a, Show (h a)) => Show (MinHeap h a)
3096 </programlisting>
3097 conforms to the above rules.
3098 </para>
3099
3100 <para>
3101 A useful idiom permitted by the above rules is as follows.
3102 If one allows overlapping instance declarations then it's quite
3103 convenient to have a "default instance" declaration that applies if
3104 something more specific does not:
3105 <programlisting>
3106   instance C a where
3107     op = ... -- Default
3108 </programlisting>
3109 </para>
3110 </sect3>
3111
3112 <sect3 id="undecidable-instances">
3113 <title>Undecidable instances</title>
3114
3115 <para>
3116 Sometimes even the rules of <xref linkend="instance-rules"/> are too onerous.
3117 For example, sometimes you might want to use the following to get the
3118 effect of a "class synonym":
3119 <programlisting>
3120   class (C1 a, C2 a, C3 a) => C a where { }
3121
3122   instance (C1 a, C2 a, C3 a) => C a where { }
3123 </programlisting>
3124 This allows you to write shorter signatures:
3125 <programlisting>
3126   f :: C a => ...
3127 </programlisting>
3128 instead of
3129 <programlisting>
3130   f :: (C1 a, C2 a, C3 a) => ...
3131 </programlisting>
3132 The restrictions on functional dependencies (<xref
3133 linkend="functional-dependencies"/>) are particularly troublesome.
3134 It is tempting to introduce type variables in the context that do not appear in
3135 the head, something that is excluded by the normal rules. For example:
3136 <programlisting>
3137   class HasConverter a b | a -> b where
3138      convert :: a -> b
3139    
3140   data Foo a = MkFoo a
3141
3142   instance (HasConverter a b,Show b) => Show (Foo a) where
3143      show (MkFoo value) = show (convert value)
3144 </programlisting>
3145 This is dangerous territory, however. Here, for example, is a program that would make the
3146 typechecker loop:
3147 <programlisting>
3148   class D a
3149   class F a b | a->b
3150   instance F [a] [[a]]
3151   instance (D c, F a c) => D [a]   -- 'c' is not mentioned in the head
3152 </programlisting>  
3153 Similarly, it can be tempting to lift the coverage condition:
3154 <programlisting>
3155   class Mul a b c | a b -> c where
3156         (.*.) :: a -> b -> c
3157
3158   instance Mul Int Int Int where (.*.) = (*)
3159   instance Mul Int Float Float where x .*. y = fromIntegral x * y
3160   instance Mul a b c => Mul a [b] [c] where x .*. v = map (x.*.) v
3161 </programlisting>
3162 The third instance declaration does not obey the coverage condition;
3163 and indeed the (somewhat strange) definition:
3164 <programlisting>
3165   f = \ b x y -> if b then x .*. [y] else y
3166 </programlisting>
3167 makes instance inference go into a loop, because it requires the constraint
3168 <literal>(Mul a [b] b)</literal>.
3169 </para>
3170 <para>
3171 Nevertheless, GHC allows you to experiment with more liberal rules.  If you use
3172 the experimental flag <option>-XUndecidableInstances</option>
3173 <indexterm><primary>-XUndecidableInstances</primary></indexterm>, 
3174 both the Paterson Conditions and the Coverage Condition
3175 (described in <xref linkend="instance-rules"/>) are lifted.  Termination is ensured by having a
3176 fixed-depth recursion stack.  If you exceed the stack depth you get a
3177 sort of backtrace, and the opportunity to increase the stack depth
3178 with <option>-fcontext-stack=</option><emphasis>N</emphasis>.
3179 </para>
3180
3181 </sect3>
3182
3183
3184 <sect3 id="instance-overlap">
3185 <title>Overlapping instances</title>
3186 <para>
3187 In general, <emphasis>GHC requires that that it be unambiguous which instance
3188 declaration
3189 should be used to resolve a type-class constraint</emphasis>. This behaviour
3190 can be modified by two flags: <option>-XOverlappingInstances</option>
3191 <indexterm><primary>-XOverlappingInstances
3192 </primary></indexterm> 
3193 and <option>-XIncoherentInstances</option>
3194 <indexterm><primary>-XIncoherentInstances
3195 </primary></indexterm>, as this section discusses.  Both these
3196 flags are dynamic flags, and can be set on a per-module basis, using 
3197 an <literal>OPTIONS_GHC</literal> pragma if desired (<xref linkend="source-file-options"/>).</para>
3198 <para>
3199 When GHC tries to resolve, say, the constraint <literal>C Int Bool</literal>,
3200 it tries to match every instance declaration against the
3201 constraint,
3202 by instantiating the head of the instance declaration.  For example, consider
3203 these declarations:
3204 <programlisting>
3205   instance context1 => C Int a     where ...  -- (A)
3206   instance context2 => C a   Bool  where ...  -- (B)
3207   instance context3 => C Int [a]   where ...  -- (C)
3208   instance context4 => C Int [Int] where ...  -- (D)
3209 </programlisting>
3210 The instances (A) and (B) match the constraint <literal>C Int Bool</literal>, 
3211 but (C) and (D) do not.  When matching, GHC takes
3212 no account of the context of the instance declaration
3213 (<literal>context1</literal> etc).
3214 GHC's default behaviour is that <emphasis>exactly one instance must match the
3215 constraint it is trying to resolve</emphasis>.  
3216 It is fine for there to be a <emphasis>potential</emphasis> of overlap (by
3217 including both declarations (A) and (B), say); an error is only reported if a 
3218 particular constraint matches more than one.
3219 </para>
3220
3221 <para>
3222 The <option>-XOverlappingInstances</option> flag instructs GHC to allow
3223 more than one instance to match, provided there is a most specific one.  For
3224 example, the constraint <literal>C Int [Int]</literal> matches instances (A),
3225 (C) and (D), but the last is more specific, and hence is chosen.  If there is no
3226 most-specific match, the program is rejected.
3227 </para>
3228 <para>
3229 However, GHC is conservative about committing to an overlapping instance.  For example:
3230 <programlisting>
3231   f :: [b] -> [b]
3232   f x = ...
3233 </programlisting>
3234 Suppose that from the RHS of <literal>f</literal> we get the constraint
3235 <literal>C Int [b]</literal>.  But
3236 GHC does not commit to instance (C), because in a particular
3237 call of <literal>f</literal>, <literal>b</literal> might be instantiate 
3238 to <literal>Int</literal>, in which case instance (D) would be more specific still.
3239 So GHC rejects the program.  
3240 (If you add the flag <option>-XIncoherentInstances</option>,
3241 GHC will instead pick (C), without complaining about 
3242 the problem of subsequent instantiations.)
3243 </para>
3244 <para>
3245 Notice that we gave a type signature to <literal>f</literal>, so GHC had to
3246 <emphasis>check</emphasis> that <literal>f</literal> has the specified type.  
3247 Suppose instead we do not give a type signature, asking GHC to <emphasis>infer</emphasis>
3248 it instead.  In this case, GHC will refrain from
3249 simplifying the constraint <literal>C Int [Int]</literal> (for the same reason
3250 as before) but, rather than rejecting the program, it will infer the type
3251 <programlisting>
3252   f :: C Int b => [b] -> [b]
3253 </programlisting>
3254 That postpones the question of which instance to pick to the 
3255 call site for <literal>f</literal>
3256 by which time more is known about the type <literal>b</literal>.
3257 </para>
3258 <para>
3259 The willingness to be overlapped or incoherent is a property of 
3260 the <emphasis>instance declaration</emphasis> itself, controlled by the
3261 presence or otherwise of the <option>-XOverlappingInstances</option> 
3262 and <option>-XIncoherentInstances</option> flags when that mdodule is
3263 being defined.  Neither flag is required in a module that imports and uses the
3264 instance declaration.  Specifically, during the lookup process:
3265 <itemizedlist>
3266 <listitem><para>
3267 An instance declaration is ignored during the lookup process if (a) a more specific
3268 match is found, and (b) the instance declaration was compiled with 
3269 <option>-XOverlappingInstances</option>.  The flag setting for the
3270 more-specific instance does not matter.
3271 </para></listitem>
3272 <listitem><para>
3273 Suppose an instance declaration does not match the constraint being looked up, but
3274 does unify with it, so that it might match when the constraint is further 
3275 instantiated.  Usually GHC will regard this as a reason for not committing to
3276 some other constraint.  But if the instance declaration was compiled with
3277 <option>-XIncoherentInstances</option>, GHC will skip the "does-it-unify?" 
3278 check for that declaration.
3279 </para></listitem>
3280 </itemizedlist>
3281 These rules make it possible for a library author to design a library that relies on 
3282 overlapping instances without the library client having to know.  
3283 </para>
3284 <para>
3285 If an instance declaration is compiled without
3286 <option>-XOverlappingInstances</option>,
3287 then that instance can never be overlapped.  This could perhaps be
3288 inconvenient.  Perhaps the rule should instead say that the
3289 <emphasis>overlapping</emphasis> instance declaration should be compiled in
3290 this way, rather than the <emphasis>overlapped</emphasis> one.  Perhaps overlap
3291 at a usage site should be permitted regardless of how the instance declarations
3292 are compiled, if the <option>-XOverlappingInstances</option> flag is
3293 used at the usage site.  (Mind you, the exact usage site can occasionally be
3294 hard to pin down.)  We are interested to receive feedback on these points.
3295 </para>
3296 <para>The <option>-XIncoherentInstances</option> flag implies the
3297 <option>-XOverlappingInstances</option> flag, but not vice versa.
3298 </para>
3299 </sect3>
3300
3301 <sect3>
3302 <title>Type synonyms in the instance head</title>
3303
3304 <para>
3305 <emphasis>Unlike Haskell 98, instance heads may use type
3306 synonyms</emphasis>.  (The instance "head" is the bit after the "=>" in an instance decl.)
3307 As always, using a type synonym is just shorthand for
3308 writing the RHS of the type synonym definition.  For example:
3309
3310
3311 <programlisting>
3312   type Point = (Int,Int)
3313   instance C Point   where ...
3314   instance C [Point] where ...
3315 </programlisting>
3316
3317
3318 is legal.  However, if you added
3319
3320
3321 <programlisting>
3322   instance C (Int,Int) where ...
3323 </programlisting>
3324
3325
3326 as well, then the compiler will complain about the overlapping
3327 (actually, identical) instance declarations.  As always, type synonyms
3328 must be fully applied.  You cannot, for example, write:
3329
3330
3331 <programlisting>
3332   type P a = [[a]]
3333   instance Monad P where ...
3334 </programlisting>
3335
3336
3337 This design decision is independent of all the others, and easily
3338 reversed, but it makes sense to me.
3339
3340 </para>
3341 </sect3>
3342
3343
3344 </sect2>
3345
3346 <sect2 id="overloaded-strings">
3347 <title>Overloaded string literals
3348 </title>
3349
3350 <para>
3351 GHC supports <emphasis>overloaded string literals</emphasis>.  Normally a
3352 string literal has type <literal>String</literal>, but with overloaded string
3353 literals enabled (with <literal>-XOverloadedStrings</literal>)
3354  a string literal has type <literal>(IsString a) => a</literal>.
3355 </para>
3356 <para>
3357 This means that the usual string syntax can be used, e.g., for packed strings
3358 and other variations of string like types.  String literals behave very much
3359 like integer literals, i.e., they can be used in both expressions and patterns.
3360 If used in a pattern the literal with be replaced by an equality test, in the same
3361 way as an integer literal is.
3362 </para>
3363 <para>
3364 The class <literal>IsString</literal> is defined as:
3365 <programlisting>
3366 class IsString a where
3367     fromString :: String -> a
3368 </programlisting>
3369 The only predefined instance is the obvious one to make strings work as usual:
3370 <programlisting>
3371 instance IsString [Char] where
3372     fromString cs = cs
3373 </programlisting>
3374 The class <literal>IsString</literal> is not in scope by default.  If you want to mention
3375 it explicitly (for exmaple, to give an instance declaration for it), you can import it
3376 from module <literal>GHC.Exts</literal>.
3377 </para>
3378 <para>
3379 Haskell's defaulting mechanism is extended to cover string literals, when <option>-XOverloadedStrings</option> is specified.
3380 Specifically:
3381 <itemizedlist>
3382 <listitem><para>
3383 Each type in a default declaration must be an 
3384 instance of <literal>Num</literal> <emphasis>or</emphasis> of <literal>IsString</literal>.
3385 </para></listitem>
3386
3387 <listitem><para>
3388 The standard defaulting rule (<ulink url="http://haskell.org/onlinereport/decls.html#sect4.3.4">Haskell Report, Section 4.3.4</ulink>)
3389 is extended thus: defaulting applies when all the unresolved constraints involve standard classes
3390 <emphasis>or</emphasis> <literal>IsString</literal>; and at least one is a numeric class
3391 <emphasis>or</emphasis> <literal>IsString</literal>.
3392 </para></listitem>
3393 </itemizedlist>
3394 </para>
3395 <para>
3396 A small example:
3397 <programlisting>
3398 module Main where
3399
3400 import GHC.Exts( IsString(..) )
3401
3402 newtype MyString = MyString String deriving (Eq, Show)
3403 instance IsString MyString where
3404     fromString = MyString
3405
3406 greet :: MyString -> MyString
3407 greet "hello" = "world"
3408 greet other = other
3409
3410 main = do
3411     print $ greet "hello"
3412     print $ greet "fool"
3413 </programlisting>
3414 </para>
3415 <para>
3416 Note that deriving <literal>Eq</literal> is necessary for the pattern matching
3417 to work since it gets translated into an equality comparison.
3418 </para>
3419 </sect2>
3420
3421 </sect1>
3422
3423 <sect1 id="other-type-extensions">
3424 <title>Other type system extensions</title>
3425
3426 <sect2 id="type-restrictions">
3427 <title>Type signatures</title>
3428
3429 <sect3><title>The context of a type signature</title>
3430 <para>
3431 Unlike Haskell 98, constraints in types do <emphasis>not</emphasis> have to be of
3432 the form <emphasis>(class type-variable)</emphasis> or
3433 <emphasis>(class (type-variable type-variable ...))</emphasis>.  Thus,
3434 these type signatures are perfectly OK
3435 <programlisting>
3436   g :: Eq [a] => ...
3437   g :: Ord (T a ()) => ...
3438 </programlisting>
3439 </para>
3440 <para>
3441 GHC imposes the following restrictions on the constraints in a type signature.
3442 Consider the type:
3443
3444 <programlisting>
3445   forall tv1..tvn (c1, ...,cn) => type
3446 </programlisting>
3447
3448 (Here, we write the "foralls" explicitly, although the Haskell source
3449 language omits them; in Haskell 98, all the free type variables of an
3450 explicit source-language type signature are universally quantified,
3451 except for the class type variables in a class declaration.  However,
3452 in GHC, you can give the foralls if you want.  See <xref linkend="universal-quantification"/>).
3453 </para>
3454
3455 <para>
3456
3457 <orderedlist>
3458 <listitem>
3459
3460 <para>
3461  <emphasis>Each universally quantified type variable
3462 <literal>tvi</literal> must be reachable from <literal>type</literal></emphasis>.
3463
3464 A type variable <literal>a</literal> is "reachable" if it it appears
3465 in the same constraint as either a type variable free in in
3466 <literal>type</literal>, or another reachable type variable.  
3467 A value with a type that does not obey 
3468 this reachability restriction cannot be used without introducing
3469 ambiguity; that is why the type is rejected.
3470 Here, for example, is an illegal type:
3471
3472
3473 <programlisting>
3474   forall a. Eq a => Int
3475 </programlisting>
3476
3477
3478 When a value with this type was used, the constraint <literal>Eq tv</literal>
3479 would be introduced where <literal>tv</literal> is a fresh type variable, and
3480 (in the dictionary-translation implementation) the value would be
3481 applied to a dictionary for <literal>Eq tv</literal>.  The difficulty is that we
3482 can never know which instance of <literal>Eq</literal> to use because we never
3483 get any more information about <literal>tv</literal>.
3484 </para>
3485 <para>
3486 Note
3487 that the reachability condition is weaker than saying that <literal>a</literal> is
3488 functionally dependent on a type variable free in
3489 <literal>type</literal> (see <xref
3490 linkend="functional-dependencies"/>).  The reason for this is there
3491 might be a "hidden" dependency, in a superclass perhaps.  So
3492 "reachable" is a conservative approximation to "functionally dependent".
3493 For example, consider:
3494 <programlisting>
3495   class C a b | a -> b where ...
3496   class C a b => D a b where ...
3497   f :: forall a b. D a b => a -> a
3498 </programlisting>
3499 This is fine, because in fact <literal>a</literal> does functionally determine <literal>b</literal>
3500 but that is not immediately apparent from <literal>f</literal>'s type.
3501 </para>
3502 </listitem>
3503 <listitem>
3504
3505 <para>
3506  <emphasis>Every constraint <literal>ci</literal> must mention at least one of the
3507 universally quantified type variables <literal>tvi</literal></emphasis>.
3508
3509 For example, this type is OK because <literal>C a b</literal> mentions the
3510 universally quantified type variable <literal>b</literal>:
3511
3512
3513 <programlisting>
3514   forall a. C a b => burble
3515 </programlisting>
3516
3517
3518 The next type is illegal because the constraint <literal>Eq b</literal> does not
3519 mention <literal>a</literal>:
3520
3521
3522 <programlisting>
3523   forall a. Eq b => burble
3524 </programlisting>
3525
3526
3527 The reason for this restriction is milder than the other one.  The
3528 excluded types are never useful or necessary (because the offending
3529 context doesn't need to be witnessed at this point; it can be floated
3530 out).  Furthermore, floating them out increases sharing. Lastly,
3531 excluding them is a conservative choice; it leaves a patch of
3532 territory free in case we need it later.
3533
3534 </para>
3535 </listitem>
3536
3537 </orderedlist>
3538
3539 </para>
3540 </sect3>
3541
3542
3543
3544 </sect2>
3545
3546 <sect2 id="implicit-parameters">
3547 <title>Implicit parameters</title>
3548
3549 <para> Implicit parameters are implemented as described in 
3550 "Implicit parameters: dynamic scoping with static types", 
3551 J Lewis, MB Shields, E Meijer, J Launchbury,
3552 27th ACM Symposium on Principles of Programming Languages (POPL'00),
3553 Boston, Jan 2000.
3554 </para>
3555
3556 <para>(Most of the following, stil rather incomplete, documentation is
3557 due to Jeff Lewis.)</para>
3558
3559 <para>Implicit parameter support is enabled with the option
3560 <option>-XImplicitParams</option>.</para>
3561
3562 <para>
3563 A variable is called <emphasis>dynamically bound</emphasis> when it is bound by the calling
3564 context of a function and <emphasis>statically bound</emphasis> when bound by the callee's
3565 context. In Haskell, all variables are statically bound. Dynamic
3566 binding of variables is a notion that goes back to Lisp, but was later
3567 discarded in more modern incarnations, such as Scheme. Dynamic binding
3568 can be very confusing in an untyped language, and unfortunately, typed
3569 languages, in particular Hindley-Milner typed languages like Haskell,
3570 only support static scoping of variables.
3571 </para>
3572 <para>
3573 However, by a simple extension to the type class system of Haskell, we
3574 can support dynamic binding. Basically, we express the use of a
3575 dynamically bound variable as a constraint on the type. These
3576 constraints lead to types of the form <literal>(?x::t') => t</literal>, which says "this
3577 function uses a dynamically-bound variable <literal>?x</literal> 
3578 of type <literal>t'</literal>". For
3579 example, the following expresses the type of a sort function,
3580 implicitly parameterized by a comparison function named <literal>cmp</literal>.