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接收一个元组并返回 at'b并且在基本情况下我们返回'b.

Answer 1

要确定函数的类型，过程基本上是这样的：

给定一个函数，

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

假设所有类型的参数和返回值都是未知的。

折叠：'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)

x并xs组成 (arg3) 的列表。

f (arg1): 'a
b (arg2): 'b
  (arg3): 'e 列表
（返回）：'b
x：'e
xs : 'e 列表

---

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

然后(arg1) 是一个接受 2 元组并返回与返回 (return)f相同类型的函数。foldr元组的第一项与 的类型相同x。foldr元组的第二项与（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像往常一样传入累加器和递归调用作为参数。

至于类型来自哪里，请记住它foldr接受三个参数：

1. 在范围内应用的函数。
2. 累加器的初始值。
3. 折叠的范围。

假设累加器有 type'b并且列表有 type 'blist。我们知道函数的整体返回类型应该是'b，因为我们有

fun  foldr f b [] = b 

现在让我们看看是什么类型f。我们有这个：

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

这接受列表的第一个元素和累加器，然后产生必须是 type 的东西'b。列表有类型'a list，累加器有类型'b，所以函数有类型('a * 'b -> 'b)。

总结一下，函数的类型是

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

这是正在报告的内容。