高阶函数

简介

在 OCaml 中，使用函数很快就会成为第二天性。我们喜欢认为 *函数描述了世界*，就像这样，我们通常编写函数来描述事物的行为。

例如，一个根据姓名向人打招呼的函数

# let say_hi name = print_string ("Hello, " ^ name ^ "!\n") ;;
val say_hi : string -> unit = <fun>

我们可以多次调用此函数，向多个人说“你好”。

#say_hi "Xavier";;
Hello, Xavier!
- : unit = ()

# say_hi "Sabine";;
Hello, Sabine!
- : unit = ()

# say_hi "Joe";;
Hello, Joe!
- : unit = ()

如果我们想多次向同一个人说“你好”，我们只需 *重复* 同一行代码。

# say_hi "Camel";;
Hello, Camel!
- : unit = ()

# say_hi "Camel";;
Hello, Camel!
- : unit = ()

# say_hi "Camel";;
Hello, Camel!
- : unit = ()

避免每次都重复这些行的一种方法是编写一个函数来重复说三次“你好”。

# let say_hi_3_times name =
  say_hi name;
  say_hi name;
  say_hi name
;;
val say_hi_3_times : string -> unit = <fun>

在这个函数中，我们可以看到一些行为

• 它对同一个名字说“你好”。
• 它正好重复了 3 次。

但是，如果我们想说 2 次“你好”会发生什么？或者 4 次或 12 次？

当这种情况发生时，通常意味着函数正在做出某些不应该做出的决策。换句话说，函数 **知道某些东西**（比如次数）。

因此，我们将创建一个函数，让 **调用者决定** 说“你好”多少次。我们通过添加一个新的参数来实现这一点，在本例中为 times

# let rec say_many_hi times name =
  if times < 1 then ()
  else begin
    say_hi name;
    say_many_hi (times - 1) name
  end
;;
val say_many_hi : int -> string -> unit = <fun>

好多了。现在我们可以调用

# say_many_hi 3 "Xavier";;
Hello, Xavier!
Hello, Xavier!
Hello, Xavier!
- : unit = ()

# say_many_hi 12 "Camel";;
Hello, Camel!
Hello, Camel!
Hello, Camel!
Hello, Camel!
Hello, Camel!
Hello, Camel!
Hello, Camel!
Hello, Camel!
Hello, Camel!
Hello, Camel!
Hello, Camel!
Hello, Camel!
- : unit = ()

不幸的是，重用此 *重复* 行为并不容易，因为我们已经硬编码了对 say_hi 的调用。

为了使它可重用，我们可以 **让调用者决定** 我们的函数应该做什么

# let rec repeat times thing_to_do =
  if times < 1 then ()
  else begin
    thing_to_do;
    repeat (times - 1) thing_to_do
  end
;;
val repeat : int -> 'a -> unit = <fun>

但是 thing_to_do 应该是什么？我们的直觉可能是我们可以调用

# repeat 3 (say_hi "Camel");;
Hello, Camel!
- : unit = ()

但我们的程序只输出一个问候语

Hello, Camel!

这不是我们想要的！我们希望它对 Camel 说 3 次“你好”。

在 OCaml 中，参数在函数本身之前进行求值，因此在本例中，我们在到达 repeat 函数之前就说“你好”了。

我们可以让 repeat 多次调用 say_hi，方法是通过用另一个函数将其包装来 *延迟* 函数的执行，如下所示

# repeat 3 (
fun () ->
    say_hi "Camel");;

这意味着我们必须重构 repeat 函数，将 thing_to_do 替换为 thing_to_do ()，以 *调用* 我们的新函数

let rec repeat times thing_to_do =
  if times < 1 then ()
  else (
    thing_to_do ();
    repeat (times - 1) thing_to_do)
;;

将 thing_to_do 重命名为 fn 后，我们得到一个简洁的 repeat 函数

# let rec repeat times fn =
  if times < 1 then ()
  else begin
    fn ();
    repeat (times - 1) fn
  end
