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

Tree is a type constructor, taking the element type parameter a to the algebraic data type Tree a. It is not a value and has no ordinary value-level function type; its kind of a type is * -> *. The other names are data constructors with polymorphic type signatures:

One :: a -> Tree a
Two :: Tree a -> Tree a -> Tree a

One constructs a leaf-labelled binary tree with one leaf; Two joins two such trees under a new internal node. Unlike a general binary tree representation with empty child slots, this representation has no empty tree.^[ref]