sml - SML で関数型を推測する方法

Question

foo次のように定義された関数があります

fun foo x y = x (x (x y));

関数の型を推測する方法は?

答えは次のとおりです。

val foo = fn : ('a -> 'a) -> 'a -> 'a

Answer 1

このプロセスは型推論と呼ばれ、SML でHindley–Milner アルゴリズムによって行われます。

まず、 のジェネリック型シグネチャから始めましょうfoo:

val foo = fn : 'c -> 'b -> 'a

where xhas type'cとyhas type 'b。

次の手順があります。

• x yは関数の適用であり、x署名が必要'b -> 'dであり、方程式が'c = 'b -> 'dあり、x ytype があり'dます。
• x (x y)'b -> 'dは、引数の型'dso 'd = 'bおよびに関数型を適用することを意味します'c = 'b -> 'b。
• x (x (x y))'b -> 'b引数の型に関数型を適用して(型の)'bを返すことを意味します。それで十分です。'afoo'b = 'a
• 統合後、ジェネリック型が'c = 'a -> 'a and 'b = 'aあります。fooval foo = fn : ('a -> 'a) -> 'a -> 'a