Re: [Caml-list] Hash function: complexity and circular structures

[Nick Lucaroni <nicholas.r.lucaroni@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1639 bytes --]

Calling find from the values ones and ones2 work because the compare
function does a physical comparison before structural comparison and both
of these values are derived from the same list you used as the key. So as
the structural comparison affirms the physical differences between the two
types, a physical comparison ends the loop of the recursive structure. And
this is also why looking up ones3 will result in an infinite loop of
comparisons.

You can implement your own comparison algorithm in the equal function of
the Hashtbl.HashedType module for the Hashtbl.Make functor if you must
proceed with cyclic lists in this fashion as keys. But as Gabriel has said,
you should look at a different data-structures.


On Fri, Jan 18, 2013 at 1:27 PM, Gabriel Scherer
<gabriel.scherer@gmail.com>wrote:

> A blunt point of view: comparing implicitly circular structures is a
> sure road to hell, and you should use an explicit representation of
> circularity (eg. with a element that just means "nothing here, you
> should rewind to the other side") that will not blow up at each
> occasion it gets -- and is generally much more flexible.
>
> On Fri, Jan 18, 2013 at 6:46 PM, Jean-Baptiste Jeannin
> <jeannin@cs.cornell.edu> wrote:
> >
> > I would be curious to know if this is by design (it is supposed not to
> > work), or if it is a problem with the implementation of compare, or of
> > Hashtbl.find. In particular, if it is by design, why have updated the
> hash
> > function to support circular lists?
> > I am also now stuck on creating an (efficient) hashtable supporting
> circular
> > data structures as keys. Any idea on this?
>

[-- Attachment #2: Type: text/html, Size: 2142 bytes --]