迴圈與遞迴

如同其他 OCaml.org 文件，程式碼範例將會是您可以測試的東西，或是程式碼的範例。以 CLI 提示符號 # 開頭、以 ;; 結尾，且有明確輸出的程式碼片段，可以在 OCaml 頂層 (ocaml 或 utop) 中測試，或貼到 OCaml 遊樂場。如果程式碼不是以 # 開頭，且沒有以 ;; 結尾，則它是如何撰寫程式碼的範例。

For 迴圈與 While 迴圈

OCaml 支援相當有限的熟悉 for 迴圈形式

for variable = start_value to end_value do
  expression
done

for variable = start_value downto end_value do
  expression
done

一個來自 LablGtk 的簡單但真實的範例

for i = 1 to n_jobs () do
  do_next_job ()
done

在 OCaml 中，for 迴圈只是撰寫的簡寫

let i = 1 in
do_next_job ();
let i = 2 in
do_next_job ();
let i = 3 in
do_next_job ();
  ...
let i = n_jobs () in
do_next_job ();
()

OCaml 不支援提前跳出 for 迴圈的概念，也就是說，它沒有 break、continue 或 last 陳述式。（您可以拋出例外並在外部捕獲它，這樣會執行得很快，但通常看起來很笨拙。）

OCaml for 迴圈內的表達式應求值為 unit (否則您會收到警告)，而整個 for 迴圈表達式會返回 unit

# for i = 1 to 10 do i done;;
Line 1, characters 20-21:
Warning 10 [non-unit-statement]: this expression should have type unit.
- : unit = ()

函數式程式設計師傾向於使用遞迴而不是明確的迴圈，而且明智的做法是對 for 迴圈抱持懷疑，因為它無法返回任何值，因此 OCaml 的 for 迴圈相對無力。我們將在下面討論遞迴。

OCaml 中的 While 迴圈 寫成

while boolean-condition do
  expression
done

與 for 迴圈一樣，該語言沒有提供跳出 while 迴圈的方法，除非拋出例外，因此這意味著 while 迴圈的用途相當有限。再次提醒，函數式程式設計師喜歡遞迴，因此 while 迴圈在 OCaml 中是次等公民。

如果您停下來考慮 while 迴圈，您可能會發現它們根本沒有任何用處，除非與我們老朋友參考結合使用。讓我們想像一下 OCaml 暫時沒有參考

let quit_loop = false in
  while not quit_loop do
    print_string "Have you had enough yet? (y/n) ";
    let str = read_line () in
      if str.[0] = 'y' then
        (* how do I set quit_loop to true ?!? *)
  done

請記住，quit_loop 不是真正的「變數」。let 綁定只是讓 quit_loop 成為 false 的簡寫。這表示 while 迴圈條件 (以紅色顯示) 始終為 true，並且迴圈會永遠執行下去！

幸運的是，OCaml 確實有參考，因此如果我們想的話，我們可以撰寫上面的程式碼。不要混淆並認為 ! (驚嘆號) 的意思是「非」，如在 C/Java 中。它在這裡的意思是「取消參考指標」，實際上與 Forth 類似。您最好將 ! 讀作「取得」或「deref」。

let quit_loop = ref false in
  while not !quit_loop do
    print_string "Have you had enough yet? (y/n) ";
    let str = read_line () in
      if str.[0] = 'y' then quit_loop := true
  done;;

對列表進行迴圈

如果您想對列表進行迴圈，請不要成為命令式程式設計師，並伸手去拿您值得信賴的六發左輪 For 迴圈！OCaml 有一些更好、更快速的方法來對列表進行迴圈，它們都位於 List 模組中。事實上，List 中有數十個好用的函式，但我這裡只會討論最實用的函式。

首先，讓我們定義一個列表供我們使用

# let my_list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10];;
val my_list : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

如果您想對列表的每個元素呼叫一次函數，請使用 List.iter，如下所示

# let f elem =
    Printf.printf "I'm looking at element %d now\n" elem
  in
    List.iter f my_list;;
