Version française
Home     About     Download     Resources     Contact us    
Browse thread
compiling large file hogs RAM and takes a long time.
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Christophe Raffalli <christophe.raffalli@u...>
Subject: Re: [Caml-list] large parametrized polymorphic variant type combinations take forever to compile

> 
> 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
---------------------------------------------