函式子

先決條件

模組

簡介

在本教學中，我們將探討如何應用函式子以及如何編寫函式子。我們還將展示一些涉及函式子的使用案例。

顧名思義，函式子幾乎就像一個函數。然而，函數是在值之間運作，而函式子則是在模組之間運作。函式子以模組作為參數，並回傳一個模組作為結果。OCaml 中的函式子是一個參數化的模組，不要與數學中的函式子混淆。

注意：本教學的範例檔案可作為Git 儲存庫取得。

專案設定

本教學使用 Dune 建置工具。請確保您已安裝 3.7 或更新版本。我們首先建立一個新的專案。我們需要一個名為 funkt 的目錄，其中包含檔案 dune-project、dune 和 funkt.ml。

$ mkdir funkt; cd funkt

將以下內容放置在 dune-project 檔案中

(lang dune 3.7)
(package (name funkt))

檔案 dune 的內容應該是這樣

(executable
  (name funkt)
  (public_name funkt)
  (libraries str))

建立一個空的檔案 funkt.ml。

使用 opam exec -- dune exec funkt 命令檢查這是否有效。它不應該執行任何操作（空檔案是有效的 OCaml 語法），但也不應該失敗。程式碼片段 libraries str 使 Str 模組（我們稍後將使用）可用。

使用現有的函式子：`Set.Make`

標準函式庫包含一個 Set 模組，旨在處理集合。此模組使您能夠對集合執行聯集、交集和差集等操作。您可以查看集合教學以瞭解有關此模組的更多資訊，但不需要學習本教學。

要為給定的元素類型建立一個集合模組（允許您使用提供的類型及其相關的函數），必須使用 Set 模組提供的函式子 Set.Make。以下是 Set 介面的簡化版本

module type OrderedType = sig
  type t
  val compare : t -> t -> int
end

module Make : functor (Ord : OrderedType) -> Set.S

以下說明如何解讀（從底部開始，然後往上）

像函數一樣（由箭頭 -> 指示），函式子 Set.Make
- 接受一個具有簽名 OrderedType 的模組，並且
- 回傳一個具有簽名 Set.S 的模組
模組類型 OrderedType 需要一個類型 t 和一個函數 compare，它們用於執行集合元素之間的比較。

注意：大多數集合操作需要比較元素以檢查它們是否相同。為了允許使用使用者定義的比較演算法，Set.Make 函式子接受一個模組，該模組指定元素類型 t 和 compare 函數。例如，將比較函數作為高階參數傳遞（如在 Array.sort 中所做的那樣）會增加大量的樣板程式碼。將集合操作作為函式子提供，可以只指定一次比較函數。

以下是如何使用 Set.Make 的範例

funkt.ml

module StringCompare = struct
  type t = string
  let compare = String.compare
end

module StringSet = Set.Make(StringCompare)

這定義了一個模組 Funkt.StringSet。Set.Make 需要的是

類型 t，這裡為 string
允許比較類型為 t 的兩個值的函數，這裡為 String.compare

注意：類型 t 必須在參數模組中定義，此處為 StringCompare。最常見的是，如本範例所示，t 是另一個類型（此處為 string）的別名。如果另一個類型也稱為 t，則編譯器將觸發錯誤「類型縮寫 t 是循環的」。這可以透過將 nonrec 關鍵字新增至類型定義來解決，如下所示

type nonrec t = t

這可以使用匿名模組表達式來簡化

module StringSet = Set.Make(struct
  type t = string
  let compare = String.compare
end)

模組表達式 struct ... end 會內嵌在 Set.Make 呼叫中。

然而，由於模組 String 已經定義了

類型名稱 t，它是 string 的別名
類型為 t -> t -> bool 的函數 compare 會比較兩個字串

這可以進一步簡化為

module StringSet = Set.Make(String)

在所有版本中，函式子應用程式 Set.Make 產生的模組都會繫結到名稱 StringSet，並且具有簽名 Set.S。模組 StringSet 提供對字串集合的操作。函數 String.compare 由 StringSet 在內部使用。

當您執行 opam exec -- dune exec funkt 時，它不會執行任何操作，但也不應該失敗。

讓我們在 funkt.ml 中新增一些程式碼，使其執行一些操作。

funkt.ml

module StringSet = Set.Make(String)

let _ =
  In_channel.input_lines stdin
  |> List.concat_map Str.(split (regexp "[ \t.,;:()]+"))
  |> StringSet.of_list
  |> StringSet.iter print_endline

以下說明此程式碼的工作方式

In_channel.input_lines：從標準輸入讀取文字行
List.concat_map：將行拆分為單字並產生單字列表
StringSet.of_list : string list -> StringSet.t：將單字列表轉換為集合
StringSet.iter : StringSet.t -> unit：顯示集合的元素