I'm looking at element 1 now
I'm looking at element 2 now
I'm looking at element 3 now
I'm looking at element 4 now
I'm looking at element 5 now
I'm looking at element 6 now
I'm looking at element 7 now
I'm looking at element 8 now
I'm looking at element 9 now
I'm looking at element 10 now
- : unit = ()

事實上，List.iter 是您每次小腦建議您使用 for 迴圈時，應該首先考慮使用的東西。

如果您想在列表中轉換每個元素 - 例如，將列表中的每個元素加倍 - 請使用 List.map。

# List.map (( * ) 2) my_list;;
- : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

函式 List.filter 只會收集滿足某些條件的列表元素，例如，返回列表中所有偶數。

# let is_even i =
    i mod 2 = 0
  in
    List.filter is_even my_list;;
- : int list = [2; 4; 6; 8; 10]

若要找出列表是否包含某些元素，請使用 List.mem (成員的簡寫)

# List.mem 12 my_list;;
- : bool = false

List.for_all 和 List.exists 與謂詞邏輯中的「forall」和「exist」運算子相同。

若要同時在兩個列表上運作，這些函數的其中一些具有 "-2" 變體，即 iter2、map2、for_all2、exists2。

map 和 filter 函數會隔離地對個別列表元素進行運算。Fold 是一種較不尋常的運算，最好將其視為「在列表的每個元素之間插入運算子」。假設我想將我的列表中的所有數字加總在一起。用手揮舞的方式來說，我想要在我的列表中的元素之間插入一個加號 (+)

# 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10;;
- : int = 55

摺疊 (fold) 運算就是做這個，雖然確切的細節稍微複雜一點。首先，如果我嘗試對一個空列表求和，答案最好是零，而不是錯誤。但是，如果我嘗試找出列表的乘積，答案最好是 1。所以有必要為摺疊提供某種「預設」引數。第二個問題不會發生在像 + 和 * 這樣的簡單運算符上：如果使用的運算符不符合結合律，也就是說，(a op b) op c 不等於 a op (b op c)，會發生什麼事？在這種情況下，如果我從列表的左端開始向右工作，和如果我從右端開始向左工作，就會有所不同。因此，摺疊有兩個版本，分別稱為 List.fold_left（從左到右工作）和 List.fold_right（從右到左工作，效率也較低）。

讓我們使用 List.fold_left 來為整數列表定義 sum 和 product 函式

# let sum = List.fold_left ( + ) 0;;
val sum : int list -> int = <fun>
# let product = List.fold_left ( * ) 1;;
val product : int list -> int = <fun>
# sum my_list;;
- : int = 55
# product my_list;;
- : int = 3628800

這很簡單！請注意，我不小心想出了一種計算數學階乘的方法

# let fact n = product (range 1 n);;
val fact : int -> int = <fun>
# fact 10;;
- : int = 3628800

（請注意，這個階乘函式不是很實用，因為它會使整數溢位，即使是很小的 n 值也會給出錯誤的答案。）

字串迴圈

String 模組還包含許多有用的字串相關函式，其中一些與字串迴圈有關。

String.copy 複製一個字串，就像 strdup 一樣。還有一個 String.iter 函式，它的作用類似於 List.iter，但作用於字串的字元。

遞迴

現在我們來到了一個難題：遞迴。函數式程式設計師的定義就是他們對遞迴函式的熱愛，而且在許多方面，函數式程式設計中的遞迴函式相當於命令式程式設計中的迴圈。在函數式語言中，迴圈是二等公民，而遞迴函式則獲得最好的支援。

編寫遞迴函式需要改變編寫 for 迴圈和 while 迴圈的思維模式，所以本節只是一個介紹和幾個範例。

在第一個範例中，我們會將整個檔案讀取到記憶體中（放入一個長字串）。基本上有三種可能的方法可以做到這一點

方法 1

取得檔案的長度，然後使用 really_input 方法一次讀取所有內容。這是最簡單的方法，但它可能無法在不是真正的檔案的通道上運作（例如，讀取鍵盤輸入），這就是為什麼我們有另外兩種方法的原因。

方法 2

