Re: [Caml-list] large parametrized polymorphic variant type combinations take forever to compile

[Christophe Raffalli <christophe.raffalli@univ-savoie.fr>]

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