試圖瞭解這個代碼塊OCaml中

Question

我想了解這段代碼是這樣做的：

let rec size x = 
    match x with 
     [] -> 0 
    | _::tail -> 1 + (size tail) ;; 

我知道，這個表達式計算列表的大小，但我不明白在代碼中它將逐一減少列表。例如，我認爲它需要從[1; 2; 3]到[2; 3]到[3]，但是它在哪裏或如何做？我不明白。

謝謝。

Answer 1

OCaml中的列表是遞歸地使用空列表（[]）和缺點（::）構造函數構建的。所以[1; 2; 3]是1::2::3::[]的句法糖。

大小是由在使用圖案_::tail每一步減少x計算（_表示我們忽略了列表的頭部）並調用相同功能size上tail。當列表爲空且模式[]成功時，函數最終終止。

這裏是size [1; 2; 3]是如何計算的簡短說明：

size 1::2::3::[] 
~> 1 + size 2::3::[] // match the case of _::tail 
~> 1 + 1 + size 3::[] // match the case of _::tail 
~> 1 + 1 + 1 + size [] // match the case of _::tail 
~> 1 + 1 + 1 + 0 // match the case of [] 
~> 3 

作爲一個側面說明，你可以從圖中看到，需要大量的信息存儲在堆棧計算size。這意味着如果輸入列表很長，那麼您的函數可能會導致堆棧溢出錯誤，但這是另一回事。

Answer 2

它使用模式匹配來提取列表的尾部（將其命名爲tail），然後使用尾部調用它自己。也許對你來說缺失的部分是模式匹配。

Answer 3

按this article，這實際上有一個確切的例子中，你正在討論：

正如我們所看到的，一個列表可以是空的（列表的形式[]），或者的組成第一個元素（它的頭部）和一個子列表（它的尾部）。該列表的格式爲h::t。

如果列表匹配空列表或使用模式匹配來提取頭部（第一項）和尾部（所有其他項目），然後使用遞歸獲取尾部長度。

因此，這是減少列表_::tail，和1 + (size tail)計算大小。 |之前的位當然是遞歸的終止條件。

這可能是更容易理解（在我看來），如果被視爲：

let rec size x = match x with 
      [] -> 0 
    | _::tail -> 1 + (size tail) 
    ;; 

（這其實是非常相似的鏈接頁面使用的格式，我只是改變了它稍微排隊->符號）。

Answer 4

實際上這段代碼使用模式匹配的力量來計算列表的大小。

match表示您將嘗試使x以下列其中一種模式進入。

第一個[]意味着你的列表是空的，所以它的大小爲0，第二個_::tail意味着你有一個元素（*），其次是列表的其餘部分，所以基本上大小1 + size(rest of the list)

（*）下劃線表示您不關心此元素的值。

Answer 5

無論何時您匹配列表，您都可以匹配表格head::tail的模式，其中head將獲得第一個元素的值，tail將獲得餘數。該模式將匹配任何非空列表，因爲尾部可以是空的，但頭部必須存在。其次，你在Ocaml中匹配的任何模式，如果你願意的話，你可以用一個下劃線替換一個變量來說「匹配這裏的東西，但我不會真正使用它，所以我不會使用它，所以我不會使用它，所以我不會使用它，所以我不是給它一個名字「。因此，在這個程序中，不是編寫head::tail -> 1 + (size tail)，而是編寫_::tail -> 1 + (size tail)，因爲它們實際上並未使用第一個元素，只是確保它存在。