命令式方法使用一個 while 迴圈，該迴圈使用例外狀況來跳出。

方法 3

遞迴迴圈再次使用例外狀況來跳出遞迴。

我們將在這裡介紹一些新概念。我們的第二種和第三種方法將使用 Buffer 模組，這是一個可擴充的緩衝區。把它想像成一個字串，你可以有效地在末尾附加更多文字。我們也將捕獲 End_of_file 例外狀況，當輸入函式到達輸入末尾時，它們會拋出此例外狀況。最後，我們將使用 Sys.argv.(1) 來取得第一個命令列參數。

(* Read whole file: Approach 1 *)
open Printf

let read_whole_chan chan =
  let len = in_channel_length chan in
  let result = (Bytes.create len) in
    really_input chan result 0 len;
    (Bytes.to_string result)

let read_whole_file filename =
  let chan = open_in filename in
    read_whole_chan chan

let main () =
  let filename = Sys.argv.(1) in
  let str = read_whole_file filename in
    printf "I read %d characters from %s\n" (String.length str) filename

方法 1 可以運作，但它不是很令人滿意，因為 read_whole_chan 無法在非檔案通道（如鍵盤輸入或通訊端）上運作。方法 2 涉及一個 while 迴圈

(* Read whole file: Approach 2 *)
open Printf

let read_whole_chan chan =
  let buf = Buffer.create 4096 in
  try
    while true do
      let line = input_line chan in
        Buffer.add_string buf line;
        Buffer.add_char buf '\n'
    done;
    assert false (* This is never executed
	                (always raises Assert_failure). *)
  with
    End_of_file -> Buffer.contents buf

let read_whole_file filename =
  let chan = open_in filename in
    read_whole_chan chan

let main () =
  let filename = Sys.argv.(1) in
  let str = read_whole_file filename in
    printf "I read %d characters from %s\n" (String.length str) filename

方法 2 的關鍵是查看中心的 while 迴圈。請記住，提前跳出 while 迴圈的唯一方法是使用例外狀況，這正是我們在這裡所做的事情。雖然我還沒有介紹例外狀況，但您可能不會難以理解當 input_line 在到達檔案末尾時拋出的 End_of_file 例外狀況。緩衝區 buf 會累積檔案內容，當我們到達檔案末尾時，我們會傳回它（Buffer.contents buf）。

關於這一點，一個奇怪的地方是 while 迴圈之後明顯多餘的陳述式 (assert false)。它是為了什麼？請記住，while 迴圈和 for 迴圈一樣，只是運算式，它們會傳回 unit 物件 (())。但是，OCaml 要求 try 內部的傳回型別與每個捕獲的例外狀況的傳回型別相符。在這種情況下，由於 End_of_file 會產生一個 string，因此 try 的主體也必須「傳回」一個字串（由於無限的 while 迴圈，實際上永遠不會傳回該字串）。assert false 具有多型型別，因此它會與 with 分支傳回的任何值統一。

這是遞迴版本。請注意，它比方法 2 更短，但至少對於命令式程式設計師來說，它不太容易理解

(* Read whole file: Approach 3 *)
open Printf

let read_whole_chan chan =
  let buf = Buffer.create 4096 in
  let rec loop () =
    let line = input_line chan in
      Buffer.add_string buf line;
      Buffer.add_char buf '\n';
      loop ()
  in
    try loop () with
      End_of_file -> Buffer.contents buf

let read_whole_file filename =
  let chan = open_in filename in
    read_whole_chan chan

let main () =
  let filename = Sys.argv.(1) in
  let str = read_whole_file filename in
  printf "I read %d characters from %s\n" (String.length str) filename

我們再次有一個無限迴圈，但在這種情況下，它是使用遞迴來完成的。loop 會在函式末尾呼叫自己。當 input_line 拋出 End_of_file 例外狀況時，無限遞迴會被中斷。

看起來如果你給它一個特別大的檔案，方法 3 可能會導致堆疊溢位，但事實並非如此！由於尾部遞迴（如下所述），編譯器會將遞迴的 loop 函式轉換為真正的 while 迴圈 (!)，該迴圈會在固定的堆疊空間中執行。

