Как взять продукт из двух списков в OCaml?

Question

У меня есть два списка:

let a = ["a";"b"]; 
let b = ["c";"d"]; 

Я хочу список вывода с такими, как:

c = ["a";"c";"a";"d";"b";"c";"b";"d"]; 

Как сделать это в OCaml, как списки неизменны? Я новичок в этом.

Answer 1

Вы бы вернули новый список. Если вы действительно заинтересованы в декартово произведение из списков, то это должно быть достаточно:

let cartesian l l' = 
    List.concat (List.map (fun e -> List.map (fun e' -> (e,e')) l') l) 

# cartesian ["a";"b"] ["c";"d"];; 
- : (string * string) list = [("a", "c"); ("a", "d"); ("b", "c"); ("b", "d")] 

Если вам нужно, что странно плоская структура вместо этого, вы можете использовать дополнительный список конкатенации.

let flat_cartesian l l' = 
    List.concat (List.concat (
    List.map (fun e -> List.map (fun e' -> [e;e']) l') l)) 

Answer 2

Если вы не хотите использовать конкатенацию, потому что это не хвост рекурсивная операция, вы можете использовать следующее (которые должны быть более эффективными):

let product l1 l2 = 
    List.rev (
    List.fold_left 
    (fun x a -> 
     List.fold_left 
     (fun y b -> 
     b::a::y 
     ) 
     x 
     l2 
    ) 
    [] 
    l1 
) 
;; 

Для декартовой продукта, просто изменить

b::a::y 

в

(a,b)::y 

Answer 3

Я бы разбить задачу на две подгруппы проблем:

• Сначала рассмотрим функцию appendeach с принимает значение и список и возвращает результат, добавив, что значение Infront каждого элемента в списке

  let rec appendeach x lst = match lst with [] -> [] 
               | hd::tl -> x::hd::(appendeach x tl);; 
  

• Затем рассмотрим функцию продукта с принимает два списка и вызывает appendeach для каждого элемента в первом списке, и весь второй список

  let rec product lst1 lst2 = match lst1 with [] -> [] | 
               hd::tl -> (appendeach hd lst2)@(product tl lst2);;