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
Type abstraction and (polymorphic) equality
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-06-30 (19:54)
From: John Skaller <skaller@u...>
Subject: Re: [Caml-list] Type abstraction and (polymorphic) equality
On Thu, 2005-06-30 at 11:51 +0200, Andreas Rossberg wrote:
> sejourne_kevin wrote:
> > 
> > A generic equality should be one that work with recursives.
> Not so easy. In order to be a proper equivalence test for cyclic data 
> structures it essentially had to test graph equivalence, which is the 
> same as testing equivalence of DFAs. So it would be a completely 
> different algorithm, with significant complexity in space and time.

I do not see that. The current algorithm is recursive descent
is it not? That can also be used with a trivial modification
to test graph equivalence, by simply keeping a list of visited
nodes and not revisiting them. 

The problem of course is that the cost per node
is O(N) where N is the recursion depth.

Profiling indicates my code spends up to 60% of all time
doing comparisons.

> In Alice ML, where we have recently added such a co-recursive 
> equivalence operation, we opted for turning it into a separate 
> operation, to avoid these issues.

That seems reasonable, since the client will usually
know if the data structure contains cycles or not.

John Skaller <skaller at users dot sourceforge dot net>
Download Felix: