top | back | next

- Haskell 98 mode: This should be used for the highest level of compatibility
with the Haskell 98 standard; known deviations
from the standard are documented in Section 9. In this mode,
any attempt to use Hugs specific extensions should trigger an error
message. Although there are some fairly substantial differences
between Haskell 1.4 and Haskell 98, our experience is that most
programs written for Haskell 1.4 or earlier will need only minor
modifications before they can be loaded and used from Hugs in
Haskell 98 mode. Note, however, that some of the demo programs
included in the standard Hugs distribution
*will not*work in Haskell 98 mode. - Hugs mode: This enables a number of advanced Hugs features such as
type system extensions, restricted type synonyms, etc. Most of
these features
are described in more detail in the following sections. The
underlying core language remains as in Haskell 98 mode: For example,
the member function of the
`Functor`class is still called`fmap`, there is no`Eval`class, fixity declarations can appear anywhere that a type signature is permitted, comprehension syntax is still restricted to lists, and so on.

The remainder of this section sketches some of the extensions that are currently supported when the interpreter is running in Hugs mode.

Multiple parameter type classes seem to have many potentially interesting applications [multi]. However, some practical attempts to use them have failed as a result of frustrating ambiguity problems. This occurs because the mechanisms that are used to resolve overloading are not aggressive enough. Or, to put it another way, the type relations that are defined by a collection of class and instance declarations are often too general for practical applications, where programmers might expect stronger dependencies between parameters. In the rest of this section we will describe these problems in more detail. We will also describe the mechanisms introduced in the September 1999 release of Hugs that allow programmers to declare explicit dependencies between parameters, avoiding these difficulties in many cases, and making multiple parameter classes more useful for some important practical applications.

class Collects e ce where

empty :: ce

insert :: e -> ce -> ce

member :: e -> ce -> Bool

instance Eq e => Collects e [e] where ...

instance Eq e => Collects e (e -> Bool) where ...

instance Collects Char BitSet where ...

instance (Hashable e, Collects a ce)

=> Collects e (Array Int ce) where ...

empty :: Collects e ce => ce

ERROR: Ambiguous type signature in class declaration

*** ambiguous type : Collects a b => b

*** assigned to : empty

f x y = insert x . insert y

g = f True 'a'

f :: (Collects a c, Collects b c) => a -> b -> c -> c

g :: (Collects Bool c, Collects Char c) => c -> c

class Collects e c where

empty :: c e

insert :: e -> c e -> c e

member :: e -> c e -> Bool

`empty`has type`Collects e c => c e`, which is not ambiguous.- The function
`f`from the previous section has a more accurate type:

f :: (Collects e c) => e -> e -> c e -> c e

- The function
`g`from the previous section is now rejected with a type error as we would hope because the type of`f`does not allow the two arguments to have different types.

There is, however, a catch. This version of the `Collects` class
is nowhere near as general as the original class seemed to be: only
one of the four instances in Section 7.1.1 can be
used with this version of `Collects` because only one of
them---the instance for lists---has a collection type
that can be written in the form `c e`, for some type
constructor `c`, and element type `e`.

To start with an abstract example, consider a declaration such as:
`
class C a b where ...
`which tells us simply that

class D a b | a -> b where ...

class E a b | a -> b, b -> a where ...

More generally, dependencies take the form `x1 ... xn -> y1 ... ym`,
where `x1`, ..., `xn`, and `y1`, ..., `yn` are
type variables with `n`>0 and `m`>=0, meaning that the
`y` parameters are uniquely determined by the `x` parameters.
Spaces can be used as separators if more than one variable appears
on any single side of a dependency, as in `t -> a b`. Note that a
class may be annotated with multiple dependencies using commas as
separators, as in the definition of `E` above.
Some dependencies that we can write in this notation are redundant,
and will be rejected by Hugs because they don't serve any useful purpose,
and may instead indicate an error in the program. Examples of dependencies
like this include `a -> a`, `a -> a a`, `a ->`, etc.
There can also be some redundancy if multiple dependencies are given,
as in `a->b, b->c, a->c`, and in which some subset implies the
remaining dependencies. Examples like this are not treated as errors.
Note that dependencies appear only in class declarations, and not in
any other part of the language. In particular, the syntax for instance
declarations, class constraints, and types is completely unchanged.

By including dependencies in a class declaration, we provide a
mechanism for the programmer to specify each multiple parameter class
more precisely. The compiler, on the other hand, is responsible for
ensuring that the set of instances that are in scope at any given
point in the program is consistent with any declared dependencies.
For example, the following pair of instance declarations cannot
appear together in the same scope because they violate the dependency
for `D`, even though either one on its own would be acceptable:
`
instance D Bool Int where ...
instance D Bool Char where ...
`Note also that the following declaration is not allowed, even by itself:

