[Haskellcafe] A Foldable binary search tree
Simon PeytonJones
simonpj at microsoft.com
Mon Dec 24 04:44:57 EST 2007
 > 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. Haskell98 contexts on datatype declarations are a misfeature 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 (existentiallike) 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 patternmatch 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 Haskell98 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
More information about the HaskellCafe
mailing list