« Moth | Main | Stitchwort »

Constraints on Haskell Type Definitions

In chapter 10 of Real World Haskell (O'Sullivan, Goerzen and Stewart, 2009, page 247) we read:

Adding a constraint to a type definition is essentially never a good idea.  It has the effect of forcing you to add type constraints to every function that will operate on values of that type.

This is then illustrated with the following data type and functions:

  data (Ord a) => OrdStack a = Bottom
| Item a (Ordstack a)
deriving (show)

isIncreasing :: (Ord a) => OrdStack a -> Bool
isIncreasing (Item a rest@(Item b _))
| a < b = isIncreasing rest
| otherwise = False

push :: (Ord a) => a -> OrdStack a -> OrdStack a
push a s = Item a s

Here the constraint (Ord a) => in the first line means that OrdStack a is only defined when Ord a holds.  This means that when OrdStack a appears in the type declarations of isIncreasing and push, these declarations also have to be constrained with (Ord a) =>.  

For isIncreasing the constraint is acceptable because isIncreasing actually uses the < operator (which is only defined for elements of Ord a). 

For push the constraint appears to be unacceptable because < does not appear in its definition.  However, this example is a bad one because a proper implementation of push would ensure that the OrdStack invariant (that the elements are ordered) was not broken, and this would require the use of the < operator:

  push :: (Ord a) => a -> OrdStack a -> OrdStack a
push a rest@(Item b _) | a < b = Item a rest
| otherwise = error "unordered stack"
push a rest@Bottom = Item a rest

A much better example of the authors point would be a pop function:

  pop :: (OrdStack a) -> (a, OrdStack a)
pop (Item a s) = (a, s)

Now this has no need at all for the < operator and it really would be unacceptable for the OrdStack data type definition to force you to include the (Ord a)=> constraint.

Reader Comments

There are no comments for this journal entry. To create a new comment, use the form below.

PostPost a New Comment

Enter your information below to add a new comment.
Author Email (optional):
Author URL (optional):
All HTML will be escaped. Hyperlinks will be created for URLs automatically.