成長類型定義的使用辛德雷米爾納類型推斷

Question

有人曾經給我看SML一個小「伎倆」，其中他們在REPL寫了約3或4的功能和最後一個值的結果類型是極長（如很多頁面卷軸很長）。

有誰知道什麼代碼產生這麼長的類型，或者如果有一個名稱爲這種行爲的？如果你以正確的方式撰寫他們

Answer 1

由辛德雷/米爾納類型推理來推斷類型可以成爲指數大小。例如：

fun f x = (x, x, x) 
val t = f (f (f (f (f 0)))) 

這裏，t是嵌套三重，其嵌套深度對應於f調用的數目n。因此，整體類型的大小爲3^n。

然而，這實際上並不是最壞的情況，因爲類型具有規則的結構，並且可以在線性空間中高效地表示（因爲在每個級別上，所有三種組成類型都是相同的並且可以共享） 。

真正的最壞的情況下使用多態實例擊敗這樣的：

fun f x y z = (x, y, z) 
val p1 = (f, f, f) 
val p2 = (p1, p1, p1) 
val p3 = (p2, p2, p2) 

在這種情況下，該類型又是成倍大，但不像上面，所有的組成類型是不同的清爽型的變量，因此，即使是圖表表示呈指數增長（在pN聲明的數量中）。

所以，是的，辛德雷/米爾納風格的類型推斷是最壞情況下的指數（在空間和時間）。然而，值得指出的是，指數情況只能出現在類型指數規模較大的情況下 - 即在沒有類型推斷的情況下甚至不能實際表達的情況。