Re: recursive datatypes

[Michel Quercia <quercia@cal.enst.fr>]

Simon Helsen wrote:

> Why does Caml type-check the following program? It wouldn't in Standard ML
> and I don't see the use for it, as it may lead to infinite programs...
>
> (I don't have a french keyboard)
>
> Pourquoi est le programme ci-desous bon type ? C'est ne pas le
> cas en Standard ML et je ne comprend pas l'usage pour ca parce que le
> programme peut eventuellement cours a l'infini...
>
> type 'a tree = Tree of 'a
>
> let f x = Tree (f x)
>

Hi,

Your code does'nt typecheck with both camllight  0.73 and ocaml 1.05.

With ocaml1.05, the following code does typecheck :

----------------------------------------
        Objective Caml version 1.05

# type 'a tree = Tree of 'a;;
type 'a tree = | Tree of 'a
# let f x = Tree (f x);;
Unbound value f
# let rec f x = Tree (f x);;
val f : 'a -> ('b tree as 'b) = <fun>
# f(3);;
Out of memory during evaluation
#
---------------------------------------

I can't explain the "('b tree as 'b)", but why your post is entitled
"recursive datatypes" ?
Did you mean :

type 'a tree = Tree of 'a tree ?

This type declaration is accepted and it is possible to build 'a tree objects
:


--------------------------------------

# type 'a tree = Tree of 'a tree;;
type 'a tree = | Tree of 'a tree
# #print_depth 5;;
# let rec x = Tree(y) and y = Tree(x);;
val x : 'a tree = Tree (Tree (Tree (Tree (Tree (Tree ...)))))
val y : 'a tree = Tree (Tree (Tree (Tree (Tree (Tree ...)))))
-------------------------------------

--
Michel Quercia
Lycee Carnot  16 bd Thiers  21000 Dijon
mailto:quercia@cal.enst.fr