OCaml中的列表的笛卡爾（外部）乘積

Question

我想遍歷列表中的元素的所有組合，這些列表具有相同的長度但不一定是相同的類型。這就像兩個列表的笛卡爾積（這在OCaml中很容易做到），但對於任意數量的列表。

首先我試着編寫一個通用的笛卡爾（外）產品函數，該函數接受列表列表並返回元組列表，但由於列表的輸入列表不包含相同類型的元素。

現在我到類型

'a list * 'b list * 'c list -> ('a * 'b * 'c) list 

的函數不幸固定的輸入的數目爲三（例如）。這是

let outer3 (l1, l2, l3) = 
    let open List in 
    l1 |> map (fun e1 -> 
     l2 |> map (fun e2 -> 
      l3 |> map (fun e3 -> 
       (e1,e2,e3)))) 
    |> concat |> concat 

這樣的工作，但它很麻煩，因爲它必須重做每個輸入數量。有一個更好的方法嗎？

背景：我想將生成的扁平列表提供給Parmap.pariter。

Answer 1

爲了解決任務的問題，我們需要使用存在類型。我們可以使用GADT，但它們默認關閉。當然，我們可以使用開放式的變體，但我更喜歡語法較重的一些，但更便於使用一流模塊的解決方案（因爲GADT可以通過一流模塊進行編程，因此它可以工作）。但足夠的理論，首先我們需要一個功能，將產生n_cartesian_product對我們來說，有型'a list list -> 'a list list

let rec n_cartesian_product = function 
    | [] -> [[]] 
    | x :: xs -> 
    let rest = n_cartesian_product xs in 
    List.concat (List.map (fun i -> List.map (fun rs -> i :: rs) rest) x) 

現在，我們需要適應不同類型分成一類'a，並在這裏談到存在的類型，讓我們定義一個簽名：

module type T = sig 
    type t 
    val x : t 
end 

現在，讓我們嘗試將提升寫這個存在：

let int x = (module struct type t = int let x = x end : T) 

它具有類型：

int -> (module T) 

讓我們延長與一些更多的情況下，例如：

let string x = (module struct type t = string let x = x end : T) 
let char x = (module struct type t = char let x = x end : T) 

let xxs = [ 
    List.map int [1;2;3;4]; 
    List.map string ["1"; "2"; "3"; "4"]; 
    List.map char ['1'; '2'; '3'; '4'] 
] 

# n_cartesian_product xxs;; 
- : (module T) list list = 
[[<module>; <module>; <module>]; [<module>; <module>; <module>]; 
[<module>; <module>; <module>]; [<module>; <module>; <module>]; 
... 

而不是頭等艙的模塊，可以使用其他的抽象，如對象或功能，如果您的類型要求允許這種（例如，如果你不需要暴露類型t）。當然，我們的存在是非常簡潔的，也許你需要延長簽名。

Answer 2

我使用@ivg的答案，但在一個版本與GADT。我在這裏重現它以供參考。在僅類型float和int可以出現在輸入列表簡單的情況下，首先設置

type wrapped = Int : int -> wrapped | Float : float -> wrapped 

這是毫無類型參數GADT。然後

let wrap_f f = Float f 
let wrap_i i = Int f 

將類型包裝到總和類型中。在wrapped價值列表中，我們可以從@ivg的回答中調用n_cartesian_product。結果是一個列表combinations: wrapped list list，它是平坦的（就目前而言）。

現在要使用Parmap，我有例如一個工作人員功能work : float * int * float * float -> float。爲了將爭論從包裝中拿出來，我模式匹配：

combinations |> List.map (function 
| [Float f1; Int i; Float f2; Float f3] -> (f1, i, f2, f3) 
| _ -> raise Invalid_argument "wrong parameter number or types") 

構造元組的扁平列表。這可以通過工作人員功能work最終送入Parmap.pariter。

此設置與使用常規總和類型type wrapsum = F of float | I of int而不是wrapped幾乎相同。模式匹配將是相同的;唯一的區別似乎是得到錯誤的輸入，例如將僅在運行時檢測到(F 1, I 1, F 2.0, F, 3.0)，而不是像這裏那樣編譯時間。