Re: [Caml-list] How to compare recursive types? Solution!

[Jerome Vouillon <vouillon@pps.jussieu.fr>]

On Thu, Apr 25, 2002 at 05:03:12PM +1000, John Max Skaller wrote:
> Basically, I normalise the type terms and use ocamls polymorphic
> equality operator! The normalisation involves counting what
> *real* level of the tree the recursive descent is in -- add one for
> each binary Pair node. Each typedef name substituted along
> the branch is tracked in an association list along with its level.
> When a typedef name is encountered that is in this list,
> replace it with Fix n, where n is the associated level number:
> this uniquely determines the recursion argument.

Assume the following definition:
  typedef y = int * y;
Then "y" and "int * y" are not equal according to your algorithm.
Is it what you expect?

Why don't you make the pointers explicit in the type?  Then, the two
types definitions below would not define the same type
  typedef x = ref(x) * int;
  typedef y = (ref(y) * int) * int;
while these two would define the same type
  typedef x = ref(x) * int;
  typedef y = ref(ref(y) * int) * int;

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