函數 StringSet.of_list 和 StringSet.iter 在函子應用結果中可用。

$ opam exec -- dune exec funkt < dune
executable
libraries
name
public_name
str
funkt

在 Set 中沒有重複的元素。因此，字串 "funkt" 只會顯示一次，儘管它在 dune 檔案中出現了兩次。

使用標準函式庫函子擴展模組

使用 include 陳述式，以下是另一種暴露 Set.Make(String) 所建立模組的方式

funkt.ml

module String = struct
  include String
  module Set = Set.Make(String)
end

let _ =
  stdin
  |> In_channel.input_lines
  |> List.concat_map Str.(split (regexp "[ \t.,;:()]+"))
  |> String.Set.of_list
  |> String.Set.iter print_endline

這允許使用者看似使用一個子模組 Set 擴展模組 String。使用 opam exec -- dune exec funkt < dune 檢查其行為。

使用函子參數化模組

來自標準函式庫的函子

函子幾乎是一個模組，只是它需要應用於一個模組。這會將其轉換為模組。從這個意義上來說，函子允許模組參數化。

標準函式庫提供的集合、映射和雜湊表就是這種情況。它的運作方式就像函子與開發者之間的契約。

如果您提供一個實作預期功能的模組，如參數介面所述
函子會回傳一個實作承諾功能的模組，如結果介面所述

以下是函子 Set.Make 和 Map.Make 期望的模組簽章

module type OrderedType = sig
  type t
  val compare : t -> t -> int
end

以下是函子 Hashtbl.Make 期望的模組簽章

module type HashedType = sig
  type t
  val equal : t -> t -> bool
  val hash : t -> int
end

函子 Set.Make、Map.Make 和 Hashtbl.Make 會回傳滿足介面 Set.S、Map.S 和 Hashtbl.S（分別）的模組，這些模組都包含一個抽象類型 t 和相關聯的函數。請參閱文件以瞭解它們提供的詳細資訊

撰寫您自己的函子

撰寫函子的原因之一是提供參數化的資料結構。這與其他資料結構上的 Set 和 Map 相同。在本節中，我們以堆積作為範例。

有許多種類的堆積資料結構。範例包括二元堆積、左傾堆積、二項式堆積或費波那契堆積。

本文件不討論用於實作堆積的資料結構和演算法種類。

實作任何堆積的常見先決條件是一種比較它們所包含元素的方法。這與 Set.Make 和 Map.Make 的參數簽章相同

module type OrderedType = sig
  type t
  val compare : t -> t -> int
end

使用這樣的參數，堆積實作至少必須提供這個介面

module type HeapType = sig
  type elt
  type t
  val empty : t
  val is_empty : t -> bool
  val insert : t -> elt -> t
  val merge : t -> t -> t
  val find : t -> elt
  val delete : t -> t
end

堆積實作可以表示為從 OrderedType 到 HeapType 的函子。每一種堆積都會是一個不同的函子。

以下是可能實作的骨架

heap.ml

module type OrderedType = sig
  type t
  val compare : t -> t -> int
end

module type S = sig
  type elt
  type t
  val empty : t
  val is_empty : t -> bool
  val insert : t -> elt -> t
  val merge : t -> t -> t
  val find : t -> elt
  val delete : t -> t
end

module Binary(Elt: OrderedType) : S = struct
  type elt (* Add your own type definition *)
  type t (* Add your own type definition *)
  (* Add private functions here *)
  let empty = failwith "Not yet implemented"
  let is_empty h = failwith "Not yet implemented"
  let insert h e = failwith "Not yet implemented"
  let merge h1 h2 = failwith "Not yet implemented"
  let find h = failwith "Not yet implemented"
  let delete h = failwith "Not yet implemented"
end

在這裡，只建議使用二元堆積實作。這可以透過為每一個新增一個函子來擴展到其他實作，例如 Heap.Leftist、Heap.Binomial、Heap.Fibonacci 等。

使用函子注入相依性

模組之間的相依性

以下是 funkt 程式的新版本

funkt.ml

module StringSet = Set.Make(String)

module IterPrint : sig
  val f : string list -> unit
end = struct
  let f = List.iter (fun s -> Out_channel.output_string stdout (s ^ "\n"))
end

let _ =
  stdin
  |> In_channel.input_lines
  |> List.concat_map Str.(split (regexp "[ \t.,;:()]+"))
  |> StringSet.of_list
  |> StringSet.elements
  |> IterPrint.f

它嵌入了一個額外的 IterPrint 模組，該模組公開了一個類型為 string list -> unit 的單一函數 f，並且有兩個相依性

透過 List.iter 和 f 的類型使用模組 List
透過 Out_channel.output_string 使用模組 Out_channel

使用 opam exec -- dune exec funkt < dune 檢查程式的行為。

