2 <indexterm><primary>language, GHC</primary></indexterm>
3 <indexterm><primary>extensions, GHC</primary></indexterm>
4 As with all known Haskell systems, GHC implements some extensions to
5 the language. To use them, you'll need to give a <option>-fglasgow-exts</option>
6 <indexterm><primary>-fglasgow-exts option</primary></indexterm> option.
10 Virtually all of the Glasgow extensions serve to give you access to
11 the underlying facilities with which we implement Haskell. Thus, you
12 can get at the Raw Iron, if you are willing to write some non-standard
13 code at a more primitive level. You need not be “stuck” on
14 performance because of the implementation costs of Haskell's
15 “high-level” features—you can always code “under” them. In an extreme case, you can write all your time-critical code in C, and then just glue it together with Haskell!
19 Before you get too carried away working at the lowest level (e.g.,
20 sloshing <literal>MutableByteArray#</literal>s around your
21 program), you may wish to check if there are libraries that provide a
22 “Haskellised veneer” over the features you want. See
23 <xref linkend="book-hslibs">.
26 <!-- LANGUAGE OPTIONS -->
27 <sect1 id="options-language">
28 <title>Language options</title>
30 <indexterm><primary>language</primary><secondary>option</secondary>
32 <indexterm><primary>options</primary><secondary>language</secondary>
34 <indexterm><primary>extensions</primary><secondary>options controlling</secondary>
37 <para> These flags control what variation of the language are
38 permitted. Leaving out all of them gives you standard Haskell
44 <term><option>-fglasgow-exts</option>:</term>
45 <indexterm><primary><option>-fglasgow-exts</option></primary></indexterm>
47 <para>This simultaneously enables all of the extensions to
48 Haskell 98 described in <xref
49 linkend="ghc-language-features">, except where otherwise
55 <term><option>-fno-monomorphism-restriction</option>:</term>
56 <indexterm><primary><option>-fno-monomorphism-restriction</option></primary></indexterm>
58 <para> Switch off the Haskell 98 monomorphism restriction.
59 Independent of the <option>-fglasgow-exts</option>
65 <term><option>-fallow-overlapping-instances</option></term>
66 <term><option>-fallow-undecidable-instances</option></term>
67 <term><option>-fallow-incoherent-instances</option></term>
68 <term><option>-fcontext-stack</option></term>
69 <indexterm><primary><option>-fallow-overlapping-instances</option></primary></indexterm>
70 <indexterm><primary><option>-fallow-undecidable-instances</option></primary></indexterm>
71 <indexterm><primary><option>-fcontext-stack</option></primary></indexterm>
73 <para> See <xref LinkEnd="instance-decls">. Only relevant
74 if you also use <option>-fglasgow-exts</option>.</para>
79 <term><option>-finline-phase</option></term>
80 <indexterm><primary><option>-finline-phase</option></primary></indexterm>
82 <para>See <xref LinkEnd="rewrite-rules">. Only relevant if
83 you also use <option>-fglasgow-exts</option>.</para>
88 <term><option>-fgenerics</option></term>
89 <indexterm><primary><option>-fgenerics</option></primary></indexterm>
91 <para>See <xref LinkEnd="generic-classes">. Independent of
92 <option>-fglasgow-exts</option>.</para>
97 <term><option>-fno-implicit-prelude</option></term>
99 <para><indexterm><primary>-fno-implicit-prelude
100 option</primary></indexterm> GHC normally imports
101 <filename>Prelude.hi</filename> files for you. If you'd
102 rather it didn't, then give it a
103 <option>-fno-implicit-prelude</option> option. The idea
104 is that you can then import a Prelude of your own. (But
105 don't call it <literal>Prelude</literal>; the Haskell
106 module namespace is flat, and you must not conflict with
107 any Prelude module.)</para>
109 <para>Even though you have not imported the Prelude, all
110 the built-in syntax still refers to the built-in Haskell
111 Prelude types and values, as specified by the Haskell
112 Report. For example, the type <literal>[Int]</literal>
113 still means <literal>Prelude.[] Int</literal>; tuples
114 continue to refer to the standard Prelude tuples; the
115 translation for list comprehensions continues to use
116 <literal>Prelude.map</literal> etc.</para>
118 <para> With one group of exceptions! You may want to
119 define your own numeric class hierarchy. It completely
120 defeats that purpose if the literal "1" means
121 "<literal>Prelude.fromInteger 1</literal>", which is what
122 the Haskell Report specifies. So the
123 <option>-fno-implicit-prelude</option> flag causes the
124 following pieces of built-in syntax to refer to <emphasis>whatever
125 is in scope</emphasis>, not the Prelude versions:</para>
129 <para>Integer and fractional literals mean
130 "<literal>fromInteger 1</literal>" and
131 "<literal>fromRational 3.2</literal>", not the
132 Prelude-qualified versions; both in expressions and in
137 <para>Negation (e.g. "<literal>- (f x)</literal>")
138 means "<literal>negate (f x)</literal>" (not
139 <literal>Prelude.negate</literal>).</para>
143 <para>In an n+k pattern, the standard Prelude
144 <literal>Ord</literal> class is still used for comparison,
145 but the necessary subtraction uses whatever
146 "<literal>(-)</literal>" is in scope (not
147 "<literal>Prelude.(-)</literal>").</para>
151 <para>Note: Negative literals, such as <literal>-3</literal>, are
152 specified by (a careful reading of) the Haskell Report as
153 meaning <literal>Prelude.negate (Prelude.fromInteger 3)</literal>.
154 However, GHC deviates from this slightly, and treats them as meaning
155 <literal>fromInteger (-3)</literal>. One particular effect of this
156 slightly-non-standard reading is that there is no difficulty with
157 the literal <literal>-2147483648</literal> at type <literal>Int</literal>;
158 it means <literal>fromInteger (-2147483648)</literal>. The strict interpretation
159 would be <literal>negate (fromInteger 2147483648)</literal>,
160 and the call to <literal>fromInteger</literal> would overflow
161 (at type <literal>Int</literal>, remember).
170 <!-- UNBOXED TYPES AND PRIMITIVE OPERATIONS -->
171 <!-- included from primitives.sgml -->
175 <!-- TYPE SYSTEM EXTENSIONS -->
176 <sect1 id="type-extensions">
177 <title>Type system extensions</title>
179 <sect2 id="nullary-types">
180 <title>Data types with no constructors</title>
182 <para>With the <option>-fglasgow-exts</option> flag, GHC lets you declare
183 a data type with no constructors. For example:</para>
186 data T a -- T :: * -> *
188 <para>Syntactically, the declaration lacks the "= constrs" part. The
189 type can be parameterised, but only over ordinary types, of kind *; since
190 Haskell does not have kind signatures, you cannot parameterise over higher-kinded
193 <para>Such data types have only one value, namely bottom.
194 Nevertheless, they can be useful when defining "phantom types".</para>
197 <sect2 id="class-method-types">
198 <title>Class method types
201 Haskell 98 prohibits class method types to mention constraints on the
202 class type variable, thus:
205 fromList :: [a] -> s a
206 elem :: Eq a => a -> s a -> Bool
208 The type of <literal>elem</literal> is illegal in Haskell 98, because it
209 contains the constraint <literal>Eq a</literal>, constrains only the
210 class type variable (in this case <literal>a</literal>).
213 With the <option>-fglasgow-exts</option> GHC lifts this restriction.
218 <sect2 id="multi-param-type-classes">
219 <title>Multi-parameter type classes
223 This section documents GHC's implementation of multi-parameter type
224 classes. There's lots of background in the paper <ULink
225 URL="http://research.microsoft.com/~simonpj/multi.ps.gz" >Type
226 classes: exploring the design space</ULink > (Simon Peyton Jones, Mark
231 I'd like to thank people who reported shorcomings in the GHC 3.02
232 implementation. Our default decisions were all conservative ones, and
233 the experience of these heroic pioneers has given useful concrete
234 examples to support several generalisations. (These appear below as
235 design choices not implemented in 3.02.)
239 I've discussed these notes with Mark Jones, and I believe that Hugs
240 will migrate towards the same design choices as I outline here.
241 Thanks to him, and to many others who have offered very useful
249 There are the following restrictions on the form of a qualified
256 forall tv1..tvn (c1, ...,cn) => type
262 (Here, I write the "foralls" explicitly, although the Haskell source
263 language omits them; in Haskell 1.4, all the free type variables of an
264 explicit source-language type signature are universally quantified,
265 except for the class type variables in a class declaration. However,
266 in GHC, you can give the foralls if you want. See <xref LinkEnd="universal-quantification">).
275 <emphasis>Each universally quantified type variable
276 <literal>tvi</literal> must be mentioned (i.e. appear free) in <literal>type</literal></emphasis>.
278 The reason for this is that a value with a type that does not obey
279 this restriction could not be used without introducing
280 ambiguity. Here, for example, is an illegal type:
284 forall a. Eq a => Int
288 When a value with this type was used, the constraint <literal>Eq tv</literal>
289 would be introduced where <literal>tv</literal> is a fresh type variable, and
290 (in the dictionary-translation implementation) the value would be
291 applied to a dictionary for <literal>Eq tv</literal>. The difficulty is that we
292 can never know which instance of <literal>Eq</literal> to use because we never
293 get any more information about <literal>tv</literal>.
300 <emphasis>Every constraint <literal>ci</literal> must mention at least one of the
301 universally quantified type variables <literal>tvi</literal></emphasis>.
303 For example, this type is OK because <literal>C a b</literal> mentions the
304 universally quantified type variable <literal>b</literal>:
308 forall a. C a b => burble
312 The next type is illegal because the constraint <literal>Eq b</literal> does not
313 mention <literal>a</literal>:
317 forall a. Eq b => burble
321 The reason for this restriction is milder than the other one. The
322 excluded types are never useful or necessary (because the offending
323 context doesn't need to be witnessed at this point; it can be floated
324 out). Furthermore, floating them out increases sharing. Lastly,
325 excluding them is a conservative choice; it leaves a patch of
326 territory free in case we need it later.
336 These restrictions apply to all types, whether declared in a type signature
341 Unlike Haskell 1.4, constraints in types do <emphasis>not</emphasis> have to be of
342 the form <emphasis>(class type-variables)</emphasis>. Thus, these type signatures
349 f :: Eq (m a) => [m a] -> [m a]
356 This choice recovers principal types, a property that Haskell 1.4 does not have.
362 <title>Class declarations</title>
370 <emphasis>Multi-parameter type classes are permitted</emphasis>. For example:
374 class Collection c a where
375 union :: c a -> c a -> c a
386 <emphasis>The class hierarchy must be acyclic</emphasis>. However, the definition
387 of "acyclic" involves only the superclass relationships. For example,
393 op :: D b => a -> b -> b
396 class C a => D a where { ... }
400 Here, <literal>C</literal> is a superclass of <literal>D</literal>, but it's OK for a
401 class operation <literal>op</literal> of <literal>C</literal> to mention <literal>D</literal>. (It
402 would not be OK for <literal>D</literal> to be a superclass of <literal>C</literal>.)
409 <emphasis>There are no restrictions on the context in a class declaration
410 (which introduces superclasses), except that the class hierarchy must
411 be acyclic</emphasis>. So these class declarations are OK:
415 class Functor (m k) => FiniteMap m k where
418 class (Monad m, Monad (t m)) => Transform t m where
419 lift :: m a -> (t m) a
428 <emphasis>In the signature of a class operation, every constraint
429 must mention at least one type variable that is not a class type
436 class Collection c a where
437 mapC :: Collection c b => (a->b) -> c a -> c b
441 is OK because the constraint <literal>(Collection a b)</literal> mentions
442 <literal>b</literal>, even though it also mentions the class variable
443 <literal>a</literal>. On the other hand:
448 op :: Eq a => (a,b) -> (a,b)
452 is not OK because the constraint <literal>(Eq a)</literal> mentions on the class
453 type variable <literal>a</literal>, but not <literal>b</literal>. However, any such
454 example is easily fixed by moving the offending context up to the
459 class Eq a => C a where
464 A yet more relaxed rule would allow the context of a class-op signature
465 to mention only class type variables. However, that conflicts with
466 Rule 1(b) for types above.
473 <emphasis>The type of each class operation must mention <emphasis>all</emphasis> of
474 the class type variables</emphasis>. For example:
480 insert :: s -> a -> s
484 is not OK, because the type of <literal>empty</literal> doesn't mention
485 <literal>a</literal>. This rule is a consequence of Rule 1(a), above, for
486 types, and has the same motivation.
488 Sometimes, offending class declarations exhibit misunderstandings. For
489 example, <literal>Coll</literal> might be rewritten
495 insert :: s a -> a -> s a
499 which makes the connection between the type of a collection of
500 <literal>a</literal>'s (namely <literal>(s a)</literal>) and the element type <literal>a</literal>.
501 Occasionally this really doesn't work, in which case you can split the
509 class CollE s => Coll s a where
510 insert :: s -> a -> s
523 <sect3 id="instance-decls">
524 <title>Instance declarations</title>
532 <emphasis>Instance declarations may not overlap</emphasis>. The two instance
537 instance context1 => C type1 where ...
538 instance context2 => C type2 where ...
542 "overlap" if <literal>type1</literal> and <literal>type2</literal> unify
544 However, if you give the command line option
545 <option>-fallow-overlapping-instances</option><indexterm><primary>-fallow-overlapping-instances
546 option</primary></indexterm> then overlapping instance declarations are permitted.
547 However, GHC arranges never to commit to using an instance declaration
548 if another instance declaration also applies, either now or later.
554 EITHER <literal>type1</literal> and <literal>type2</literal> do not unify
560 OR <literal>type2</literal> is a substitution instance of <literal>type1</literal>
561 (but not identical to <literal>type1</literal>), or vice versa.
565 Notice that these rules
570 make it clear which instance decl to use
571 (pick the most specific one that matches)
578 do not mention the contexts <literal>context1</literal>, <literal>context2</literal>
579 Reason: you can pick which instance decl
580 "matches" based on the type.
585 However the rules are over-conservative. Two instance declarations can overlap,
586 but it can still be clear in particular situations which to use. For example:
588 instance C (Int,a) where ...
589 instance C (a,Bool) where ...
591 These are rejected by GHC's rules, but it is clear what to do when trying
592 to solve the constraint <literal>C (Int,Int)</literal> because the second instance
593 cannot apply. Yell if this restriction bites you.
596 GHC is also conservative about committing to an overlapping instance. For example:
598 class C a where { op :: a -> a }
599 instance C [Int] where ...
600 instance C a => C [a] where ...
602 f :: C b => [b] -> [b]
605 From the RHS of f we get the constraint <literal>C [b]</literal>. But
606 GHC does not commit to the second instance declaration, because in a paricular
607 call of f, b might be instantiate to Int, so the first instance declaration
608 would be appropriate. So GHC rejects the program. If you add <option>-fallow-incoherent-instances</option>
609 GHC will instead silently pick the second instance, without complaining about
610 the problem of subsequent instantiations.
613 Regrettably, GHC doesn't guarantee to detect overlapping instance
614 declarations if they appear in different modules. GHC can "see" the
615 instance declarations in the transitive closure of all the modules
616 imported by the one being compiled, so it can "see" all instance decls
617 when it is compiling <literal>Main</literal>. However, it currently chooses not
618 to look at ones that can't possibly be of use in the module currently
619 being compiled, in the interests of efficiency. (Perhaps we should
620 change that decision, at least for <literal>Main</literal>.)
627 <emphasis>There are no restrictions on the type in an instance
628 <emphasis>head</emphasis>, except that at least one must not be a type variable</emphasis>.
629 The instance "head" is the bit after the "=>" in an instance decl. For
630 example, these are OK:
634 instance C Int a where ...
636 instance D (Int, Int) where ...
638 instance E [[a]] where ...
642 Note that instance heads <emphasis>may</emphasis> contain repeated type variables.
643 For example, this is OK:
647 instance Stateful (ST s) (MutVar s) where ...
651 The "at least one not a type variable" restriction is to ensure that
652 context reduction terminates: each reduction step removes one type
653 constructor. For example, the following would make the type checker
654 loop if it wasn't excluded:
658 instance C a => C a where ...
662 There are two situations in which the rule is a bit of a pain. First,
663 if one allows overlapping instance declarations then it's quite
664 convenient to have a "default instance" declaration that applies if
665 something more specific does not:
674 Second, sometimes you might want to use the following to get the
675 effect of a "class synonym":
679 class (C1 a, C2 a, C3 a) => C a where { }
681 instance (C1 a, C2 a, C3 a) => C a where { }
685 This allows you to write shorter signatures:
697 f :: (C1 a, C2 a, C3 a) => ...
701 I'm on the lookout for a simple rule that preserves decidability while
702 allowing these idioms. The experimental flag
703 <option>-fallow-undecidable-instances</option><indexterm><primary>-fallow-undecidable-instances
704 option</primary></indexterm> lifts this restriction, allowing all the types in an
705 instance head to be type variables.
712 <emphasis>Unlike Haskell 1.4, instance heads may use type
713 synonyms</emphasis>. As always, using a type synonym is just shorthand for
714 writing the RHS of the type synonym definition. For example:
718 type Point = (Int,Int)
719 instance C Point where ...
720 instance C [Point] where ...
724 is legal. However, if you added
728 instance C (Int,Int) where ...
732 as well, then the compiler will complain about the overlapping
733 (actually, identical) instance declarations. As always, type synonyms
734 must be fully applied. You cannot, for example, write:
739 instance Monad P where ...
743 This design decision is independent of all the others, and easily
744 reversed, but it makes sense to me.
751 <emphasis>The types in an instance-declaration <emphasis>context</emphasis> must all
752 be type variables</emphasis>. Thus
756 instance C a b => Eq (a,b) where ...
764 instance C Int b => Foo b where ...
768 is not OK. Again, the intent here is to make sure that context
769 reduction terminates.
771 Voluminous correspondence on the Haskell mailing list has convinced me
772 that it's worth experimenting with a more liberal rule. If you use
773 the flag <option>-fallow-undecidable-instances</option> can use arbitrary
774 types in an instance context. Termination is ensured by having a
775 fixed-depth recursion stack. If you exceed the stack depth you get a
776 sort of backtrace, and the opportunity to increase the stack depth
777 with <option>-fcontext-stack</option><emphasis>N</emphasis>.
790 <sect2 id="implicit-parameters">
791 <title>Implicit parameters
794 <para> Implicit paramters are implemented as described in
795 "Implicit parameters: dynamic scoping with static types",
796 J Lewis, MB Shields, E Meijer, J Launchbury,
797 27th ACM Symposium on Principles of Programming Languages (POPL'00),
800 <para>(Most of the following, stil rather incomplete, documentation is due to Jeff Lewis.)</para>
802 A variable is called <emphasis>dynamically bound</emphasis> when it is bound by the calling
803 context of a function and <emphasis>statically bound</emphasis> when bound by the callee's
804 context. In Haskell, all variables are statically bound. Dynamic
805 binding of variables is a notion that goes back to Lisp, but was later
806 discarded in more modern incarnations, such as Scheme. Dynamic binding
807 can be very confusing in an untyped language, and unfortunately, typed
808 languages, in particular Hindley-Milner typed languages like Haskell,
809 only support static scoping of variables.
812 However, by a simple extension to the type class system of Haskell, we
813 can support dynamic binding. Basically, we express the use of a
814 dynamically bound variable as a constraint on the type. These
815 constraints lead to types of the form <literal>(?x::t') => t</literal>, which says "this
816 function uses a dynamically-bound variable <literal>?x</literal>
817 of type <literal>t'</literal>". For
818 example, the following expresses the type of a sort function,
819 implicitly parameterized by a comparison function named <literal>cmp</literal>.
821 sort :: (?cmp :: a -> a -> Bool) => [a] -> [a]
823 The dynamic binding constraints are just a new form of predicate in the type class system.
826 An implicit parameter is introduced by the special form <literal>?x</literal>,
827 where <literal>x</literal> is
828 any valid identifier. Use if this construct also introduces new
829 dynamic binding constraints. For example, the following definition
830 shows how we can define an implicitly parameterized sort function in
831 terms of an explicitly parameterized <literal>sortBy</literal> function:
833 sortBy :: (a -> a -> Bool) -> [a] -> [a]
835 sort :: (?cmp :: a -> a -> Bool) => [a] -> [a]
838 Dynamic binding constraints behave just like other type class
839 constraints in that they are automatically propagated. Thus, when a
840 function is used, its implicit parameters are inherited by the
841 function that called it. For example, our <literal>sort</literal> function might be used
842 to pick out the least value in a list:
844 least :: (?cmp :: a -> a -> Bool) => [a] -> a
845 least xs = fst (sort xs)
847 Without lifting a finger, the <literal>?cmp</literal> parameter is
848 propagated to become a parameter of <literal>least</literal> as well. With explicit
849 parameters, the default is that parameters must always be explicit
850 propagated. With implicit parameters, the default is to always
854 An implicit parameter differs from other type class constraints in the
855 following way: All uses of a particular implicit parameter must have
856 the same type. This means that the type of <literal>(?x, ?x)</literal>
857 is <literal>(?x::a) => (a,a)</literal>, and not
858 <literal>(?x::a, ?x::b) => (a, b)</literal>, as would be the case for type
862 An implicit parameter is bound using an expression of the form
863 <emphasis>expr</emphasis> <literal>with</literal> <emphasis>binds</emphasis>,
864 where <literal>with</literal> is a new keyword. This form binds the implicit
865 parameters arising in the body, not the free variables as a <literal>let</literal> or
866 <literal>where</literal> would do. For example, we define the <literal>min</literal> function by binding
867 <literal>cmp</literal>.
870 min = least with ?cmp = (<=)
872 Syntactically, the <emphasis>binds</emphasis> part of a <literal>with</literal> construct must be a
873 collection of simple bindings to variables (no function-style
874 bindings, and no type signatures); these bindings are neither
875 polymorphic or recursive.
878 Note the following additional constraints:
881 <para> You can't have an implicit parameter in the context of a class or instance
882 declaration. For example, both these declarations are illegal:
884 class (?x::Int) => C a where ...
885 instance (?x::a) => Foo [a] where ...
887 Reason: exactly which implicit parameter you pick up depends on exactly where
888 you invoke a function. But the ``invocation'' of instance declarations is done
889 behind the scenes by the compiler, so it's hard to figure out exactly where it is done.
890 Easiest thing is to outlaw the offending types.</para>
897 <sect2 id="linear-implicit-parameters">
898 <title>Linear implicit parameters
901 Linear implicit parameters are an idea developed by Koen Claessen,
902 Mark Shields, and Simon PJ. They address the long-standing
903 problem that monads seem over-kill for certain sorts of problem, notably:
906 <listitem> <para> distributing a supply of unique names </para> </listitem>
907 <listitem> <para> distributing a suppply of random numbers </para> </listitem>
908 <listitem> <para> distributing an oracle (as in QuickCheck) </para> </listitem>
912 Linear implicit parameters are just like ordinary implicit parameters,
913 except that they are "linear" -- that is, they cannot be copied, and
914 must be explicitly "split" instead. Linear implicit parameters are
915 written '<literal>%x</literal>' instead of '<literal>?x</literal>'.
916 (The '/' in the '%' suggests the split!)
921 import GHC.Exts( Splittable )
923 data NameSupply = ...
925 splitNS :: NameSupply -> (NameSupply, NameSupply)
926 newName :: NameSupply -> Name
928 instance Splittable NameSupply where
932 f :: (%ns :: NameSupply) => Env -> Expr -> Expr
933 f env (Lam x e) = Lam x' (f env e)
936 env' = extend env x x'
937 ...more equations for f...
939 Notice that the implicit parameter %ns is consumed
941 <listitem> <para> once by the call to <literal>newName</literal> </para> </listitem>
942 <listitem> <para> once by the recursive call to <literal>f</literal> </para></listitem>
946 So the translation done by the type checker makes
947 the parameter explicit:
949 f :: NameSupply -> Env -> Expr -> Expr
950 f ns env (Lam x e) = Lam x' (f ns1 env e)
952 (ns1,ns2) = splitNS ns
954 env = extend env x x'
956 Notice the call to 'split' introduced by the type checker.
957 How did it know to use 'splitNS'? Because what it really did
958 was to introduce a call to the overloaded function 'split',
959 defined by the class <literal>Splittable</literal>:
961 class Splittable a where
964 The instance for <literal>Splittable NameSupply</literal> tells GHC how to implement
965 split for name supplies. But we can simply write
971 g :: (Splittable a, %ns :: a) => b -> (b,a,a)
973 The <literal>Splittable</literal> class is built into GHC. It's exported by module
974 <literal>GHC.Exts</literal>.
979 <listitem> <para> '<literal>?x</literal>' and '<literal>%x</literal>'
980 are entirely distinct implicit parameters: you
981 can use them together and they won't intefere with each other. </para>
984 <listitem> <para> You can bind linear implicit parameters in 'with' clauses. </para> </listitem>
986 <listitem> <para>You cannot have implicit parameters (whether linear or not)
987 in the context of a class or instance declaration. </para></listitem>
991 <sect3><title>Warnings</title>
994 The monomorphism restriction is even more important than usual.
995 Consider the example above:
997 f :: (%ns :: NameSupply) => Env -> Expr -> Expr
998 f env (Lam x e) = Lam x' (f env e)
1001 env' = extend env x x'
1003 If we replaced the two occurrences of x' by (newName %ns), which is
1004 usually a harmless thing to do, we get:
1006 f :: (%ns :: NameSupply) => Env -> Expr -> Expr
1007 f env (Lam x e) = Lam (newName %ns) (f env e)
1009 env' = extend env x (newName %ns)
1011 But now the name supply is consumed in <emphasis>three</emphasis> places
1012 (the two calls to newName,and the recursive call to f), so
1013 the result is utterly different. Urk! We don't even have
1017 Well, this is an experimental change. With implicit
1018 parameters we have already lost beta reduction anyway, and
1019 (as John Launchbury puts it) we can't sensibly reason about
1020 Haskell programs without knowing their typing.
1027 <sect2 id="functional-dependencies">
1028 <title>Functional dependencies
1031 <para> Functional dependencies are implemented as described by Mark Jones
1032 in "Type Classes with Functional Dependencies", Mark P. Jones,
1033 In Proceedings of the 9th European Symposium on Programming,
1034 ESOP 2000, Berlin, Germany, March 2000, Springer-Verlag LNCS 1782.
1038 There should be more documentation, but there isn't (yet). Yell if you need it.
1043 <sect2 id="universal-quantification">
1044 <title>Arbitrary-rank polymorphism
1048 Haskell type signatures are implicitly quantified. The new keyword <literal>forall</literal>
1049 allows us to say exactly what this means. For example:
1057 g :: forall b. (b -> b)
1059 The two are treated identically.
1063 However, GHC's type system supports <emphasis>arbitrary-rank</emphasis>
1064 explicit universal quantification in
1066 For example, all the following types are legal:
1068 f1 :: forall a b. a -> b -> a
1069 g1 :: forall a b. (Ord a, Eq b) => a -> b -> a
1071 f2 :: (forall a. a->a) -> Int -> Int
1072 g2 :: (forall a. Eq a => [a] -> a -> Bool) -> Int -> Int
1074 f3 :: ((forall a. a->a) -> Int) -> Bool -> Bool
1076 Here, <literal>f1</literal> and <literal>g1</literal> are rank-1 types, and
1077 can be written in standard Haskell (e.g. <literal>f1 :: a->b->a</literal>).
1078 The <literal>forall</literal> makes explicit the universal quantification that
1079 is implicitly added by Haskell.
1082 The functions <literal>f2</literal> and <literal>g2</literal> have rank-2 types;
1083 the <literal>forall</literal> is on the left of a function arrrow. As <literal>g2</literal>
1084 shows, the polymorphic type on the left of the function arrow can be overloaded.
1087 The functions <literal>f3</literal> and <literal>g3</literal> have rank-3 types;
1088 they have rank-2 types on the left of a function arrow.
1091 GHC allows types of arbitrary rank; you can nest <literal>forall</literal>s
1092 arbitrarily deep in function arrows. (GHC used to be restricted to rank 2, but
1093 that restriction has now been lifted.)
1094 In particular, a forall-type (also called a "type scheme"),
1095 including an operational type class context, is legal:
1097 <listitem> <para> On the left of a function arrow </para> </listitem>
1098 <listitem> <para> On the right of a function arrow (see <xref linkend="hoist">) </para> </listitem>
1099 <listitem> <para> As the argument of a constructor, or type of a field, in a data type declaration. For
1100 example, any of the <literal>f1,f2,f3,g1,g2,g3</literal> above would be valid
1101 field type signatures.</para> </listitem>
1102 <listitem> <para> As the type of an implicit parameter </para> </listitem>
1103 <listitem> <para> In a pattern type signature (see <xref linkend="scoped-type-variables">) </para> </listitem>
1105 There is one place you cannot put a <literal>forall</literal>:
1106 you cannot instantiate a type variable with a forall-type. So you cannot
1107 make a forall-type the argument of a type constructor. So these types are illegal:
1109 x1 :: [forall a. a->a]
1110 x2 :: (forall a. a->a, Int)
1111 x3 :: Maybe (forall a. a->a)
1113 Of course <literal>forall</literal> becomes a keyword; you can't use <literal>forall</literal> as
1114 a type variable any more!
1123 In a <literal>data</literal> or <literal>newtype</literal> declaration one can quantify
1124 the types of the constructor arguments. Here are several examples:
1130 data T a = T1 (forall b. b -> b -> b) a
1132 data MonadT m = MkMonad { return :: forall a. a -> m a,
1133 bind :: forall a b. m a -> (a -> m b) -> m b
1136 newtype Swizzle = MkSwizzle (Ord a => [a] -> [a])
1142 The constructors have rank-2 types:
1148 T1 :: forall a. (forall b. b -> b -> b) -> a -> T a
1149 MkMonad :: forall m. (forall a. a -> m a)
1150 -> (forall a b. m a -> (a -> m b) -> m b)
1152 MkSwizzle :: (Ord a => [a] -> [a]) -> Swizzle
1158 Notice that you don't need to use a <literal>forall</literal> if there's an
1159 explicit context. For example in the first argument of the
1160 constructor <function>MkSwizzle</function>, an implicit "<literal>forall a.</literal>" is
1161 prefixed to the argument type. The implicit <literal>forall</literal>
1162 quantifies all type variables that are not already in scope, and are
1163 mentioned in the type quantified over.
1167 As for type signatures, implicit quantification happens for non-overloaded
1168 types too. So if you write this:
1171 data T a = MkT (Either a b) (b -> b)
1174 it's just as if you had written this:
1177 data T a = MkT (forall b. Either a b) (forall b. b -> b)
1180 That is, since the type variable <literal>b</literal> isn't in scope, it's
1181 implicitly universally quantified. (Arguably, it would be better
1182 to <emphasis>require</emphasis> explicit quantification on constructor arguments
1183 where that is what is wanted. Feedback welcomed.)
1187 You construct values of types <literal>T1, MonadT, Swizzle</literal> by applying
1188 the constructor to suitable values, just as usual. For example,
1199 a3 = MkSwizzle reverse
1202 a4 = let r x = Just x
1209 mkTs :: (forall b. b -> b -> b) -> a -> [T a]
1210 mkTs f x y = [T1 f x, T1 f y]
1216 The type of the argument can, as usual, be more general than the type
1217 required, as <literal>(MkSwizzle reverse)</literal> shows. (<function>reverse</function>
1218 does not need the <literal>Ord</literal> constraint.)
1222 When you use pattern matching, the bound variables may now have
1223 polymorphic types. For example:
1229 f :: T a -> a -> (a, Char)
1230 f (T1 w k) x = (w k x, w 'c' 'd')
1232 g :: (Ord a, Ord b) => Swizzle -> [a] -> (a -> b) -> [b]
1233 g (MkSwizzle s) xs f = s (map f (s xs))
1235 h :: MonadT m -> [m a] -> m [a]
1236 h m [] = return m []
1237 h m (x:xs) = bind m x $ \y ->
1238 bind m (h m xs) $ \ys ->
1245 In the function <function>h</function> we use the record selectors <literal>return</literal>
1246 and <literal>bind</literal> to extract the polymorphic bind and return functions
1247 from the <literal>MonadT</literal> data structure, rather than using pattern
1253 <title>Type inference</title>
1256 In general, type inference for arbitrary-rank types is undecideable.
1257 GHC uses an algorithm proposed by Odersky and Laufer ("Putting type annotations to work", POPL'96)
1258 to get a decidable algorithm by requiring some help from the programmer.
1259 We do not yet have a formal specification of "some help" but the rule is this:
1262 <emphasis>For a lambda-bound or case-bound variable, x, either the programmer
1263 provides an explicit polymorphic type for x, or GHC's type inference will assume
1264 that x's type has no foralls in it</emphasis>.
1267 What does it mean to "provide" an explicit type for x? You can do that by
1268 giving a type signature for x directly, using a pattern type signature
1269 (<xref linkend="scoped-type-variables">), thus:
1271 \ f :: (forall a. a->a) -> (f True, f 'c')
1273 Alternatively, you can give a type signature to the enclosing
1274 context, which GHC can "push down" to find the type for the variable:
1276 (\ f -> (f True, f 'c')) :: (forall a. a->a) -> (Bool,Char)
1278 Here the type signature on the expression can be pushed inwards
1279 to give a type signature for f. Similarly, and more commonly,
1280 one can give a type signature for the function itself:
1282 h :: (forall a. a->a) -> (Bool,Char)
1283 h f = (f True, f 'c')
1285 You don't need to give a type signature if the lambda bound variable
1286 is a constructor argument. Here is an example we saw earlier:
1288 f :: T a -> a -> (a, Char)
1289 f (T1 w k) x = (w k x, w 'c' 'd')
1291 Here we do not need to give a type signature to <literal>w</literal>, because
1292 it is an argument of constructor <literal>T1</literal> and that tells GHC all
1299 <sect3 id="implicit-quant">
1300 <title>Implicit quantification</title>
1303 GHC performs implicit quantification as follows. <emphasis>At the top level (only) of
1304 user-written types, if and only if there is no explicit <literal>forall</literal>,
1305 GHC finds all the type variables mentioned in the type that are not already
1306 in scope, and universally quantifies them.</emphasis> For example, the following pairs are
1310 f :: forall a. a -> a
1317 h :: forall b. a -> b -> b
1323 Notice that GHC does <emphasis>not</emphasis> find the innermost possible quantification
1326 f :: (a -> a) -> Int
1328 f :: forall a. (a -> a) -> Int
1330 f :: (forall a. a -> a) -> Int
1333 g :: (Ord a => a -> a) -> Int
1334 -- MEANS the illegal type
1335 g :: forall a. (Ord a => a -> a) -> Int
1337 g :: (forall a. Ord a => a -> a) -> Int
1339 The latter produces an illegal type, which you might think is silly,
1340 but at least the rule is simple. If you want the latter type, you
1341 can write your for-alls explicitly. Indeed, doing so is strongly advised
1348 <title>Liberalised type synonyms
1352 Type synonmys are like macros at the type level, and
1353 GHC does validity checking on types <emphasis>only after expanding type synonyms</emphasis>.
1354 That means that GHC can be very much more liberal about type synonyms than Haskell 98:
1356 <listitem> <para>You can write a <literal>forall</literal> (including overloading)
1357 in a type synonym, thus:
1359 type Discard a = forall b. Show b => a -> b -> (a, String)
1364 g :: Discard Int -> (Int,Bool) -- A rank-2 type
1371 You can write an unboxed tuple in a type synonym:
1373 type Pr = (# Int, Int #)
1381 You can apply a type synonym to a forall type:
1383 type Foo a = a -> a -> Bool
1385 f :: Foo (forall b. b->b)
1387 After epxanding the synonym, <literal>f</literal> has the legal (in GHC) type:
1389 f :: (forall b. b->b) -> (forall b. b->b) -> Bool
1394 You can apply a type synonym to a partially applied type synonym:
1396 type Generic i o = forall x. i x -> o x
1399 foo :: Generic Id []
1401 After epxanding the synonym, <literal>foo</literal> has the legal (in GHC) type:
1403 foo :: forall x. x -> [x]
1411 GHC currently does kind checking before expanding synonyms (though even that
1415 After expanding type synonyms, GHC does validity checking on types, looking for
1416 the following mal-formedness which isn't detected simply by kind checking:
1419 Type constructor applied to a type involving for-alls.
1422 Unboxed tuple on left of an arrow.
1425 Partially-applied type synonym.
1429 this will be rejected:
1431 type Pr = (# Int, Int #)
1436 because GHC does not allow unboxed tuples on the left of a function arrow.
1441 <title>For-all hoisting</title>
1443 It is often convenient to use generalised type synonyms at the right hand
1444 end of an arrow, thus:
1446 type Discard a = forall b. a -> b -> a
1448 g :: Int -> Discard Int
1451 Simply expanding the type synonym would give
1453 g :: Int -> (forall b. Int -> b -> Int)
1455 but GHC "hoists" the <literal>forall</literal> to give the isomorphic type
1457 g :: forall b. Int -> Int -> b -> Int
1459 In general, the rule is this: <emphasis>to determine the type specified by any explicit
1460 user-written type (e.g. in a type signature), GHC expands type synonyms and then repeatedly
1461 performs the transformation:</emphasis>
1463 <emphasis>type1</emphasis> -> forall a1..an. <emphasis>context2</emphasis> => <emphasis>type2</emphasis>
1465 forall a1..an. <emphasis>context2</emphasis> => <emphasis>type1</emphasis> -> <emphasis>type2</emphasis>
1467 (In fact, GHC tries to retain as much synonym information as possible for use in
1468 error messages, but that is a usability issue.) This rule applies, of course, whether
1469 or not the <literal>forall</literal> comes from a synonym. For example, here is another
1470 valid way to write <literal>g</literal>'s type signature:
1472 g :: Int -> Int -> forall b. b -> Int
1478 <sect2 id="existential-quantification">
1479 <title>Existentially quantified data constructors
1483 The idea of using existential quantification in data type declarations
1484 was suggested by Laufer (I believe, thought doubtless someone will
1485 correct me), and implemented in Hope+. It's been in Lennart
1486 Augustsson's <Command>hbc</Command> Haskell compiler for several years, and
1487 proved very useful. Here's the idea. Consider the declaration:
1493 data Foo = forall a. MkFoo a (a -> Bool)
1500 The data type <literal>Foo</literal> has two constructors with types:
1506 MkFoo :: forall a. a -> (a -> Bool) -> Foo
1513 Notice that the type variable <literal>a</literal> in the type of <function>MkFoo</function>
1514 does not appear in the data type itself, which is plain <literal>Foo</literal>.
1515 For example, the following expression is fine:
1521 [MkFoo 3 even, MkFoo 'c' isUpper] :: [Foo]
1527 Here, <literal>(MkFoo 3 even)</literal> packages an integer with a function
1528 <function>even</function> that maps an integer to <literal>Bool</literal>; and <function>MkFoo 'c'
1529 isUpper</function> packages a character with a compatible function. These
1530 two things are each of type <literal>Foo</literal> and can be put in a list.
1534 What can we do with a value of type <literal>Foo</literal>?. In particular,
1535 what happens when we pattern-match on <function>MkFoo</function>?
1541 f (MkFoo val fn) = ???
1547 Since all we know about <literal>val</literal> and <function>fn</function> is that they
1548 are compatible, the only (useful) thing we can do with them is to
1549 apply <function>fn</function> to <literal>val</literal> to get a boolean. For example:
1556 f (MkFoo val fn) = fn val
1562 What this allows us to do is to package heterogenous values
1563 together with a bunch of functions that manipulate them, and then treat
1564 that collection of packages in a uniform manner. You can express
1565 quite a bit of object-oriented-like programming this way.
1568 <sect3 id="existential">
1569 <title>Why existential?
1573 What has this to do with <emphasis>existential</emphasis> quantification?
1574 Simply that <function>MkFoo</function> has the (nearly) isomorphic type
1580 MkFoo :: (exists a . (a, a -> Bool)) -> Foo
1586 But Haskell programmers can safely think of the ordinary
1587 <emphasis>universally</emphasis> quantified type given above, thereby avoiding
1588 adding a new existential quantification construct.
1594 <title>Type classes</title>
1597 An easy extension (implemented in <Command>hbc</Command>) is to allow
1598 arbitrary contexts before the constructor. For example:
1604 data Baz = forall a. Eq a => Baz1 a a
1605 | forall b. Show b => Baz2 b (b -> b)
1611 The two constructors have the types you'd expect:
1617 Baz1 :: forall a. Eq a => a -> a -> Baz
1618 Baz2 :: forall b. Show b => b -> (b -> b) -> Baz
1624 But when pattern matching on <function>Baz1</function> the matched values can be compared
1625 for equality, and when pattern matching on <function>Baz2</function> the first matched
1626 value can be converted to a string (as well as applying the function to it).
1627 So this program is legal:
1634 f (Baz1 p q) | p == q = "Yes"
1636 f (Baz2 v fn) = show (fn v)
1642 Operationally, in a dictionary-passing implementation, the
1643 constructors <function>Baz1</function> and <function>Baz2</function> must store the
1644 dictionaries for <literal>Eq</literal> and <literal>Show</literal> respectively, and
1645 extract it on pattern matching.
1649 Notice the way that the syntax fits smoothly with that used for
1650 universal quantification earlier.
1656 <title>Restrictions</title>
1659 There are several restrictions on the ways in which existentially-quantified
1660 constructors can be use.
1669 When pattern matching, each pattern match introduces a new,
1670 distinct, type for each existential type variable. These types cannot
1671 be unified with any other type, nor can they escape from the scope of
1672 the pattern match. For example, these fragments are incorrect:
1680 Here, the type bound by <function>MkFoo</function> "escapes", because <literal>a</literal>
1681 is the result of <function>f1</function>. One way to see why this is wrong is to
1682 ask what type <function>f1</function> has:
1686 f1 :: Foo -> a -- Weird!
1690 What is this "<literal>a</literal>" in the result type? Clearly we don't mean
1695 f1 :: forall a. Foo -> a -- Wrong!
1699 The original program is just plain wrong. Here's another sort of error
1703 f2 (Baz1 a b) (Baz1 p q) = a==q
1707 It's ok to say <literal>a==b</literal> or <literal>p==q</literal>, but
1708 <literal>a==q</literal> is wrong because it equates the two distinct types arising
1709 from the two <function>Baz1</function> constructors.
1717 You can't pattern-match on an existentially quantified
1718 constructor in a <literal>let</literal> or <literal>where</literal> group of
1719 bindings. So this is illegal:
1723 f3 x = a==b where { Baz1 a b = x }
1727 You can only pattern-match
1728 on an existentially-quantified constructor in a <literal>case</literal> expression or
1729 in the patterns of a function definition.
1731 The reason for this restriction is really an implementation one.
1732 Type-checking binding groups is already a nightmare without
1733 existentials complicating the picture. Also an existential pattern
1734 binding at the top level of a module doesn't make sense, because it's
1735 not clear how to prevent the existentially-quantified type "escaping".
1736 So for now, there's a simple-to-state restriction. We'll see how
1744 You can't use existential quantification for <literal>newtype</literal>
1745 declarations. So this is illegal:
1749 newtype T = forall a. Ord a => MkT a
1753 Reason: a value of type <literal>T</literal> must be represented as a pair
1754 of a dictionary for <literal>Ord t</literal> and a value of type <literal>t</literal>.
1755 That contradicts the idea that <literal>newtype</literal> should have no
1756 concrete representation. You can get just the same efficiency and effect
1757 by using <literal>data</literal> instead of <literal>newtype</literal>. If there is no
1758 overloading involved, then there is more of a case for allowing
1759 an existentially-quantified <literal>newtype</literal>, because the <literal>data</literal>
1760 because the <literal>data</literal> version does carry an implementation cost,
1761 but single-field existentially quantified constructors aren't much
1762 use. So the simple restriction (no existential stuff on <literal>newtype</literal>)
1763 stands, unless there are convincing reasons to change it.
1771 You can't use <literal>deriving</literal> to define instances of a
1772 data type with existentially quantified data constructors.
1774 Reason: in most cases it would not make sense. For example:#
1777 data T = forall a. MkT [a] deriving( Eq )
1780 To derive <literal>Eq</literal> in the standard way we would need to have equality
1781 between the single component of two <function>MkT</function> constructors:
1785 (MkT a) == (MkT b) = ???
1788 But <VarName>a</VarName> and <VarName>b</VarName> have distinct types, and so can't be compared.
1789 It's just about possible to imagine examples in which the derived instance
1790 would make sense, but it seems altogether simpler simply to prohibit such
1791 declarations. Define your own instances!
1803 <sect2 id="scoped-type-variables">
1804 <title>Scoped Type Variables
1808 A <emphasis>pattern type signature</emphasis> can introduce a <emphasis>scoped type
1809 variable</emphasis>. For example
1815 f (xs::[a]) = ys ++ ys
1824 The pattern <literal>(xs::[a])</literal> includes a type signature for <VarName>xs</VarName>.
1825 This brings the type variable <literal>a</literal> into scope; it scopes over
1826 all the patterns and right hand sides for this equation for <function>f</function>.
1827 In particular, it is in scope at the type signature for <VarName>y</VarName>.
1831 Pattern type signatures are completely orthogonal to ordinary, separate
1832 type signatures. The two can be used independently or together.
1833 At ordinary type signatures, such as that for <VarName>ys</VarName>, any type variables
1834 mentioned in the type signature <emphasis>that are not in scope</emphasis> are
1835 implicitly universally quantified. (If there are no type variables in
1836 scope, all type variables mentioned in the signature are universally
1837 quantified, which is just as in Haskell 98.) In this case, since <VarName>a</VarName>
1838 is in scope, it is not universally quantified, so the type of <VarName>ys</VarName> is
1839 the same as that of <VarName>xs</VarName>. In Haskell 98 it is not possible to declare
1840 a type for <VarName>ys</VarName>; a major benefit of scoped type variables is that
1841 it becomes possible to do so.
1845 Scoped type variables are implemented in both GHC and Hugs. Where the
1846 implementations differ from the specification below, those differences
1851 So much for the basic idea. Here are the details.
1855 <title>What a pattern type signature means</title>
1857 A type variable brought into scope by a pattern type signature is simply
1858 the name for a type. The restriction they express is that all occurrences
1859 of the same name mean the same type. For example:
1861 f :: [Int] -> Int -> Int
1862 f (xs::[a]) (y::a) = (head xs + y) :: a
1864 The pattern type signatures on the left hand side of
1865 <literal>f</literal> express the fact that <literal>xs</literal>
1866 must be a list of things of some type <literal>a</literal>; and that <literal>y</literal>
1867 must have this same type. The type signature on the expression <literal>(head xs)</literal>
1868 specifies that this expression must have the same type <literal>a</literal>.
1869 <emphasis>There is no requirement that the type named by "<literal>a</literal>" is
1870 in fact a type variable</emphasis>. Indeed, in this case, the type named by "<literal>a</literal>" is
1871 <literal>Int</literal>. (This is a slight liberalisation from the original rather complex
1872 rules, which specified that a pattern-bound type variable should be universally quantified.)
1873 For example, all of these are legal:</para>
1876 t (x::a) (y::a) = x+y*2
1878 f (x::a) (y::b) = [x,y] -- a unifies with b
1880 g (x::a) = x + 1::Int -- a unifies with Int
1882 h x = let k (y::a) = [x,y] -- a is free in the
1883 in k x -- environment
1885 k (x::a) True = ... -- a unifies with Int
1886 k (x::Int) False = ...
1889 w (x::a) = x -- a unifies with [b]
1895 <title>Scope and implicit quantification</title>
1903 All the type variables mentioned in a pattern,
1904 that are not already in scope,
1905 are brought into scope by the pattern. We describe this set as
1906 the <emphasis>type variables bound by the pattern</emphasis>.
1909 f (x::a) = let g (y::(a,b)) = fst y
1913 The pattern <literal>(x::a)</literal> brings the type variable
1914 <literal>a</literal> into scope, as well as the term
1915 variable <literal>x</literal>. The pattern <literal>(y::(a,b))</literal>
1916 contains an occurrence of the already-in-scope type variable <literal>a</literal>,
1917 and brings into scope the type variable <literal>b</literal>.
1923 The type variable(s) bound by the pattern have the same scope
1924 as the term variable(s) bound by the pattern. For example:
1927 f (x::a) = <...rhs of f...>
1928 (p::b, q::b) = (1,2)
1929 in <...body of let...>
1931 Here, the type variable <literal>a</literal> scopes over the right hand side of <literal>f</literal>,
1932 just like <literal>x</literal> does; while the type variable <literal>b</literal> scopes over the
1933 body of the <literal>let</literal>, and all the other definitions in the <literal>let</literal>,
1934 just like <literal>p</literal> and <literal>q</literal> do.
1935 Indeed, the newly bound type variables also scope over any ordinary, separate
1936 type signatures in the <literal>let</literal> group.
1943 The type variables bound by the pattern may be
1944 mentioned in ordinary type signatures or pattern
1945 type signatures anywhere within their scope.
1952 In ordinary type signatures, any type variable mentioned in the
1953 signature that is in scope is <emphasis>not</emphasis> universally quantified.
1961 Ordinary type signatures do not bring any new type variables
1962 into scope (except in the type signature itself!). So this is illegal:
1969 It's illegal because <VarName>a</VarName> is not in scope in the body of <function>f</function>,
1970 so the ordinary signature <literal>x::a</literal> is equivalent to <literal>x::forall a.a</literal>;
1971 and that is an incorrect typing.
1978 The pattern type signature is a monotype:
1983 A pattern type signature cannot contain any explicit <literal>forall</literal> quantification.
1987 The type variables bound by a pattern type signature can only be instantiated to monotypes,
1988 not to type schemes.
1992 There is no implicit universal quantification on pattern type signatures (in contrast to
1993 ordinary type signatures).
2003 The type variables in the head of a <literal>class</literal> or <literal>instance</literal> declaration
2004 scope over the methods defined in the <literal>where</literal> part. For example:
2018 (Not implemented in Hugs yet, Dec 98).
2029 <title>Result type signatures</title>
2037 The result type of a function can be given a signature,
2042 f (x::a) :: [a] = [x,x,x]
2046 The final <literal>:: [a]</literal> after all the patterns gives a signature to the
2047 result type. Sometimes this is the only way of naming the type variable
2052 f :: Int -> [a] -> [a]
2053 f n :: ([a] -> [a]) = let g (x::a, y::a) = (y,x)
2054 in \xs -> map g (reverse xs `zip` xs)
2066 Result type signatures are not yet implemented in Hugs.
2072 <title>Where a pattern type signature can occur</title>
2075 A pattern type signature can occur in any pattern. For example:
2080 A pattern type signature can be on an arbitrary sub-pattern, not
2085 f ((x,y)::(a,b)) = (y,x) :: (b,a)
2094 Pattern type signatures, including the result part, can be used
2095 in lambda abstractions:
2098 (\ (x::a, y) :: a -> x)
2105 Pattern type signatures, including the result part, can be used
2106 in <literal>case</literal> expressions:
2110 case e of { (x::a, y) :: a -> x }
2118 To avoid ambiguity, the type after the “<literal>::</literal>” in a result
2119 pattern signature on a lambda or <literal>case</literal> must be atomic (i.e. a single
2120 token or a parenthesised type of some sort). To see why,
2121 consider how one would parse this:
2135 Pattern type signatures can bind existential type variables.
2140 data T = forall a. MkT [a]
2143 f (MkT [t::a]) = MkT t3
2156 Pattern type signatures
2157 can be used in pattern bindings:
2160 f x = let (y, z::a) = x in ...
2161 f1 x = let (y, z::Int) = x in ...
2162 f2 (x::(Int,a)) = let (y, z::a) = x in ...
2163 f3 :: (b->b) = \x -> x
2166 In all such cases, the binding is not generalised over the pattern-bound
2167 type variables. Thus <literal>f3</literal> is monomorphic; <literal>f3</literal>
2168 has type <literal>b -> b</literal> for some type <literal>b</literal>,
2169 and <emphasis>not</emphasis> <literal>forall b. b -> b</literal>.
2170 In contrast, the binding
2175 makes a polymorphic function, but <literal>b</literal> is not in scope anywhere
2176 in <literal>f4</literal>'s scope.
2186 <sect2 id="sec-kinding">
2187 <title>Explicitly-kinded quantification</title>
2190 Haskell infers the kind of each type variable. Sometimes it is nice to be able
2191 to give the kind explicitly as (machine-checked) documentation,
2192 just as it is nice to give a type signature for a function. On some occasions,
2193 it is essential to do so. For example, in his paper "Restricted Data Types in Haskell" (Haskell Workshop 1999)
2194 John Hughes had to define the data type:
2196 data Set cxt a = Set [a]
2197 | Unused (cxt a -> ())
2199 The only use for the <literal>Unused</literal> constructor was to force the correct
2200 kind for the type variable <literal>cxt</literal>.
2203 GHC now instead allows you to specify the kind of a type variable directly, wherever
2204 a type variable is explicitly bound. Namely:
2206 <listitem><para><literal>data</literal> declarations:
2208 data Set (cxt :: * -> *) a = Set [a]
2209 </Screen></para></listitem>
2210 <listitem><para><literal>type</literal> declarations:
2212 type T (f :: * -> *) = f Int
2213 </Screen></para></listitem>
2214 <listitem><para><literal>class</literal> declarations:
2216 class (Eq a) => C (f :: * -> *) a where ...
2217 </Screen></para></listitem>
2218 <listitem><para><literal>forall</literal>'s in type signatures:
2220 f :: forall (cxt :: * -> *). Set cxt Int
2221 </Screen></para></listitem>
2226 The parentheses are required. Some of the spaces are required too, to
2227 separate the lexemes. If you write <literal>(f::*->*)</literal> you
2228 will get a parse error, because "<literal>::*->*</literal>" is a
2229 single lexeme in Haskell.
2233 As part of the same extension, you can put kind annotations in types
2236 f :: (Int :: *) -> Int
2237 g :: forall a. a -> (a :: *)
2241 atype ::= '(' ctype '::' kind ')
2243 The parentheses are required.
2248 <!-- ==================== End of type system extensions ================= -->
2251 <!-- ==================== ASSERTIONS ================= -->
2253 <sect1 id="sec-assertions">
2255 <indexterm><primary>Assertions</primary></indexterm>
2259 If you want to make use of assertions in your standard Haskell code, you
2260 could define a function like the following:
2266 assert :: Bool -> a -> a
2267 assert False x = error "assertion failed!"
2274 which works, but gives you back a less than useful error message --
2275 an assertion failed, but which and where?
2279 One way out is to define an extended <function>assert</function> function which also
2280 takes a descriptive string to include in the error message and
2281 perhaps combine this with the use of a pre-processor which inserts
2282 the source location where <function>assert</function> was used.
2286 Ghc offers a helping hand here, doing all of this for you. For every
2287 use of <function>assert</function> in the user's source:
2293 kelvinToC :: Double -> Double
2294 kelvinToC k = assert (k >= 0.0) (k+273.15)
2300 Ghc will rewrite this to also include the source location where the
2307 assert pred val ==> assertError "Main.hs|15" pred val
2313 The rewrite is only performed by the compiler when it spots
2314 applications of <function>Exception.assert</function>, so you can still define and
2315 use your own versions of <function>assert</function>, should you so wish. If not,
2316 import <literal>Exception</literal> to make use <function>assert</function> in your code.
2320 To have the compiler ignore uses of assert, use the compiler option
2321 <option>-fignore-asserts</option>. <indexterm><primary>-fignore-asserts option</primary></indexterm> That is,
2322 expressions of the form <literal>assert pred e</literal> will be rewritten to <literal>e</literal>.
2326 Assertion failures can be caught, see the documentation for the
2327 <literal>Exception</literal> library (<xref linkend="sec-Exception">)
2333 <!-- ====================== PATTERN GUARDS ======================= -->
2335 <sect1 id="pattern-guards">
2336 <title>Pattern guards</title>
2339 <indexterm><primary>Pattern guards (Glasgow extension)</primary></indexterm>
2340 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.)
2344 Suppose we have an abstract data type of finite maps, with a
2348 lookup :: FiniteMap -> Int -> Maybe Int
2351 The lookup returns <function>Nothing</function> if the supplied key is not in the domain of the mapping, and <function>(Just v)</function> otherwise,
2352 where <VarName>v</VarName> is the value that the key maps to. Now consider the following definition:
2356 clunky env var1 var2 | ok1 && ok2 = val1 + val2
2357 | otherwise = var1 + var2
2359 m1 = lookup env var1
2360 m2 = lookup env var2
2361 ok1 = maybeToBool m1
2362 ok2 = maybeToBool m2
2363 val1 = expectJust m1
2364 val2 = expectJust m2
2368 The auxiliary functions are
2372 maybeToBool :: Maybe a -> Bool
2373 maybeToBool (Just x) = True
2374 maybeToBool Nothing = False
2376 expectJust :: Maybe a -> a
2377 expectJust (Just x) = x
2378 expectJust Nothing = error "Unexpected Nothing"
2382 What is <function>clunky</function> doing? The guard <literal>ok1 &&
2383 ok2</literal> checks that both lookups succeed, using
2384 <function>maybeToBool</function> to convert the <function>Maybe</function>
2385 types to booleans. The (lazily evaluated) <function>expectJust</function>
2386 calls extract the values from the results of the lookups, and binds the
2387 returned values to <VarName>val1</VarName> and <VarName>val2</VarName>
2388 respectively. If either lookup fails, then clunky takes the
2389 <literal>otherwise</literal> case and returns the sum of its arguments.
2393 This is certainly legal Haskell, but it is a tremendously verbose and
2394 un-obvious way to achieve the desired effect. Arguably, a more direct way
2395 to write clunky would be to use case expressions:
2399 clunky env var1 var1 = case lookup env var1 of
2401 Just val1 -> case lookup env var2 of
2403 Just val2 -> val1 + val2
2409 This is a bit shorter, but hardly better. Of course, we can rewrite any set
2410 of pattern-matching, guarded equations as case expressions; that is
2411 precisely what the compiler does when compiling equations! The reason that
2412 Haskell provides guarded equations is because they allow us to write down
2413 the cases we want to consider, one at a time, independently of each other.
2414 This structure is hidden in the case version. Two of the right-hand sides
2415 are really the same (<function>fail</function>), and the whole expression
2416 tends to become more and more indented.
2420 Here is how I would write clunky:
2424 clunky env var1 var1
2425 | Just val1 <- lookup env var1
2426 , Just val2 <- lookup env var2
2428 ...other equations for clunky...
2432 The semantics should be clear enough. The qualifers are matched in order.
2433 For a <literal><-</literal> qualifier, which I call a pattern guard, the
2434 right hand side is evaluated and matched against the pattern on the left.
2435 If the match fails then the whole guard fails and the next equation is
2436 tried. If it succeeds, then the appropriate binding takes place, and the
2437 next qualifier is matched, in the augmented environment. Unlike list
2438 comprehensions, however, the type of the expression to the right of the
2439 <literal><-</literal> is the same as the type of the pattern to its
2440 left. The bindings introduced by pattern guards scope over all the
2441 remaining guard qualifiers, and over the right hand side of the equation.
2445 Just as with list comprehensions, boolean expressions can be freely mixed
2446 with among the pattern guards. For example:
2457 Haskell's current guards therefore emerge as a special case, in which the
2458 qualifier list has just one element, a boolean expression.
2462 <!-- ===================== PARALLEL LIST COMPREHENSIONS =================== -->
2464 <sect1 id="parallel-list-comprehensions">
2465 <title>Parallel List Comprehensions</title>
2466 <indexterm><primary>list comprehensions</primary><secondary>parallel</secondary>
2468 <indexterm><primary>parallel list comprehensions</primary>
2471 <para>Parallel list comprehensions are a natural extension to list
2472 comprehensions. List comprehensions can be thought of as a nice
2473 syntax for writing maps and filters. Parallel comprehensions
2474 extend this to include the zipWith family.</para>
2476 <para>A parallel list comprehension has multiple independent
2477 branches of qualifier lists, each separated by a `|' symbol. For
2478 example, the following zips together two lists:</para>
2481 [ (x, y) | x <- xs | y <- ys ]
2484 <para>The behavior of parallel list comprehensions follows that of
2485 zip, in that the resulting list will have the same length as the
2486 shortest branch.</para>
2488 <para>We can define parallel list comprehensions by translation to
2489 regular comprehensions. Here's the basic idea:</para>
2491 <para>Given a parallel comprehension of the form: </para>
2494 [ e | p1 <- e11, p2 <- e12, ...
2495 | q1 <- e21, q2 <- e22, ...
2500 <para>This will be translated to: </para>
2503 [ e | ((p1,p2), (q1,q2), ...) <- zipN [(p1,p2) | p1 <- e11, p2 <- e12, ...]
2504 [(q1,q2) | q1 <- e21, q2 <- e22, ...]
2509 <para>where `zipN' is the appropriate zip for the given number of
2514 <!-- =============================== PRAGMAS =========================== -->
2516 <sect1 id="pragmas">
2517 <title>Pragmas</title>
2519 <indexterm><primary>pragma</primary></indexterm>
2521 <para>GHC supports several pragmas, or instructions to the
2522 compiler placed in the source code. Pragmas don't normally affect
2523 the meaning of the program, but they might affect the efficiency
2524 of the generated code.</para>
2526 <para>Pragmas all take the form
2528 <literal>{-# <replaceable>word</replaceable> ... #-}</literal>
2530 where <replaceable>word</replaceable> indicates the type of
2531 pragma, and is followed optionally by information specific to that
2532 type of pragma. Case is ignored in
2533 <replaceable>word</replaceable>. The various values for
2534 <replaceable>word</replaceable> that GHC understands are described
2535 in the following sections; any pragma encountered with an
2536 unrecognised <replaceable>word</replaceable> is (silently)
2539 <sect2 id="inline-pragma">
2540 <title>INLINE pragma
2542 <indexterm><primary>INLINE pragma</primary></indexterm>
2543 <indexterm><primary>pragma, INLINE</primary></indexterm></title>
2546 GHC (with <option>-O</option>, as always) tries to inline (or “unfold”)
2547 functions/values that are “small enough,” thus avoiding the call
2548 overhead and possibly exposing other more-wonderful optimisations.
2552 You will probably see these unfoldings (in Core syntax) in your
2557 Normally, if GHC decides a function is “too expensive” to inline, it
2558 will not do so, nor will it export that unfolding for other modules to
2563 The sledgehammer you can bring to bear is the
2564 <literal>INLINE</literal><indexterm><primary>INLINE pragma</primary></indexterm> pragma, used thusly:
2567 key_function :: Int -> String -> (Bool, Double)
2569 #ifdef __GLASGOW_HASKELL__
2570 {-# INLINE key_function #-}
2574 (You don't need to do the C pre-processor carry-on unless you're going
2575 to stick the code through HBC—it doesn't like <literal>INLINE</literal> pragmas.)
2579 The major effect of an <literal>INLINE</literal> pragma is to declare a function's
2580 “cost” to be very low. The normal unfolding machinery will then be
2581 very keen to inline it.
2585 An <literal>INLINE</literal> pragma for a function can be put anywhere its type
2586 signature could be put.
2590 <literal>INLINE</literal> pragmas are a particularly good idea for the
2591 <literal>then</literal>/<literal>return</literal> (or <literal>bind</literal>/<literal>unit</literal>) functions in a monad.
2592 For example, in GHC's own <literal>UniqueSupply</literal> monad code, we have:
2595 #ifdef __GLASGOW_HASKELL__
2596 {-# INLINE thenUs #-}
2597 {-# INLINE returnUs #-}
2605 <sect2 id="noinline-pragma">
2606 <title>NOINLINE pragma
2609 <indexterm><primary>NOINLINE pragma</primary></indexterm>
2610 <indexterm><primary>pragma</primary><secondary>NOINLINE</secondary></indexterm>
2611 <indexterm><primary>NOTINLINE pragma</primary></indexterm>
2612 <indexterm><primary>pragma</primary><secondary>NOTINLINE</secondary></indexterm>
2615 The <literal>NOINLINE</literal> pragma does exactly what you'd expect:
2616 it stops the named function from being inlined by the compiler. You
2617 shouldn't ever need to do this, unless you're very cautious about code
2621 <para><literal>NOTINLINE</literal> is a synonym for
2622 <literal>NOINLINE</literal> (<literal>NOTINLINE</literal> is specified
2623 by Haskell 98 as the standard way to disable inlining, so it should be
2624 used if you want your code to be portable).</para>
2628 <sect2 id="specialize-pragma">
2629 <title>SPECIALIZE pragma</title>
2631 <indexterm><primary>SPECIALIZE pragma</primary></indexterm>
2632 <indexterm><primary>pragma, SPECIALIZE</primary></indexterm>
2633 <indexterm><primary>overloading, death to</primary></indexterm>
2635 <para>(UK spelling also accepted.) For key overloaded
2636 functions, you can create extra versions (NB: more code space)
2637 specialised to particular types. Thus, if you have an
2638 overloaded function:</para>
2641 hammeredLookup :: Ord key => [(key, value)] -> key -> value
2644 <para>If it is heavily used on lists with
2645 <literal>Widget</literal> keys, you could specialise it as
2649 {-# SPECIALIZE hammeredLookup :: [(Widget, value)] -> Widget -> value #-}
2652 <para>To get very fancy, you can also specify a named function
2653 to use for the specialised value, as in:</para>
2656 {-# RULES hammeredLookup = blah #-}
2659 <para>where <literal>blah</literal> is an implementation of
2660 <literal>hammerdLookup</literal> written specialy for
2661 <literal>Widget</literal> lookups. It's <emphasis>Your
2662 Responsibility</emphasis> to make sure that
2663 <function>blah</function> really behaves as a specialised
2664 version of <function>hammeredLookup</function>!!!</para>
2666 <para>Note we use the <literal>RULE</literal> pragma here to
2667 indicate that <literal>hammeredLookup</literal> applied at a
2668 certain type should be replaced by <literal>blah</literal>. See
2669 <xref linkend="rules"> for more information on
2670 <literal>RULES</literal>.</para>
2672 <para>An example in which using <literal>RULES</literal> for
2673 specialisation will Win Big:
2676 toDouble :: Real a => a -> Double
2677 toDouble = fromRational . toRational
2679 {-# SPECIALIZE toDouble :: Int -> Double = i2d #-}
2680 i2d (I# i) = D# (int2Double# i) -- uses Glasgow prim-op directly
2683 The <function>i2d</function> function is virtually one machine
2684 instruction; the default conversion—via an intermediate
2685 <literal>Rational</literal>—is obscenely expensive by
2688 <para>A <literal>SPECIALIZE</literal> pragma for a function can
2689 be put anywhere its type signature could be put.</para>
2693 <sect2 id="specialize-instance-pragma">
2694 <title>SPECIALIZE instance pragma
2698 <indexterm><primary>SPECIALIZE pragma</primary></indexterm>
2699 <indexterm><primary>overloading, death to</primary></indexterm>
2700 Same idea, except for instance declarations. For example:
2703 instance (Eq a) => Eq (Foo a) where {
2704 {-# SPECIALIZE instance Eq (Foo [(Int, Bar)]) #-}
2708 The pragma must occur inside the <literal>where</literal> part
2709 of the instance declaration.
2712 Compatible with HBC, by the way, except perhaps in the placement
2718 <sect2 id="line-pragma">
2723 <indexterm><primary>LINE pragma</primary></indexterm>
2724 <indexterm><primary>pragma, LINE</primary></indexterm>
2728 This pragma is similar to C's <literal>#line</literal> pragma, and is mainly for use in
2729 automatically generated Haskell code. It lets you specify the line
2730 number and filename of the original code; for example
2736 {-# LINE 42 "Foo.vhs" #-}
2742 if you'd generated the current file from something called <filename>Foo.vhs</filename>
2743 and this line corresponds to line 42 in the original. GHC will adjust
2744 its error messages to refer to the line/file named in the <literal>LINE</literal>
2751 <title>RULES pragma</title>
2754 The RULES pragma lets you specify rewrite rules. It is described in
2755 <xref LinkEnd="rewrite-rules">.
2760 <sect2 id="deprecated-pragma">
2761 <title>DEPRECATED pragma</title>
2764 The DEPRECATED pragma lets you specify that a particular function, class, or type, is deprecated.
2765 There are two forms.
2769 You can deprecate an entire module thus:</para>
2771 module Wibble {-# DEPRECATED "Use Wobble instead" #-} where
2775 When you compile any module that import <literal>Wibble</literal>, GHC will print
2776 the specified message.</para>
2781 You can deprecate a function, class, or type, with the following top-level declaration:
2784 {-# DEPRECATED f, C, T "Don't use these" #-}
2787 When you compile any module that imports and uses any of the specifed entities,
2788 GHC will print the specified message.
2792 <para>You can suppress the warnings with the flag <option>-fno-warn-deprecations</option>.</para>
2798 <!-- ======================= REWRITE RULES ======================== -->
2800 <sect1 id="rewrite-rules">
2801 <title>Rewrite rules
2803 <indexterm><primary>RULES pagma</primary></indexterm>
2804 <indexterm><primary>pragma, RULES</primary></indexterm>
2805 <indexterm><primary>rewrite rules</primary></indexterm></title>
2808 The programmer can specify rewrite rules as part of the source program
2809 (in a pragma). GHC applies these rewrite rules wherever it can.
2817 "map/map" forall f g xs. map f (map g xs) = map (f.g) xs
2824 <title>Syntax</title>
2827 From a syntactic point of view:
2833 Each rule has a name, enclosed in double quotes. The name itself has
2834 no significance at all. It is only used when reporting how many times the rule fired.
2840 There may be zero or more rules in a <literal>RULES</literal> pragma.
2846 Layout applies in a <literal>RULES</literal> pragma. Currently no new indentation level
2847 is set, so you must lay out your rules starting in the same column as the
2848 enclosing definitions.
2854 Each variable mentioned in a rule must either be in scope (e.g. <function>map</function>),
2855 or bound by the <literal>forall</literal> (e.g. <function>f</function>, <function>g</function>, <function>xs</function>). The variables bound by
2856 the <literal>forall</literal> are called the <emphasis>pattern</emphasis> variables. They are separated
2857 by spaces, just like in a type <literal>forall</literal>.
2863 A pattern variable may optionally have a type signature.
2864 If the type of the pattern variable is polymorphic, it <emphasis>must</emphasis> have a type signature.
2865 For example, here is the <literal>foldr/build</literal> rule:
2868 "fold/build" forall k z (g::forall b. (a->b->b) -> b -> b) .
2869 foldr k z (build g) = g k z
2872 Since <function>g</function> has a polymorphic type, it must have a type signature.
2879 The left hand side of a rule must consist of a top-level variable applied
2880 to arbitrary expressions. For example, this is <emphasis>not</emphasis> OK:
2883 "wrong1" forall e1 e2. case True of { True -> e1; False -> e2 } = e1
2884 "wrong2" forall f. f True = True
2887 In <literal>"wrong1"</literal>, the LHS is not an application; in <literal>"wrong2"</literal>, the LHS has a pattern variable
2894 A rule does not need to be in the same module as (any of) the
2895 variables it mentions, though of course they need to be in scope.
2901 Rules are automatically exported from a module, just as instance declarations are.
2912 <title>Semantics</title>
2915 From a semantic point of view:
2921 Rules are only applied if you use the <option>-O</option> flag.
2927 Rules are regarded as left-to-right rewrite rules.
2928 When GHC finds an expression that is a substitution instance of the LHS
2929 of a rule, it replaces the expression by the (appropriately-substituted) RHS.
2930 By "a substitution instance" we mean that the LHS can be made equal to the
2931 expression by substituting for the pattern variables.
2938 The LHS and RHS of a rule are typechecked, and must have the
2946 GHC makes absolutely no attempt to verify that the LHS and RHS
2947 of a rule have the same meaning. That is undecideable in general, and
2948 infeasible in most interesting cases. The responsibility is entirely the programmer's!
2955 GHC makes no attempt to make sure that the rules are confluent or
2956 terminating. For example:
2959 "loop" forall x,y. f x y = f y x
2962 This rule will cause the compiler to go into an infinite loop.
2969 If more than one rule matches a call, GHC will choose one arbitrarily to apply.
2975 GHC currently uses a very simple, syntactic, matching algorithm
2976 for matching a rule LHS with an expression. It seeks a substitution
2977 which makes the LHS and expression syntactically equal modulo alpha
2978 conversion. The pattern (rule), but not the expression, is eta-expanded if
2979 necessary. (Eta-expanding the epression can lead to laziness bugs.)
2980 But not beta conversion (that's called higher-order matching).
2984 Matching is carried out on GHC's intermediate language, which includes
2985 type abstractions and applications. So a rule only matches if the
2986 types match too. See <xref LinkEnd="rule-spec"> below.
2992 GHC keeps trying to apply the rules as it optimises the program.
2993 For example, consider:
3002 The expression <literal>s (t xs)</literal> does not match the rule <literal>"map/map"</literal>, but GHC
3003 will substitute for <VarName>s</VarName> and <VarName>t</VarName>, giving an expression which does match.
3004 If <VarName>s</VarName> or <VarName>t</VarName> was (a) used more than once, and (b) large or a redex, then it would
3005 not be substituted, and the rule would not fire.
3012 In the earlier phases of compilation, GHC inlines <emphasis>nothing
3013 that appears on the LHS of a rule</emphasis>, because once you have substituted
3014 for something you can't match against it (given the simple minded
3015 matching). So if you write the rule
3018 "map/map" forall f,g. map f . map g = map (f.g)
3021 this <emphasis>won't</emphasis> match the expression <literal>map f (map g xs)</literal>.
3022 It will only match something written with explicit use of ".".
3023 Well, not quite. It <emphasis>will</emphasis> match the expression
3029 where <function>wibble</function> is defined:
3032 wibble f g = map f . map g
3035 because <function>wibble</function> will be inlined (it's small).
3037 Later on in compilation, GHC starts inlining even things on the
3038 LHS of rules, but still leaves the rules enabled. This inlining
3039 policy is controlled by the per-simplification-pass flag <option>-finline-phase</option><emphasis>n</emphasis>.
3046 All rules are implicitly exported from the module, and are therefore
3047 in force in any module that imports the module that defined the rule, directly
3048 or indirectly. (That is, if A imports B, which imports C, then C's rules are
3049 in force when compiling A.) The situation is very similar to that for instance
3061 <title>List fusion</title>
3064 The RULES mechanism is used to implement fusion (deforestation) of common list functions.
3065 If a "good consumer" consumes an intermediate list constructed by a "good producer", the
3066 intermediate list should be eliminated entirely.
3070 The following are good producers:
3082 Enumerations of <literal>Int</literal> and <literal>Char</literal> (e.g. <literal>['a'..'z']</literal>).
3088 Explicit lists (e.g. <literal>[True, False]</literal>)
3094 The cons constructor (e.g <literal>3:4:[]</literal>)
3100 <function>++</function>
3106 <function>map</function>
3112 <function>filter</function>
3118 <function>iterate</function>, <function>repeat</function>
3124 <function>zip</function>, <function>zipWith</function>
3133 The following are good consumers:
3145 <function>array</function> (on its second argument)
3151 <function>length</function>
3157 <function>++</function> (on its first argument)
3163 <function>foldr</function>
3169 <function>map</function>
3175 <function>filter</function>
3181 <function>concat</function>
3187 <function>unzip</function>, <function>unzip2</function>, <function>unzip3</function>, <function>unzip4</function>
3193 <function>zip</function>, <function>zipWith</function> (but on one argument only; if both are good producers, <function>zip</function>
3194 will fuse with one but not the other)
3200 <function>partition</function>
3206 <function>head</function>
3212 <function>and</function>, <function>or</function>, <function>any</function>, <function>all</function>
3218 <function>sequence_</function>
3224 <function>msum</function>
3230 <function>sortBy</function>
3239 So, for example, the following should generate no intermediate lists:
3242 array (1,10) [(i,i*i) | i <- map (+ 1) [0..9]]
3248 This list could readily be extended; if there are Prelude functions that you use
3249 a lot which are not included, please tell us.
3253 If you want to write your own good consumers or producers, look at the
3254 Prelude definitions of the above functions to see how to do so.
3259 <sect2 id="rule-spec">
3260 <title>Specialisation
3264 Rewrite rules can be used to get the same effect as a feature
3265 present in earlier version of GHC:
3268 {-# SPECIALIZE fromIntegral :: Int8 -> Int16 = int8ToInt16 #-}
3271 This told GHC to use <function>int8ToInt16</function> instead of <function>fromIntegral</function> whenever
3272 the latter was called with type <literal>Int8 -> Int16</literal>. That is, rather than
3273 specialising the original definition of <function>fromIntegral</function> the programmer is
3274 promising that it is safe to use <function>int8ToInt16</function> instead.
3278 This feature is no longer in GHC. But rewrite rules let you do the
3283 "fromIntegral/Int8/Int16" fromIntegral = int8ToInt16
3287 This slightly odd-looking rule instructs GHC to replace <function>fromIntegral</function>
3288 by <function>int8ToInt16</function> <emphasis>whenever the types match</emphasis>. Speaking more operationally,
3289 GHC adds the type and dictionary applications to get the typed rule
3292 forall (d1::Integral Int8) (d2::Num Int16) .
3293 fromIntegral Int8 Int16 d1 d2 = int8ToInt16
3297 this rule does not need to be in the same file as fromIntegral,
3298 unlike the <literal>SPECIALISE</literal> pragmas which currently do (so that they
3299 have an original definition available to specialise).
3305 <title>Controlling what's going on</title>
3313 Use <option>-ddump-rules</option> to see what transformation rules GHC is using.
3319 Use <option>-ddump-simpl-stats</option> to see what rules are being fired.
3320 If you add <option>-dppr-debug</option> you get a more detailed listing.
3326 The defintion of (say) <function>build</function> in <FileName>PrelBase.lhs</FileName> looks llike this:
3329 build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
3330 {-# INLINE build #-}
3334 Notice the <literal>INLINE</literal>! That prevents <literal>(:)</literal> from being inlined when compiling
3335 <literal>PrelBase</literal>, so that an importing module will “see” the <literal>(:)</literal>, and can
3336 match it on the LHS of a rule. <literal>INLINE</literal> prevents any inlining happening
3337 in the RHS of the <literal>INLINE</literal> thing. I regret the delicacy of this.
3344 In <filename>ghc/lib/std/PrelBase.lhs</filename> look at the rules for <function>map</function> to
3345 see how to write rules that will do fusion and yet give an efficient
3346 program even if fusion doesn't happen. More rules in <filename>PrelList.lhs</filename>.
3358 <sect1 id="generic-classes">
3359 <title>Generic classes</title>
3361 <para>(Note: support for generic classes is currently broken in
3365 The ideas behind this extension are described in detail in "Derivable type classes",
3366 Ralf Hinze and Simon Peyton Jones, Haskell Workshop, Montreal Sept 2000, pp94-105.
3367 An example will give the idea:
3375 fromBin :: [Int] -> (a, [Int])
3377 toBin {| Unit |} Unit = []
3378 toBin {| a :+: b |} (Inl x) = 0 : toBin x
3379 toBin {| a :+: b |} (Inr y) = 1 : toBin y
3380 toBin {| a :*: b |} (x :*: y) = toBin x ++ toBin y
3382 fromBin {| Unit |} bs = (Unit, bs)
3383 fromBin {| a :+: b |} (0:bs) = (Inl x, bs') where (x,bs') = fromBin bs
3384 fromBin {| a :+: b |} (1:bs) = (Inr y, bs') where (y,bs') = fromBin bs
3385 fromBin {| a :*: b |} bs = (x :*: y, bs'') where (x,bs' ) = fromBin bs
3386 (y,bs'') = fromBin bs'
3389 This class declaration explains how <literal>toBin</literal> and <literal>fromBin</literal>
3390 work for arbitrary data types. They do so by giving cases for unit, product, and sum,
3391 which are defined thus in the library module <literal>Generics</literal>:
3395 data a :+: b = Inl a | Inr b
3396 data a :*: b = a :*: b
3399 Now you can make a data type into an instance of Bin like this:
3401 instance (Bin a, Bin b) => Bin (a,b)
3402 instance Bin a => Bin [a]
3404 That is, just leave off the "where" clasuse. Of course, you can put in the
3405 where clause and over-ride whichever methods you please.
3409 <title> Using generics </title>
3410 <para>To use generics you need to</para>
3413 <para>Use the flags <option>-fglasgow-exts</option> (to enable the extra syntax),
3414 <option>-fgenerics</option> (to generate extra per-data-type code),
3415 and <option>-package lang</option> (to make the <literal>Generics</literal> library
3419 <para>Import the module <literal>Generics</literal> from the
3420 <literal>lang</literal> package. This import brings into
3421 scope the data types <literal>Unit</literal>,
3422 <literal>:*:</literal>, and <literal>:+:</literal>. (You
3423 don't need this import if you don't mention these types
3424 explicitly; for example, if you are simply giving instance
3425 declarations.)</para>
3430 <sect2> <title> Changes wrt the paper </title>
3432 Note that the type constructors <literal>:+:</literal> and <literal>:*:</literal>
3433 can be written infix (indeed, you can now use
3434 any operator starting in a colon as an infix type constructor). Also note that
3435 the type constructors are not exactly as in the paper (Unit instead of 1, etc).
3436 Finally, note that the syntax of the type patterns in the class declaration
3437 uses "<literal>{|</literal>" and "<literal>|}</literal>" brackets; curly braces
3438 alone would ambiguous when they appear on right hand sides (an extension we
3439 anticipate wanting).
3443 <sect2> <title>Terminology and restrictions</title>
3445 Terminology. A "generic default method" in a class declaration
3446 is one that is defined using type patterns as above.
3447 A "polymorphic default method" is a default method defined as in Haskell 98.
3448 A "generic class declaration" is a class declaration with at least one
3449 generic default method.
3457 Alas, we do not yet implement the stuff about constructor names and
3464 A generic class can have only one parameter; you can't have a generic
3465 multi-parameter class.
3471 A default method must be defined entirely using type patterns, or entirely
3472 without. So this is illegal:
3475 op :: a -> (a, Bool)
3476 op {| Unit |} Unit = (Unit, True)
3479 However it is perfectly OK for some methods of a generic class to have
3480 generic default methods and others to have polymorphic default methods.
3486 The type variable(s) in the type pattern for a generic method declaration
3487 scope over the right hand side. So this is legal (note the use of the type variable ``p'' in a type signature on the right hand side:
3491 op {| p :*: q |} (x :*: y) = op (x :: p)
3499 The type patterns in a generic default method must take one of the forms:
3505 where "a" and "b" are type variables. Furthermore, all the type patterns for
3506 a single type constructor (<literal>:*:</literal>, say) must be identical; they
3507 must use the same type variables. So this is illegal:
3511 op {| a :+: b |} (Inl x) = True
3512 op {| p :+: q |} (Inr y) = False
3514 The type patterns must be identical, even in equations for different methods of the class.
3515 So this too is illegal:
3519 op1 {| a :*: b |} (x :*: y) = True
3522 op2 {| p :*: q |} (x :*: y) = False
3524 (The reason for this restriction is that we gather all the equations for a particular type consructor
3525 into a single generic instance declaration.)
3531 A generic method declaration must give a case for each of the three type constructors.
3537 The type for a generic method can be built only from:
3539 <listitem> <para> Function arrows </para> </listitem>
3540 <listitem> <para> Type variables </para> </listitem>
3541 <listitem> <para> Tuples </para> </listitem>
3542 <listitem> <para> Arbitrary types not involving type variables </para> </listitem>
3544 Here are some example type signatures for generic methods:
3547 op2 :: Bool -> (a,Bool)
3548 op3 :: [Int] -> a -> a
3551 Here, op1, op2, op3 are OK, but op4 is rejected, because it has a type variable
3555 This restriction is an implementation restriction: we just havn't got around to
3556 implementing the necessary bidirectional maps over arbitrary type constructors.
3557 It would be relatively easy to add specific type constructors, such as Maybe and list,
3558 to the ones that are allowed.</para>
3563 In an instance declaration for a generic class, the idea is that the compiler
3564 will fill in the methods for you, based on the generic templates. However it can only
3569 The instance type is simple (a type constructor applied to type variables, as in Haskell 98).
3574 No constructor of the instance type has unboxed fields.
3578 (Of course, these things can only arise if you are already using GHC extensions.)
3579 However, you can still give an instance declarations for types which break these rules,
3580 provided you give explicit code to override any generic default methods.
3588 The option <option>-ddump-deriv</option> dumps incomprehensible stuff giving details of
3589 what the compiler does with generic declarations.
3594 <sect2> <title> Another example </title>
3596 Just to finish with, here's another example I rather like:
3600 nCons {| Unit |} _ = 1
3601 nCons {| a :*: b |} _ = 1
3602 nCons {| a :+: b |} _ = nCons (bot::a) + nCons (bot::b)
3605 tag {| Unit |} _ = 1
3606 tag {| a :*: b |} _ = 1
3607 tag {| a :+: b |} (Inl x) = tag x
3608 tag {| a :+: b |} (Inr y) = nCons (bot::a) + tag y
3614 <sect1 id="newtype-deriving">
3615 <title>Generalised derived instances for newtypes</title>
3618 When you define an abstract type using <literal>newtype</literal>, you may want
3619 the new type to inherit some instances from its representation. In
3620 Haskell 98, you can inherit instances of <literal>Eq</literal>, <literal>Ord</literal>,
3621 <literal>Enum</literal> and <literal>Bounded</literal> by deriving them, but for any
3622 other classes you have to write an explicit instance declaration. For
3623 example, if you define
3626 newtype Dollars = Dollars Int
3629 and you want to use arithmetic on <literal>Dollars</literal>, you have to
3630 explicitly define an instance of <literal>Num</literal>:
3633 instance Num Dollars where
3634 Dollars a + Dollars b = Dollars (a+b)
3637 All the instance does is apply and remove the <literal>newtype</literal>
3638 constructor. It is particularly galling that, since the constructor
3639 doesn't appear at run-time, this instance declaration defines a
3640 dictionary which is <emphasis>wholly equivalent</emphasis> to the <literal>Int</literal>
3641 dictionary, only slower!
3644 <sect2> <title> Generalising the deriving clause </title>
3646 GHC now permits such instances to be derived instead, so one can write
3648 newtype Dollars = Dollars Int deriving (Eq,Show,Num)
3651 and the implementation uses the <emphasis>same</emphasis> <literal>Num</literal> dictionary
3652 for <literal>Dollars</literal> as for <literal>Int</literal>. Notionally, the compiler
3653 derives an instance declaration of the form
3656 instance Num Int => Num Dollars
3659 which just adds or removes the <literal>newtype</literal> constructor according to the type.
3663 We can also derive instances of constructor classes in a similar
3664 way. For example, suppose we have implemented state and failure monad
3665 transformers, such that
3668 instance Monad m => Monad (State s m)
3669 instance Monad m => Monad (Failure m)
3671 In Haskell 98, we can define a parsing monad by
3673 type Parser tok m a = State [tok] (Failure m) a
3676 which is automatically a monad thanks to the instance declarations
3677 above. With the extension, we can make the parser type abstract,
3678 without needing to write an instance of class <literal>Monad</literal>, via
3681 newtype Parser tok m a = Parser (State [tok] (Failure m) a)
3684 In this case the derived instance declaration is of the form
3686 instance Monad (State [tok] (Failure m)) => Monad (Parser tok m)
3689 Notice that, since <literal>Monad</literal> is a constructor class, the
3690 instance is a <emphasis>partial application</emphasis> of the new type, not the
3691 entire left hand side. We can imagine that the type declaration is
3692 ``eta-converted'' to generate the context of the instance
3697 We can even derive instances of multi-parameter classes, provided the
3698 newtype is the last class parameter. In this case, a ``partial
3699 application'' of the class appears in the <literal>deriving</literal>
3700 clause. For example, given the class
3703 class StateMonad s m | m -> s where ...
3704 instance Monad m => StateMonad s (State s m) where ...
3706 then we can derive an instance of <literal>StateMonad</literal> for <literal>Parser</literal>s by
3708 newtype Parser tok m a = Parser (State [tok] (Failure m) a)
3709 deriving (Monad, StateMonad [tok])
3712 The derived instance is obtained by completing the application of the
3713 class to the new type:
3716 instance StateMonad [tok] (State [tok] (Failure m)) =>
3717 StateMonad [tok] (Parser tok m)
3722 As a result of this extension, all derived instances in newtype
3723 declarations are treated uniformly (and implemented just by reusing
3724 the dictionary for the representation type), <emphasis>except</emphasis>
3725 <literal>Show</literal> and <literal>Read</literal>, which really behave differently for
3726 the newtype and its representation.
3730 <sect2> <title> A more precise specification </title>
3732 Derived instance declarations are constructed as follows. Consider the
3733 declaration (after expansion of any type synonyms)
3736 newtype T v1...vn = T' (S t1...tk vk+1...vn) deriving (c1...cm)
3739 where <literal>S</literal> is a type constructor, <literal>t1...tk</literal> are
3741 <literal>vk+1...vn</literal> are type variables which do not occur in any of
3742 the <literal>ti</literal>, and the <literal>ci</literal> are partial applications of
3743 classes of the form <literal>C t1'...tj'</literal>. The derived instance
3744 declarations are, for each <literal>ci</literal>,
3747 instance ci (S t1...tk vk+1...v) => ci (T v1...vp)
3749 where <literal>p</literal> is chosen so that <literal>T v1...vp</literal> is of the
3750 right <emphasis>kind</emphasis> for the last parameter of class <literal>Ci</literal>.
3754 As an example which does <emphasis>not</emphasis> work, consider
3756 newtype NonMonad m s = NonMonad (State s m s) deriving Monad
3758 Here we cannot derive the instance
3760 instance Monad (State s m) => Monad (NonMonad m)
3763 because the type variable <literal>s</literal> occurs in <literal>State s m</literal>,
3764 and so cannot be "eta-converted" away. It is a good thing that this
3765 <literal>deriving</literal> clause is rejected, because <literal>NonMonad m</literal> is
3766 not, in fact, a monad --- for the same reason. Try defining
3767 <literal>>>=</literal> with the correct type: you won't be able to.
3771 Notice also that the <emphasis>order</emphasis> of class parameters becomes
3772 important, since we can only derive instances for the last one. If the
3773 <literal>StateMonad</literal> class above were instead defined as
3776 class StateMonad m s | m -> s where ...
3779 then we would not have been able to derive an instance for the
3780 <literal>Parser</literal> type above. We hypothesise that multi-parameter
3781 classes usually have one "main" parameter for which deriving new
3782 instances is most interesting.
3790 ;;; Local Variables: ***
3792 ;;; sgml-parent-document: ("users_guide.sgml" "book" "chapter" "sect1") ***
projects / ghc-hetmet.git / blob