</para>
<para>
-Executive summary of our extensions:
-</para>
-
- <variablelist>
-
- <varlistentry>
- <term>Unboxed types and primitive operations:</Term>
- <listitem>
- <para>You can get right down to the raw machine types and
- operations; included in this are “primitive
- arrays” (direct access to Big Wads of Bytes). Please
- see <XRef LinkEnd="glasgow-unboxed"> and following.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Type system extensions:</term>
- <listitem>
- <para> GHC supports a large number of extensions to Haskell's
- type system. Specifically:</para>
-
- <variablelist>
- <varlistentry>
- <term>Multi-parameter type classes:</term>
- <listitem>
- <para><xref LinkEnd="multi-param-type-classes"></para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Functional dependencies:</term>
- <listitem>
- <para><xref LinkEnd="functional-dependencies"></para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Implicit parameters:</term>
- <listitem>
- <para><xref LinkEnd="implicit-parameters"></para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Linear implicit parameters:</term>
- <listitem>
- <para><xref LinkEnd="linear-implicit-parameters"></para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Local universal quantification:</term>
- <listitem>
- <para><xref LinkEnd="universal-quantification"></para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Extistentially quantification in data types:</term>
- <listitem>
- <para><xref LinkEnd="existential-quantification"></para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Scoped type variables:</term>
- <listitem>
- <para>Scoped type variables enable the programmer to
- supply type signatures for some nested declarations,
- where this would not be legal in Haskell 98. Details in
- <xref LinkEnd="scoped-type-variables">.</para>
- </listitem>
- </varlistentry>
- </variablelist>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Pattern guards</term>
- <listitem>
- <para>Instead of being a boolean expression, a guard is a list
- of qualifiers, exactly as in a list comprehension. See <xref
- LinkEnd="pattern-guards">.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Data types with no constructors</term>
- <listitem>
- <para>See <xref LinkEnd="nullary-types">.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Parallel list comprehensions</term>
- <listitem>
- <para>An extension to the list comprehension syntax to support
- <literal>zipWith</literal>-like functionality. See <xref
- linkend="parallel-list-comprehensions">.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Foreign calling:</term>
- <listitem>
- <para>Just what it sounds like. We provide
- <emphasis>lots</emphasis> of rope that you can dangle around
- your neck. Please see <xref LinkEnd="ffi">.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Pragmas</term>
- <listitem>
- <para>Pragmas are special instructions to the compiler placed
- in the source file. The pragmas GHC supports are described in
- <xref LinkEnd="pragmas">.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Rewrite rules:</term>
- <listitem>
- <para>The programmer can specify rewrite rules as part of the
- source program (in a pragma). GHC applies these rewrite rules
- wherever it can. Details in <xref
- LinkEnd="rewrite-rules">.</para>
- </listitem>
- </varlistentry>
-
- <varlistentry>
- <term>Generic classes:</term>
- <listitem>
- <para>(Note: support for generic classes is currently broken
- in GHC 5.02).</para>
-
- <para>Generic class declarations allow you to define a class
- whose methods say how to work over an arbitrary data type.
- Then it's really easy to make any new type into an instance of
- the class. This generalises the rather ad-hoc "deriving"
- feature of Haskell 98. Details in <xref
- LinkEnd="generic-classes">.</para>
- </listitem>
- </varlistentry>
- </variablelist>
-
-<para>
Before you get too carried away working at the lowest level (e.g.,
sloshing <literal>MutableByteArray#</literal>s around your
program), you may wish to check if there are libraries that provide a
<xref linkend="book-hslibs">.
</para>
+<!-- LANGUAGE OPTIONS -->
<sect1 id="options-language">
<title>Language options</title>
</sect1>
<!-- UNBOXED TYPES AND PRIMITIVE OPERATIONS -->
+<!-- included from primitives.sgml -->
&primitives;
-<sect1 id="glasgow-ST-monad">
-<title>Primitive state-transformer monad</title>
-
-<para>
-<indexterm><primary>state transformers (Glasgow extensions)</primary></indexterm>
-<indexterm><primary>ST monad (Glasgow extension)</primary></indexterm>
-</para>
-
-<para>
-This monad underlies our implementation of arrays, mutable and
-immutable, and our implementation of I/O, including “C calls”.
-</para>
-
-<para>
-The <literal>ST</literal> library, which provides access to the
-<function>ST</function> monad, is described in <xref
-linkend="sec-ST">.
-</para>
-
-</sect1>
-
-<sect1 id="glasgow-prim-arrays">
-<title>Primitive arrays, mutable and otherwise
-</title>
-
-<para>
-<indexterm><primary>primitive arrays (Glasgow extension)</primary></indexterm>
-<indexterm><primary>arrays, primitive (Glasgow extension)</primary></indexterm>
-</para>
-
-<para>
-GHC knows about quite a few flavours of Large Swathes of Bytes.
-</para>
-
-<para>
-First, GHC distinguishes between primitive arrays of (boxed) Haskell
-objects (type <literal>Array# obj</literal>) and primitive arrays of bytes (type
-<literal>ByteArray#</literal>).
-</para>
-
-<para>
-Second, it distinguishes between…
-<variablelist>
-
-<varlistentry>
-<term>Immutable:</term>
-<listitem>
-<para>
-Arrays that do not change (as with “standard” Haskell arrays); you
-can only read from them. Obviously, they do not need the care and
-attention of the state-transformer monad.
-</para>
-</listitem>
-</varlistentry>
-<varlistentry>
-<term>Mutable:</term>
-<listitem>
-<para>
-Arrays that may be changed or “mutated.” All the operations on them
-live within the state-transformer monad and the updates happen
-<emphasis>in-place</emphasis>.
-</para>
-</listitem>
-</varlistentry>
-<varlistentry>
-<term>“Static” (in C land):</term>
-<listitem>
-<para>
-A C routine may pass an <literal>Addr#</literal> pointer back into Haskell land. There
-are then primitive operations with which you may merrily grab values
-over in C land, by indexing off the “static” pointer.
-</para>
-</listitem>
-</varlistentry>
-<varlistentry>
-<term>“Stable” pointers:</term>
-<listitem>
-<para>
-If, for some reason, you wish to hand a Haskell pointer (i.e.,
-<emphasis>not</emphasis> an unboxed value) to a C routine, you first make the
-pointer “stable,” so that the garbage collector won't forget that it
-exists. That is, GHC provides a safe way to pass Haskell pointers to
-C.
-</para>
-
-<para>
-Please see <xref LinkEnd="sec-stable-pointers"> for more details.
-</para>
-</listitem>
-</varlistentry>
-<varlistentry>
-<term>“Foreign objects”:</term>
-<listitem>
-<para>
-A “foreign object” is a safe way to pass an external object (a
-C-allocated pointer, say) to Haskell and have Haskell do the Right
-Thing when it no longer references the object. So, for example, C
-could pass a large bitmap over to Haskell and say “please free this
-memory when you're done with it.”
-</para>
-
-<para>
-Please see <xref LinkEnd="sec-ForeignObj"> for more details.
-</para>
-</listitem>
-</varlistentry>
-</variablelist>
-</para>
-
-<para>
-The libraries documentatation gives more details on all these
-“primitive array” types and the operations on them.
-</para>
-
-</sect1>
+<!-- TYPE SYSTEM EXTENSIONS -->
+<sect1 id="type-extensions">
+<title>Type system extensions</title>
-<sect1 id="nullary-types">
+<sect2 id="nullary-types">
<title>Data types with no constructors</title>
<para>With the <option>-fglasgow-exts</option> flag, GHC lets you declare
<para>Such data types have only one value, namely bottom.
Nevertheless, they can be useful when defining "phantom types".</para>
-</sect1>
-
-<sect1 id="pattern-guards">
-<title>Pattern guards</title>
-
-<para>
-<indexterm><primary>Pattern guards (Glasgow extension)</primary></indexterm>
-The discussion that follows is an abbreviated version of Simon Peyton Jones's original <ULink URL="http://research.microsoft.com/~simonpj/Haskell/guards.html">proposal</ULink>. (Note that the proposal was written before pattern guards were implemented, so refers to them as unimplemented.)
-</para>
-
-<para>
-Suppose we have an abstract data type of finite maps, with a
-lookup operation:
-
-<programlisting>
-lookup :: FiniteMap -> Int -> Maybe Int
-</programlisting>
-
-The lookup returns <function>Nothing</function> if the supplied key is not in the domain of the mapping, and <function>(Just v)</function> otherwise,
-where <VarName>v</VarName> is the value that the key maps to. Now consider the following definition:
-</para>
-
-<programlisting>
-clunky env var1 var2 | ok1 && ok2 = val1 + val2
-| otherwise = var1 + var2
-where
- m1 = lookup env var1
- m2 = lookup env var2
- ok1 = maybeToBool m1
- ok2 = maybeToBool m2
- val1 = expectJust m1
- val2 = expectJust m2
-</programlisting>
-
-<para>
-The auxiliary functions are
-</para>
-
-<programlisting>
-maybeToBool :: Maybe a -> Bool
-maybeToBool (Just x) = True
-maybeToBool Nothing = False
-
-expectJust :: Maybe a -> a
-expectJust (Just x) = x
-expectJust Nothing = error "Unexpected Nothing"
-</programlisting>
-
-<para>
-What is <function>clunky</function> doing? The guard <literal>ok1 &&
-ok2</literal> checks that both lookups succeed, using
-<function>maybeToBool</function> to convert the <function>Maybe</function>
-types to booleans. The (lazily evaluated) <function>expectJust</function>
-calls extract the values from the results of the lookups, and binds the
-returned values to <VarName>val1</VarName> and <VarName>val2</VarName>
-respectively. If either lookup fails, then clunky takes the
-<literal>otherwise</literal> case and returns the sum of its arguments.
-</para>
-
-<para>
-This is certainly legal Haskell, but it is a tremendously verbose and
-un-obvious way to achieve the desired effect. Arguably, a more direct way
-to write clunky would be to use case expressions:
-</para>
-
-<programlisting>
-clunky env var1 var1 = case lookup env var1 of
- Nothing -> fail
- Just val1 -> case lookup env var2 of
- Nothing -> fail
- Just val2 -> val1 + val2
-where
- fail = val1 + val2
-</programlisting>
-
-<para>
-This is a bit shorter, but hardly better. Of course, we can rewrite any set
-of pattern-matching, guarded equations as case expressions; that is
-precisely what the compiler does when compiling equations! The reason that
-Haskell provides guarded equations is because they allow us to write down
-the cases we want to consider, one at a time, independently of each other.
-This structure is hidden in the case version. Two of the right-hand sides
-are really the same (<function>fail</function>), and the whole expression
-tends to become more and more indented.
-</para>
+</sect2>
+<sect2 id="class-method-types">
+<title>Class method types
+</title>
<para>
-Here is how I would write clunky:
-</para>
-
+Haskell 98 prohibits class method types to mention constraints on the
+class type variable, thus:
<programlisting>
-clunky env var1 var1
- | Just val1 <- lookup env var1
- , Just val2 <- lookup env var2
- = val1 + val2
-...other equations for clunky...
+ class Seq s a where
+ fromList :: [a] -> s a
+ elem :: Eq a => a -> s a -> Bool
</programlisting>
-
-<para>
-The semantics should be clear enough. The qualifers are matched in order.
-For a <literal><-</literal> qualifier, which I call a pattern guard, the
-right hand side is evaluated and matched against the pattern on the left.
-If the match fails then the whole guard fails and the next equation is
-tried. If it succeeds, then the appropriate binding takes place, and the
-next qualifier is matched, in the augmented environment. Unlike list
-comprehensions, however, the type of the expression to the right of the
-<literal><-</literal> is the same as the type of the pattern to its
-left. The bindings introduced by pattern guards scope over all the
-remaining guard qualifiers, and over the right hand side of the equation.
-</para>
-
-<para>
-Just as with list comprehensions, boolean expressions can be freely mixed
-with among the pattern guards. For example:
+The type of <literal>elem</literal> is illegal in Haskell 98, because it
+contains the constraint <literal>Eq a</literal>, constrains only the
+class type variable (in this case <literal>a</literal>).
</para>
-
-<programlisting>
-f x | [y] <- x
- , y > 3
- , Just z <- h y
- = ...
-</programlisting>
-
<para>
-Haskell's current guards therefore emerge as a special case, in which the
-qualifier list has just one element, a boolean expression.
+With the <option>-fglasgow-exts</option> GHC lifts this restriction.
</para>
-</sect1>
-
- <sect1 id="parallel-list-comprehensions">
- <title>Parallel List Comprehensions</title>
- <indexterm><primary>list comprehensions</primary><secondary>parallel</secondary>
- </indexterm>
- <indexterm><primary>parallel list comprehensions</primary>
- </indexterm>
-
- <para>Parallel list comprehensions are a natural extension to list
- comprehensions. List comprehensions can be thought of as a nice
- syntax for writing maps and filters. Parallel comprehensions
- extend this to include the zipWith family.</para>
-
- <para>A parallel list comprehension has multiple independent
- branches of qualifier lists, each separated by a `|' symbol. For
- example, the following zips together two lists:</para>
-
-<programlisting>
- [ (x, y) | x <- xs | y <- ys ]
-</programlisting>
-
- <para>The behavior of parallel list comprehensions follows that of
- zip, in that the resulting list will have the same length as the
- shortest branch.</para>
-
- <para>We can define parallel list comprehensions by translation to
- regular comprehensions. Here's the basic idea:</para>
-
- <para>Given a parallel comprehension of the form: </para>
-
-<programlisting>
- [ e | p1 <- e11, p2 <- e12, ...
- | q1 <- e21, q2 <- e22, ...
- ...
- ]
-</programlisting>
-
- <para>This will be translated to: </para>
-
-<programlisting>
- [ e | ((p1,p2), (q1,q2), ...) <- zipN [(p1,p2) | p1 <- e11, p2 <- e12, ...]
- [(q1,q2) | q1 <- e21, q2 <- e22, ...]
- ...
- ]
-</programlisting>
-
- <para>where `zipN' is the appropriate zip for the given number of
- branches.</para>
- </sect1>
+</sect2>
-<sect1 id="multi-param-type-classes">
+<sect2 id="multi-param-type-classes">
<title>Multi-parameter type classes
</title>
feedback.
</para>
-<sect2>
+<sect3>
<title>Types</title>
<para>
This choice recovers principal types, a property that Haskell 1.4 does not have.
</para>
-</sect2>
+</sect3>
-<sect2>
+<sect3>
<title>Class declarations</title>
<para>
</para>
-</sect2>
+</sect3>
-<sect2 id="instance-decls">
+<sect3 id="instance-decls">
<title>Instance declarations</title>
<para>
</para>
-</sect2>
+</sect3>
-</sect1>
+</sect2>
-<sect1 id="implicit-parameters">
+<sect2 id="implicit-parameters">
<title>Implicit parameters
</title>
27th ACM Symposium on Principles of Programming Languages (POPL'00),
Boston, Jan 2000.
</para>
-
+<para>(Most of the following, stil rather incomplete, documentation is due to Jeff Lewis.)</para>
<para>
-There should be more documentation, but there isn't (yet). Yell if you need it.
+A variable is called <emphasis>dynamically bound</emphasis> when it is bound by the calling
+context of a function and <emphasis>statically bound</emphasis> when bound by the callee's
+context. In Haskell, all variables are statically bound. Dynamic
+binding of variables is a notion that goes back to Lisp, but was later
+discarded in more modern incarnations, such as Scheme. Dynamic binding
+can be very confusing in an untyped language, and unfortunately, typed
+languages, in particular Hindley-Milner typed languages like Haskell,
+only support static scoping of variables.
</para>
-<itemizedlist>
-<listitem>
-<para> You can't have an implicit parameter in the context of a class or instance
-declaration. For example, both these declarations are illegal:
+<para>
+However, by a simple extension to the type class system of Haskell, we
+can support dynamic binding. Basically, we express the use of a
+dynamically bound variable as a constraint on the type. These
+constraints lead to types of the form <literal>(?x::t') => t</literal>, which says "this
+function uses a dynamically-bound variable <literal>?x</literal>
+of type <literal>t'</literal>". For
+example, the following expresses the type of a sort function,
+implicitly parameterized by a comparison function named <literal>cmp</literal>.
<programlisting>
- class (?x::Int) => C a where ...
- instance (?x::a) => Foo [a] where ...
+ sort :: (?cmp :: a -> a -> Bool) => [a] -> [a]
</programlisting>
-Reason: exactly which implicit parameter you pick up depends on exactly where
-you invoke a function. But the ``invocation'' of instance declarations is done
-behind the scenes by the compiler, so it's hard to figure out exactly where it is done.
-Easiest thing is to outlaw the offending types.</para>
-</listitem>
+The dynamic binding constraints are just a new form of predicate in the type class system.
+</para>
+<para>
+An implicit parameter is introduced by the special form <literal>?x</literal>,
+where <literal>x</literal> is
+any valid identifier. Use if this construct also introduces new
+dynamic binding constraints. For example, the following definition
+shows how we can define an implicitly parameterized sort function in
+terms of an explicitly parameterized <literal>sortBy</literal> function:
+<programlisting>
+ sortBy :: (a -> a -> Bool) -> [a] -> [a]
+ sort :: (?cmp :: a -> a -> Bool) => [a] -> [a]
+ sort = sortBy ?cmp
+</programlisting>
+Dynamic binding constraints behave just like other type class
+constraints in that they are automatically propagated. Thus, when a
+function is used, its implicit parameters are inherited by the
+function that called it. For example, our <literal>sort</literal> function might be used
+to pick out the least value in a list:
+<programlisting>
+ least :: (?cmp :: a -> a -> Bool) => [a] -> a
+ least xs = fst (sort xs)
+</programlisting>
+Without lifting a finger, the <literal>?cmp</literal> parameter is
+propagated to become a parameter of <literal>least</literal> as well. With explicit
+parameters, the default is that parameters must always be explicit
+propagated. With implicit parameters, the default is to always
+propagate them.
+</para>
+<para>
+An implicit parameter differs from other type class constraints in the
+following way: All uses of a particular implicit parameter must have
+the same type. This means that the type of <literal>(?x, ?x)</literal>
+is <literal>(?x::a) => (a,a)</literal>, and not
+<literal>(?x::a, ?x::b) => (a, b)</literal>, as would be the case for type
+class constraints.
+</para>
+<para>
+An implicit parameter is bound using an expression of the form
+<emphasis>expr</emphasis> <literal>with</literal> <emphasis>binds</emphasis>,
+where <literal>with</literal> is a new keyword. This form binds the implicit
+parameters arising in the body, not the free variables as a <literal>let</literal> or
+<literal>where</literal> would do. For example, we define the <literal>min</literal> function by binding
+<literal>cmp</literal>.
+<programlisting>
+ min :: [a] -> a
+ min = least with ?cmp = (<=)
+</programlisting>
+Syntactically, the <emphasis>binds</emphasis> part of a <literal>with</literal> construct must be a
+collection of simple bindings to variables (no function-style
+bindings, and no type signatures); these bindings are neither
+polymorphic or recursive.
+</para>
+<para>
+Note the following additional constraints:
+<itemizedlist>
+<listitem>
+<para> You can't have an implicit parameter in the context of a class or instance
+declaration. For example, both these declarations are illegal:
+<programlisting>
+ class (?x::Int) => C a where ...
+ instance (?x::a) => Foo [a] where ...
+</programlisting>
+Reason: exactly which implicit parameter you pick up depends on exactly where
+you invoke a function. But the ``invocation'' of instance declarations is done
+behind the scenes by the compiler, so it's hard to figure out exactly where it is done.
+Easiest thing is to outlaw the offending types.</para>
+</listitem>
</itemizedlist>
+</para>
-</sect1>
+</sect2>
-<sect1 id="linear-implicit-parameters">
+<sect2 id="linear-implicit-parameters">
<title>Linear implicit parameters
</title>
<para>
<para>
For example:
<programlisting>
+ import GHC.Exts( Splittable )
+
data NameSupply = ...
splitNS :: NameSupply -> (NameSupply, NameSupply)
newName :: NameSupply -> Name
- instance PrelSplit.Splittable NameSupply where
+ instance Splittable NameSupply where
split = splitNS
Notice the call to 'split' introduced by the type checker.
How did it know to use 'splitNS'? Because what it really did
was to introduce a call to the overloaded function 'split',
-defined by
+defined by the class <literal>Splittable</literal>:
<programlisting>
class Splittable a where
split :: a -> (a,a)
<programlisting>
g :: (Splittable a, %ns :: a) => b -> (b,a,a)
</programlisting>
-The <literal>Splittable</literal> class is built into GHC. It's defined in <literal>PrelSplit</literal>,
-and exported by <literal>GlaExts</literal>.
+The <literal>Splittable</literal> class is built into GHC. It's exported by module
+<literal>GHC.Exts</literal>.
</para>
<para>
Other points:
</itemizedlist>
</para>
-<sect2><title>Warnings</title>
+<sect3><title>Warnings</title>
<para>
The monomorphism restriction is even more important than usual.
Haskell programs without knowing their typing.
</para>
-</sect2>
+</sect3>
-</sect1>
+</sect2>
-<sect1 id="functional-dependencies">
+<sect2 id="functional-dependencies">
<title>Functional dependencies
</title>
<para>
There should be more documentation, but there isn't (yet). Yell if you need it.
</para>
-</sect1>
+</sect2>
-<sect1 id="universal-quantification">
-<title>Explicit universal quantification
+<sect2 id="universal-quantification">
+<title>Arbitrary-rank polymorphism
</title>
<para>
</para>
-<sect2 id="univ">
+<sect3 id="univ">
<title>Examples
</title>
from the <literal>MonadT</literal> data structure, rather than using pattern
matching.
</para>
-</sect2>
+</sect3>
-<sect2>
+<sect3>
<title>Type inference</title>
<para>
it needs to know.
</para>
-</sect2>
+</sect3>
-<sect2 id="implicit-quant">
+<sect3 id="implicit-quant">
<title>Implicit quantification</title>
<para>
can write your for-alls explicitly. Indeed, doing so is strongly advised
for rank-2 types.
</para>
+</sect3>
</sect2>
-</sect1>
-<sect1 id="hoist">
-<title>Type synonyms and hoisting
+<sect2>
+<title>Liberalised type synonyms
</title>
<para>
-Type synonmys are like macros at the type level, and GHC is much more liberal
-about them than Haskell 98. In particular:
+Type synonmys are like macros at the type level, and
+GHC does validity checking on types <emphasis>only after expanding type synonyms</emphasis>.
+That means that GHC can be very much more liberal about type synonyms than Haskell 98:
<itemizedlist>
<listitem> <para>You can write a <literal>forall</literal> (including overloading)
in a type synonym, thus:
h x = (# x, x #)
</programlisting>
</para></listitem>
+
+<listitem><para>
+You can apply a type synonym to a forall type:
+<programlisting>
+ type Foo a = a -> a -> Bool
+
+ f :: Foo (forall b. b->b)
+</programlisting>
+After epxanding the synonym, <literal>f</literal> has the legal (in GHC) type:
+<programlisting>
+ f :: (forall b. b->b) -> (forall b. b->b) -> Bool
+</programlisting>
+</para></listitem>
+
+<listitem><para>
+You can apply a type synonym to a partially applied type synonym:
+<programlisting>
+ type Generic i o = forall x. i x -> o x
+ type Id x = x
+
+ foo :: Generic Id []
+</programlisting>
+After epxanding the synonym, <literal>foo</literal> has the legal (in GHC) type:
+<programlisting>
+ foo :: forall x. x -> [x]
+</programlisting>
+</para></listitem>
+
</itemizedlist>
</para>
+
+<para>
+GHC currently does kind checking before expanding synonyms (though even that
+could be changed.)
+</para>
<para>
-GHC does validity checking on types <emphasis>after expanding type synonyms</emphasis>
-so, for example,
+After expanding type synonyms, GHC does validity checking on types, looking for
+the following mal-formedness which isn't detected simply by kind checking:
+<itemizedlist>
+<listitem><para>
+Type constructor applied to a type involving for-alls.
+</para></listitem>
+<listitem><para>
+Unboxed tuple on left of an arrow.
+</para></listitem>
+<listitem><para>
+Partially-applied type synonym.
+</para></listitem>
+</itemizedlist>
+So, for example,
this will be rejected:
<programlisting>
type Pr = (# Int, Int #)
</programlisting>
because GHC does not allow unboxed tuples on the left of a function arrow.
</para>
+</sect2>
+<sect2 id="hoist">
+<title>For-all hoisting</title>
<para>
-However, it is often convenient to use these sort of generalised synonyms at the right hand
+It is often convenient to use generalised type synonyms at the right hand
end of an arrow, thus:
<programlisting>
type Discard a = forall b. a -> b -> a
g :: Int -> Int -> forall b. b -> Int
</programlisting>
</para>
-</sect1>
+</sect2>
-<sect1 id="existential-quantification">
+<sect2 id="existential-quantification">
<title>Existentially quantified data constructors
</title>
quite a bit of object-oriented-like programming this way.
</para>
-<sect2 id="existential">
+<sect3 id="existential">
<title>Why existential?
</title>
adding a new existential quantification construct.
</para>
-</sect2>
+</sect3>
-<sect2>
+<sect3>
<title>Type classes</title>
<para>
universal quantification earlier.
</para>
-</sect2>
+</sect3>
-<sect2>
+<sect3>
<title>Restrictions</title>
<para>
</para>
-</sect2>
-
-</sect1>
-
-<sect1 id="sec-assertions">
-<title>Assertions
-<indexterm><primary>Assertions</primary></indexterm>
-</title>
-
-<para>
-If you want to make use of assertions in your standard Haskell code, you
-could define a function like the following:
-</para>
-
-<para>
-
-<programlisting>
-assert :: Bool -> a -> a
-assert False x = error "assertion failed!"
-assert _ x = x
-</programlisting>
-
-</para>
-
-<para>
-which works, but gives you back a less than useful error message --
-an assertion failed, but which and where?
-</para>
-
-<para>
-One way out is to define an extended <function>assert</function> function which also
-takes a descriptive string to include in the error message and
-perhaps combine this with the use of a pre-processor which inserts
-the source location where <function>assert</function> was used.
-</para>
-
-<para>
-Ghc offers a helping hand here, doing all of this for you. For every
-use of <function>assert</function> in the user's source:
-</para>
-
-<para>
-
-<programlisting>
-kelvinToC :: Double -> Double
-kelvinToC k = assert (k >= 0.0) (k+273.15)
-</programlisting>
-
-</para>
-
-<para>
-Ghc will rewrite this to also include the source location where the
-assertion was made,
-</para>
-
-<para>
-
-<programlisting>
-assert pred val ==> assertError "Main.hs|15" pred val
-</programlisting>
-
-</para>
+</sect3>
-<para>
-The rewrite is only performed by the compiler when it spots
-applications of <function>Exception.assert</function>, so you can still define and
-use your own versions of <function>assert</function>, should you so wish. If not,
-import <literal>Exception</literal> to make use <function>assert</function> in your code.
-</para>
-
-<para>
-To have the compiler ignore uses of assert, use the compiler option
-<option>-fignore-asserts</option>. <indexterm><primary>-fignore-asserts option</primary></indexterm> That is,
-expressions of the form <literal>assert pred e</literal> will be rewritten to <literal>e</literal>.
-</para>
-
-<para>
-Assertion failures can be caught, see the documentation for the
-<literal>Exception</literal> library (<xref linkend="sec-Exception">)
-for the details.
-</para>
-
-</sect1>
+</sect2>
-<sect1 id="scoped-type-variables">
+<sect2 id="scoped-type-variables">
<title>Scoped Type Variables
</title>
So much for the basic idea. Here are the details.
</para>
-<sect2>
+<sect3>
<title>What a pattern type signature means</title>
<para>
A type variable brought into scope by a pattern type signature is simply
w (x::a) = x -- a unifies with [b]
</programlisting>
-</sect2>
+</sect3>
-<sect2>
+<sect3>
<title>Scope and implicit quantification</title>
<para>
</para>
-</sect2>
+</sect3>
-<sect2>
+<sect3>
<title>Result type signatures</title>
<para>
Result type signatures are not yet implemented in Hugs.
</para>
-</sect2>
+</sect3>
-<sect2>
+<sect3>
<title>Where a pattern type signature can occur</title>
<para>
</itemizedlist>
</para>
+</sect3>
</sect2>
+<sect2 id="sec-kinding">
+<title>Explicitly-kinded quantification</title>
+
+<para>
+Haskell infers the kind of each type variable. Sometimes it is nice to be able
+to give the kind explicitly as (machine-checked) documentation,
+just as it is nice to give a type signature for a function. On some occasions,
+it is essential to do so. For example, in his paper "Restricted Data Types in Haskell" (Haskell Workshop 1999)
+John Hughes had to define the data type:
+<Screen>
+ data Set cxt a = Set [a]
+ | Unused (cxt a -> ())
+</Screen>
+The only use for the <literal>Unused</literal> constructor was to force the correct
+kind for the type variable <literal>cxt</literal>.
+</para>
+<para>
+GHC now instead allows you to specify the kind of a type variable directly, wherever
+a type variable is explicitly bound. Namely:
+<itemizedlist>
+<listitem><para><literal>data</literal> declarations:
+<Screen>
+ data Set (cxt :: * -> *) a = Set [a]
+</Screen></para></listitem>
+<listitem><para><literal>type</literal> declarations:
+<Screen>
+ type T (f :: * -> *) = f Int
+</Screen></para></listitem>
+<listitem><para><literal>class</literal> declarations:
+<Screen>
+ class (Eq a) => C (f :: * -> *) a where ...
+</Screen></para></listitem>
+<listitem><para><literal>forall</literal>'s in type signatures:
+<Screen>
+ f :: forall (cxt :: * -> *). Set cxt Int
+</Screen></para></listitem>
+</itemizedlist>
+</para>
+
+<para>
+The parentheses are required. Some of the spaces are required too, to
+separate the lexemes. If you write <literal>(f::*->*)</literal> you
+will get a parse error, because "<literal>::*->*</literal>" is a
+single lexeme in Haskell.
+</para>
+
+<para>
+As part of the same extension, you can put kind annotations in types
+as well. Thus:
+<Screen>
+ f :: (Int :: *) -> Int
+ g :: forall a. a -> (a :: *)
+</Screen>
+The syntax is
+<Screen>
+ atype ::= '(' ctype '::' kind ')
+</Screen>
+The parentheses are required.
+</para>
+</sect2>
</sect1>
+<!-- ==================== End of type system extensions ================= -->
+
+
+<!-- ==================== ASSERTIONS ================= -->
+
+<sect1 id="sec-assertions">
+<title>Assertions
+<indexterm><primary>Assertions</primary></indexterm>
+</title>
+
+<para>
+If you want to make use of assertions in your standard Haskell code, you
+could define a function like the following:
+</para>
+
+<para>
+
+<programlisting>
+assert :: Bool -> a -> a
+assert False x = error "assertion failed!"
+assert _ x = x
+</programlisting>
+
+</para>
+
+<para>
+which works, but gives you back a less than useful error message --
+an assertion failed, but which and where?
+</para>
+
+<para>
+One way out is to define an extended <function>assert</function> function which also
+takes a descriptive string to include in the error message and
+perhaps combine this with the use of a pre-processor which inserts
+the source location where <function>assert</function> was used.
+</para>
+
+<para>
+Ghc offers a helping hand here, doing all of this for you. For every
+use of <function>assert</function> in the user's source:
+</para>
+
+<para>
+
+<programlisting>
+kelvinToC :: Double -> Double
+kelvinToC k = assert (k >= 0.0) (k+273.15)
+</programlisting>
+
+</para>
+
+<para>
+Ghc will rewrite this to also include the source location where the
+assertion was made,
+</para>
+
+<para>
+
+<programlisting>
+assert pred val ==> assertError "Main.hs|15" pred val
+</programlisting>
+
+</para>
+
+<para>
+The rewrite is only performed by the compiler when it spots
+applications of <function>Exception.assert</function>, so you can still define and
+use your own versions of <function>assert</function>, should you so wish. If not,
+import <literal>Exception</literal> to make use <function>assert</function> in your code.
+</para>
+
+<para>
+To have the compiler ignore uses of assert, use the compiler option
+<option>-fignore-asserts</option>. <indexterm><primary>-fignore-asserts option</primary></indexterm> That is,
+expressions of the form <literal>assert pred e</literal> will be rewritten to <literal>e</literal>.
+</para>
+
+<para>
+Assertion failures can be caught, see the documentation for the
+<literal>Exception</literal> library (<xref linkend="sec-Exception">)
+for the details.
+</para>
+
+</sect1>
+
+<!-- ====================== PATTERN GUARDS ======================= -->
+
+<sect1 id="pattern-guards">
+<title>Pattern guards</title>
+
+<para>
+<indexterm><primary>Pattern guards (Glasgow extension)</primary></indexterm>
+The discussion that follows is an abbreviated version of Simon Peyton Jones's original <ULink URL="http://research.microsoft.com/~simonpj/Haskell/guards.html">proposal</ULink>. (Note that the proposal was written before pattern guards were implemented, so refers to them as unimplemented.)
+</para>
+
+<para>
+Suppose we have an abstract data type of finite maps, with a
+lookup operation:
+
+<programlisting>
+lookup :: FiniteMap -> Int -> Maybe Int
+</programlisting>
+
+The lookup returns <function>Nothing</function> if the supplied key is not in the domain of the mapping, and <function>(Just v)</function> otherwise,
+where <VarName>v</VarName> is the value that the key maps to. Now consider the following definition:
+</para>
+
+<programlisting>
+clunky env var1 var2 | ok1 && ok2 = val1 + val2
+| otherwise = var1 + var2
+where
+ m1 = lookup env var1
+ m2 = lookup env var2
+ ok1 = maybeToBool m1
+ ok2 = maybeToBool m2
+ val1 = expectJust m1
+ val2 = expectJust m2
+</programlisting>
+
+<para>
+The auxiliary functions are
+</para>
+
+<programlisting>
+maybeToBool :: Maybe a -> Bool
+maybeToBool (Just x) = True
+maybeToBool Nothing = False
+
+expectJust :: Maybe a -> a
+expectJust (Just x) = x
+expectJust Nothing = error "Unexpected Nothing"
+</programlisting>
+
+<para>
+What is <function>clunky</function> doing? The guard <literal>ok1 &&
+ok2</literal> checks that both lookups succeed, using
+<function>maybeToBool</function> to convert the <function>Maybe</function>
+types to booleans. The (lazily evaluated) <function>expectJust</function>
+calls extract the values from the results of the lookups, and binds the
+returned values to <VarName>val1</VarName> and <VarName>val2</VarName>
+respectively. If either lookup fails, then clunky takes the
+<literal>otherwise</literal> case and returns the sum of its arguments.
+</para>
+
+<para>
+This is certainly legal Haskell, but it is a tremendously verbose and
+un-obvious way to achieve the desired effect. Arguably, a more direct way
+to write clunky would be to use case expressions:
+</para>
+
+<programlisting>
+clunky env var1 var1 = case lookup env var1 of
+ Nothing -> fail
+ Just val1 -> case lookup env var2 of
+ Nothing -> fail
+ Just val2 -> val1 + val2
+where
+ fail = val1 + val2
+</programlisting>
+
+<para>
+This is a bit shorter, but hardly better. Of course, we can rewrite any set
+of pattern-matching, guarded equations as case expressions; that is
+precisely what the compiler does when compiling equations! The reason that
+Haskell provides guarded equations is because they allow us to write down
+the cases we want to consider, one at a time, independently of each other.
+This structure is hidden in the case version. Two of the right-hand sides
+are really the same (<function>fail</function>), and the whole expression
+tends to become more and more indented.
+</para>
+
+<para>
+Here is how I would write clunky:
+</para>
+
+<programlisting>
+clunky env var1 var1
+ | Just val1 <- lookup env var1
+ , Just val2 <- lookup env var2
+ = val1 + val2
+...other equations for clunky...
+</programlisting>
+
+<para>
+The semantics should be clear enough. The qualifers are matched in order.
+For a <literal><-</literal> qualifier, which I call a pattern guard, the
+right hand side is evaluated and matched against the pattern on the left.
+If the match fails then the whole guard fails and the next equation is
+tried. If it succeeds, then the appropriate binding takes place, and the
+next qualifier is matched, in the augmented environment. Unlike list
+comprehensions, however, the type of the expression to the right of the
+<literal><-</literal> is the same as the type of the pattern to its
+left. The bindings introduced by pattern guards scope over all the
+remaining guard qualifiers, and over the right hand side of the equation.
+</para>
+
+<para>
+Just as with list comprehensions, boolean expressions can be freely mixed
+with among the pattern guards. For example:
+</para>
+
+<programlisting>
+f x | [y] <- x
+ , y > 3
+ , Just z <- h y
+ = ...
+</programlisting>
+
+<para>
+Haskell's current guards therefore emerge as a special case, in which the
+qualifier list has just one element, a boolean expression.
+</para>
+</sect1>
+
+<!-- ===================== PARALLEL LIST COMPREHENSIONS =================== -->
+
+ <sect1 id="parallel-list-comprehensions">
+ <title>Parallel List Comprehensions</title>
+ <indexterm><primary>list comprehensions</primary><secondary>parallel</secondary>
+ </indexterm>
+ <indexterm><primary>parallel list comprehensions</primary>
+ </indexterm>
+
+ <para>Parallel list comprehensions are a natural extension to list
+ comprehensions. List comprehensions can be thought of as a nice
+ syntax for writing maps and filters. Parallel comprehensions
+ extend this to include the zipWith family.</para>
+
+ <para>A parallel list comprehension has multiple independent
+ branches of qualifier lists, each separated by a `|' symbol. For
+ example, the following zips together two lists:</para>
+
+<programlisting>
+ [ (x, y) | x <- xs | y <- ys ]
+</programlisting>
+
+ <para>The behavior of parallel list comprehensions follows that of
+ zip, in that the resulting list will have the same length as the
+ shortest branch.</para>
+
+ <para>We can define parallel list comprehensions by translation to
+ regular comprehensions. Here's the basic idea:</para>
+
+ <para>Given a parallel comprehension of the form: </para>
+
+<programlisting>
+ [ e | p1 <- e11, p2 <- e12, ...
+ | q1 <- e21, q2 <- e22, ...
+ ...
+ ]
+</programlisting>
+
+ <para>This will be translated to: </para>
+
+<programlisting>
+ [ e | ((p1,p2), (q1,q2), ...) <- zipN [(p1,p2) | p1 <- e11, p2 <- e12, ...]
+ [(q1,q2) | q1 <- e21, q2 <- e22, ...]
+ ...
+ ]
+</programlisting>
+
+ <para>where `zipN' is the appropriate zip for the given number of
+ branches.</para>
+
+ </sect1>
+
+<!-- =============================== PRAGMAS =========================== -->
<sect1 id="pragmas">
<title>Pragmas</title>
</sect1>
+<!-- ======================= REWRITE RULES ======================== -->
+
<sect1 id="rewrite-rules">
<title>Rewrite rules
projects / ghc-hetmet.git / blobdiff