Type constraints for automatic function constraint deduction in Haskell

Question

For educational purposes I am playing around with trees in Haskell. I have Tree a type defined like this

data Tree a = EmptyTree | Node a (Tree a) (Tree a)

and a lot of functions that share a basic constraint - Ord a - so they have types like

treeInsert :: Ord a => a -> Tree a -> Tree a
treeMake :: Ord a => [a] -> Tree a

and so on. I can also define Tree a like this

data Ord a => Tree a = EmptyTree | Node a (Tree a) (Tree a)

but I can not simplify my functions and omit the extra Ord a to be as the following:

treeInsert :: a -> Tree a -> Tree a
treeMake :: [a] -> Tree a

Why does Haskell (running with -XDatatypeContexts) not automatically deduce this constraint? It seems to to be quite obvious for me that it should. Why am I wrong?

Here is some example source code

data (Eq a, Ord a) => Tree a = EmptyTree | Node a (Tree a) (Tree a)

treeInsert :: a -> Tree a -> Tree a
treeInsert a EmptyTree = Node a EmptyTree EmptyTree
treeInsert a node@(Node v left right)
 | a == v = node
 | a > v = Node v left (treeInsert a right)
 | a < v = Node v (treeInsert a left) right

mkTree :: [a] -> Tree a
mkTree [] = EmptyTree
mkTree (x:xs) = treeInsert x (mkTree xs)

I am getting this

Tree.hs:5:26:
    No instance for (Ord a)
      arising from a use of `Node'
    In the expression: Node a EmptyTree EmptyTree
    In an equation for `treeInsert':
        treeInsert a EmptyTree = Node a EmptyTree EmptyTree
Failed, modules loaded: none.

raymonad's link contains what you're looking for. "GADT-style declarations differ in one important respect: they treat class constraints on the data constructors differently. Specifically, if the constructor is given a type-class context, that context is made available by pattern matching." — phipsgabler
There's no need for both Eq and Ord in a context. Eq is a superclass of Ord, so the latter is enough. — augustss

AndrewC AndrewC · Accepted Answer · 2013-06-04T22:04:50

This is a well-known gotcha about contexts for data declaration. If you define data Ord a => Tree a = ... all it does is force any function that mentions Tree a to have an Ord a context. This doesn't save you any typing, but on the plus side an explicit context is clear about what's needed.

GADTs to the rescue!

The workaround is to use Generalised Abstract Data Types (GADTs).

{-# Language GADTs, GADTSyntax #-}

We can put the context on the constructor directly, by providing an explict type signature:

data Tree a where
   EmptyTree :: (Ord a,Eq a) => Tree a
   Node :: (Ord a,Eq a) => a -> Tree a -> Tree a -> Tree a

and then whenever we pattern match with Node a left right we get an implicit (Ord a,Eq a) context, just like you want, so we can start to define treeInsert like this:

treeInsert :: a -> Tree a -> Tree a
treeInsert a EmptyTree = Node a EmptyTree EmptyTree
treeInsert a (Node top left right) 
          | a < top   = Node top (treeInsert a left) right
          | otherwise = Node top left (treeInsert a right)

Deriving stuff

If you just add deriving Show there, you get an error:

Can't make a derived instance of `Show (Tree a)':
  Constructor `EmptyTree' must have a Haskell-98 type
  Constructor `Node' must have a Haskell-98 type
  Possible fix: use a standalone deriving declaration instead
In the data type declaration for `Tree'

That's a pain, but like it says, if we add the StandaloneDeriving extension ({-# Language GADTs, GADTSyntax, StandaloneDeriving #-}) we can then do stuff like

deriving instance Show a => Show (Tree a)
deriving instance Eq (Tree a) -- wow

and everything works out ok. The wow was because the implicit Eq a context means we don't need an explicit Eq a on the instance.

The context only comes from contstructors

Bear in mind that you only get the implicit context from using one of the constructors. (Remember that's where the context was defined.)

This is actually why we needed the context on the EmptyTree constructor. If we'd just put EmptyTree::Tree a, the line

treeInsert a EmptyTree = Node a EmptyTree EmptyTree

wouldn't have an (Ord a,Eq a) context from the left hand side of the equation, so the instances would be missing from the right hand side, where they're needed for the Node constructor. That would be an error, so it's helpful in this case to keep the contexts consistent.

This also means that you can't have

treeMake :: [a] -> Tree a

treeMake xs = foldr treeInsert EmptyTree xs

you'll get a no instance for (Ord a) error, because there's no constructor on the left hand side to give you the (Ord a,Eq a) context.

That means you still need

treeMake :: Ord a => [a] -> Tree a

There's no way round it this time, sorry, but on the plus side, this may well be the only tree function you'll want to write with no tree argument. Most tree functions will take a tree on the left hand side of the definition and do somthing to it, so you'll have the implicit context most of the time.

Type constraints for automatic function constraint deduction in Haskell

3 Answers

GADTs to the rescue!

Deriving stuff

The context only comes from contstructors