Create a script that looks like this:

#!/usr/bin/env bash

GREEN=`echo -e '\033[92m'`
RED=`echo -e '\033[91m'`
RESET=`echo -e '\033[0m'`

/usr/bin/ghci "${@}" |\
  sed "s/^Failed, modules loaded:/${RED}&${RESET}/g;s/^Ok, modules loaded:/${GREEN}&${RESET}/g"

If your ghci is not located in /usr/bin, change the path in the script accordingly. If you want, you can name your script ghci so that it takes over the original one. Just make sure its location appears in your PATH variable before the location of the true ghci.

If all goes well, you should now see colors whenever you load your modules:

% ghci Sirenial.Merge
...
Failed, modules loaded: Sirenial.Query.

And then when the bug has been fixed:

% ghci Sirenial.Merge
...
Ok, modules loaded: Sirenial.Merge, Sirenial.Query.

This has only been tested on Terminal.app in Snow Leopard. If it doesn’t work for your system, please leave a comment, with—if possible—a fix.

There is a small issue: sometimes sed delays the colored parts a bit, causing your prompt to be printed before the success or error message. Again, if you know a fix, please comment.

With the whole of the Netherlands covered in snow, the traffic is completely jammed. But that didn’t bother my flatmates and me, because we stayed home all day. In the afternoon we rolled the biggest snowball in the street; at the end it reached a meter in diameter and it took three of us to push it around. We guessed it weighed approximately 250 kg at that point.

While dinner was cooking I went outside again to take some pictures.

Our giant snowball. At the end it took 3 people to push it around.
In the background is the orange-lit road.		Looking up at the snowy foliage. Some stars are visible in the sky.

The dual to this story holds as well: many (if not all) GADTs can be represented as type classes. To see how, take a look at the standard GADT example:

data Term :: * -> * where
  Lit  :: Int        -> Term Int
  Inc  :: Term Int   -> Term Int
  IsZ  :: Term Int   -> Term Bool
  If   :: Term Bool  -> Term a    -> Term a     -> Term a
  Pair :: Term a     -> Term b    -> Term (a,b)
  Fst  :: Term (a,b) -> Term a
  Snd  :: Term (a,b) -> Term b

Each constructor result type is indexed by the type of the construct it represents. This example is explained in detail in Simple Unification-based Type Inference for GADTs by Simon Peyton Jones et al.

Writing Term like this allows the following well-typed evaluation function:

eval :: Term a -> a
eval term = case term of
  Lit n    -> n
  Inc t    -> eval t + 1
  IsZ t    -> eval t == 0
  If c x y -> if eval c then eval x else eval y
  Pair x y -> (eval x, eval y)
  Fst t    -> fst (eval t)
  Snd t    -> snd (eval t)

To convert a GADT G to a type class, create a new type class GC with one type parameter g. This type parameter g will have the same kind as G, and its arguments will have the same semantics as those of the G. Then for each constructor create one function in the type class with the exact same type, replacing every occurrence of G by g.

If we follow this recipe for Term we get:

class TermC term where
  lit  :: Int         -> term Int
  inc  :: term Int    -> term Int
  isZ  :: term Int    -> term Bool
  if_  :: term Bool   -> term a    -> term a      -> term a
  pair :: term a      -> term b    -> term (a, b)
  fst_ :: term (a, b) -> term a
  snd_ :: term (a, b) -> term b

I’ve used the same names as the constructors except I made them lowercase. I appended _ to some to avoid name clashes (fst, snd) or lexical errors (if).

Of course, the free instance of TermC is Term.

Now the recipe doesn’t make any assumptions about the GADT in question, but I don’t know if this is right, because you can do some powerful things with GADTs. The two special things in datatypes I can think of—class constraints and existentially quantified variables—are no problem in type classes. Also the thing that makes GADTs truly special—custom type indices in constructor result types—have always been allowed in type classes. If I have overlooked something, please let me know and leave a comment.

However, perhaps the more important question is: can we do everything with TermC that we could do with Term? Well, we can certainly implement eval: this becomes a newtype with a corresponding instance TermC:

