Daniel de Rauglaudre a écrit :
> Hi,
>
> On Tue, Aug 28, 2007 at 11:18:50PM +1000, Pietro Abate wrote:
>
>   
>> the other day I was looking for a fringe case to show me the worst
>> complexity of the type inference algorithm...
>>     
>
> Interesting. To see the resulting time, I changed the code into:
>
>   let f =
>   let x1 = fun x -> (x,x) in
>   let x2 = fun y -> x1 ( x1 y ) in
>   let x3 = fun y -> x2 ( x2 y ) in
>   let x4 = fun y -> x3 ( x3 y ) in
>   let x5 = fun y -> x4 ( x4 y ) in
>   x5 ( fun z -> z ) ;;
>
>   
This is strange, it is problematic even with -rectypes while this is
not necessary if the subtypes are shared ... I already so ocaml
printing some types with sharing, so why is this not the case here ?
(I am using 3.09.2)

With pml I seem to get a polynomial
behavior (at least quadratic but probably cubic), I tested up to 9.
This is because the type of xi  is bigger and bigger (but linear in i)
and it is copied by the generalisation and particularisation for each i.

Christophe