How important are circular lists/recursive objects?

How important are circular lists/recursive objects?

[Brian Hurt]

In Ocaml you have some ability to define recursive data structures.  The 
classic example of this is the circular list:

let rec example = 1 :: 2 :: example;;

There are obvious limitations to this sort of trick:

# let rec example = List.map (fun x -> x + 1) (1 :: 2 :: example);;
This kind of expression is not allowed as right-hand side of `let rec'
#

The question is: if this behavior was completely outlawed, and either you 
couldn't build up circular lists/recursive data structures of this type at 
all, or had to call special functions (List.circularize, say), to create 
them, would this be a signifigant problem?  Does anyone actually use this 
construct, and if so, for what?

Brian

Re: How important are circular lists/recursive objects?

[Gleb Alexeyev]

Brian Hurt wrote:
> 
> The question is: if this behavior was completely outlawed, and either 
> you couldn't build up circular lists/recursive data structures of this 
> type at all, or had to call special functions (List.circularize, say), 
> to create them, would this be a signifigant problem?  Does anyone 
> actually use this construct, and if so, for what?
> 
I do not use Ocaml for anything "real", but I think cyclic 
data-structures are occasionally useful. The first example that springs 
to mind: to implement "let rec" construct in interpreter one would need 
cyclic environment.

Re: [Caml-list] How important are circular lists/recursive objects?

[Ville-Pertti Keinonen]

On Apr 3, 2007, at 2:55 AM, Brian Hurt wrote:

> The question is: if this behavior was completely outlawed, and  
> either you couldn't build up circular lists/recursive data  
> structures of this type at all, or had to call special functions  
> (List.circularize, say), to create them, would this be a  
> signifigant problem?  Does anyone actually use this construct, and  
> if so, for what?

Are you referring to all cases of let rec for non-functions, or just  
those that include "bare" self-references?  Most of the cases I can  
think of involve closures (so they're not necessarily cyclic, merely  
self-referential), e.g. useful lazy lists can often be constructed  
with something like:

let rec l = LazyList (1, lazy (do_something l))

Re: [Caml-list] How important are circular lists/recursive objects?

[Andrej Bauer]

Brian Hurt wrote:
> Does anyone  actually use this construct, and if so, for what?

When I teach my students "theory" of programming languages, we write 
interpreters for mini languages. The recursive data structures are used 
to create closures of recursive functions, environments that contain 
mutually recursive values, closures of objects, etc. Life would be very 
hard without this feature.

Andrej

Re: [Caml-list] How important are circular lists/recursive objects?

[Jon Harrop]

On Tuesday 03 April 2007 08:00, Andrej Bauer wrote:
> Brian Hurt wrote:
> > Does anyone  actually use this construct, and if so, for what?
>
> When I teach my students "theory" of programming languages, we write
> interpreters for mini languages. The recursive data structures are used
> to create closures of recursive functions, environments that contain
> mutually recursive values, closures of objects, etc. Life would be very
> hard without this feature.

There is a nice example here:

  http://www.ffconsultancy.com/ocaml/benefits/interpreter.html

Specifically, in the "eval" function:

    | ELetRec(var, arg, body, rest) ->
        let rec vars = (var, VClosure(arg, vars, body)) :: vars in
        eval vars rest

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] How important are circular lists/recursive objects?

[Philippe Wang]

Brian Hurt wrote:
>
> In Ocaml you have some ability to define recursive data structures.  
> The classic example of this is the circular list:
>
> let rec example = 1 :: 2 :: example;;
>
> There are obvious limitations to this sort of trick:
>
> # let rec example = List.map (fun x -> x + 1) (1 :: 2 :: example);;
> This kind of expression is not allowed as right-hand side of `let rec'
> #
>
> The question is: if this behavior was completely outlawed, and either 
> you couldn't build up circular lists/recursive data structures of this 
> type at all, or had to call special functions (List.circularize, say), 
> to create them, would this be a signifigant problem?  Does anyone 
> actually use this construct, and if so, for what?
>
> Brian
In this case, it's simply the application that is not allowed as 
right-hand side of `let rec'.

For instance, you can't do this :
# let ( + ) a b = a :: b ;;
val ( + ) : 'a -> 'a list -> 'a list = <fun>
# let rec example = 1 + (2 + example) ;;
This kind of expression is not allowed as right-hand side of `let rec'

