OCaml的：两套每个值的排列？ （如何翻译这个从Java）

Question

我有两套由Set.Make（T）返回。我想生成两个值的每一个可能的组合。我怎样才能做到这一点？

此工作，以产生一些对，但不是全部：

List.combine (IntSet.elements odp) (IntSet.elements ftw)

这会做在Java中：

for (int i : ktr) {
     for (int m : mnx) {
       System.out.println(i + ", " + m);
     }
}

Answer 1

如果xs和ys是两个列表，则它们的笛卡尔乘积（返回对的列表）可被计算如下：

List.concat (List.map (fun x -> List.map (fun y -> (x, y))
                                         ys)
                      xs)

在这种情况下，你的xs和ys被IntSet.elements odp和IntSet.elements ftw

Answer 2

用结合@大卫Crawshaw的溶液（这是尾递归）@ newacct的（这是完全通用）：

let cartesian_product xs ys =
  List.fold_left (fun acc x -> 
    List.fold_left (fun acc y -> 
      (x,y) :: acc) 
      acc ys) 
    [] xs

let product = 
  cartesian_product (IntSet.elements odb) (IntSet.elements ftw)

这将扭转自然顺序。它可以通过施加List.rev到结果得到恢复（List.rev也尾递归）。

Answer 3

您正在寻找两个集合的笛卡尔乘积。

此问题已经被问在OCaml的邮件列表线程。这个答案是由布赖恩伤害：对于

module TypeSet = Set.Make(Type);;

创建，表示产品：

module TypeType = struct
    type t = Type.t * Type.t;;
    let compare (x1, x2) (y1, y2) =
        let r = Type.compare x1 y1 in
        if r == 0 then
            Type.compare x2 y2
        else
            r
    ;;
end;;

module TypeTypeSet = Set.Make(TypeType);;

然后生成与产品：

let cartesian_product s1 s2 =
    let f x y t = TypeTypeSet.add (x, y) t in
    let g x t = TypeSet.fold (f x) s2 t in
    TypeSet.fold g s1 TypeTypeSet.empty
;;