;;
val repeat : int -> (unit -> 'a) -> unit = <fun>

我们可以使用 repeat 重新创建我们最初的 say_many_hi，或者任意次数地重复任何工作

# let say_many_hi times name = repeat times (fun () -> say_hi name);;
val say_many_hi : int -> string -> unit = <fun>
  
# let print_big_space () = repeat 10 print_newline;;
val print_big_space : unit -> unit = <fun>

这就是 **高阶函数** 的强大之处。它们使您能够从更简单的函数创建复杂的行为。

以下是一些来自现实世界的其他示例

# let say_hi_to_many names = List.iter say_hi names;;
val say_hi_to_many : string list -> unit = <fun>


# module StringSet = Set.Make(String);;
module StringSet :
  sig
    type elt = string
    type t = StringSet.t
    val empty : t [...]
  end

# let only_once fn names =
  names
  |> StringSet.of_list
  |> StringSet.iter fn;;
val only_once : (string -> unit) -> string list -> unit = <fun>
 
# let yell_hi name =
  name
  |> String.uppercase_ascii
  |> say_hi;;
val yell_hi : string -> unit = <fun>
  
# let call_for_dinner names = only_once yell_hi names;;
val call_for_dinner : string list -> unit = <fun>

常见的高阶函数

在实际应用中，某些模式会一遍又一遍地重复出现。熟悉它们很有用，因为它们是函数式程序员常用词汇的一部分。其中一些是

• 柯里化和反柯里化
• 管道、组合和链式调用
• 迭代
• 过滤
• 映射
• 折叠（或归约）
• 排序
• 绑定（或扁平映射）

柯里化和反柯里化

由于在 OCaml 中所有函数实际上都只接受一个参数，因此当您调用 add x y 时，您实际上是在调用两个函数！((add x) y)

有时，以不同的顺序应用函数的 *部分* 会很有帮助，有时，让函数真正一次性接收所有参数会很有帮助。

这就是我们所说的柯里化和反柯里化

• 一个柯里化的 add 函数将像 add x y 这样调用。
• 一个反柯里化的 add 函数将像 add (x, y) 这样调用。请注意，这实际上只是一个参数！

在我们开始一些示例之前，让我们定义一些辅助函数，它们将帮助我们对函数进行柯里化和反柯里化。

反柯里化

我们的反柯里化辅助函数是一个函数，它接收一个函数作为输入并返回另一个函数。它本质上是一个包装器。

输入函数必须具有类型 'a -> 'b -> 'c。这是任何接收 2 个参数的函数的类型。

输出函数将具有类型 ('a * 'b) -> 'c。注意参数 'a 和 'b 现在是如何打包到一个元组中的！

这是我们的辅助函数

(* [uncurry] takes a function that is normally curried,
   and returns a function that takes all arguments at once. *)
# let uncurry f (x, y) = f x y;;
val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c = <fun>

如果我们想为更多参数编写 uncurry，我们只需创建一个新的 uncurry3 或 uncurry4 甚至 uncurry5 函数，其工作原理完全相同

# let uncurry4 f (w, x, y, z) = f w x y z;;
val uncurry4 : ('a -> 'b -> 'c -> 'd -> 'e) -> 'a * 'b * 'c * 'd -> 'e = <fun>

当您处理列表（我们在 OCaml 中经常这样做）并且列表碰巧包含元组时，反柯里化非常有用。

例如，这个包含姓名和喜欢的表情符号的元组列表

# let people = [
  "🐫", "Sabine";
  "🚀", "Xavier";
  "✨", "Louis";
]
;;

如果我们想对这些元素中的任何一个做些什么，我们需要拆分元组并调用一个函数

# let greet emoji name =
  Printf.printf "Glad to see you like %s, %s!\n" emoji name
;;

let emoji, name = List.hd people in
# greet emoji name
;;

但我们也可以对 greet 函数进行反柯里化，使其作用于整个元组！

# uncurry greet (List.hd people)
;;

柯里化

另一方面，有时我们有已经使用元组工作的函数，并且我们希望像接收多个参数的函数一样使用它们。

为此，我们可以定义一个小的 curry 辅助函数，它将接收一个函数作为输入，并返回另一个函数作为输出。它本质上是一个包装器。

输入函数必须具有类型：('a * 'b) -> 'c - 这是任何接收一个包含 2 个参数的元组的函数的类型。

输出函数将具有类型 'a -> 'b -> 'c - 注意参数 'a 和 'b 现在是如何解包的！

这是我们的辅助函数

(* [curry] takes a function that is normally curried,
   and returns a function that takes all arguments at once. *)
let curry f x y = f (x, y)
;;

如果我们想为更多参数编写curry，我们只需要创建一个新的curry3或curry4甚至curry5函数，它们的工作原理完全相同。

let curry4 f w x y z = f (w, x, y, z)
;;

当你在处理列表（我们在OCaml中经常这样做）并且列表只有一个值，但你的函数需要多个值时，柯里化非常有用。

例如，这是一个姓名列表和一个未柯里化的揭示函数。

let names = [
  "Sabine";
  "Xavier";
  "Louis";
]
;;

let reveal (title, name) =
  Printf.printf "But it was %s, %s!\n" title name
;;

如果我们想在某个姓名上使用reveal，我们必须将其放入一个元组中，然后进行调用。就像这样

List.iter (fun name ->
  let title = "The OCamler" in
  reveal (title, name)) names
;;

但我们也可以将reveal函数柯里化为接受2个参数！

List.iter (curry reveal "The OCamler") names
;;

可读性说明

柯里化和反柯里化都很有趣，直到你的代码变得非常难以阅读。

有时对函数进行柯里化是有意义的，有时更清晰的做法是手动将其包装在一个函数中。

例如，这是一个包含大量柯里化/反柯里化的管道，如果我们手动编写包装函数，它很可能更容易阅读和维护。

let do_and_return f x = f x; x
;;

let flip (x, y) = (y, x)
;;

names 
|> List.map (do_and_return (greet "👋🏼"))
|> List.map (Fun.flip List.assoc (List.map flip people))
|> List.iter (curry reveal "The OCamler")
;;

与一个更易读、更易维护的版本相比

let find_by_name name1 =
  List.find (fun (_emoji, name2) -> name1 = name2) people
;;

(* first iterate over the names, greeting them *)
names |> List.iter (greet "👋🏼")
;;

(* then find the right emoji by name *)
names
|> List.map find_by_name
|> List.iter (fun (emoji, _name) -> reveal ("The OCamler", emoji))
;;

管道、组合和链式调用

在OCaml中，我们经常使用函数，因此值从一个函数传递到另一个函数，形成我们称之为管道的东西。

let a = foo () in
let b = bar a in
let c = baz b in
(* ... *)

当然，我们始终可以以嵌套的方式调用函数，以避免额外的变量和所有这些输入。

let c = baz (bar (foo ())) in
(* ... *)

但有时这并不容易阅读，尤其是在函数数量增加时，因为它是从内到外进行的。

为了避免这种情况，我们使用|>运算符。

let c = foo () |> bar |> baz in 
(* ... *)

此运算符转换为我们手动执行的完全相同的嵌套调用，并且实际上没有任何魔法。它被定义为一个函数。

(* the pipeline operator *)
let (|>) x fn = fn x

它接收一个值x和一个函数fn，一旦它同时拥有这两个值，它就会用x调用fn。这让我们可以反转顺序并构建从左到右或从上到下而不是从内到外读取的管道。

但是当我们的函数有多个参数时会发生什么？

让我们看一个字符串操作的例子。我们想从电子邮件中获取域名。

let email = "[email protected]"
;;

email
|> String.split_on_char '@'
|> Fun.flip List.nth 0
|> Option.map (fun str -> String.sub str 0 5)
|> Option.get
;;

由于OCaml默认对函数进行柯里化，因此可以使用部分应用，只传入一些参数，并将最后一个参数留到管道中传递。

这适用于最重要的参数位于最后一个位置（我们称之为t-last）的函数，以及使用标记参数并允许通过首先传递所有命名参数来将最重要的参数传递到最后的函数（我们通常称之为t-first）。

这两种情况听起来非常相似，但在可用性方面存在很大的实际差异。让我们使用这些函数的标记参数版本重新访问上面的示例。

open StdLabels

module List = struct
  include List
  let nth_opt t ~at = nth_opt at t
end

email
|> String.split_on_char ~sep:'@'
|> List.nth_opt ~at:0
|> Option.map (String.sub ~off:0 ~len:5)
|> Option.value ~default:"new-user"
;;

(** 注意(@leostera)：这个例子有点糟糕，我希望有一个例子，其中标签的使用大大提高了可读性，但由于ListLabels.nth_opt不接受参数，因此我们仍然需要那个讨厌的fun flip :( 会再回来处理这个问题)

迭代

当我们想到循环和遍历事物集合时，我们通常会想到迭代。

• 循环遍历列表中的元素
• 遍历映射中的键

但在OCaml中，迭代模式可以扩展到其他类型的数​​据类型，例如可选值或结果，或者树和惰性序列。

在OCaml中，迭代意味着如果存在一个值（或多个值），我们希望将一个函数应用于它。

遍历列表

OCaml中的列表是一个链表，由表头（第一个元素）和表尾（列表的其余部分）组成。

我们可以通过对列表进行模式匹配来遍历它。在这样做时，我们要么得到一个空列表（[]），要么得到一个带有表头和表尾的模式（n :: rest）。在带有表头和表尾的分支上，我们可以直接使用表头值并将其应用于一个函数，然后使用表尾进行递归。

let rec print_nums nums =
  match nums with
  (* if the list is empty, we do nothing *)
  | [] -> ()
  (* if the list is not empty... *)
  | n :: rest ->
    (* we print the first element *)
    Printf.printf "%d\n" n;
    (* and repeat over the rest of the list *)
    print_nums rest

现在，如果我们想对列表的每个元素执行其他操作，我们可以简单地请求一个将在其上运行的函数。

let rec print_all fn nums =
  match nums with
  | [] -> ()
  | n :: rest ->
    fn n;
    print_all fn rest

这样，我们可以用任何函数fn调用print_all，所以它实际上只是遍历列表并在每个元素上运行一个函数。

这正是标准库中List.iter的定义方式。

遍历可选值和结果

在OCaml中，另一种常见的迭代数据类型是可选值和结果值。通常，我们只希望在选项中包含Some值或存在Ok值时运行函数。如果其中没有值，或者我们有Error，我们不想做任何事情。

我们可以通过对我们的值进行模式匹配并在Some或Ok分支中对内部值调用我们的函数来做到这一点。

let run_if_some opt fn =
  match opt with
  | Some value -> fn value
  | None -> ()
;;
 
let run_if_ok res fn =
  match res with
  | Ok value -> fn value
  | Error _  -> ()
;;

这就是标准库中Option.iter和Result.iter的定义方式。

遍历映射和集合

OCaml中也经常使用映射和集合等更大的数据集合。我们为它们提供了专门的模块，但它们具有函子接口。这意味着你不能直接使用Set或Map，而是必须调用模块级函数Set.Make来创建你自己的自定义版本的Set模块，以用于你想要存储在其中的特定类型。

创建Set或Map模块后，你会发现它们提供了将值转换为列表的函数。

使用这两个函数中的任何一个，我们可以构建一个遍历映射或集合的迭代器。

let iter values collection fn  =
  let values : 'a list = values collection in 
  List.iter fn values
;;
  
module StringSet = Set.Make(String);;
module IntMap = Map.Make(Int);;

let iter_map map fn = iter IntMap.bindings map fn ;;
let iter_set set fn = iter StringSet.elements set fn ;;

你会注意到，这次我们没有使用模式匹配来直接遍历Map或Set的值。这是因为Set和Map的表示是私有的。

映射和集合迭代函数的实际实现确实在幕后使用了模式匹配。

遍历惰性序列

通常，实现某些数据类型的模块将提供遍历它的函数。

但有些数据是惰性的，它一次只允许我们访问一个元素。因此，如果数据看起来像[1,2,3]，则只有在访问第一个和第二个元素后才能计算第三个值。

OCaml中的惰性序列由Seq模块表示，该模块具有一个名为uncons的函数来获取下一个元素。此函数还返回我们可以用来获取第二个元素的新序列，依此类推。

let rec iter seq fn = 
  match Seq.uncons seq with
  | None -> ()
  | Some (value, seq2) -> 
    fn value;
    iter seq2 fn
;;

此函数将尝试获取序列的第一个元素，如果存在，则在其上运行我们的函数fn。然后它将重复遍历从第二个元素开始的新序列（seq2）。

这几乎完全是标准库中Seq.iter的定义方式。

遍历自定义数据类型

到目前为止，我们已经了解了如何遍历标准库中的数据类型。现在我们将了解如何遍历我们自己的树数据类型。

我们将定义我们的树类型以包含2个构造函数。一个用于叶节点，它是树的末端的节点。另一个用于具有子节点的节点。

type 'value tree =
 | Leaf of 'value 
 | Node of 'value tree * 'value
;;

因此，我们的数据类型允许我们表示树状数据。

graph TD
  Node1([Node]) --> ML
  Node1 --> Node2
  Node2([Node]) --> Caml((Caml))
  Node2 --> Node3
  Node3([Node]) --> CamlLight([CamlLight])
  Node3 --> Leaf
  Leaf  --> OCaml

现在，在我们定义迭代函数之前，重要的是要定义迭代对于我们的数据类型意味着什么。我们是否希望从树的底部开始迭代？我们是否希望从顶部开始迭代？我们是否应该从中间开始迭代？

对于我们的示例，我们将从上到下迭代，同时进行。

let rec iter tree fn = 
  match tree with
  | Leaf value -> fn value
  | Node (tree2, value) -> 
      fn value;
      iter tree2 fn
;;

同样，我们通过对值进行模式匹配来进行迭代，将函数应用于解构的值并在剩余数据上进行递归。

映射

与迭代相反，有时我们希望将函数应用于某些数据，并且我们希望保留结果而不更改数据的形状。

例如，如果我们有一个用户列表，也许我们想获取一个用户名列表。或者如果我们有一个可选密码，我们可能希望只在设置密码时对其进行加密。

这称为映射。

映射列表

映射列表与遍历列表非常相似。我们对列表进行模式匹配，获取其表头，在其上运行函数，并对主体进行递归。

主要区别在于，我们不会丢弃在元素上运行函数产生的结果值，而是会从中重建一个列表。

let rec map list fn =
  match list with
  | [] -> []
  | head :: tail -> (fn head) :: (map tail fn)
;;

请注意我们如何使用::构造函数来解构列表和重建列表。

映射选项

只有当我们想在我们的选项内部存在值时更改内容时，映射可选值才有意义。也就是说，如果我们有一个None，则没有要映射的内容，因此我们只能映射Some x值。

let map opt fn =
  match opt with
  | Some value -> Some (fn value)
  | None -> None
;;

请注意，匹配的两侧都返回相同的内容：如果我们有一个None，我们返回None，如果我们有一个Some，我们返回一个Some。这样，结构就被保留了。

映射结果

当我们有结果时，映射变得有点棘手。现在我们有两种可以更改内部值的方式，而且它们都是完全有效的映射！

我们可以映射Ok value构造函数中的值，或者我们可以映射Error reason构造函数中的错误值。

(* maps a result over the ok value *)
let map_ok res fn =
  match res with
  | Ok value -> Ok (fn value)
  | Error reason -> Error reason
;;

(* maps a result over the error value *)
let map_err res fn =
  match res with
  | Ok value -> Ok value
  | Error reason -> Error (fn reason)
;;

这两种方法在不同的情况下都很有用，例如想要更改错误类型，或者只在获得Ok值后执行操作。

映射自定义数据类型

在使用自定义数据类型（例如我们在迭代部分中使用的tree）时，我们应该始终尝试保留数据的结构。也就是说，如果我们对其进行映射，我们会期望相同的节点和节点之间的连接，但其中包含不同的值。

let rec map tree fn =
  match tree with
  | Leaf value -> Leaf (fn value)
  | Node (tree2, value) -> Node (map tree2 fn, fn value)
;;

请注意，树的结构被保留了，但是每次遇到value时，我们都会将其更新为(fn value)。

折叠（或归约）

有时我们希望迭代数据并在遍历每个元素时收集结果。这种行为称为“折叠”或“归约”，它对于数据汇总非常有用。

例如，如果我们有一个从 1 到 10 的数字列表，我们可以通过折叠将它们加起来。

let sum = List.fold_left (+) 0 [1;2;3;4;5;6;7;8;9;10];;

如果我们想在我们之前在迭代章节中看到的自定义树类型上实现求和，我们可以这样做。

type 'value tree =
 | Leaf of 'value 
 | Node of 'value tree * 'value
;;

let rec sum_tree tree =
  match tree with
  | Leaf value -> value
  | Node (tree2, value) -> value + (sum_tree tree2)
;;

如果我们将此泛化以应用于我们的树上的任何转换并将其归约为单个值，则需要将我们的+函数替换为参数fn。

let rec fold_tree tree fn =
  match tree with
  | Leaf value -> fn value
  | Node (tree2, value) -> fn value (fold_tree tree2 fn)
;;

但我们很快就会遇到一个问题：我们的fn函数旨在组合两个项目，所以在Leaf分支中，第二个项目是什么？

折叠要求我们定义一个零值，即累加器的起点，当集合或数据类型“为空”时将使用它。

某些数据类型没有合适的“空”值。例如，我们的树就没有。列表有空列表。选项有一个None构造函数。结果也没有合适的“空”值。

因此，要修复我们的fold_tree，我们只需要传入一个零值或累加器值。

let rec fold_tree tree fn acc =
  match tree with
  | Leaf value -> fn value acc
  | Node (tree2, value) -> fn value (fold_tree tree2 fn acc)
;;

瞧！我们的函数现在类型正确，我们可以用它将我们的树归约为任何值。

排序

另一种通常使用高阶函数实现的常见行为是对集合进行排序。

Array.sort和List.sort都实现了这样的接口：如果你传入一个知道如何比较两个元素的函数，它们将调整排序以使用此比较。

对于数组，此操作会就地修改数组。

let array = [| 4;9;1;10 |];;

(* sorts the array in ascending order *)
Array.sort (fun a b -> a - b) array;;

(* sorts the array in descending order *)
Array.sort (fun a b -> b - a) array;;

对于列表，此操作会返回一个新的已排序列表。

let list = [4;9;1;10] ;;
let asc = List.sort (fun a b -> a - b) list ;;
let desc = List.sort (fun a b -> b - a) list ;;

大多数 OCaml 模块都包含一个compare函数，可以将其传递给sort。

let int_array = [|3;0;100|];;
Array.sort Int.compare int_array;;

List.sort String.compare ["z";"b";"a"];;

List.sort Bool.compare [true;false;false];;

绑定

函数式编程中最后一个常见的高阶模式是从内部连接数据的能力。由于历史原因，这通常称为绑定。

例如，如果我们有一个列表，并使用返回列表的函数对其进行映射，那么我们将得到一个列表的列表。有时我们想要这样，但有时我们宁愿新列表被展平而不是嵌套。

要使用列表执行此操作，我们可以使用concat_map函数，它看起来像这样。

let twice x = [x;x];;
let double ls = List.concat_map twice ls;;

double [1;2;3];; (* [1;1;2;2;3;3] *)

绑定作为提前返回

此相同的模式可用于构建短路特定值的函数链。

例如，如果您必须从数据库中检索用户，并且只有在存在用户时才尝试访问用户的电子邮件，您可以使用Option.bind对第一个操作进行短路。

type user = {
    email: string option
}

let get_user () = None ;;
let get_email user = user.email ;;

let email = Option.bind (get_user ()) get_email ;;

在此示例中，因为我们的get_user ()调用返回 None，所以永远不会调用get_email。只有当get_user返回Some user时，才会调用get_email。

这也适用于结果值。

type user = {
    email: string
}

let get_user () = Error `no_database ;;
let get_email user = Ok user.email ;;

let email = Result.bind (get_user ()) get_email ;;

主要区别在于，在这种情况下，Result.bind偏向于Ok value，因此，如果结果值为Error reason，它将通过绑定进行短路，并只返回出现的第一个错误。

Let-ops

不幸的是，调用Result.bind可能有点笨拙。我们无法像对map的调用那样将我们的值通过一系列绑定传递。例如，这不是有效的。

let email = get_user ()
           |> Result.bind get_email
           |> Result.bind extract_domain
           |> Result.bind validate_domain
           ;;

值得庆幸的是，OCaml 允许我们重新定义一组称为let-operators的操作符，这些操作符可用于简化bind调用的使用，使其看起来非常接近正常的let绑定。

(* first we will declare out let* operator to be equal to Result.bind *)
let (let*) = Result.bind

let* user = get_user () in
let* email = get_email user in
let* domain = extract_domain email in
validate_domain domain

这具有使代码更易读的优点，而不会改变我们对绑定调用的期望行为。

异步代码

实现 Promise/Future 的 OCaml 异步库通常也具有一个bind函数，允许您链接计算。