Filter
Top Products
3.4. TYPE DEFINITIONS 29
#Nil;;
it : ’a list = Nil
#Cons(1,Nil);;
it : int list = Cons (1, Nil)
#Cons(1,Cons(2,Nil));;
it : int list = Cons (1, Cons (2, Nil))
#Cons(1,Cons(2,Cons(3,Nil)));;
it : int list = Cons (1, Cons (2, Cons (3, Nil)))
Because the constructors are distinct and injective, it is easy to see that all
these values, which we think of as lists [], [1], [1; 2] and [1; 2;3], are distinct. Indeed,
purely from these properties of the constructors, it follows that arbitrarily long lists
of elements may be encoded in the new type. Actually, CAML already has a type
list just like this one defined. The only difference is syntactic: the empty list is
written [] and the recursive constructor ::, has infix status. Thus, the above lists
are actually written:
#[];;
it : ’a list = []
#1::[];;
it : int list = [1]
#1::2::[];;
it : int list = [1; 2]
#1::2::3::[];;
it : int list = [1; 2; 3]
The lists are printed in an even more natural notation, and this is also allowed for
input. Nevertheless, when the exact expression in terms of constructors is needed,
it must be remembered that this is only a surface syntax. For example, we can
define functions to take the head and tail of a list, using pattern matching.
#let hd (h::t) = h;;
Toplevel input:
>let hd (h::t) = h;;
> ^^^^^^^^^^^^^
Warning: this matching is not exhaustive.
hd : ’a list -> ’a = <fun>
#let tl (h::t) = t;;
Toplevel input:
>let tl (h::t) = t;;
> ^^^^^^^^^^^^^
Warning: this matching is not exhaustive.
tl : ’a list -> ’a list = <fun>
The compiler warns us that these both fail when applied to the empty list, since
there is no pattern to cover it (remember that the constructors are distinct). Let
us see them in action:
#hd [1;2;3];;
it : int = 1
#tl [1;2;3];;
it : int list = [2; 3]
#hd [];;
Uncaught exception: Match_failure