了解以下功能的类型

Question

我在OCaml中编写了一个merge_sorted函数，它接受一个比较函数和两个排序列表并将它们合并在一起。我试图理解为什么这个函数的类型是

('a -> 'a -> bool) -> 'a list -> 'a list -> 'a list

并不是

('a -> 'a -> bool) -> 'a list

因为它只返回一个列表。下面是merge_sorted函数的代码

let rec merge_sorted lt a b = 
    match a with 
    | [] -> b
    | h::t -> match b with
            | []-> a 
            | hh::tt -> if (lt h hh) 
                        then h::merge_sorted lt t b 
                        else hh::merge_sorted lt a tt;;

Answer 1

该函数采用类型为'a -> 'a -> bool，'a list和'a list的三个参数。它返回'a list类型的值。函数的类型（当以curried形式定义时）由参数类型组成，由->分隔，后跟返回类型。

因此类型真的是('a -> 'a -> bool) -> 'a list -> 'a list -> 'a list。前两个'a lists是第二个和第三个参数类型。最后一个'a list是返回类型。

这不仅仅是一个符号公约。您的函数实际上接受比较函数（类型为'a -> 'a -> bool）并返回两个参数的函数。返回的函数接受一个列表（类型为'a list）并返回一个函数。等等。