#type`sum_ex1`

`=`

`Ctor`

of`sum_ex1`

`;;`

`type sum_ex1 = | Ctor of sum_ex1`

#type`record_ex1`

`=`

`{`

`field`

`:`

`record_ex1`

`}`

`;;`

`type record_ex1 = { field: record_ex1 }`

How to build values with such types is not obvious, since we need a value before building one! The recursive declaration of values allows to get out of this vicious circle.

#let

rec`sum_val`

`=`

`Ctor`

`sum_val`

`;;`

`val sum_val : sum_ex1 = Ctor (Ctor (Ctor (Ctor (Ctor ...))))`

#let

rec`val_record_1`

`=`

`{`

`field`

`=`

`val_record_2`

`}`

and

`val_record_2`

`=`

`{`

`field`

`=`

`val_record_1`

`}`

`;;`

`val val_record_1 : record_ex1 = {field={field={field={field={field=...}}}}}`

`val val_record_2 : record_ex1 = {field={field={field={field={field=...}}}}}`

Arbitrary planar trees can be represented by such a data structure.

#type

'a`tree`

`=`

`Vertex`

of

'a

`*`

'a`tree`

`list`

`;;`

`type 'a tree = | Vertex of 'a * 'a tree list`

#let`height_1`

`=`

`Vertex`

(`0`

`,[]`

)`;;`

`val height_1 : int tree = Vertex (0, [])`

#let`height_2`

`=`

`Vertex`

(`0`

`,[`

`Vertex`

(`1`

`,[]`

);`Vertex`

(`2`

`,[]`

);`Vertex`

(`3`

`,[]`

)

`]`

)`;;`

`val height_2 : int tree =`

`Vertex (0, [Vertex (1, []); Vertex (2, []); Vertex (3, [])])`

#let`height_3`

`=`

`Vertex`

(`0`

`,[`

`height_2;`

`height_1`

`]`

)`;;`

`val height_3 : int tree =`

`Vertex`

`(0,`

`[Vertex (0, [Vertex (...); Vertex (...); Vertex (...)]); Vertex (0, [])])`

`(* same with a record *)`

#type

'a`tree_rec`

`=`

`{`

`label`

`:`

'a`;`

`sons`

`:`

'a`tree_rec`

`list`

`}`

`;;`

`type 'a tree_rec = { label: 'a; sons: 'a tree_rec list }`

#let`hgt_rec_1`

`=`

`{`

`label`

`=`

`0`

;`sons`

`=[]`

`}`

`;;`

`val hgt_rec_1 : int tree_rec = {label=0; sons=[]}`

#let`hgt_rec_2`

`=`

`{`

`label`

`=`

`0`

;`sons`

`=[`

hgt_rec_1`]`

`}`

`;;`

`val hgt_rec_2 : int tree_rec = {label=0; sons=[{label=0; sons=[]}]}`

We might think that an enumerated type with only one constructor is not useful, but by default, Objective CAML does not accept recursive type abbreviations.

#type

'a`tree`

`=`

'a

`*`

'a`tree`

`list`

`;;`

`Characters 7-34:`

`The type abbreviation tree is cyclic`

We can define values with such a structure, but they do not have the same type.

#let`tree_1`

`=`

(`0`

`,[]`

)`;;`

`val tree_1 : int * 'a list = 0, []`

#let`tree_2`

`=`

(`0`

`,[`

(`1`

`,[]`

);

(`2`

`,[]`

);

(`3`

`,[]`

)

`]`

)`;;`

`val tree_2 : int * (int * 'a list) list = 0, [1, []; 2, []; 3, []]`

#let`tree_3`

`=`

(`0`

`,[`

`tree_2;`

`tree_1`

`]`

)`;;`

`val tree_3 : int * (int * (int * 'a list) list) list =`

`0, [0, [...; ...; ...]; 0, []]`

In the same way, Objective CAML is not able to infer a type for a function whose argument is a value of this form.

#let`max_list`

`=`

`List.fold_left`

`max`

`0`

`;;`

`val max_list : int list -> int = <fun>`

#let

rec`height`

`=`

function

`Vertex`

(`_,[]`

)`->`

`1`

`|`

`Vertex`

(`_,`

sons)`->`

`1`

`+`

(max_list

(List.map`height`

`sons`

))`;;`

`val height : 'a tree -> int = <fun>`

#let

rec`height2`

`=`

function

(`_,[]`

)`->`

`1`

`|`

(`_,`

sons)`->`

`1`

`+`

(max_list

(List.map`height2`

`sons`

))`;;`

`Characters 95-99:`

`This expression has type 'a list but is here used with type`

`('b * 'a list) list`

The error message tells us that the function

However, object typing allows to build values, whose type is cyclic. Let us consider the following function, and try to guess its type.

The type of

#let`f`

`x`

`=`

`x#copy`

`=`

`x`

`;;`

Objective CAML does accept this function, and notes the type cyclicity using

#let`f`

`x`

`=`

`x#copy`

`=`

`x`

`;;`

`val f : (< copy : 'a; .. > as 'a) -> bool = <fun>`

In fact, the problems are the same, but by default, Objective CAML will not accept such types unless objects are concerned. The function

#let

rec`height`

`a`

`=`

match`a#sons`

with

`[]`

`->`

`1`

`|`

`l`

`->`

`1`

`+`

(max_list

(List.map`height`

`l`

))`;;`

`val height : (< sons : 'a list; .. > as 'a) -> int = <fun>`