newtype Eval a = Eval { evalC :: a }

instance TermC Eval where
  lit       = Eval
  inc t     = Eval $ evalC t + 1
  isZ t     = Eval $ evalC t == 0
  if_ c x y = Eval $ if evalC c then evalC x else evalC y
  pair x y  = Eval $ (evalC x, evalC y)
  fst_ t    = Eval $ fst (evalC t)
  snd_ t    = Eval $ snd (evalC t)

The instance is very, very similar to the original evaluation function. Only instead of recursively calling eval, we call evalC and wrap the result in an Eval constructor. The type of evalC :: Eval a -> a is also similar to eval :: Term a -> a.

What I like most about encoding terms and their evaluation this way is that all the code is Haskell 98!

But not everything is this easy. The step evaluator on the Haskell wiki page on GADTs, for example, uses deep pattern matching and as we saw last time this is a lot easier to do on datatypes than in class instances. In fact, I don’t know if this particular example is possible to translate at all, and if it is, it’s certainly not going to be Haskell 98.

Another thing GADTs are useful for is witnesses in families of types. Again, I don’t know if it is possible to translate this use case to class instances.

Summing up, any GADT can be translated to a type class, but not all uses of GADTs have obvious translations. The standard GADT example, however, is trivial to translate. For that reason, it is probably not the most interesting choice as standard example of GADTs.

Recently there’s been a bit of talk in the Haskell café about what a DSL is. Robert Atkey gave the nice answer that you can often capture a DSL in one or more type classes, and implementations of this DSL then correspond to instances of these type classes.

Arithmetic expressions with variables, for example, can be captured by this type:

type Arith = forall a. (Num a, Var a) => a

The Num constraint allows the use of integers and the basic operators, while Var allows the use of variables:

class Var a where
  var :: String -> a

I would like to show you the various things you can do with a value of type Arith.

Example Arith values

Before we do that, however, let’s think about what this definition of Arith really means. It’s not any specific type yet, such as Int or Float. Rather, it’s an expression composed entirely of functions from the Num and Var type classes. Since fromInteger and var are the only functions from those classes that don’t take recursive values as arguments, calls to those two functions will necessarily make up the leaves of any Arith tree—provided it is finite. Here are some example values:

example1 :: Arith
example1 = 1 + 2 * 3

example2 :: Arith
example2 = 2 * var "x" + 0 * var "y"

Note that the integer literals in these examples are automatically expanded to calls to fromInteger. To keep the examples somewhat smaller, we will ignore the negate, abs and signum functions from the Num type class. We will also ignore Num’s superclasses Eq and Show, providing empty instances where necessary; they mess up some of our examples.

Evaluation as instance

Now, given values of type Arith, what can we do with them? One thing we can think of is to combine them into a bigger expression:

example3 :: Arith
example3 = 6 + example1 - 3 * example2

Can we inspect them, or make them smaller? Well, the type is polymorphic, so we can narrow it to a concrete type. We don’t know any types yet that are instances of both Num and Var, however, so let’s make one! We’ll go for one that evaluates the expression, yielding an integer given an environment:

newtype Eval = Eval { runEval :: Env -> Integer }
type    Env  = [(String, Integer)]

instance Show Eval
instance Eq Eval

instance Num Eval where
  Eval f + Eval g = Eval (liftA2 (+) f g)
  Eval f * Eval g = Eval (liftA2 (*) f g)
  Eval f - Eval g = Eval (liftA2 (-) f g)
  fromInteger n   = Eval (const n)

instance Var Eval where
  var name = Eval $ \e -> case lookup name e of
    Nothing -> error ("unbound variable: " ++ name)
    Just x -> x

Now we can evaluate Ariths simply by calling runExpr on them:

*Arith> runEval example1 []
7
*Arith> runEval example2 [("x", 6), ("y", 7)]
12

This method of writing functions on Ariths is very much like writing catamorphisms: the tree is reduced to a value, and operands have already had the catamorphisms applied to them recursively, so any computation you want to run on the tree in this way has to be compositional.

