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] Polymorphic variants
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2002-04-25 (13:20)
From: Jerome Vouillon <vouillon@p...>
Subject: Re: [Caml-list] How to compare recursive types?
On Wed, Apr 24, 2002 at 04:55:29PM +1000, John Max Skaller wrote:
> How to compare recursive types?

You should definitively read "Recursive Subtyping Revealed" by
Vladimir Gapeyev, Michael Levin, and Benjamin Pierce.
(Available from

If you are only interested in equality, you can use the same algorithm
as for subtyping (equality is a preorder).  The complexity of this
algorithm can be improved from quadratic to (almost) linear by
exploiting the fact that type equality is an equivalence relation: the
algorithm uses a set of pairs of already encountered types, but you
can use a union-find datastructure instead.

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