instance D [a] b where ...

instance D t s where ...

The benefit of including dependency information is that it allows us to
define more general multiple parameter classes, without ambiguity
problems, and with the benefit of more accurate types. To illustrate
this, we return to the collection class example, and annotate the
original definition from Section 7.1.1 with a
simple dependency:
`
class Collects e ce | ce -> e where
empty :: ce
insert :: e -> ce -> ce
member :: e -> ce -> Bool
`The dependency

What about the ambiguity problems that we encountered
with the original definition? The `empty` function
still has type `Collects e ce => ce`, but it is no
longer necessary to regard that as an ambiguous type:
Although the variable `e` does not appear on the
right of the `=>` symbol, the dependency for
class `Collects` tells us that it is uniquely
determined by `ce`, which *does* appear on the right
of the `=>` symbol. Hence the context in
which `empty` is used can still give enough information
to determine types for both `ce` and `e`, without
ambiguity. More generally, we need only regard a type as
ambiguous if it contains a variable on the left of the `=>` that
is not uniquely determined (either directly or indirectly) by
the variables on the right.

Dependencies also help to produce more accurate types for user defined
functions, and hence to provide earlier detection of errors, and less
cluttered types for programmers to work with. Recall the previous
definition for a function `f`:
`
f x y = insert x y = insert x . insert y
`for which we originally obtained a type:

f :: (Collects a c, Collects b c) => a -> b -> c -> c

f :: (Collects a c) => a -> a -> c -> c

Although we have given only a few examples here, it should be clear that the addition of dependency information can help to make multiple parameter classes more useful in practice, avoiding ambiguity problems, and allowing more general sets of instance declarations.

instance (Eq [Tree a], Eq a) => Eq (Tree a) where ...

instance Eq a => Eq (Bool -> a) where ...

instance Num a => Num (String,[a]) where ...

It is possible that some syntactic restrictions on instance declarations might be introduced at some point in the future in a way that will offer much of the flexibility of the current approach, but in a way that guarantees decidability.

If the command line option `+m` is selected, then a lazier
form of overlapping instances is supported, which we refer to
as `multi instance resolution.' The main idea is to omit the
normal tests for overlapping instances, but to generate an
error message if the type checker can find more than one way
to resolve overloading for a particular instance of the class.
For example, with the `+m` option selected, then the two
instance declarations in the following program are accepted,
even though they have overlapping (in fact, identical) constraints
on the right of the `=>` symbol:
`
class Numeric a where describe :: a -> String
instance Integral a => Numeric a where describe n = "Integral"
instance Floating a => Numeric a where describe n = "Floating"
`As it turns out, these instances do not cause any problems in
practice because they can be distinguished by the contexts on
the left of the

Main> describe (23::Int)

"Integral"

Main> describe (23::Float)

"Floating"

Main>

In Hugs mode, these restrictions are relaxed, and any type,
whether in head normal form or not, is permitted to appear
in a context. For example, the principal type of an
expression `(\x -> x==[])` is `Eq [a] => [a] -> Bool`,
reflecting the fact that the equality function is used to compare
lists of type `[a]`. In previous versions of Hugs, and in Haskell 98,
an inferred type of `Eq a => [a] -> Bool` would have been produced
for this term. The latter type can still be used if an explicit type
signature is provided for the term, assuming that an instance declaration
of the form:
`
instance Eq a => Eq [a] where ...
`is in scope. For example, the following program is valid:

f :: Eq a => [a] -> Bool

f x = x==[]

The current implementation does not use our prefered syntax for record operations; too many of the symbols that we would like to have used are already used in conflicting ways elsewhere in the syntax of Haskell 98.

(a = True, b = "Hello", c = 12::Int)

(c = 12::Int, a = True, b = "Hello")

Prelude> #a (a = True, b = "Hello", c = 12::Int)

True

Prelude> #b (a = True, b = "Hello", c = 12::Int)

"Hello"

Prelude> #c (a = True, b = "Hello", c = 12::Int)

12

Prelude>

Record values can also be inspected by using pattern matching, with a
syntax that mirrors the notation used for constructing a record. For
example:
`
Prelude> (\(a=x, c=y, b=_) -> (y,x)) (a = True, b = "Hello", c = 12::Int)
(12,True)
Prelude>
`The order of fields in a record pattern

Prelude> [ x | (a=[x], b=True) <- [(b=undefined, a=[]), (a=[2],b=True)]]

[2]

Prelude>

Prelude> [ x | (b=True, a=[x]) <- [(b=undefined, a=[]), (a=[2],b=True)]]

Program error: {undefined}

Prelude>

Prelude> (a = True, b = "Hello", c = 12::Int)

ERROR: Cannot find "show" function for:

*** expression : (a=True, b="Hello", c=12)

*** of type : Rec (a::Bool, b::[Char], c::Int)

Prelude>

Prelude> :load Trex

Trex> (a = True, b = "Hello", c = 12::Int)

(a=True, b="Hello", c=12)

Trex> (c = 12::Int, a = True, b = "Hello")

(a=True, b="Hello", c=12)

Trex>

In a similar way, it is sometimes useful to test whether two records
are equal by using the `==` operator. Any program that requires
this feature can obtain the necessary instances of the `Eq` class
by importing the `Trex` library, as shown above.

Of course, like all other values in Haskell, records have types,
and these are written using expressions of the
form `Rec r` where `Rec` is a built-in type constructor
and `r` represents a `row' that associates labels with
types. For example:
`
Trex> :t (c = 12::Int, a = True, b = "Hello")
(a=True, b="Hello", c=12) :: Rec (a::Bool, b::[Char], c::Int)
Trex>
`The type here tells us, unsurprisingly, that the
record

