Filter
Top Products
3.4. TYPE DEFINITIONS 31
#let rec append l1 l2 =
match l1 with
[] -> l2
| (h::t) -> h::(append t l2);;
append : ’a list -> ’a list -> ’a list = <fun>
#append [1;2;3] [4;5];;
it : int list = [1; 2; 3; 4; 5]
#let rec map f =
fun [] -> []
| (h::t) -> (f h)::(map f t);;
map : (’a -> ’b) -> ’a list -> ’b list = <fun>
#map (fun x -> 2 * x) [1;2;3];;
it : int list = [2; 4; 6]
#let rec rev =
fun [] -> []
| (h::t) -> append (rev t) [h];;
#rev [1;2;3;4];;
it : int list = [4; 3; 2; 1]
3.4.3 Tree structures
It is often helpful to visualize the elements of recursive types as tree structures,
with the recursive constructors at the branch nodes and the other datatypes at the
leaves. The recursiveness merely says that plugging subtrees together gives another
tree. In the case of lists the ‘trees’ are all rather spindly and one-sided, with the
list [1;2;3;4] being represented as:
❅
❅
❅
❅
❅
❅
❅
❅
❅
❅
❅
❅
1
2
3
4 []
It is not difficult to define recursive types which allow more balanced trees, e.g.
#type (’a)btree = Leaf of ’a
| Branch of (’a)btree * (’a)btree;;
In general, there can be several different recursive constructors, each with a
different number of descendants. This gives a very natural way of representing the
syntax trees of programming (and other formal) languages. For example, here is a
type to represent arithmetical expressions built up from integers by addition and
multiplication:
#type expression = Integer of int
| Sum of expression * expression
| Product of expression * expression;;