(* Question: How hard can ML type inference be? 
   Answer  : Harder than you might imagine! 
*) 

> PolyML.print_depth 1000000;
val it = (): unit

> fun pair x f = f x x ;
val pair = fn: 'a -> ('a -> 'a -> 'b) -> 'b

> fun f1 x = pair x ;
val f1 = fn: 'a -> ('a -> 'a -> 'b) -> 'b

> fun f2 x = f1 (f1 x);
val f2 = fn:
   'a -> ((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c

> fun f3 x = f2 (f2 x);
val f3 = fn:
   'a ->
     ((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e

> fun f4 x = f3 (f3 x);
val f4 = fn:
   'a ->
     ((((((((((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c)
     -> 'c) ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) ->
     (((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) -> 'f) -> 'f) ->
     (((((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) ->
     'c) ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) ->
     (((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) -> 'f) -> 'f) -> 'g) -> 'g) ->
     (((((((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) ->
     'c) ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) ->
     (((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) -> 'f) -> 'f) ->
     (((((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) ->
     'c) ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) ->
     (((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) -> 'f) -> 'f) -> 'g) -> 'g) -> 'h) -> 'h) ->
     (((((((((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c)
     -> 'c) ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) ->
     (((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) -> 'f) -> 'f) ->
     (((((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) ->
     'c) ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) ->
     (((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) -> 'f) -> 'f) -> 'g) -> 'g) ->
     (((((((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) ->
     'c) ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) ->
     (((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) -> 'f) -> 'f) ->
     (((((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) ->
     'c) ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) ->
     (((((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) ->
     (((((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c)
     ->
     (((('a -> 'a -> 'b) -> 'b) -> (('a -> 'a -> 'b) -> 'b) -> 'c) -> 'c) ->
     'd) -> 'd) -> 'e) -> 'e) -> 'f) -> 'f) -> 'g) -> 'g) -> 'h) -> 'h) -> 'i)
     -> 'i
>