相依性注入

相依性注入是一種針對相依性進行參數化的方法。

以下是模組 IterPrint 的重構，以使用此技術

iterPrint.ml

module type Iterable = sig
  type 'a t
  val iter : ('a -> unit) -> 'a t -> unit
end

module type S = sig
  type 'a t
  val f : string t -> unit
end

module Make(Dep: Iterable) : S with type 'a t := 'a Dep.t = struct
  let f = Dep.iter (fun s -> Out_channel.output_string stdout (s ^ "\n"))
end

模組 IterPrint 被重構為一個函子，它會將提供函數 iter 的模組作為參數。with type 'a t := 'a Dep.t 約束表示參數 Dep 中的類型 t 會取代結果模組中的類型 t。這允許 f 的類型使用 Dep 的 t 類型。透過此重構，IterPrint 只有一個相依性。在其編譯時，函數 iter 的實作尚不可用。

注意：OCaml 介面檔案 (.mli) 必須是模組，而不是函子。函子必須嵌入在模組中。因此，習慣上將它們稱為 Make。

funkt.ml

module StringSet = Set.Make(String)
module IterPrint = IterPrint.Make(List)

let _ =
  stdin
  |> In_channel.input_lines
  |> List.concat_map Str.(split (regexp "[ \t.,;:()]+"))
  |> StringSet.of_list
  |> StringSet.elements
  |> IterPrint.f

當編譯模組 Funkt 時，相依性 List 會被注入。請注意，使用 IterPrint 的程式碼沒有變更。使用 opam exec -- dune exec funkt < dune 檢查程式的行為。

取代相依性

現在，取代 IterListPrint 內部的 iter 實作不再是重構；而是使用另一個相依性的另一個函子應用。在這裡，Array 取代了 List

funkt.ml

module StringSet = Set.Make(String)
module IterPrint = IterPrint.Make(Array)

let _ =
  stdin
  |> In_channel.input_lines
  |> List.concat_map Str.(split (regexp "[ \t.,;:()]+"))
  |> StringSet.of_list
  |> StringSet.elements
  |> Array.of_list
  |> IterPrint.f

使用 opam exec -- dune exec funkt < dune 檢查程式的行為。

注意：IterPrint.Make 接收和回傳的模組都有一個類型 t。with type ... := ... 約束表示這兩個類型 t 相同。這使得注入相依性和結果模組中的函數使用完全相同的類型。當結果模組不公開參數的包含類型時（即當它是實作細節時），不需要 with type 約束。

命名和範圍界定

with type 約束會統一函子參數和結果模組中的類型。我們在上一節中使用過它。本節說明此約束的命名和範圍界定機制。

粗略地說，我們可能會將 Iter.Make 定義如下

module Make(Dep: Iterable) : S = struct
  type 'a t = 'a Dep.t
  let f = Dep.iter (fun s -> Out_channel.output_string stdout (s ^ "\n"))
end

如果未使用函數 f，專案將會在沒有錯誤的情況下編譯。

但是，由於在 funkt.ml 中會呼叫 Make 來建立模組 IterPrint，因此專案會編譯失敗，並顯示以下錯誤訊息

5 | ..stdin
6 |   |> In_channel.input_lines
7 |   |> List.concat_map Str.(split (regexp "[ \t.,;:()]+"))
8 |   |> StringSet.of_list
9 |   |> StringSet.elements
Error: This expression has type string list
       but an expression was expected of type string IterPrint.t

在函子外部，不知道 type 'a t 設定為 Dep.t。在 funkt.ml 中，IterPrint.t 會顯示為 Make 結果公開的抽象類型。這就是為什麼需要 with type 約束的原因。它會傳播 IterPrint.t 與 Dep.t（在此情況下為 List.t）類型相同的資訊。

使用 with type 約束的類型不會被函子主體內的定義所遮蔽。在此範例中，可以將 Make 函子重新定義如下

module Make(Dep: Iterable) : S with type 'a t := 'a Dep.t = struct
  type 'a t = LocalType
  let g LocalType = "LocalType"
  let f = Dep.iter(fun s ->
    Out_channel.output_string stdout (g LocalType ^ "\n");
    Out_channel.output_string stdout (s ^ "\n"))
end

在上述範例中，with type 中的 t 會優先於只有本機範圍的本機 t。不要太常遮蔽名稱，因為這會讓程式碼更難以理解。

撰寫函子來擴展模組

在本節中，我們定義一個函子，以相同的方式擴展數個模組。這與使用標準函式庫函子擴展模組中的概念相同，只是我們自行撰寫函子。

在這個範例中，我們使用函數 scan_left 擴展了 List 和 Array 模組。它的功能幾乎與 fold_left 相同，只是它會傳回所有中間值，而不是像 fold_left 那樣傳回最後一個值。

建立一個包含以下檔案的全新目錄

dune-project

(lang dune 3.7)

dune

(library (name scanLeft))

scanLeft.ml

module type LeftFoldable = sig
  type 'a t
  val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b
  val of_list : 'a list -> 'a t
end

module type S = sig
  type 'a t
  val scan_left : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t
end

module Make(F: LeftFoldable) : S with type 'a t := 'a F.t = struct
  let scan_left f b u =
    let f (b, u) a =
      let b' = f b a in
      (b', b' :: u) in
    u |> F.fold_left f (b, []) |> snd |> List.rev |> F.of_list
end

執行 dune utop 命令。進入 toplevel 後，輸入以下命令。

# module Array = struct
    include Stdlib.Array
    include ScanLeft.Make(Stdlib.Array)
  end;;

# module List = struct
    include List
    include ScanLeft.Make(struct
      include List
      let of_list = Fun.id
    end)
  end;;

# Array.init 10 Fun.id |> Array.scan_left ( + ) 0;;
- : int array = [|0; 1; 3; 6; 10; 15; 21; 28; 36; 45|]

# List.init 10 Fun.id |> List.scan_left ( + ) 0;;
- : int list = [0; 1; 3; 6; 10; 15; 21; 28; 36; 45]

模組 Array 和 List 會顯示已使用 Array.scan_left 和 List.scan_left 增強。為了簡潔起見，這裡不會顯示前兩個 toplevel 命令的輸出。

具狀態模組的初始化

模組可以保留狀態。函子可以提供初始化具狀態模組的方法。例如，以下是以狀態處理隨機數產生種子的可能方式

random.ml

module type SeedType : sig
  val v : int array
end

module type S : sig
  val reset_state : unit -> unit

  val bits : unit -> int
  val bits32 : unit -> int32
  val bits64 : unit -> int64
  val nativebits : unit -> nativeint
  val int : int -> int
  val int32 : int32 -> int32
  val int64 : int64 -> int64
  val nativeint : nativeint -> nativeint
  val full_int : int -> int
  val float : float -> float
  val bool : unit -> bool
end

module Make(Seed: SeedType) : S = struct
  let state = Seed.v |> Random.State.make |> ref
  let reset_state () = state := Random.State.make Seed.v

  let bits () = Random.State.bits !state
  let bits32 () = Random.State.bits32 !state
  let bits64 () = Random.State.bits64 !state
  let nativebits () = Random.State.nativebits !state
  let int = Random.State.int !state
  let int32 = Random.State.int32 !state
  let int64 = Random.State.int64 !state
  let nativeint = Random.State.nativeint !state
  let full_int = Random.State.full_int !state
  let float = Random.State.float !state
  let bool () = Random.State.bool !state
end

建立此檔案並啟動 utop。

# #mod_use "random.ml";;

# module R1 = Random.Make(struct let v = [|0; 1; 2; 3|] end);;

# module R2 = Random.Make(struct let v = [|0; 1; 2; 3|] end);;

# R1.bits ();;
- : int = 75783189

# R2.bits ();;
- : int = 75783189

# R1.bits ();;
- : int = 774473149

# R1.reset_state ();;
- : unit = ()

# R2.bits ();;
- : int = 774473149

# R1.bits ();;
- : int = 75783189

使用相同的狀態建立模組 R1 和 R2；因此，第一次呼叫 R1.bits 和 R2.bits 會傳回相同的值。

第二次呼叫 R1.bits 會將 R1 的狀態移動一步，並傳回對應的位元。呼叫 R1.reset_state 會將 R1 的狀態設定為其初始值。

第二次呼叫 R2.bits 會顯示模組沒有共用狀態。否則，會傳回第一次呼叫 bits 的值。

第三次呼叫 R1.bits 會傳回與第一次呼叫相同的結果，這證明狀態確實已重設。

結論

函子應用程式本質上與函數應用程式的運作方式相同：傳遞參數並取得結果。不同之處在於，我們傳遞的是模組而不是值。除了舒適性之外，它還能實現一種設計方法，其中關注點不僅在於孤島中分離，這是模組實現的，而且還在於彼此堆疊的階段中分離。

仍然需要協助嗎？

詢問 OCaml 社群

開啟問題

協助改進我們的文件

所有 OCaml 文件都是開放原始碼。發現錯誤或不清楚的地方嗎？提交提取要求。

貢獻

函式子

先決條件

簡介

專案設定

使用現有的函式子：Set.Make

使用標準函式庫函子擴展模組

使用函子參數化模組

來自標準函式庫的函子

撰寫您自己的函子

使用函子注入相依性

命名和範圍界定

撰寫函子來擴展模組

具狀態模組的初始化

結論

仍然需要協助嗎？

協助改進我們的文件

使用現有的函式子：`Set.Make`