sml - SMLの関数のタイプ

Question

以下に示す関数のタイプがなぜであるかを誰かが私に説明できます
('a * 'b -> 'b) -> 'b -> 'a list -> 'bか？

関数は次のとおりです。

fun foldr f b [] = b 
  | foldr f b (x::xs) = f (x, (foldr f b xs))

この関数を見ると、タプルを取り込んで戻って('a * 'b -> 'b) -> 'bくる関数があり、基本ケースでは。を返すので、型は正しいはずです。f'b'b

Answer 1

関数のタイプを判別するためのプロセスは、基本的に次のようになります。

与えられた関数、

fun foldr f b []      = b
  | foldr f b (x::xs) = f (x, (foldr f b xs))

すべてのタイプのパラメーターと戻り値が不明であると想定します。

foldr：'a->' b->'c->' d
f（arg1）：'a
b（arg2）：'b
  （arg3）：'c
（戻る）：'d

---

fun foldr f b []      = b

まず、b（arg2）は（return）の戻り型と同じでfoldrあり、（arg3）はいくつかの未知の型のリストであることがわかります。

f（arg1）：'a
b（arg2）：'b
  （arg3）：'eリスト
（戻る）：'b

---

  | foldr f b (x::xs)

xxs（arg3）のリストを作成します。

f（arg1）：'a
b（arg2）：'b
  （arg3）：'eリスト
（戻る）：'b
x：'e
xs：'eリスト

---

                      = f (x, (foldr f b xs))

次に、 （arg1）は、2タプルを取り、 returns（return）fと同じ型を返す関数です。foldrタプルの最初の項目は同じタイプのですx。foldrタプルの2番目の項目は、 （return）のreturnタイプと同じタイプです。型は、これまでのところ、への再帰呼び出しにも当てはまりますfoldr。

f（arg1）：'e *'b->'b
b（arg2）：'b
  （arg3）：'eリスト
（戻る）：'b
x：'e
xs：'eリスト

---

fun foldr f b []      = b
  | foldr f b (x::xs) = f (x, (foldr f b xs))

これ以上単純化することはできないため、次のタイプがあります。

フォルダー：('a * 'b -> 'b) -> 'b -> 'a list -> 'b

Answer 2

foldr上記のコードは正しくないと思います。そのはず

fun  foldr f b [] = b 
   | foldr f b (x::xs) = (f x (foldr f b xs))

つまり、引数のタプルを渡すのではなく、foldr通常どおり、アキュムレータとへの再帰呼び出しを引数として渡す必要があります。

タイプの由来については、次のfoldr3つのパラメーターを使用することを忘れないでください。

1. 範囲全体に適用する関数。
2. アキュムレータの初期値。
3. 折りたたむ範囲。

アキュムレータのタイプがタイプ'bで、リストのタイプがであるとし'blistます。関数の全体的な戻り値のタイプは、である必要がある'bことがわかっています。

fun  foldr f b [] = b 

タイプが何であるかを見てみましょうf。私たちはこれを持っています：

foldr f b (x::xs) = (f x (foldr f b xs))

これにより、リストの最初の要素とアキュムレータが取り込まれ、タイプが必要なものが生成されます'b。リストにはタイプが'a listあり、アキュムレータにはタイプ'bがあるため、関数にはタイプがあり('a * 'b -> 'b)ます。

これを要約すると、関数のタイプは次のとおりです。

('a * 'b -> 'b) -> 'b -> 'a list -> 'b

これが報告されているものです。