On Tue, 14 May 2002, Francois Pottier wrote:

> The worst-case complexity is obtained by nesting `let' bindings
> on the left side, i.e.
>
>   let x1 = let x2 = let x3 = ...
>
> Do you generate such code, Markus?

Mmm, I thought (misleaded by a teacher, of course) that the following
would exhibit exponential behavior of type-inference:

let f y z = (z y) y
let f y = f (f y)
let f y = f (f y)
let f y = f (f y)
let f y = f (f y)
let f y = f (f y)
(* ad libitum *)

It seems that what takes time is occurence checking (disabled
with -rectypes) and pretty-printing of types (because internally, there
are many sharings), not type inference itself. For this (unatural)
example, bad behaviour of occurence checking is visible
(less than 0.04 seconds with -rectypes, and more than 10 minutes
[I'm not patient enough to wait more] without -rectypes).


-- Alain

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners