Cartesian producto de 2 listas en Haskell

Como han señalado otras respuestas, usar una comprensión de lista es la forma más natural de hacer esto en Haskell.

Si estás aprendiendo Haskell y quieres trabajar en el desarrollo de intuiciones sobre clases de tipos como Monad, sin embargo, es un ejercicio divertido descubrir por qué esta definición un poco más corta es equivalente:

import Control.Monad (liftM2)

cartProd :: [a] -> [b] -> [(a, b)]
cartProd = liftM2 (,)

Probablemente nunca querrías escribir esto en código real, pero la idea básica es algo que verás en Haskell todo el tiempo: estamos usando liftM2 para levantar la función no monádica (,) en una mónada-en este caso específicamente la mónada de lista.

Si esto no tiene ningún sentido o no es útil, olvídalo, es solo otra forma de ver el problema.

Si sus listas de entrada son del mismo tipo, puede obtener el producto cartesiano de un número arbitrario de listas usando sequence (usando la mónada List). Esto le dará una lista de listas en lugar de una lista de tuplas:

> sequence [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

Hay una manera muy elegante de hacer esto con Funtores Aplicativos:

import Control.Applicative

(,) <$> [1,2,3] <*> [4,5,6]
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

La idea básica es aplicar una función en argumentos "envueltos", por ejemplo,

(+) <$> (Just 4) <*> (Just 10)
-- Just 14

En el caso de las listas, la función se aplicará a todas las combinaciones, por lo que todo lo que tienes que hacer es "tupla" con (,).

Véase http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors o (más teórico) http://www.soi.city.ac.uk / ~ ross / papers / Applicative.pdf para más detalles.

La manera correcta es usar las comprensiones de listas, como otras personas ya han señalado, pero si quieres hacerlo sin usar las comprensiones de listas por cualquier razón, entonces puedes hacer esto:

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs [] = []
cartProd [] ys = []
cartProd (x:xs) ys = map (\y -> (x,y)) ys ++ cartProd xs ys

Otra forma de lograr esto es usando aplicativos:

import Control.Applicative

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = (,) <$> xs <*> ys

Otra forma, usando la notación do:

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = do x <- xs
                    y <- ys
                    return (x,y)

Otras respuestas asumen que las dos listas de entrada son finitas. Con frecuencia, el código idiomático de Haskell incluye listas infinitas, por lo que vale la pena comentar brevemente cómo producir un producto cartesiano infinito en caso de que sea necesario.

El enfoque estándar es usar diagonalización; escribiendo una entrada a lo largo de la parte superior y la otra entrada a lo largo de la izquierda, podríamos escribir una tabla bidimensional que contuviera el producto cartesiano completo de la siguiente manera:{[17]]}

   1  2  3  4 ...
a a1 a2 a3 a4 ...
b b1 b2 b3 b4 ...
c c1 c2 c3 c4 ...
d d1 d2 d3 d4 ...

.  .  .  .  . .
.  .  .  .  .  .
.  .  .  .  .   .

Por supuesto, trabajar a través de una sola fila nos dará infinitamente elementos antes de que llegue a la siguiente fila; de manera similar, ir en sentido de columna sería desastroso. Pero podemos ir a lo largo de diagonales que van hacia abajo y hacia la izquierda, comenzando de nuevo en un poco más a la derecha cada vez que llegamos al borde de la cuadrícula.

a1

   a2
b1

      a3
   b2
c1

         a4
      b3
   c2
d1

...y así sucesivamente. En orden, esto nos daría:

a1 a2 b1 a3 b2 c1 a4 b3 c2 d1 ...

Para codificar esto en Haskell, primero podemos escribir la versión que produce la tabla bidimensional: {[17]]}

cartesian2d :: [a] -> [b] -> [[(a, b)]]
cartesian2d as bs = [[(a, b) | a <- as] | b <- bs]

An el método ineficiente de diagonalizar es iterar primero a lo largo de las diagonales y luego a lo largo de la profundidad de cada diagonal, sacando el elemento apropiado cada vez. Para simplificar la explicación, asumiré que ambas listas de entrada son infinitas, por lo que no tenemos que perder el tiempo con la comprobación de límites.

diagonalBad :: [[a]] -> [a]
diagonalBad xs =
    [ xs !! row !! col
    | diagonal <- [0..]
    , depth <- [0..diagonal]
    , let row = depth
          col = diagonal - depth
    ]

