Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / a / Solution

An empty constructor and a constructor containing a label and two subtrees give a polymorphic algebraic data type:

data STree a = Empty | Node (STree a) a (STree a)
  deriving (Eq, Show)

The binary search tree invariant is $\boxed{\text{every left label}<x<\text{every right label}}$ at each Node left x right, together with the same invariant recursively in both subtrees. Labels are distinct because the representation is of a set. The declaration itself needs no ordering constraint; operations that compare labels require Ord a in their type signatures.