在下一個範例中，我們將展示遞迴如何非常適合建構或檢查某些型別的資料結構，尤其是樹狀結構。讓我們使用遞迴型別來表示檔案系統中的檔案

# type filesystem = File of string | Directory of filesystem list;;
type filesystem = File of string | Directory of filesystem list

opendir 和 readdir 函式用於開啟目錄並從目錄中讀取元素。我將定義一個方便的 readdir_no_ex 函式，該函式會隱藏 readdir 在到達目錄末尾時拋出的惱人 End_of_file 例外狀況

# #load "unix.cma";;
# open Unix;;
# let readdir_no_ex dirh =
  try
    Some (readdir dirh)
  with
    End_of_file -> None;;
val readdir_no_ex : dir_handle -> string option = <fun>

readdir_no_ex 的型別是這樣。回想一下我們之前關於空指標的討論。

# readdir_no_ex;;
- : dir_handle -> string option = <fun>

我還將定義一個簡單的遞迴函式，可以用於將 filesystem 型別轉換為字串以供（例如）列印

# let rec string_of_filesystem fs =
  match fs with
  | File filename -> filename ^ "\n"
  | Directory fs_list ->
      List.fold_left (^) "" (List.map string_of_filesystem fs_list);;
val string_of_filesystem : filesystem -> string = <fun>

請注意 fold_left 和 map 的使用。map 用於將列表中的每個 filesystem（遞迴地）轉換為 string。然後，fold_left (^) "" 將列表連接成一個大的字串。另請注意模式比對的使用。（函式庫定義了一個名為 String.concat 的函式，它基本上等效於 fold_left (^)，但實作效率更高）。

現在讓我們定義一個函式，以遞迴方式讀取目錄結構，並傳回遞迴的 filesystem 資料結構。我將逐步展示這個函式，但本節結尾將印出整個函式。首先是函式的綱要

let rec read_directory path =
  let dirh = opendir path in
  let rec loop () =
    (* ..... *) in
  Directory (loop ())

呼叫 opendir 會開啟給定的路徑，並傳回一個 dir_handle，我們稍後可以使用 readdir_no_ex 從中讀取名稱。函式的傳回值將是一個 Directory fs_list，因此我們需要完成函式的全部操作是編寫傳回 filesystem 列表的 loop 函式。loop 的型別將是

loop : unit -> filesystem list

我們如何定義迴圈？讓我們再次逐步進行

let rec loop () =
  let filename = readdir_no_ex dirh in
  (* ..... *)

首先，我們從目錄控制代碼讀取下一個檔案名稱。filename 的型別為 string option，換句話說，它可以是 None 或 Some "foo"，其中 foo 是目錄中下一個檔案名稱的名稱。我們還需要忽略 "." 和 ".." 檔案（也就是說，目前目錄和父目錄）。我們可以透過一個不錯的模式比對來完成所有這些操作

let rec loop () =
  let filename = readdir_no_ex dirh in
    match filename with
    | None -> []
    | Some "." -> loop ()
    | Some ".." -> loop ()
    | Some filename ->
        (* ..... *)

None 的情況很容易。以遞迴方式思考 (!)，如果呼叫 loop 並且我們已到達目錄末尾，則 loop 需要傳回一個項目清單。由於沒有任何項目，它會傳回空列表 ([])。

對於 "." 和 ".."，我們只會忽略該檔案並再次呼叫 loop。

當 loop 讀取實際檔案名稱時，我們該怎麼辦（以下的 Some filename 比對）？讓 pathname 為檔案的完整路徑。我們「stat」檔案以查看它是否真的是目錄。如果它是目錄，我們透過遞迴呼叫 read_directory 來設定 this，該函式會傳回 Directory something。請注意，read_directory 的整體結果是 Directory (loop ())。如果檔案確實是一個檔案（不是目錄），那麼我們讓 this 為 File pathname。接下來，我們做一些聰明的事情：我們傳回 this :: loop ()。這是對 loop () 的遞迴呼叫，目的是計算其餘的目錄成員（一個列表），我們在該列表前面加上 this。

# let rec read_directory path =
  let dirh = opendir path in
  let rec loop () =
    let filename = readdir_no_ex dirh in
      match filename with
      | None -> []
      | Some "." -> loop ()
      | Some ".." -> loop ()
      | Some filename ->
          let pathname = path ^ "/" ^ filename in
          let stat = lstat pathname in
          let this =
            if stat.st_kind = S_DIR then
              read_directory pathname
            else
              File pathname
          in
            this :: loop ()
  in
    Directory (loop ());;
val read_directory : string -> filesystem = <fun>

這是一個相當複雜的遞迴位元，但儘管這是一個虛構的範例，但它相當典型地代表了在真實世界函數式程式中發現的複雜遞迴模式。從中可以學到兩個重要的教訓

• 使用遞迴來建立列表

let rec loop () =
  match data with (* Could also be an if statement *)
  | base case -> []
  | recursive case -> element :: loop ()

將此與我們之前的 range 函式進行比較。遞迴模式完全相同

let rec range a b =
  if a > b then []              (* Base case *)
  else a :: range (a + 1) b     (* Recursive case *)

• 使用遞迴來建立樹狀結構

let rec read_directory path =
  (* blah blah *)
  if file_is_a_directory path then
    read_directory path_to_file
  else
    Leaf file

現在，要使這個成為一個可運作的程式，只需少量的程式碼來呼叫 read_directory 並顯示結果

let path = Sys.argv.(1) in
let fs = read_directory path in
print_endline (string_of_filesystem fs)

遞迴範例：列表中的最大元素

請記住列表的基本遞迴模式

let rec loop () =
  a match or if statement
  | base case -> []
  | recursive case -> element :: loop ()

這裡的關鍵實際上是使用比對/基本案例/遞迴案例模式。在此範例（尋找列表中的最大元素）中，我們將有兩個基本案例和一個遞迴案例。但在我們跳到程式碼之前，讓我們退一步來思考這個問題。透過思考這個問題，解決方案將如同魔法般出現。（是真的！）

首先，讓我們明確列表的最大元素只是最大的那個，例如，列表 [1; 2; 3; 4; 1] 的最大元素是 4。

當然，也有例外。空列表 []沒有最大元素。如果我們傳遞一個空列表，它會拋出錯誤。

單元素列表（例如 [4]）的最大元素是什麼？這很容易！它只是元素本身，因此 list_max [4] 應該傳回 4，或者在一般情況下，list_max [x] 應該傳回 x。

一般列表 x :: remainder（這是列表的 "cons" 表示法，所以 remainder 是尾部 - 也是一個列表）的最大元素是什麼？

請思考一下。假設您知道 remainder 的最大元素，比如說是 y。那麼 x :: remainder 的最大元素是什麼？這取決於 x > y 還是 x <= y。如果 x 大於 y，則整體最大值為 x，相反地，如果 x 小於 y，則整體最大值為 y。

這真的可行嗎？

再考慮一下 [1; 2; 3; 4; 1]。這等於 1 :: [2; 3; 4; 1]。現在，尾部 [2; 3; 4; 1] 的最大元素是 4。所以現在我們關注 x = 1 和 y = 4。因為 y = 4 比較大，所以頭部的元素 x = 1 無關緊要，整個列表的最大值是 y = 4。

現在讓我們把上面的規則寫成程式碼，來建立一個可用的函式

# let rec list_max xs =
  match xs with
  | [] -> (* empty list: fail *)
      failwith "list_max called on empty list"
  | [x] -> (* single element list: return the element *)
      x
  | x :: remainder -> (* multiple element list: recursive case *)
      max x (list_max remainder);;
val list_max : 'a list -> 'a = <fun>

我已經加入了註解，這樣您就可以看到我們上面決定的規則/特殊情況是如何對應到程式碼的每一行的。

它有效嗎？

