40.1 The annoying monomorphism restriction

One of the most annoying features of Haskell, when trying to program in a combinatorial style, is the monomorphism restriction. It means that a definition that is not syntactically a function is not allowed to be overloaded, unless an explicit type signature is provided.

As a simple example, say that you are going to use the function show a lot and want to introduce a shorter name, s say. Because of the monomorphism restriction, you can not write

s = show

There are two solutions: you can provide a type signature

s :: Show a => a -> String
s = show

or you can eta-expand the definition

s x = show x

In the Fudget library, we have used the eta expansion trick whenever possible, since the inclusion of explicit type signatures just entail extra maintenance work when the library is changed. For example, when a type is renamed or a function is made more general, an arbitrary number of type signatures may need to be updated.

Unfortunately, the eta expansion trick can not always be used, because not all overloaded values are functions. For example, fudgets are not functions, so in case you want to introduce a short name for displayF, you have to use a type signature:

dF :: (Graphic a) => F a b
dF = displayF

Even more unfortunately, there are cases when it is not possible to express the type signature. This occurs when the definition is local to another definition which is polymorphic. It can happen that the local type depends on type variables in the outer definition, but Haskell has no mechanism for expressing such types explicitly. Although these cases turn out to be rare in practice, it is a principal flaw of the language.

40.2 The Haskell string + class system anomaly

An inelegance of Haskell is that you can not directly make the type String an instance of a class. This is due to the combination of two facts:

• String is not a data type, but a synonym for [Char].
• Instance definition can only be made for uninstantiated type constructors, i.e., you can make instances for Char, and for lists in general, but you can not make a particular instance for [Char]. (See [JJM97] for a discussion of class system design choices.)

This has affected the classes Graphic, ColorGen and FontGen presented in Chapter 27, and FormElement in Section 29.2. At one point during the development, we avoided the problem by defining a data type that was used instead of strings,

newtype Name = Name String

but since this required the use of the constructor Name in a lot of places, we later resorted to the same hack that is used for the Haskell classes Show and Read, i.e., we added extra methods for dealing with lists to the classes. This allow the methods for strings to be defined in the instance declarations for Char. This means that instead of getting an instance for String, you get instances for Char, String, [String], [[String]] and so on. For our classes it was not too difficult to invent a meaning for the extra instances: Char was treated as one-character strings. For the Graphic class, (nested) lists of strings are drawn by drawing all the strings using some layout chosen by the layout system. For the ColorGen and FontGen classes, lists were taken to mean spare alternatives: you can write, e.g., ["midnightblue","black"] to provide one nice color and a safe fallback color. Empty lists can give run-time errors, but are also likely to cause typing problems (making the overloading unresolvable) which are discovered at compile time.

40.3 Existentially quantified types

Existentially quantified types [LO92] provide a very nice language feature, in particular in conjunction with Haskell's type classes [Läu94]. We feel that this feature should have been made part the Haskell standard a long time ago. As it is now, existentially quantified types are provided as a language extension by some Haskell compilers (at the time of writing, only HBC [Aug97], as far as we know).

We have found existential types useful in several contexts: the implementation of Gadgets in Fudgets (Chapter 31), the combinators for syntax-oriented manipulation (Chapter 28) and the datatypes for graphics (Chapter 27).

Since existential types are not part of the Haskell standard, we have tried to keep their use away from core machinery of the Fudget library. Instead we use them on the side to provide a nice feature as an additional bonus. This has affected how we used them in the graphics data types. For example, since leaves of drawing usually are of type Gfx, we could have used existential quantification directly in the Drawing type,

data Drawing lbl
  =  Graphic leaf => AtomicD leaf
  |  ...

eliminating the need for the type Gfx. We could also have defined the GCSpec type as

data GCSpec
  =  (ColorGen c, FontGen f) => SoftGC [GCAttributes c f]
  |  HardGC GCtx

allowing you to write for example

SoftGC [GCForeground "red"]

instead of

SoftGC [GCForeground (colorSpec "red")]

40.4 Dependent types

The Fudget library provides two combinators for tagged parallel composition of fudgets: the binary operator >+< and the list combinator listF:

>+< :: F a b -> F c d -> F (Either a c) (Either b d)
listF :: (Eq a) => [(a, F b c)] -> F (a, b) (a, c)

The former allows the composed fudgets to have different types, but composing a large number of fudgets make addressing the individual fudgets clumsy: you use compositions of the constructors Left and Right.

The latter makes it easy to compose many fudgets, but they must all have the same type.

The use of dependent types would allows us to define a combinator that combines the advantages of >+< and listF. In type theory [NPS90], there are two forms of dependent types: dependent products (function types), and dependent sums (pairs). The second form is the one we need here. It allows us to construct pairs, where the type of the second component depends on the value of the first component.

Using a Haskell-like notation, we write

(t::a, b t)

for the pair type where the first component is of type a and the second component is of type b t, where t is the value of the first component. Note that b is a function returning a type.

By viewing t as a tag, we can form lists of tagged values of different type, and define a variant of listF with the following type:

dListF :: Eq a => [(t::a, F (i t) (o t))] -> F (t::a, i t) (t::a, o t)