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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 6DCF3BC6B for ; Tue, 10 Jul 2007 09:09:41 +0200 (CEST) Received: from smtp5-g19.free.fr (smtp5-g19.free.fr [212.27.42.35]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6A79fVh005289 for ; Tue, 10 Jul 2007 09:09:41 +0200 Received: from [192.168.144.128] (lns-bzn-20-82-64-9-145.adsl.proxad.net [82.64.9.145]) by smtp5-g19.free.fr (Postfix) with ESMTP id 9B73C4510F; Tue, 10 Jul 2007 09:09:40 +0200 (CEST) Message-ID: <469330B3.4080005@univ-savoie.fr> Date: Tue, 10 Jul 2007 09:09:39 +0200 From: Christophe Raffalli User-Agent: Thunderbird 1.5.0.12 (X11/20070604) MIME-Version: 1.0 To: Jacques Garrigue Cc: sds@gnu.org, caml-list@inria.fr Subject: Re: [Caml-list] large parametrized polymorphic variant type combinations take forever to compile References: <4666E11F.6000308@podval.org> <4692991E.8040205@gnu.org> <20070710.083733.116353766.garrigue@math.nagoya-u.ac.jp> In-Reply-To: <20070710.083733.116353766.garrigue@math.nagoya-u.ac.jp> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-Miltered: at concorde with ID 469330B5.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; christophe:01 raffalli:01 christophe:01 raffalli:01 univ-savoie:01 parametrized:01 ocaml:01 ocaml:01 encodes:01 satisfiable:01 bool:01 bool:01 chablais:01 73376:01 univ-savoie:01 > > Are you using the CVS 3.10 version? > Performance has been been improved, but as I already answerred you, > complexity for polymorphic variant pattern-matching is still O(n*n), This looks strange: OCaml compute useless cases and incomplete pattern and since you can encode SAT in that, I would think that OCaml pattern matching (with monomorphic or polymorphic variant) would be exponential ... OK, this is for large patterns, not just case analysis. As an example, the following function f encodes the following SAT problem: not a, b ; a, not c ; not b, c ; a, b, c and f is incomplete iff the above set of clauses is satisfiable type r = { a : bool; b : bool; c : bool } let f = function | { a = true; b = false } -> () | { a = false; c = true } -> () | { b = true; c = false } -> () | { a = false; b = false; c = false } -> () -- Christophe Raffalli Université de Savoie Batiment Le Chablais, bureau 21 73376 Le Bourget-du-Lac Cedex tél: (33) 4 79 75 81 03 fax: (33) 4 79 75 87 42 mail: Christophe.Raffalli@univ-savoie.fr www: http://www.lama.univ-savoie.fr/~RAFFALLI --------------------------------------------- IMPORTANT: this mail is signed using PGP/MIME At least Enigmail/Mozilla, mutt or evolution can check this signature. The public key is stored on www.keyserver.net ---------------------------------------------