how to upset the ocaml type system....

[Pietro Abate <Pietro.Abate@anu.edu.au>]

hi all,

the other day I was looking for a fringe case to show me the worst
complexity of the type inference algorithm...

I think I found what I was looking for:

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
let x6 = fun y -> x5 ( x5 y ) in
let x7 = fun y -> x6 ( x6 y ) in
x7 ( fun z -> z ) ;;

are there any other examples that exhibit worst-case complexity ?

pietro

ps: the example is from the paper "polymorphic unification and ML
typing" from kannellakis

-- 
++ Blog: http://blog.rsise.anu.edu.au/?q=pietro
++ 
++ "All great truths begin as blasphemies." -George Bernard Shaw
++ Please avoid sending me Word or PowerPoint attachments.
   See http://www.fsf.org/philosophy/no-word-attachments.html