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 
(return): 'd 

所有的

---

fun foldr f b []  = b 

首先，我們可以看到，b（ARG2）是一樣的foldr（返程）和（參數3）的返回類型是一些未知類型的列表。

 
f (arg1): 'a 
b (arg2): 'b 
    (arg3): 'e list 
(return): 'b 

---

| foldr f b (x::xs) 

x和xs彌補（參數3）名單。

 
f (arg1): 'a 
b (arg2): 'b 
    (arg3): 'e list 
(return): 'b 
x  : 'e 
xs  : 'e list 

---

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

然後f（ARG1）是一個函數，它有2元組，並返回相同類型foldr返回（返回）。元組的第一項是x的相同類型。元組的第二項是返回類型foldr（返回）的相同類型。對於遞歸調用foldr，類型也持有至今。

 
f (arg1): 'e * 'b -> 'b 
b (arg2): 'b 
    (arg3): 'e list 
(return): 'b 
x  : 'e 
xs  : 'e list 

---

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

它不能被任何進一步的簡化，使我們有類型：

foldr相似：('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作爲參數如常。

至於其中類型從何而來，記得foldr發生在三個參數：

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 

這是被報道的內容。