三浦です

> 例えばどんなときに計算量が爆発するのか、教えてもらってもよろしい
> でしょうか。(ネットで検索しても良く分かりませんでした)
> もっとも私に理解できる能力があるかも問題ですが。
> 私の構想中の自作言語は、この型の自動汎化の機構に全面的に
> 依存しているので、できないと大変困るのです。
私が作った型推論器ではブロック(高階関数)の型推論が重かったです。
この手の推論では型付けが収束するまで何度でも型推論を繰り返す
必要があります。
私はあまり遅いと感じなかったですが、TaPLによれば、再帰型(Listや
Treeなどの自分自身へのポインタを含んだ型)の推論で指数オーダになる
場合もあるととのことです。