SML 中函数的类型

Question

谁能向我解释为什么下面给出的函数类型是
<代码>('a * 'b -> 'b) -> 'b-> '列表-> '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（return）的返回类型相同，而（arg3）是一些未知类型的列表。

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

---

  | foldr f b (x::xs)

x 和 xs 组成 (arg3) 列表。

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 返回 (return) 相同类型的函数。元组的第一项与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-> '列表-> '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

“Which is what is reporting”。