¿Cómo tomar el producto de dos listas en OCaml?

Question

tengo dos listas:

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

Quiero una lista de salida C, tales como:

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

Cómo hacerlo en ocaml como listas son inmutables? Soy nuevo en eso.

Answer 1

Devolverías una nueva lista. Si realmente está interesado en el producto cartesiano de las listas, entonces esto debe ser suficiente:

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

Si necesita que la estructura plana extraño lugar, se puede utilizar una lista de concatenación adicional.

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

Answer 2

Si no desea utilizar la concatenación, porque esto no es una operación recursiva de cola, puede utilizar el siguiente (que debería ser más eficiente):

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

Para el producto cartesiano, basta con cambiar

b::a::y 

en

(a,b)::y 

Answer 3

Me dividir el problema en dos subproblemas:

• consideran en primer lugar un appendeach función con toma un valor y una lista y devuelve el resultado de añadir ese valor delante de cada elemento de la lista

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

• luego considerar un producto con función toma dos listas y llama appendeach para cada elemento de la primera lista y toda la segunda lista

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