producto cruzado de dos listas

Question

jugando con 'funciones de extensión' para el módulo de lista. (pasé bastante tiempo en desarrollo 'mapfold' - que se rosca un acumulador como pliegue, pero lo utiliza como un parámetro para crear nuevos valores como mapa - luego descubrieron que eso es lo que List.scan_left hace)

Para la generación de prueba de datos, que tenía que hacer un producto vectorial de dos listas, esto es lo que ocurrió:

///Perform cross product of two lists, return tuple 
let crossproduct l1 l2 = 
    let product lst v2 = List.map (fun v1 -> (v1, v2)) lst 
    List.map_concat (product l1) l2 

¿es esta la buena, o hay ya alguna forma mejor de hacer esto?

La misma pregunta para éste:

///Perform cross product of three lists, return tuple 
let crossproduct3 l1 l2 l3 = 
    let tuplelist = crossproduct l1 l2 //not sure this is the best way... 
    let product3 lst2 v3 = List.map (fun (v1, v2) -> (v1, v2, v3)) lst2 
    List.map_concat (product3 tuplelist) l3 

Answer 1

otra opción es usar F # "expresiones de secuencia" y escribir algo como esto:

let crossproduct l1 l2 = 
    seq { for el1 in l1 do 
      for el2 in l2 do 
      yield el1, el2 };; 

(de hecho, es casi lo mismo que lo que escribiste, porque 'para .. in .. do' en la expresión de secuencia se puede ver como map_concat). Esto funciona con secuencias (flojas), pero si quieres trabajar con listas, simplemente envolverías el código dentro [...] en lugar de dentro de la secuencia {...}.

Answer 2

Su función crossproduct se ve bien (probablemente haya notado las palabras clave "in" que faltan). Me gusta esta versión de crossproduct3 mejor, pero eso es sólo yo:

let crossproduct3 l1 l2 l3 = 
List.map_concat 
(fun z -> 
(List.map_concat (fun y -> List.map (fun x -> (x, y, z)) l3) l2)) l1;; 

Su función tiene una complejidad algorítmica equivalente.

Por último, al utilizar productos cruzados en una forma explícita lista vacía, puede golpear en las value restriction (más o menos, una restricción que se asegura que el compilador sólo infiere tipos polimórficos para un valor sintáctico), es particularmente estricta en F#. La solución es para anotar las llamadas que utilizan una lista vacía, de la siguiente manera (si desea que la segunda lista que se compone de números enteros):

(crossproduct [3; 4] [] : (int * int) list) 

Answer 3

recientemente he necesitado algo similar - que tenía que comprimir una lista de secuencias a una secuencia de listas - por lo [(a1,a2,a3,...);(b1,b2,b3,...);(c1,c2,c3,...)] -> ([a1;b1;c1], [a2;b2;c3], ...)

El siguiente código hará esto:

let rec listZip (sl : 'a seq list) = 
     seq { 
      match sl with 
      | [] -> yield [] 
      | hd::tl -> 
       for h in hd do 
       for t in listZip tl do 
       yield (h::t) 
    } 

Answer 4

acabo de encontrar una solución más elegante a este cálculo utilizando expresiones:

type Product() = 
    member this.Bind (l,f) = List.collect f l  
    member this.Return n = [n] 

let enumeratedPizzas = 
    Product() { 
    let! x = ["New York";"Chicago"] 
    let! y = ["Pepperoni";"Sausage"] 
    let! z = ["Cheese";"Double Cheese"] 
    return x,y,z 
    } 

Por Techneilogy, copiado de fssnip.net, siga el enlace para ver el código comentado.

Answer 5

Estaba usando la respuesta de Benjol por un tiempo hasta que descubrí que puedes hacer casi lo mismo con Linq.La solución de Benjol es probable que aún el más elegante, pero si alguien quiere una solución que se puede utilizar con C# también entonces aquí van:

query { 
    for i in [1, 2] do 
    for j in [3, 4] do 
    select (i, j) 
} 

que es casi exactamente la misma que la solución de Tomas Petricek excepto la solución no necesita para anidar for loops por lo que es un poco más simple.