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 

这是被报道的内容。