Esta implementación es un poco desafortunada: la operación de indexación de listas repetidas !! se vuelve más y más costosa a medida que avanzamos, dando un rendimiento asintótico bastante malo. A más la implementación eficiente tomará la idea anterior, pero implementarla usando cremalleras. Por lo tanto, vamos a dividir nuestra cuadrícula infinita en tres formas como esta:

a1 a2 / a3 a4 ...
     /
    /
b1 / b2 b3 b4 ...
  /
 /
/
c1 c2 c3 c4 ...
---------------------------------
d1 d2 d3 d4 ...

 .  .  .  . .
 .  .  .  .  .
 .  .  .  .   .

El triángulo superior izquierdo serán los bits que ya hemos emitido; el cuadrilátero superior derecho serán filas que se han emitido parcialmente pero que aún contribuirán al resultado; y el rectángulo inferior serán filas que aún no hemos comenzado a emitir. Para empezar, el triángulo superior y el cuadrilátero superior estarán vacíos, y el rectángulo inferior será toda la cuadrícula. En cada paso, podemos emitir el primer elemento de cada fila en el cuadrilátero superior (esencialmente moviendo la línea inclinada hacia arriba por una), luego agregar una nueva fila del rectángulo inferior al cuadrilátero superior (esencialmente moviendo la línea horizontal hacia abajo por una).

diagonal :: [[a]] -> [a]
diagonal = go [] where
    go upper lower = [h | h:_ <- upper] ++ case lower of
        []         -> concat (transpose upper')
        row:lower' -> go (row:upper') lower'
        where upper' = [t | _:t <- upper]

Aunque esto parece un poco más complicado, es significativamente más eficiente. También se encarga de los límites de comprobación que hemos punteado en el más simple versión.

¡Pero no deberías escribir todo este código tú mismo, por supuesto! En su lugar, debe usar el paquete universe. En Data.Universe.Helpers, hay (+*+), que empaqueta las funciones anteriores cartesian2d y diagonal para dar solo la operación del producto cartesiano:

Data.Universe.Helpers> "abcd" +*+ [1..4]
[('a',1),('a',2),('b',1),('a',3),('b',2),('c',1),('a',4),('b',3),('c',2),('d',1),('b',4),('c',3),('d',2),('c',4),('d',3),('d',4)]

También puedes ver las diagonales si esa estructura se vuelve útil: {[17]]}

Data.Universe.Helpers> mapM_ print . diagonals $ cartesian2d "abcd" [1..4]
[('a',1)]
[('a',2),('b',1)]
[('a',3),('b',2),('c',1)]
[('a',4),('b',3),('c',2),('d',1)]
[('b',4),('c',3),('d',2)]
[('c',4),('d',3)]
[('d',4)]

Si tiene muchas listas para producir juntas, iterar (+*+) puede sesgar injustamente ciertas listas; puede usar choices :: [[a]] -> [[a]] para sus necesidades de productos cartesianos n-dimensionales.

Bueno, una manera muy fácil de hacer esto sería con las comprensiones de listas:

cartProd :: [a] -> [b] -> [(a, b)]
cartProd xs ys = [(x, y) | x <- xs, y <- ys]

Que supongo que es cómo haría esto, aunque no soy un experto en Haskell (de ninguna manera).

Algo como:

cartProd x y = [(a,b) | a <- x, b <- y]

Es un trabajo para sequence ing. Una implementación monádica de la misma podría ser:

cartesian :: [[a]] -> [[a]]
cartesian [] = return []
cartesian (x:xs) = x >>= \x' -> cartesian xs >>= \xs' -> return (x':xs')

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

Como puede notar, lo anterior se asemeja a la implementación de map por funciones puras pero en tipo monádico. En consecuencia, puede simplificarlo hasta

cartesian :: [[a]] -> [[a]]
cartesian = mapM id

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

Aquí está mi implementación del producto cartesiano n-ary:

crossProduct :: [[a]] -> [[a]]
crossProduct (axis:[]) = [ [v] | v <- axis ]
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ]

Simplemente agregando una forma más para el entusiasta, usando solo coincidencia de patrones recursivos.

cartProd :: [a]->[b]->[(a,b)]
cartProd _ []=[]
cartProd [] _ = []
cartProd (x:xs) (y:ys) = [(x,y)] ++ cartProd [x] ys  ++ cartProd xs ys ++  cartProd xs [y]