[Caml-list] Representation of anonymous recursive types

[John Max Skaller <skaller@ozemail.com.au>]

What is a good way to represent an anonymous recursive type
so that they can be easily compared for equality?

Felix currently supports recursion, but only for generative types,
that is, ones for which there is an entry into a symbol table.
Binding the type then replaces the name with the symbol
table index.

This cannot work for an anonymous type, unless of course
a secret entry is made in the symbol table, and that would
fail to correctly support type comparisons.

I'm thinking of something like:

  type texpr = [ ....
   | `Rec int
   | `As int * texpr]

where the argument of `Rec indicates the containing `As term with
the same index. I think this means that the standard Ocaml
comparison <> will correctly test equality.

Example:

   (Cons of int * 'a | Empty) as 'a

is modelled by:

   `As (1, `Sum [`Nctor ("Cons", `Prod [`Int; `Rec 1]); `Cctor "Empty"])

For uniqueness, the index has to be 1 for inner most recursion,
2 for next outer one, etc.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850



-------------------
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