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

Вы ищете декартово произведение двух множеств.

Этот вопрос был задан in a thread в списке рассылки OCaml. Этот ответ предлагает Brian Hurt: Для

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 
;; 

Answer 3

Объединяя решение @David 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 также является хвостовым рекурсивным).