Filter
Top Products
3.4. TYPE DEFINITIONS 25
Rather than using the rec keyword every time we declare a recursive function,
eccentrics might prefer to define a recursion operator Rec, and thereafter use that,
e.g.
#let rec Rec f = f(fun x -> Rec f x);;
Rec : ((’a -> ’b) -> ’a -> ’b) -> ’a -> ’b = <fun>
#let fact = Rec (fun f n -> if n = 0 then 1 else n * f(n - 1));;
fact : int -> int = <fun>
#fact 3;;
it : int = 6
Note, however, that the function abstraction ‘fun x -> ...’ in the definition
was essential, otherwise the expression Rec f goes into an infinite recursion when
evaluated, before it is even applied to its argument:
#let rec Rec f = f(Rec f);;
Rec : (’a -> ’a) -> ’a = <fun>
#let fact = Rec (fun f n -> if n = 0 then 1 else n * f(n - 1));;
Uncaught exception: Out_of_memory
3.4 Type definitions
CAML has facilities for declaring new type constructors, so that composite types can
be built up out of existing ones. In fact, CAML goes further and allows a composite
type to be built up not only out of preexisting types but also from the composite
type itself. Such types, naturally enough, are said to be recursive, even if they don’t
avail themselves of the chance to use the type being defined in the definition. They
are declared using the type keyword followed by an equation indicating how the
new type is built up from existing ones and itself. We will illustrate this by a few
examples. The first one is the definition of a sum type, intended to correspond to
the disjoint union of two existing types.
#type (’a,’b)sum = inl of ’a | inr of ’b;;
Type sum defined.
Roughly, an object of type (’a,’b)sum is either something of type ’a or some-
thing of type ’b. More formally, however, all these things have different types.
The type declaration also declares the so-called constructors inl and inr. These
are functions that take objects of the component types and inject them into the
new type. Indeed, we can see their types in the CAML system and apply them to
objects:
#inl;;
it : ’a -> (’a, ’b) sum = <fun>
#inr;;
it : ’a -> (’b, ’a) sum = <fun>
#inl 5;;
it : (int, ’a) sum = inl 5
#inr false;;
it : (’a, bool) sum = inr false
We can visualize the situation via the following diagram. Given two existing
types α and β, the type (α, β)sum is composed precisely of separate copies of α
and β, and the two constructors map onto the respective copies: