0

谁能向我解释为什么下面给出的函数类型是
('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.

4

2 回答 2

4

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

给定一个函数,

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)

xxs组成 (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元组的第一项与 的类型相同xfoldr元组的第二项与(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

于 2011-02-12T11:01:48.873 回答
1

我认为上面的代码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

这是正在报告的内容。

于 2011-02-12T10:52:54.053 回答