Trex> (a=True, b="Hello", c=12) :: Rec (b::String, c::Int, a::Bool)

(a=True, b="Hello", c=12)

Trex>

Trex> (a=True, b="Hello", c=12) :: Rec (b::String, c::Int)

ERROR: Type error in type signature expression

*** term : (a=True, b="Hello", c=12)

*** type : Rec (a::Bool, b::[Char], c::a)

*** does not match : Rec (b::String, c::Int)

*** because : field mismatch

Trex>

In the simplest case, any given record `r` can be extended with a
new field labelled `l`, provided that `r` does not already
include an `l` field. For example, we can
construct `(a=True, b="Hello")` by
extending `(a = True)` with a field `b="Hello"`:
`
Trex> (b = "Hello" | (a = True))
(a=True, b="Hello")
Trex>
`Alternatively, we can construct the same result by
extending

Trex> (a = True | (b = "Hello"))

(a=True, b="Hello")

Trex>

Trex> (a=True, b="Hello", c=12::Int | (b1="World"))

(a=True, b="Hello", b1="World", c=12)

Trex>

Trex> (a=True | (a=False))

ERROR: Repeated label "a" in record (a=True, a=False)

Trex> (a=True | r) where r = (a=12::Int)

ERROR: (a::Int) already includes a "a" field

Trex>

Much the same syntax can be used in patterns to decompose record values:
`
Trex> (\(b=bval | r) -> (bval,r)) (a=True, b="Hello")
("Hello",(a=True))
Trex>
`In the previous examples, we saw how a record could be extended with
new fields. As this example shows, we can use pattern matching to do
the reverse operation, removing fields from a record.

We can also use pattern matching to understand how selector functions
like `#a`, `#b`, and so on are implemented. For example,
the selector `#x` is equivalent to the
function `(\ (x=value | _) -> value)`.
A selector function like this is polymorphic in the sense that it can
be used with *any*record containing an `x` field, regardless of
the type associated with that particular component, or of any other fields
that the record might contain:
`
Trex> (\(x=value | _) -> value) (x=True, b="Hello")
True
Trex> (\(x=value | _) -> value) (name="Hugs", age=2, x="None")
"None"
Trex>
`To understand how this works, it is useful to look at the type that
Hugs assigns to this particular selector function:

Trex> :type (\(x=value | _) -> value)

\(x=value | _) -> value :: r\x => Rec (x::a | r) -> a

Trex>

`Rec (x::a | r)`is the type of a record with an`x`component of type`a`. The*row variable*`r`represents the rest of the row; that is, it represents any other fields in the record apart from`x`. This syntax---for record type extension---was chosen to mirror the syntax that we have already seen in the examples above for record value extension.- The constraint
`r\x`tells us that the type on the right of the`=>`symbol is only valid if "`r`lacks`x`," that is, if`r`is a row that does not contain an`x`field. If you are already familiar with Haskell type classes, then you may like to think of`\x`as a kind of class constraint, written with postfix syntax, whose instances are precisely the rows without an`x`field.

In fact, the built-in selector functions have exactly the same type as
the user-defined selector shown above:
`
Prelude> :type #x
#x :: b\x => Rec (x::a | b) -> a
Prelude>
`The row constraints that we see here can also occur in the type of any
function that operates on record values if the types of those records
are not fully determined at compile-time. For example, given the following
definition:

