[Haskell-cafe] A Foldable binary search tree

[Simon Peyton-Jones]

| > data (Ord a) => BST a = Empty | BST (BST a) a (BST a)
|
| Experience has taught me to _never_ put class contexts on data
| definitions.

Correct.  Haskell-98 contexts on data-type declarations are a mis-feature of Haskell, which I resisted at the time but failed to eliminate.

As others have pointed out, GHC allows you to put a context on any data constructor.  I prefer this "where" syntax:

data BST a where
  Empty :: BST a
  BST :: Ord a => BST a -> a -> BST a -> BST a

but the other (existential-like) syntax also works:

data BST a = Empty | Ord a => BST (BST a) a (BST a)

The constructors have the signature they advertise.  When you use BST as a constructor, you must supply an Ord context.  But when you pattern-match on it, you *get* an Ord context.  For example

f :: a -> BST a -> Bool
f x Empty = False
f x (BST t1 y t2) = x>y

Note the absence of an Ord context on f.

This works properly when combined with GADTs.  The uniform rule is: you must supply the context when you use the constructor as a function, and you bring the context into scope when you pattern match on the constructor.

Having this "context on data constructors" work right all the time is relatively new.  Previously it really only worked for existentials; but now there are no restrictions on the contexts you write on data constructors.

The Haskell 98 behaviour remains when you use the Haskell-98 syntax.

| I would accept this pain if it meant I could write:
|
| insert :: a -> BST a -> BST a

And so you can!  But to get this, you'll have to write an Ord context on the Empty constructor too.

Simon