Как заставить Хиндли и Милнера молить о пощаде

Простой и в то же время кошмарный пример, демонстрирующий Силу и Мощь показательной функции.

> let f0 x = (x, x);;

val f0 : 'a -> 'a * 'a

> let f1 x = f0 (f0 x);;

val f1 : 'a -> ('a * 'a) * ('a * 'a)

> let f2 x = f1 (f1 x);;

val f2 :
  'a ->
    ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
    ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))

> let f3 x = f2 (f2 x);;

val f3 :
  'a ->
    ((((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))))) *
     (((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))))) *
    ((((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))))) *
     (((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))))) *
      ((((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))) *
       (((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a))) *
        ((('a * 'a) * ('a * 'a)) * (('a * 'a) * ('a * 'a)))))))

Если вам не жаль свой fsi.exe, можете пойти еще дальше:

> let f4 x = f3 (f3 x);;

Моя консоль честно трудилась 42 секунды, выводя тип этой функции на экран. В её возвращаемом значении 65536 упоминаний 'a.