From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 004A8BBC1 for ; Wed, 5 Mar 2008 17:49:40 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAMtdzkfAXQImh2dsb2JhbACQcgEBAQgKKZox X-IronPort-AV: E=Sophos;i="4.25,451,1199660400"; d="scan'208";a="9917625" Received: from discorde.inria.fr ([192.93.2.38]) by mail3-smtp-sop.national.inria.fr with ESMTP; 05 Mar 2008 17:49:40 +0100 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id m25GneXH031177 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Wed, 5 Mar 2008 17:49:40 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAEJezkfBL1AZi2dsb2JhbACQcgEBAQgEBgcIGpo0 X-IronPort-AV: E=Sophos;i="4.25,451,1199660400"; d="scan'208";a="8042802" Received: from gw.exalead.com (HELO exalead.com) ([193.47.80.25]) by mail2-smtp-roc.national.inria.fr with ESMTP; 05 Mar 2008 17:49:40 +0100 Received: from [192.168.204.148] (madpc064.exalead.com [192.168.204.148]) (authenticated bits=0) by exalead.com (8.14.0/8.14.0) with ESMTP id m25GndY4016584 for ; Wed, 5 Mar 2008 17:49:39 +0100 Message-ID: <47CECF23.1020508@exalead.com> Date: Wed, 05 Mar 2008 17:49:39 +0100 From: Berke Durak User-Agent: Thunderbird 1.5.0.10 (X11/20070221) MIME-Version: 1.0 To: Caml-list List Subject: Canonical Set/Map datastructure? Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 47CECF24.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; berke:01 durak:01 berke:01 durak:01 functors:01 polymorphic:01 modules:02 modules:02 functional:02 canonical:03 canonical:03 suffice:03 hoc:03 correctly:04 comparison:05 The Map and Set modules use AVL trees which are efficient but not canonical - a given set of elements can have more than one representation. This means that you cannot use ad hoc comparison on sets and maps, and this is why they are presented as functors. Does anyone know if, in the many years that have passed since the implementation of those fine modules, someone has invented a (functional) datastructure that is as efficient while being canonic? That would permit polymorphic set and map modules that work correctly on sets of sets, for instance. Of course, the order induced on sets by the adhoc comparison doesn't have to be a useful order; just being a good order would suffice. -- Berke DURAK