# list_max [1; 2; 3; 4; 1];;
- : int = 4
# list_max [];;
Exception: Failure "list_max called on empty list".
# list_max [5; 4; 3; 2; 1];;
- : int = 5
# list_max [5; 4; 3; 2; 1; 100];;
- : int = 100

請注意，所提出的解決方案 (a) 與命令式 for 迴圈解決方案非常不同，而且 (b) 與問題規範的關聯性更強。函數式程式設計師會告訴您，這是因為函數式風格比命令式風格處於更高的層次，因此更好也更容易。您是否相信他們取決於您。可以肯定的是，對函數式版本進行邏輯推理要簡單得多，如果您想正式證明 list_max 是正確的（「正確」是指數學上可以證明一個程式沒有錯誤，這對於太空梭、核電廠和一般來說更高品質的軟體很有用）。

尾部遞迴

讓我們再次查看 range 函式，這大概是第二十次了

# let rec range a b =
  if a > b then []
  else a :: range (a+1) b;;
val range : int -> int -> int list = <fun>

我將稍微重寫它，使程式的結構更清晰（但仍然是相同的函式）

# let rec range a b =
  if a > b then [] else
    let result = range (a+1) b in
      a :: result;;
val range : int -> int -> int list = <fun>

讓我們呼叫它

# List.length (range 1 10);;
- : int = 10
# List.length (range 1 1000000);;
Stack overflow during evaluation (looping recursion?).

嗯…乍看之下，這似乎是遞迴程式設計的問題，因此也是整個函數式程式設計的問題！如果您使用遞迴而不是迭代的方式來寫程式碼，那麼在處理大量輸入時，您必然會耗盡堆疊空間，對吧？

事實上，是錯的。編譯器可以對某些類型的遞迴函式執行簡單的優化，將它們轉換為 while 迴圈。因此，這些特定類型的遞迴函式在恆定的堆疊空間中執行，並且具有與命令式 while 迴圈相當的效率。這些函式稱為尾部遞迴函式。

在尾部遞迴函式中，遞迴呼叫發生在最後。還記得我們上面的 loop () 函式嗎？它們都具有以下形式

let rec loop () =
  (* do something *)
  loop ()

因為對 loop () 的遞迴呼叫是最後發生的，所以 loop 是尾部遞迴的，編譯器會將整個函式轉換為 while 迴圈。

不幸的是，range 不是尾部遞迴的，上面的較長版本說明了原因。對 range 的遞迴呼叫並非發生在最後。實際上，最後發生的是 :: (cons) 操作。因此，編譯器不會將遞迴轉換為 while 迴圈，並且該函式在堆疊空間的使用上效率不高。

使用累積引數或 accumulator 可以讓您以尾部遞迴的方式編寫諸如上面的 range 之類的函式，這意味著它們將是高效的，並且可以在大量輸入下正常運作。讓我們規劃重寫後的 range 函式，它將使用累積引數來儲存「到目前為止的結果」

let rec range2 a b accum =
  (* ... *)

let range a b =
  range2 a b []

accum 引數將會累積結果。它是「到目前為止的結果」。我們傳入空的列表（「到目前為止沒有結果」）。簡單的情況是當 a > b 時

let rec range2 a b accum =
  if a > b then accum
  else
    (* ... *)

如果 a > b（也就是說，如果我們已經到達遞迴的末尾），則停止並回傳結果 (accum)。

現在的訣竅是編寫 else 子句，並確保對 range2 的呼叫是我們所做的最後一件事，這樣該函式才是尾部遞迴的

# let rec range2 a b accum =
  if a > b then accum
  else range2 (a + 1) b (a :: accum);;
val range2 : int -> int -> int list -> int list = <fun>

這個函式只有一個小問題。它會反向建構列表！但是，這很容易通過將 range 重新定義為來解決

# let range a b = List.rev (range2 a b []);;
val range : int -> int -> int list = <fun>

這次它有效了，儘管它執行起來有點慢，因為它真的必須建構一個包含一百萬個元素的列表

# List.length (range 1 1000000);;
- : int = 1000000

以下實作比之前的實作快兩倍，因為它不需要反轉列表

