谁能向我解释为什么下面给出的函数类型是
('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
.
要确定函数的类型,过程基本上是这样的:
给定一个函数,
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
我认为上面的代码foldr
不正确;它应该是
fun foldr f b [] = b
| foldr f b (x::xs) = (f x (foldr f b xs))
也就是说,它不应该传入参数元组,而是foldr
像往常一样传入累加器和递归调用作为参数。
至于类型来自哪里,请记住它foldr
接受三个参数:
假设累加器有 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
这是正在报告的内容。