ocaml的99個問題：無法理解的溶液，用於產生組合

Question

https://ocaml.org/learn/tutorials/99problems.html

我想了解，用於從一個列表的N個元素選擇的k個不同的對象的組合的溶液中。下面是代碼：

let extract k list = 
    let rec aux k acc emit = function 
     | [] -> acc 
     | h :: t -> 
     if k = 1 then aux k (emit [h] acc) emit t else 
      let new_emit x = emit (h :: x) in 
      aux k (aux (k-1) acc new_emit t) emit t 
    in 
    let emit x acc = x :: acc in 
    aux k [] emit list;; 

的發射功能被定義爲接受兩個參數：

let emit x acc = x :: acc 

所以我不太明白下面一行是如何工作的，因爲它發出的呼叫只給一個參數：

let new_emit x = emit (h :: x) 

此外，new_emit函數只接受一個參數，並作爲參數傳遞給AUX功能傳遞，怎麼能應對以下行（這裏是EMIT通過提供兩個參數）呼籲：OCaml中

if k = 1 then aux k (emit [h] acc) emit t 

Answer 1

功能通常是令行禁止，這意味着多個參數的函數是由帶一個參數，並返回一個函數，它的下一個參數（等）來表示。 OCaml有一些語法糖來使這個更好閱讀：let f x y = ...是let f = fun x -> fun y -> ...的簡稱。

通常，程序員通過一次傳遞所有參數來使用這樣的函數，但是隻能傳遞一個函數並返回'部分應用'函數。這就是emit發生的情況。

因此，您可以將let emit_new x = emit (h :: x)定義爲emit的版本，其中第一個參數已經提供。

Answer 2

這裏缺少的一點是，由於咖啡和一流的功能，函數的參數數量並不像您想象的那麼刻板。

在此特定情況下，emit的定義

let emit x acc = x :: acc 

給它的類型'a -> 'a list -> 'a list。這種類型可以有兩個不同的讀數，您可以將其視爲一個函數，它需要兩個參數，一個是'a類型，另一個是'a list，然後返回'a list類型的對象。但是，您也可以將其作爲一個參數'a的參數讀取，並返回'a list -> 'a list類型的函數。

定義

let new_emit x = emit (h :: x) 

使用該咖喱解釋：由於emit具有用於類型 'a -> 'a list -> 'a list，將其施加到h::x產生類型 'a list -> 'a list的函數，因此該函數new_emit具有用於 'a -> 'a list -> 'a list類型。換句話說，函數new_emit仍然接受兩個輸入參數，即使它的定義只涉及一個參數。注意，爲了使事情更容易理解的new_emit的定義也可以寫成要麼

let new_emit x = fun acc -> emit (h :: x) acc 

或

let new_emit x acc = emit (h :: x) acc 

在上下文中，用於新組合添加到組合由列表採取element_list並添加它以前選擇的所有元素。然後使用new_emit的定義來選取新元素h。換句話說，這條線

if k = 1 then aux k (emit [h] acc) emit t else 

裝置添加的元素列表[h]加上所有先前拾取元件的組合列表，因爲所有元件已經被拾取，而

let new_emit x = emit (h :: x) in 
     aux k (aux (k-1) acc new_emit t) emit t 

可以分解爲：

先挑元素h：

let new_emit x = emit (h :: x) 

然後構造的所有組合，其中h存在：

let combination_where_h_was_selected = aux (k-1) acc new_emit t 

然後構造所有組合，其中h是不存在：

 aux k combination_where_h_was_selected emit t 

PS： 作爲對數的受試者的更先進的發言一個函數的參數，請注意即使是「可變參數」函數也完全可能在OCaml中。例如，定義列表中的深奧和低效的方式將

let start f = f (fun x -> x) 
let elt x t k = k (fun l -> t (fun l -> x ::l) l) 
let stop f = f (fun x -> x) [] 
let [] = start stop 
let l = start (elt 1) (elt 2) (elt 3) (elt 4) stop 
;; assert (l = [1;2;3;4])