Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Cyclic ?!
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2002-08-17 (10:59)
From: Michael Hicks <mwh@c...>
Subject: RE: [Caml-list] Cyclic ?!
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.


-----Original Message-----
[] On Behalf Of Oleg
Sent: Wednesday, August 14, 2002 10:20 PM
Subject: [Caml-list] Cyclic ?!


I'm puzzled by the following compiler behavior:

If I define bin_tree as

type 'a bin_tree = 
         | 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?

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list:
To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: