Come prendere il prodotto di due liste in OCaml?

Question

Ho due liste:

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

Voglio una lista di output C come ad esempio:

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

Come fare in OCaml come liste sono immutabili? Sono nuovo ad esso.

Answer 1

Si restituirebbe una nuova lista. Se sei veramente interessato al prodotto cartesiano delle liste, allora questo dovrebbe essere sufficiente:

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")] 

Se avete bisogno di quella strana struttura piatta, invece, è possibile utilizzare un elenco di concatenazione aggiuntivo.

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

Answer 2

Se non si desidera utilizzare la concatenazione, perché questa non è un'operazione ricorsiva di coda, è possibile utilizzare il seguente (che dovrebbe essere più efficiente):

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

Per il prodotto cartesiano, basta cambiare

b::a::y 

in

(a,b)::y 

Answer 3

avrei rotto il problema in due problemi secondari:

• considerano primo luogo una funzione appendeach con assume un valore e un elenco e restituisce il risultato della somma quel valore fronte di ogni elemento nell'elenco

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

• poi considerare un prodotto con funzione prende due liste e chiede appendeach per ogni elemento della prima lista e l'intero secondo elenco

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