# let rec range2 a b accum =
  if b < a then accum
  else range2 a (b - 1) (b :: accum);;
val range2 : int -> int -> int list -> int list = <fun>
# let range a b =
  range2 a b [];;
val range : int -> int -> int list = <fun>

這只是對尾部遞迴的簡要概述，但在現實情況中，判斷函式是否為尾部遞迴可能相當困難。

我們在這裡真正學到了什麼？

其中一件事是，遞迴函式對於沒有經驗的程式設計師來說有一個危險的陷阱。您的函式在少量輸入（在測試期間）時似乎可以正常運作，但當暴露在大量輸入時，可能會在實際應用中發生災難性的失敗。這是反對使用遞迴函式的一個論點；相反地，請盡可能使用明確的 while 迴圈。

可變記錄、參考（再次！）和陣列

之前我們順帶提到了記錄。這些類似於 C 的 struct

# type pair_of_ints = {a : int; b : int};;
type pair_of_ints = { a : int; b : int; }
# {a = 3; b = 5};;
- : pair_of_ints = {a = 3; b = 5}
# {a = 3};;
Line 1, characters 1-8:
Error: Some record fields are undefined: b

讓我們繼續介紹另一個有趣的功能：OCaml 記錄可以具有可變的欄位。通常，像 {a = 3; b = 5} 這樣的表示式是一個不可變的常數物件。但是，如果記錄具有可變欄位，則可以變更記錄中的那些欄位。這是 OCaml 的一個命令式功能，因為函數式語言通常不允許可變物件（或參考或可變陣列，我們稍後會看到）。

下面是一個定義了可變欄位的物件，用於計算物件被存取的次數。您可以想像這在快取方案中用於決定要從記憶體中移除哪些物件。

# type name = {name : string; mutable access_count : int};;
type name = { name : string; mutable access_count : int; }

這是一個定義在名稱上的函式，它會印出 name 欄位並遞增可變的 access_count 欄位

# let print_name name =
  print_endline ("The name is " ^ name.name);
  name.access_count <- name.access_count + 1;;
val print_name : name -> unit = <fun>

請注意 print_name 的一個奇怪（且非常不函數式）的功能：它會修改其 access_count 參數。這個函式不是「純粹」的。OCaml 是一種函數式語言，但它不會強迫您接受函數式程式設計。

無論如何，讓我們看看 print_name 的實際運作

# let n = {name = "Richard Jones"; access_count = 0};;
val n : name = {name = "Richard Jones"; access_count = 0}
# n;;
- : name = {name = "Richard Jones"; access_count = 0}
# print_name n;;
The name is Richard Jones
- : unit = ()
# n;;
- : name = {name = "Richard Jones"; access_count = 1}
# print_name n;;
The name is Richard Jones
- : unit = ()
# n;;
- : name = {name = "Richard Jones"; access_count = 2}

只有明確標記為 mutable 的欄位才能使用 <- 運算子賦值。如果您嘗試賦值給不可變的欄位，OCaml 不會允許您這樣做

# n.name <- "John Smith";;
Line 1, characters 1-23:
Error: The record field name is not mutable

我們現在應該很熟悉的參考是使用具有可變 contents 欄位的記錄來實作的。請查看 Stdlib 中的定義

type 'a ref = {mutable contents : 'a}

仔細看看 OCaml 的頂層針對參考的值所列印的內容

# let r = ref 100;;
val r : int Stdlib.ref = {Stdlib.contents = 100}

陣列是 OCaml 提供的另一種可變結構。在 OCaml 中，普通的列表是實作為連結列表，而連結列表對於某些類型的操作來說速度較慢。例如，取得列表的頭部，或迭代列表以對每個元素執行某些操作，都相當快。但是，當跳轉到列表的第 n 個元素或嘗試隨機存取列表時，您會發現這兩者都是緩慢的操作。OCaml Array 型別是真正的陣列，因此隨機存取速度很快，但插入和刪除元素的速度很慢。Array 也是可變的，因此您也可以隨機更改元素。

陣列的基本概念很簡單