average r = (#x r + #y r) / 2

average :: (Fractional a, b\y, b\x) => Rec (y::a, x::a | b) -> a

average :: (Fractional a) => Rec (x::a, y::a) -> a

average :: (r\x, r\y) => Rec (x::Double, y::Double | r) -> Double

average :: Rec (x::Double, y::Double) -> Double

average :: Rec (x::Double, y::Double, z::Bool) -> Double

These examples show an important difference between the system of
records described here, and the record facilities provided by SML.
In particular, SML prohibits definitions that involve records for
which the complete set of fields cannot be determined at compile-time.
So, the SML equivalent of the `average` function described above would
be rejected because there is no way to determine if the record `r` will
have any fields other than `x` or `y`. SML programmers usually
avoid such problems by giving a type annotation that completely specifies the
structure of the record. But, of course, if a definition is limited
in this way, then it also less flexible.

With the current implementation of our type system, there is an advantage to knowing the full type of a record at compile-time because it allows the compiler to generate more efficient code. However, unlike SML, the type system also offers the extra flexibility of polymorphism and extensibility over records if that is needed.

p :: Eq a => a -> Bool

p x = x==x && p [x]

p :: Eq a => a -> Bool

p x = x==x && q [x]

q x = x==x && p [x]

amazed :: (forall a. a -> a) -> (Bool,Char)

amazed i = (i True, i 'a')

twice :: (forall b. b -> f b) -> a -> f (f a)

twice f = f . f

- In Hugs mode,
`forall`is a reserved word. - Quantified variables may be of any kind,
including
`*`(types) or`* -> *`(unary type constructors), as in the examples above. - Variables quantified in a
`forall`type must appear in the scope of the quantifier. Unused quantified variables would serve no useful purpose, and are perhaps most likely to occur as the result of mispelling a variable name. - Nested quantifiers are not allowed, and quantifiers can only appear in the types of function arguments, not in the results.
- A function can only take polymorphic arguments if an explicit type
signature is provided for that function. Any call to such a function
must have at least as many arguments as are needed to include the
rightmost argument with a quantified type. For example, neither of
the functions
`amazed`or`twice`defined above can be partially applied. - It is not necessary for all polymorphic arguments to appear at the
beginning of a type signature. For example, the following type
signature is valid:
However, as a consequence of the rules given above, the

eg :: Int -> (forall a. [a] -> [a]) -> Int -> [Int]

`eg`function defined here must always be applied to at least two arguments, even though the first of these does not have a polymorphic type. - In the definition of a function, there must be at least as many
arguments on the left hand side of the definition as are needed to
included the rightmost argument with a quantified type. Only
variables (or a wildcard,
`_`) can be used as arguments on the left hand side of a function definition where a value of polymorphic type is expected. - Arbitrary expressions can be used for polymorphic arguments in a
function call, provided that they can be assigned the necessary
polymorphic type. For example, all of the following expressions
are valid calls to the
`amazed`function defined above:

amazed (let i x = x in i)

amazed (\x -> x)

amazed (id . id . id . id)

amazed (id id id id id)

data Monad1 m = MkMonad1 {

unit1 :: (forall a. a -> m a),

bind1 :: (forall a b. m a -> (a -> m b) -> m b)

}

data Monad2 m = MkMonad2 (forall a. a -> m a)

(forall a b. m a -> (a -> m b) -> m b)

listMonad1 = MkMonad1 {unit1 = \x->[x],

bind1 = \x f -> concat (map f x)}

listMonad2 = MkMonad1 (\x->[x]) (\x f -> concat (map f x))

(forall b. b -> m b) -> (forall b c. m b -> (b->m c) -> m c) -> Monad1 m

(forall b. b -> m b) -> (forall b c. m b -> (b->m c) -> m c) -> Monad2 m

Monad1 []

Monad2 []

halfListMonad :: (forall a b. [a] -> (a -> [b]) -> [b]) -> Monad2 []

halfListMonad b = MkMonad2 (\x -> [x]) b

The `runST` primitive that is used in work with lazy state
threads is now handled using the facilities described here to define
it as a function:
`
runST :: (forall s. ST s a) -> a
`As a result, it is no longer necessary to build the

- It is an error for a variable to be used in a type where a more
specific type is inferred. For example,
`(\(x::a) -> not x)`is not a valid expression. - It is an error for distinct variables to be used where the
types concerned are the same. For example, the expression
`(\(x::a) (y::b) -> [x,y])`is not valid. - Type variables bound in a pattern may be used in type signatures
or further pattern type annotations within the scope of the
binding. For example:
In current versions of Haskell, there is no way to write a type for the local function

f (x::a) = let g :: a -> [a]

g y = [x,y]

in g x

`g`in this example because of the convention that free type variables are implicitly bound by a universal quantifier. In this example, the variable is instead bound in the pattern`(x::a)`and so the type assigned to`g`is actually monomorphic. - Type signatures do not introduce bindings for type variables,
but may involve type variables bound in an enclosing scope.
For example, there is no direct relation between the
variable
`t`appearing in the type signature and the variable`t`appearing in the pattern annotation in the following code:The explanation for this is that the type signature for

pair :: t -> s -> (t,s)

pair x (y::t) = (x,y::t)

`pair`(which might, in practice, be separated from the definition) is not in the scope of the binding of the variables`x`and`y`. - In the current implementation, pattern type annotations that include variables are allowed on the left hand side of a pattern binding, but scope only over the right hand side of the binding.

data Appl = forall a. MkAppl (a -> Int) a (a -> a)

MkAppl :: (a -> Int) -> a -> (a -> a) -> Appl.

good1 (MkAppl f x i) = f x

good2 (MkAppl f x i) = map f (iterate i x)

bad1 (MkAppl f x i) = x

bad3 y = let g (MkAppl f x i) = length [x,y] + 1 in True

good (MkAppl f (x::a) i) = map f (iterate i x :: [a])

A datatype whose definition involves existentially quantified variables
cannot use the standard Haskell mechanisms for `deriving` instances
of standard classes like `Eq` and `Show`. If instances of
these classes are required, then they must be provided explicitly by
the programmer. It is possible, however, to attach type class
constraints to existentially quantified variables in a datatype
definition. For example, we can define a type of "`show`"able
values using the definition:
`
data Showable = forall a. Show a => MkShowable a
`This will mean that all of the operations of the specified classes, in
this case just

instance Show Showable where

show (MkShowable x) = show x

Main> map show [MkShowable 3, MkShowable True, MkShowable 'a']

["3", "True", "'a'"]

Main>

type T a1 ... am = rhs in f1, ..., fn

data T a1 ... am = ...

type Stack a = [a] in emptyStack, push, pop, top, isEmpty

emptyStack :: Stack a

emptyStack = []

push :: a -> Stack a -> Stack a

push = (:)

pop :: Stack a -> Stack a

pop [] = error "pop: empty stack"

pop (_:xs) = xs

top :: Stack a -> a

top [] = error "top: empty stack"

top (x:_) = x

isEmpty :: Stack a -> Bool

isEmpty = null

? emptyStack ++ [1]

ERROR: Type error in application

*** Expression : emptyStack ++ [1]

*** Term : emptyStack

*** Type : Stack b

*** Does not match : [a]

?

instance Eq a => Eq (Stack a) where

s1 == s2 | isEmpty s1 = isEmpty s2

| isEmpty s2 = isEmpty s1

| otherwise = top s1 == top s2 && pop s1 == pop s2

type Stack a = [a] in

emptyStack :: Stack a,

push :: a -> Stack a -> Stack a,

pop :: Stack a -> Stack a,

top :: Stack a -> a,

isEmpty :: Stack a -> Bool

emptyStack = []

...

A variable is called *dynamically bound* when it is bound by the calling
context of a function and *statically bound* 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.

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 `(?x::t') => t`,
which says "this function uses a dynamically-bound variable
`?x` of type `t'`".
For example, the following expresses the type of a sort
function, implicitly parameterized by a comparison function
named `cmp`.
`
sort :: (?cmp :: a -> a -> Bool) => [a] -> [a]
`The dynamic binding constraints are just a new form of
predicate in the type class system.

An implicit parameter is introduced by the special form `?x`,
where `x` 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 `sortBy` function:
`
sortBy :: (a -> a -> Bool) -> [a] -> [a]
sort :: (?cmp :: a -> a -> Bool) => [a] -> [a]
sort = sortBy ?cmp
`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

least :: (?cmp :: a -> a -> Bool) => [a] -> a

least xs = fst (sort xs)

However, 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 `(?x, ?x)` is `(?x::a) => (a, a)`,
and not `(?x::a, ?x::b) => (a, b)`, as would be the case for
type class constraints.

An implicit parameter is bound using an expression of the
form `e with binds`, or equivalently as `dlet binds in e`,
where both `with` and `dlet` (dynamic let) are new keywords.
These forms bind the implicit parameters arising in the body, not
the free variables as a `let` or `where` would do.
For example, we define the `min` function by binding `cmp`.
`
min :: [a] -> a
min = least with ?cmp = (<=)
`Syntactically, the

top | back | next

May 22, 1999