The free instance

Let’s do something slightly more complicated: constant folding. The idea of constant folding is to eliminate trivial uses of the operators. x * 0, for example, can be reduced to 0, regardless of x’s value. Other examples are multiplication by 1 and subtraction of 0. Also, if an expression doesn’t use any variables, we can evaluate it right away.

What type should our constant folding function have? We would expect something like this:

foldConstants :: Arith -> Arith

Can we write this function as a newtype with instances, too? This turns out to be a lot more difficult. For example, in the case of + we want to inspect the left-hand and right-hand sides to check whether they are zero. But the operands are of type Arith, so we would have to write helper functions such as isZero :: Arith -> Bool which in turn have to be written with new newtypes and instances. This quickly gets out hand. We are running into problems because our catamorphism isn’t regular anymore.

It would be nice if we could do a ‘deep’ inspection of the operands, like we can do when writing functions on normal datatypes. So let’s do that: make a normal datatype and write our foldConstants on that type.

data ReifyArith
  = Add ReifyArith ReifyArith
  | Mul ReifyArith ReifyArith
  | Sub ReifyArith ReifyArith
  | Int Integer
  | Var String
  deriving (Eq, Show, Data, Typeable)

instance Num ReifyArith where
  (+) = Add
  (*) = Mul
  (-) = Sub
  fromInteger = Int

instance Var ReifyArith where
  var = Var

I’ve called this datatype ReifyArith because it reifies an Arith value, turning it into something concrete and tangible. I like to call ReifyArith the free instance, because you can write such a datatype for any combination of classes that adhere to the requirements Robert Atkey mentioned in his email, either as an ADT or a GADT.

From ReifyArith back to Arith

The nice thing about the free instance is that we do not lose any information: we can easily go back to the polymorphic version of our expressions, like so:

generify :: ReifyArith -> Arith
generify expr = case expr of
  Add x y      -> generify x + generify y
  Mul x y      -> generify x * generify y
  Sub x y      -> generify x - generify y
  Int n        -> fromInteger n
  Var name     -> var name

Using this technique, we can manipulate Arith values in arbitrary ways. One thing I particularly like is that the ReifyArith is entirely internal to our module and doesn’t need to be exposed to the outside world.

Constant folding

Now that we have a normal datatype, we can write our constant folding transformation. We implement it as a function that does only one step of the rewriting and then use generic programming (Scrap Your Boilerplate in this case) to apply it recursively to our tree. This is why we also derived Data and Typeable for ReifyArith.

step :: ReifyArith -> ReifyArith
step expr = case expr of
  -- Reduce computations on integer literals
  Add (Int x) (Int y) -> Int (x + y)
  Mul (Int x) (Int y) -> Int (x * y)
  Sub (Int x) (Int y) -> Int (x - y)

  -- Rewrite rules based on 0 and 1
  Add (Int 0) y -> y
  Add x (Int 0) -> x
  Mul (Int 0) _ -> 0
  Mul _ (Int 0) -> 0
  Mul (Int 1) y -> y
  Mul x (Int 1) -> x
  Sub x (Int 0) -> x

  -- Catch all other cases
  _ -> expr

foldConstants :: Arith -> Arith
foldConstants expr = generify (everywhere (mkT step) expr)

Let’s see if it works:

*Arith> foldConstants example1 :: ReifyArith
Int 7
*Arith> foldConstants example2 :: ReifyArith
Mul (Int 2) (Var "x")

Indeed, in the first case the transformation is able to fold the entire expression to a single integer literal, and in the second case it has completely eliminated the second term.

Conclusion

We have seen that although polymorphic values look abstract and intangible, they are in fact easily manipulated. If a regular, compositional catamorphism is required, the function can be written as instances of the relevant datatypes. If a more complicated, non-regular scheme is required, we can reify the value as a concrete datatype and define the function on that.

Many thanks to Sjoerd Visscher for valuable feedback!

fold :: (Fam phi, HFunctor phi (PF phi), Fold (PF phi)) =>
  Algebra phi r -> phi ix -> ix -> r

