From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by sympa.inria.fr (Postfix) with ESMTPS id D848D7EEB3 for ; Fri, 18 Jan 2013 21:11:55 +0100 (CET) Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of trigger0219@gmail.com) identity=pra; client-ip=209.85.220.177; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="trigger0219@gmail.com"; x-sender="trigger0219@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail4-smtp-sop.national.inria.fr: domain of trigger0219@gmail.com designates 209.85.220.177 as permitted sender) identity=mailfrom; client-ip=209.85.220.177; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="trigger0219@gmail.com"; x-sender="trigger0219@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail4-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-vc0-f177.google.com) identity=helo; client-ip=209.85.220.177; receiver=mail4-smtp-sop.national.inria.fr; envelope-from="trigger0219@gmail.com"; x-sender="postmaster@mail-vc0-f177.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqIBADSs+VDRVdyxm2dsb2JhbABEvjIIFg4BAQEBAQgJCwkUJ4IeAQEEAUABGx0BAwELAQUFBAcNLiEBAREBBQEcBhOIBgEDCQaeeIw0gnuFBAoZJw1Zh38BBQyLfYUwA4hhi1WBVos3gzEWKYFYgl0 X-IronPort-AV: E=Sophos;i="4.84,494,1355094000"; d="scan'208";a="168965002" Received: from mail-vc0-f177.google.com ([209.85.220.177]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 18 Jan 2013 21:11:55 +0100 Received: by mail-vc0-f177.google.com with SMTP id fo14so3755703vcb.8 for ; Fri, 18 Jan 2013 12:11:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:mime-version:sender:in-reply-to:references:from:date :x-google-sender-auth:message-id:subject:to:cc:content-type; bh=sbj4jyqYJJgftZIQVN4BS3XM/14Q2VPkhPK/SpOoE/U=; b=rmTFeZVxnx62QvoflUWSYiyDYnzTN319Ed9TOqrjjP4lhXt3g4kOS8avpdQ4TaxSmD 6AXjoC3mQDjsd86iSbgPbS4lylUi6GJgdFEvm/I7nhNlsYBHl+Nm6xWzCOumSLNN8vqe SwUEbLAgTW1X5ifj1IVpROSkmn883wko8QfYVOYt7Gny3zQhuDXH1KocYx4BFh6s8v97 IvA0jPCERBrWFOmSjiMWhRxq1uqQxlLMxWPQ0NBRe1+jtkE4PwDZHvtPY/zpLQJx9MXC wzn1MTTGVgxYpvcxLcpc1HvcAY1lfy/b4v3uM8Qv8Cannu4B6FQ7LkYnjYqTS6WxeCno ssfg== X-Received: by 10.220.142.74 with SMTP id p10mr11045607vcu.63.1358539913828; Fri, 18 Jan 2013 12:11:53 -0800 (PST) MIME-Version: 1.0 Sender: trigger0219@gmail.com Received: by 10.220.115.81 with HTTP; Fri, 18 Jan 2013 12:11:13 -0800 (PST) In-Reply-To: References: <50F81A48.4080901@cs.cornell.edu> <50F98A81.6080902@cs.cornell.edu> From: Nick Lucaroni Date: Fri, 18 Jan 2013 15:11:13 -0500 X-Google-Sender-Auth: 7iFVJTEYqwBM685Kxj9pzeWOYW8 Message-ID: To: Gabriel Scherer Cc: Jean-Baptiste Jeannin , Edgar Friendly , "caml-list@inria.fr" Content-Type: multipart/alternative; boundary=f46d0434bf54fa196404d395b827 Subject: Re: [Caml-list] Hash function: complexity and circular structures --f46d0434bf54fa196404d395b827 Content-Type: text/plain; charset=ISO-8859-1 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 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 > 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? > --f46d0434bf54fa196404d395b827 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
Calling find from the values ones and ones2 work because the compare f= unction 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 typ= es, a physical comparison ends the loop of the recursive structure. And thi= s is also why looking up ones3 will result in an infinite loop of compariso= ns.

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


On Fri, Jan 18, 2013 at 1:27 PM, Gabrie= l 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 ci= rcular
> data structures as keys. Any idea on this?

--f46d0434bf54fa196404d395b827--