Let's remind that :: is a constructor of the type definition
type 'a list = :: of 'a * 'a list | []
(even if we can't write it in a .ml file)

If
# let rec example = List.map (fun x -> x + 1) (1 :: 2 :: example);;
were allowed, you would need lazy evaluation not to loop indefinitely.
So if you really want to loop, you need to use let rec to define a 
function and not just a data. (meaning the data "can't loop" while 
functions can)
Or like it has been suggested, you can use the module Lazy, but it's 
more job to do.


Well, sometime it can be useful (though some find it ugly) to define 
recursive data structures such as this one (it's only a simple example) :

# type 'a example = {
   mutable data : 'a list ;
   add : 'a -> unit ;
}

let create_example () =
  let rec e = {
      data = []   ;
      add = (fun x -> e.data <- x :: e.data);
  } in e
;;
type 'a example = { mutable data : 'a list; add : 'a -> unit; }
val create_example : unit -> 'a example = <fun>

Then you can program like this :

# let e = create_example ();;
val e : '_a example = {data = []; add = <fun>}
# let () = List.iter e.add [1; 2; 3; 4];;
# let l = e.data ;;
val l : int list = [4; 3; 2; 1]
# e ;;
- : int example = {data = [4; 3; 2; 1]; add = <fun>}

Like this, you can, for instance, create a environment data structure 
with an abstraction barrier, as then you can define the abstract 
structure for the environment and the functions that handle it, while 
being able to change the list choice to a map or hash table choice and 
so on.



Andrej Bauer wrote:
> Brian Hurt wrote:
>> Does anyone  actually use this construct, and if so, for what?
>
> When I teach my students "theory" of programming languages, we write 
> interpreters for mini languages. The recursive data structures are 
> used to create closures of recursive functions, environments that 
> contain mutually recursive values, closures of objects, etc. Life 
> would be very hard without this feature.
>
> Andrej
I don't think life would be very hard without this feature. (well, I 
mean I don't see any example that need this feature very badly)
For recursive closures, for instance, the idea is to have something that 
looks like
| RecClosure of
        name (* the name of the defined closure *)
     * name (* the first argument *)
     * expression (* i.e. the definition *)
     * environment
Then if you need to evaluate an application, like
| App of expression * expression

So when you match an application with a recursive closure at the 
left-hand side...
| App((ClosureRec (name, arg, def, env) as recclos), expr_b) ->
    let next_env = bind_var name recclos env in
    eval (bind_var x (eval higher_env expr_b) next_env) def

Well, maybe it's quite inefficient compared to the use of a recursive 
data structure, I don't know, I haven't really thought about this question.
But I mean I think it's not really hard to write an *interpreter* 
without "recursive data structure defined with let rec", until I'm 
showed an eloquent example :-p

Regards,

--
Philippe Wang
 

Re: [Caml-list] How important are circular lists/recursive objects?

[Bruno De Fraine]

Hello Jon,

On 03 Apr 2007, at 14:09, Jon Harrop wrote:

> Specifically, in the "eval" function:
>
>     | ELetRec(var, arg, body, rest) ->
>         let rec vars = (var, VClosure(arg, vars, body)) :: vars in
>         eval vars rest

Actually, I think this critical piece of code is incorrect. As such,  
the new "vars" is shadowing the old value of "vars", while it seems  
you still want to refer to this old value in one place. I.e.:

     | ELetRec(var, arg, body, rest) ->
         let rec new_vars = (var, VClosure(arg, new_vars, body)) ::  
vars in
         eval new_vars rest

If I define eval like this, it will still correctly evaluate your  
fibonacci example, but it will no longer loop infinitely on an  
example like "let foo x = x + 1 in let bar y = (foo y) + 1 in bar 3".

Regards,
Bruno


-- 
Bruno De Fraine
Vrije Universiteit Brussel
Faculty of Applied Sciences, INFO - SSEL
Room 4K208, Pleinlaan 2, B-1050 Brussels
tel: +32 (0)2 629 29 75
fax: +32 (0)2 629 28 70
e-mail: Bruno.De.Fraine@vub.ac.be

Re: How important are circular lists/recursive objects?

[Stefan Monnier]

> The question is: if this behavior was completely outlawed, and either you
> couldn't build up circular lists/recursive data structures of this type at
> all, or had to call special functions (List.circularize, say), to create
> them, would this be a signifigant problem?  Does anyone actually use this
> construct, and if so, for what?

This is the case in SML: you need to go through a `ref' cell in order to
create a cycle.  This has very rarely been presented as
a serious limitation.  OCaml's trick is occasionally useful, but I don't
think anybody would lose her sleep over it.


        Stefan

Re: [Caml-list] Re: How important are circular lists/recursive objects?

[skaller]

On Tue, 2007-04-03 at 23:52 -0400, Stefan Monnier wrote:
> > The question is: if this behavior was completely outlawed, and either you
> > couldn't build up circular lists/recursive data structures of this type at
> > all, or had to call special functions (List.circularize, say), to create
> > them, would this be a signifigant problem?  Does anyone actually use this
> > construct, and if so, for what?
> 
> This is the case in SML: you need to go through a `ref' cell in order to
> create a cycle.  This has very rarely been presented as
> a serious limitation.  OCaml's trick is occasionally useful, but I don't
> think anybody would lose her sleep over it.

You can also create cycles using functional abstraction (otherwise
a pure FPL wouldn't need a garbage collector, ref counting would
suffice).

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

RE: [Caml-list] Re: How important are circular lists/recursive objects?

[Don Syme]

Hi Stefan,

You might like to read my paper "Initializing Mutually Referential Abstract Objects", http://dx.doi.org/10.1016/j.entcs.2005.11.038, where I argue that this is a serious limitation, and argue the case for an alternative.  Interestingly Scala is considering using the kind of recursive initialization I propose in the paper, though much more extensively than I originally proposed.

Cheers & best wishes,
Don


-----Original Message-----
From: caml-list-bounces@yquem.inria.fr [mailto:caml-list-bounces@yquem.inria.fr] On Behalf Of Stefan Monnier
Sent: 04 April 2007 05:53
To: caml-list@inria.fr
Subject: [Caml-list] Re: How important are circular lists/recursive objects?

> The question is: if this behavior was completely outlawed, and either you
> couldn't build up circular lists/recursive data structures of this type at
> all, or had to call special functions (List.circularize, say), to create
> them, would this be a signifigant problem?  Does anyone actually use this
> construct, and if so, for what?

This is the case in SML: you need to go through a `ref' cell in order to
create a cycle.  This has very rarely been presented as
a serious limitation.  OCaml's trick is occasionally useful, but I don't
think anybody would lose her sleep over it.


        Stefan


_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] How important are circular lists/recursive objects?

[Brian Hurt]

On Tue, 3 Apr 2007, Andrej Bauer wrote:

> Brian Hurt wrote:
>> Does anyone  actually use this construct, and if so, for what?
>
> When I teach my students "theory" of programming languages, we write 
> interpreters for mini languages. The recursive data structures are used to 
> create closures of recursive functions, environments that contain mutually 
> recursive values, closures of objects, etc. Life would be very hard without 
> this feature.

No.  I'm just thinking about circular lists.

It's somewhat off-topic, but here's where I'm comming from.  Imagine a 
language with variant types and Wadler-style views

For those who don't know what Wadler style views, the long intro is:
http://citeseer.ist.psu.edu/wadler86views.html

The short intro is that it's a way to tie new data structures into pattern 
matching.  You could define a new data type, and a new operator on that 
datatype, for example (in pseudo-Ocaml):
 	type 'a t = Cons of 'a * 'a t | Nil;;

 	let cons h t = Cons(h, t);;

 	let decons arg matches doesnt_match =
 		match arg with
 			| Cons(h, t) -> matches h t
 			| Nil -> doesnt_match ()
 	;;

You could then tie the cons and decons functions in with the argument, 
maybe like:

 	define ( ::. ) = cons, decons ;;

so that when the compiler saw the code:

 	match lst with
 		| h ::. t -> expr1
 		| _ -> expr2

it would compile it as:
 	decons lst (fun h t -> expr1) (fun () -> expr2)

Allowing users of your new data structure to pattern match on the data 
structure using the normal operators for that data structure.

As you might guess from the above example, at this point you don't need to 
define lists as a built-in data structure.  You have all the capabilities 
you need to implement lists as a library.  With one, minor, exception- how 
does the compiler handler expressions like:
 	let rec a = 1 ::. 2 ::. a in ...

As that code compiles like:
 	let rec a = cons 1 (cons 2 a) in ...

Ocaml handles this construct because it knows about lists.  But it doesn't 
know about this t data structure.  It could be defined in another module, 
and be an abstract type.  It could have an arbitrarily complicated 
definition.  There is no garuentee in this case that cons doesn't look at 
the argument.  In fact, it'd be perfectly reasonble for t to be an 
implementation of Okasaki's random access lists:
http://citeseer.ist.psu.edu/okasaki95purely.html
at which point the implementation of cons *would* inspect the tail 
argument.

So, the question is: if a (at this point in time entirely hypothetical) 
programming language decided to go this route, and decided to simply 
outlaw self-referential data structures such as circular lists, would this 
be a problem?  Not that recursive and mutually recursive functions would 
still allowed, those are downright necessary.  I'm only thinking 
self-referential data structures.  But the compiler needs to know the 
structure of a closure, for obvious reasons, so the compiler knowing how 
to cheat and "fill in" the closure with the right values after those 
values have been generated isn't a problem.  I've become quite fond of the 
continuation passing style of code recently.

And this probably holds for a lazy thunk as well, especially considering a 
lazy thunk contains a closure (at least initially).

I will note that in Ocaml you can do:
# let rec x = lazy (Lazy.force x);;
val x : 'a Lazy.t = <lazy>
# Lazy.force x;;
Exception: Lazy.Undefined.
#

Simply because it compiles doesn't mean it makes sense, necessarily.

But hopefully this will clarify what I'm asking.

Brian

Re: [Caml-list] How important are circular lists/recursive objects?

[Jon Harrop]

On Thursday 05 April 2007 00:28, Brian Hurt wrote:
> On Tue, 3 Apr 2007, Andrej Bauer wrote:
> > Brian Hurt wrote:
> >> Does anyone  actually use this construct, and if so, for what?
> >
> > When I teach my students "theory" of programming languages, we write
> > interpreters for mini languages. The recursive data structures are used
> > to create closures of recursive functions, environments that contain
> > mutually recursive values, closures of objects, etc. Life would be very
> > hard without this feature.
>
> No.  I'm just thinking about circular lists.

The cyclic graph in an interpreter is a closure<->environment cycle, whereas a 
cyclic list involves only one structure (the list itself). However, I think 
the problems and properties are equivalent in this context.

> It's somewhat off-topic, but here's where I'm comming from.  Imagine a
> language with variant types and Wadler-style views
>
> For those who don't know what Wadler style views, the long intro is:
> http://citeseer.ist.psu.edu/wadler86views.html

How is Wadler's proposal related to views (active patterns) in F#?

> The short intro is that it's a way to tie new data structures into pattern
> matching.  You could define a new data type, and a new operator on that
> datatype, for example (in pseudo-Ocaml):
>  	type 'a t = Cons of 'a * 'a t | Nil;;
>
>  	let cons h t = Cons(h, t);;
>
>  	let decons arg matches doesnt_match =
>  		match arg with
>
>  			| Cons(h, t) -> matches h t
>  			| Nil -> doesnt_match ()
>
>  	;;
>
> You could then tie the cons and decons functions in with the argument,
> maybe like:
>
>  	define ( ::. ) = cons, decons ;;
>
> so that when the compiler saw the code:
>
>  	match lst with
>
>  		| h ::. t -> expr1
>  		| _ -> expr2
>
> it would compile it as:
>  	decons lst (fun h t -> expr1) (fun () -> expr2)
>
> Allowing users of your new data structure to pattern match on the data
> structure using the normal operators for that data structure.

You can do similar things with F#. A simpler example is getting rid of the 
integer total orderings of OCaml in favour of a more sane sum type:

  let (|Less|Equal|Greater|) c =
    if c<0 then Less else
      if c=0 then Equal else Greater

> As you might guess from the above example, at this point you don't need to
> define lists as a built-in data structure.

Is that not already true because pattern matching over variant type 
constructors provides everything you need?

> You have all the capabilities 
> you need to implement lists as a library.  With one, minor, exception- how
> does the compiler handler expressions like:
>  	let rec a = 1 ::. 2 ::. a in ...
>
> As that code compiles like:
>  	let rec a = cons 1 (cons 2 a) in ...

Provided it compiles to:

  let rec a = Cons(1, Cons(2, a))

you're ok.

> Ocaml handles this construct because it knows about lists.  But it doesn't
> know about this t data structure.

OCaml can already do that with user-defined data structures.

> It could be defined in another module, 
> and be an abstract type.  It could have an arbitrarily complicated
> definition.  There is no garuentee in this case that cons doesn't look at
> the argument.  In fact, it'd be perfectly reasonble for t to be an
> implementation of Okasaki's random access lists:
> http://citeseer.ist.psu.edu/okasaki95purely.html
> at which point the implementation of cons *would* inspect the tail
> argument.

Yes.

> So, the question is: if a (at this point in time entirely hypothetical)
> programming language decided to go this route, and decided to simply
> outlaw self-referential data structures such as circular lists, would this
> be a problem?

Can you define more precisely what you mean by "self-referential data 
structures" because that either seems to cover arbitrarily little or too many 
useful data structures.

But I think these are orthogonal concepts. OCaml already forbids:

  let rec a = cons 1 (cons 2 a)

because you can only use constructors in that context.

> Not that recursive and mutually recursive functions would 
> still allowed, those are downright necessary.  I'm only thinking
> self-referential data structures.

But data structures can contain closures and closures contain environments 
than can refer back to the data structure.

> But the compiler needs to know the 
> structure of a closure, for obvious reasons, so the compiler knowing how
> to cheat and "fill in" the closure with the right values after those
> values have been generated isn't a problem.  I've become quite fond of the
> continuation passing style of code recently.
>
> And this probably holds for a lazy thunk as well, especially considering a
> lazy thunk contains a closure (at least initially).
>
> I will note that in Ocaml you can do:
> # let rec x = lazy (Lazy.force x);;
> val x : 'a Lazy.t = <lazy>
> # Lazy.force x;;
> Exception: Lazy.Undefined.
> #
>
> Simply because it compiles doesn't mean it makes sense, necessarily.

I have a patch for the compiler that ensures sensicalness of programs. ;-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Re: How important are circular lists/recursive objects?

[Fabrice Marchant]

On Wed, 04 Apr 2007 15:28:18 +1000
skaller <skaller@users.sourceforge.net> wrote:
 
> You can also create cycles using functional abstraction 

  Sorry, I completely missed this old exciting topic and posts.

Please could you develop a bit to show how we can create cycles using functional abstraction ?

 In fact, my problem is I do not exactly see what means "functional abstraction".

Do you speak about something like this ?

type circular_list = Circular_list of (unit -> circular_list)

let rec cl = fun () -> Circular_list (fun () -> Circular_list cl)

Regards,

Fabrice

Re: [Caml-list] Re: How important are circular lists/recursive objects?

[skaller]

On Thu, 2007-10-04 at 19:48 +0200, Fabrice Marchant wrote:
> On Wed, 04 Apr 2007 15:28:18 +1000
> skaller <skaller@users.sourceforge.net> wrote:
>  
> > You can also create cycles using functional abstraction 
> 
>   Sorry, I completely missed this old exciting topic and posts.
> 
> Please could you develop a bit to show how we can create cycles using functional abstraction ?
> 
>  In fact, my problem is I do not exactly see what means "functional abstraction".

I mean lambda-abstraction in theory and closure in practice.

> Do you speak about something like this ?
> 
> type circular_list = Circular_list of (unit -> circular_list)
> let rec cl = fun () -> Circular_list (fun () -> Circular_list cl)

I think of something like:

	let f () = 
		let rec g() = k () 
		and k = g in
		k()
		
where g refers to itself. Other than use of a function closure
to create a box, let/in bindings cannot create cycles because
non-functional values have to be constructed from existing
already initialised values.

So apart from functional closures, FPLs can't have cycles and 
thus strangely would ensure that ref counting would be enough,
and you'd not need a garbage collector.

Once you have mutable variables then you need a gc because
it is easy to get cycles with mutable cells.

So what is weird about functions? It is because you can
create function closure with uninitialised slots for
storing bindings, and initialise the slots later by
executing it .. by which time you can put the address
of the closure itself in one of those slots.

So what is it that GUARANTEES that these uninitialised
values in the stack from of the function are not
incorrectly accessed? The answer is abstraction,
in particular lambda (functional) abstraction.
The local variables of a function cannot be accessed
from outside the function, you have to execute it.
So it is safe to create closures with uninitialised
slots in them -- in fact, that's the only way!

Note that stuff like:

	let rec x= (1,x)

is not generally allowed: in functional terms it is ill-defined,
and it certainly can't be implemented unless you box values
which is implementation detail. Felix doesn't box tuples,
so this would crash if Felix allowed it. 


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Re: How important are circular lists/recursive objects?

[rossberg]

skaller <skaller@users.sourceforge.net> wrote:
>
> Other than use of a function closure
> to create a box, let/in bindings cannot create cycles because
> non-functional values have to be constructed from existing
> already initialised values.
>
> So apart from functional closures, FPLs can't have cycles

That's solely a question of the semantics of their fixpoint operator.
Ocaml certainly supports "let rec xs = 1::xs". And just for perspecive,
the following is the canonical definition of the (infinite) list of
Fibonacci numbers in Haskell:

  fibs = 1:1:zipWith (+) fibs (tail fibs)


> Note that stuff like:
>
> 	let rec x= (1,x)
>
> is not generally allowed: in functional terms it is ill-defined,

It is disallowed in OCaml because it has a cyclic type, not because it is
a cyclic value. Try with "ocaml -rectypes".

- Andreas

Re: [Caml-list] Re: How important are circular lists/recursive objects?

[skaller]

On Thu, 2007-10-04 at 23:36 +0200, rossberg@ps.uni-sb.de wrote:
> skaller <skaller@users.sourceforge.net> wrote:

> > Note that stuff like:
> >
> > 	let rec x= (1,x)
> >
> > is not generally allowed: in functional terms it is ill-defined,
> 
> It is disallowed in OCaml because it has a cyclic type, not because it is
> a cyclic value. Try with "ocaml -rectypes".

lists have cyclic types too, they're not disallowed!

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Re: How important are circular lists/recursive objects?

[Dominique Martinet]

On 05/10/2007, skaller <skaller@users.sourceforge.net> wrote:
> On Thu, 2007-10-04 at 23:36 +0200, rossberg@ps.uni-sb.de wrote:
> > skaller <skaller@users.sourceforge.net> wrote:
>
> > > Note that stuff like:
> > >
> > >     let rec x= (1,x)
> > >
> > > is not generally allowed: in functional terms it is ill-defined,
> >
> > It is disallowed in OCaml because it has a cyclic type, not because it is
> > a cyclic value. Try with "ocaml -rectypes".
>
> lists have cyclic types too, they're not disallowed!

Lists have a base case to end the cycle, your definition does not (it
would be int*int*int...*int and infinity of time, wheras a list
contains either a value (head) and a list (tail), either nothing (that
is, the empty list [])

Re: [Caml-list] Re: How important are circular lists/recursive objects?

[Andreas Rossberg]

skaller wrote:
>>> Note that stuff like:
>>>
>>> 	let rec x= (1,x)
>>>
>>> is not generally allowed: in functional terms it is ill-defined,
>>>       
>> It is disallowed in OCaml because it has a cyclic type, not because it is
>> a cyclic value. Try with "ocaml -rectypes".
>>     
>
> lists have cyclic types too, they're not disallowed!
>   

Technically speaking they haven't, because conventional variant types 
are nominal, not structural.

In any case, even OCaml without -rectypes allows some cyclic types (if 
the cycle goes through an object or polymorphic variant type), but not 
arbitrary ones. That is a pragmatic design decision to avoid too many 
bogus examples to type-check.

- Andreas