Context synonyms aim to make it possible to give long contexts a name and reuse it throughout modules. Using a context synonym, the example above can be rewritten to:

context FoldFam phi = (Fam phi, HFunctor phi (PF phi), Fold (PF phi))
fold :: FoldFam phi => Algebra phi r -> phi ix -> ix -> r

Note that context synonyms are reminiscent of class aliases, but that proposal is a lot more involved than this one. Here we are only aiming to give long contexts a convenient short name.

During the fifth Haskell Hackathon, a team of programmers (including myself) set out to implement an extension to GHC to make exactly this possible. We were aware of a trick that makes context synonyms already somewhat possible: create a new class and make the right-hand side of the context synonym the superclass constraints of the new type class:

class    (Fam phi, HFunctor phi (PF phi), Fold (PF phi)) => FoldFam phi

The problem with this approach, however, is that types for which you would like to use the FoldFam constraint are not automatically instances of this new class. Only last week it dawned on me that you can remedy this by supplying one big general instance that makes every type an instance:

instance (Fam phi, HFunctor phi (PF phi), Fold (PF phi)) => FoldFam phi

Such an instance is sometimes used as in instance Monad f => Applicative f where ..., but this doesn’t have the desired effect in Haskell. Our FoldFam instance, however, is exactly what we want: match any type with that instance, then check the constraints. This also means we cannot add any more specific instances, which is also what we want.

So it seems we were trying to implement a feature that already sort of exists. To make things worse, Erik pointed out that this use of type classes and instances is documented literally in the GHC docs as old as version 6.0! If only we had known during the Hackathon.

There’s a very pretty piece of forest in Driebergen called the Heidetuin (heath garden). Whenever I’m in the neighbourhood I pass through it because it’s so pretty, especially when the sun is out.

Prelude> let 3 - 4 = 5
Prelude> 3 - 4
5
Prelude>

Wait, what? Oh, right, I guess this isn’t very special: we’re just redefining the minus operator, and for some very specific input at that.

Prelude> 1 - 2
*** Exception: : Non-exhaustive patterns in function -
Prelude>

Yes, that’s what we were expecting. How about the following?

Prelude> let 5 = 6
Prelude>

Wait, what? GHC seems to accept our definition of 5. Have we really redefined 5?

Prelude> 5
5
Prelude>

No, it seems it’s just ignored it. What does let 5 = 6 mean, then?

To find out, remember that anywhere you define values using =, you may write patterns on the left-hand side, unwrapping constructors and directly naming fields inside. Here’s an example:

Prelude Data.List> let Just ix = elemIndex 'j' ['a'..'z']
Prelude Data.List> ix
9
Prelude Data.List>

This works even in a top-level declaration in your module! There’s no limit to the number of values you may introduce:

Prelude> let one : two : three : _ = [1..]
Prelude> (two, three)
(2,3)
Prelude>

So if we can introduce any number of values, can we also introduce zero new names?

Prelude> let Just True = Nothing
Prelude> let _ = "meep"
Prelude>

Yup, those lets are accepted. They just don’t do anything useful.

Now we can figure out what let 5 = 6 means: the pattern on the left-hand side of = contains no new names and so no new names are bound, just like in the example above. This opposed to our very first example, where there is a new name on the left-hand side, namely -.

On a final note, here is what happens when the patterns don’t match the values on the right-hand side:

Prelude> let ('a', b) = ('b', 'c')
Prelude> b
*** Exception: : Irrefutable pattern failed for pattern ('a', b)

On the way from home to university are several farmers that sell part of their produce to people passing by. One of them sells stoofperen (cooking pears) and I couldn’t resist picking up a bag since I’d never prepared them before. The toughest part was peeling them—I spent over an hour and a half. But! The result is well worth it. Three hours of simmering in water and some sugar yielded this beautiful bowl of sweet yummy reddish pears.

Things to remember the next time: 1) use a sharper knife, 2) add a bit less sugar and 3) stir less (or not at all) so that they stay in bigger pieces.