# let a = Array.create 10 0;;
Line 1, characters 9-21:
Alert deprecated: Stdlib.Array.create
Use Array.make/ArrayLabels.make instead.
val a : int array = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]
# for i = 0 to Array.length a - 1 do
    a.(i) <- i
  done;;
- : unit = ()
# a;;
- : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]

請注意寫入陣列的語法：[| element; element; ... |]

OCaml 編譯器的設計考慮了大量的數值處理（傳統上 FORTRAN 用於處理的那種），因此它包含各種專門針對數字、向量和矩陣陣列的優化。以下是一些用於執行密集矩陣乘法的基準程式碼。請注意，它使用了 for 迴圈，並且總體而言風格非常命令式

# let size = 30;;
val size : int = 30

# let mkmatrix rows cols =
  let count = ref 1
  and last_col = cols - 1
  and m = Array.make_matrix rows cols 0 in
    for i = 0 to rows - 1 do
      let mi = m.(i) in
        for j = 0 to last_col do
          mi.(j) <- !count;
          incr count
        done;
    done;
    m;;
val mkmatrix : int -> int -> int array array = <fun>

# let rec inner_loop k v m1i m2 j =
  if k < 0 then v
  else inner_loop (k - 1) (v + m1i.(k) * m2.(k).(j)) m1i m2 j;;
val inner_loop : int -> int -> int array -> int array array -> int -> int =
  <fun>

# let mmult rows cols m1 m2 m3 =
  let last_col = cols - 1
  and last_row = rows - 1 in
    for i = 0 to last_row do
      let m1i = m1.(i) and m3i = m3.(i) in
      for j = 0 to last_col do
        m3i.(j) <- inner_loop last_row 0 m1i m2 j
      done;
    done;;
val mmult :
  int -> int -> int array array -> int array array -> int array array -> unit =
  <fun>

# let () =
  let n =
    try int_of_string Sys.argv.(1)
    with Invalid_argument _ -> 1
  and m1 = mkmatrix size size
  and m2 = mkmatrix size size
  and m3 = Array.make_matrix size size 0 in
    for i = 1 to n - 1 do
      mmult size size m1 m2 m3
    done;
    mmult size size m1 m2 m3;
    Printf.printf "%d %d %d %d\n" m3.(0).(0) m3.(2).(3) m3.(3).(2) m3.(4).(4);;
Exception: Failure "int_of_string".

相互遞迴函式

假設我想定義兩個互相呼叫的函式。這實際上不是一件很常做的事情，但有時可能會很有用。這是一個刻意設計的例子（感謝 Ryan Tarpine）：數字 0 是偶數。其他大於 0 的數字，如果它們的前一個數字是奇數，則為偶數。因此

# let rec even n =
  match n with
  | 0 -> true
  | x -> odd (x - 1);;
Line 4, characters 10-13:
Error: Unbound value odd

上面的程式碼無法編譯，因為我們還沒有定義函式 odd！這很容易。零不是奇數，而其他大於 0 的數字，如果它們的前一個數字是偶數，則為奇數。因此，要完成此操作，我們也需要該函式

# let rec even n =
  match n with
  | 0 -> true
  | x -> odd (x - 1);;
Line 4, characters 10-13:
Error: Unbound value odd

# let rec odd n =
  match n with
  | 0 -> false
  | x -> even (x - 1);;
Line 4, characters 10-14:
Error: Unbound value even

唯一的問題是...這個程式無法編譯。為了編譯 even 函式，我們需要已經有 odd 的定義，而為了編譯 odd，我們需要 even 的定義。因此，交換這兩個定義也無濟於事。

在 OCaml 中沒有「前向原型」（如同在 C 衍生的語言中所見），但是有一個特殊的語法可以定義一組兩個或多個相互遞迴函式，例如 odd 和 even

# let rec even n =
    match n with
    | 0 -> true
    | x -> odd (x - 1)
  and odd n =
    match n with
    | 0 -> false
    | x -> even (x - 1);;
val even : int -> bool = <fun>
val odd : int -> bool = <fun>

您也可以使用類似的語法來編寫相互遞迴的類別定義和模組。