If memory serves, ML datatypes elegantly overload about three distrinct
type-theoretic constructs.  In particular, the variant tags in the data
type definition double as the "witnesses" to coercions between an
iso-recursive type and its "unrolling" of one level.  Without going into
detail, this is why you can define something like

type foo = Rec of foo;;

but you can't define

type foo = foo;;

The latter definition is in the style of "equi-recursive" types, in
which a recursive type is equivalent any number of its unrollings.  This
formulation is harder to typecheck, as I recall.  There is a similar
analogy between the two definitions of bin_tree that you present.

Mike

-----Original Message-----
From: owner-caml-list@pauillac.inria.fr
[mailto:owner-caml-list@pauillac.inria.fr] On Behalf Of Oleg
Sent: Wednesday, August 14, 2002 10:20 PM
To: caml-list@inria.fr
Subject: [Caml-list] Cyclic ?!

Hi

I'm puzzled by the following compiler behavior:

If I define bin_tree as

type 'a bin_tree = 
           Empty
         | Node of 'a bin_tree * 'a * 'a bin_tree

the compiler accepts it. OTOH if I define it as

type 'a bin_tree = ('a bin_tree * 'a * 'a bin_tree) option

It gives an error: "The type abbreviation bin_tree is cyclic".
Why??? And what's the difference between the two, really?

Thanks
Oleg
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives:
http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ:
http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners