Re: recursive datatypes

From: Michel Quercia (quercia@cal.enst.fr)
Date: Wed Nov 12 1997 - 17:16:36 MET


Date: Wed, 12 Nov 1997 17:16:36 +0100
From: Michel Quercia <quercia@cal.enst.fr>
To: Simon Helsen <helsen@informatik.uni-tuebing.de>,
Subject: Re: recursive datatypes

--------------CF4D7515F765174144DB0F3A
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

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



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:12 MET