multiplos - suma de dos numeros en haskell

Producto cartesiano de 2 listas en Haskell (12)

Deseo producir el producto cartesiano de 2 listas en Haskell, pero no puedo encontrar la manera de hacerlo. El producto cartesiano ofrece todas las combinaciones de los elementos de la lista:

xs = [1,2,3] ys = [4,5,6] cartProd :: [a] -> [b] -> [(a,b)] cartProd xs ys ==> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Esta no es una pregunta real sobre la tarea y no está relacionada con ninguna de esas preguntas, pero la forma en que se resuelve este problema puede ayudar con una de ellas.

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 ]

Bueno, una manera muy fácil de hacer esto sería con listas de comprensión:

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

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

Como otras respuestas han notado, usar una lista de comprensión 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 tipo 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 quieras 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 elevar la función no monádica (,) a una mónada este caso específicamente la lista de mónada.

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

Es un trabajo para sequence . Una implementación monádica 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 observar, lo anterior se asemeja a la implementación del map por funciones puras pero de 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]]

Esto es muy fácil con la lista de comprensiones. Para obtener el producto cartesiano de las listas xs e ys , solo necesitamos tomar la tupla (x,y) para cada elemento x en xs y cada elemento y en ys .

Esto nos da la siguiente lista de comprensión:

cartProd xs ys = [(x,y) | x <- xs, y <- ys]

Hay una manera muy elegante de hacer esto con los Funcionadores 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 ej.

(+) <$> (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 (,) .

Ver 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 detalles.

La forma correcta es usar listas de comprensión, como ya han señalado otras personas, pero si quisiera hacerlo sin usar listas de comprensión por algún motivo, podría hacerlo:

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 usar applicatives:

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

Otra forma más, usando la notación do :

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

Otras respuestas suponen 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 la entrada uno a lo largo de la parte superior y la otra entrada a lo largo de la izquierda, podríamos escribir una tabla bidimensional que contenía el producto cartesiano completo como este:

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 en una sola fila nos dará infinitos elementos antes de que llegue a la siguiente fila; similarmente ir a la columna sería desastroso. Pero podemos seguir las diagonales que bajan y hacia la izquierda, comenzando de nuevo un poco más hacia la derecha cada vez que llegamos al borde de la grilla.

a1 a2 b1 a3 b2 c1 a4 b3 c2 d1

...y así. 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:

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

Un método ineficiente de diagonalizar es repetir primero a lo largo de las diagonales y luego a lo largo de cada diagonal, extrayendo el elemento apropiado cada vez. Para simplificar la explicación, supongo que ambas listas de entrada son infinitas, por lo que no tenemos que perder el control de los 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 desafortunado: ¡la operación de indexación de listas repetidas !! se vuelve más y más caro a medida que avanzamos, dando un rendimiento asintótico bastante malo. Una implementación más eficiente tomará la idea anterior pero la implementará usando cremalleras. Entonces, dividiremos nuestra grilla 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á filas que se han emitido parcialmente pero que contribuirán al resultado; y el rectángulo inferior será 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á la cuadrícula completa. En cada paso, podemos emitir el primer elemento de cada fila en el cuadrilátero superior (esencialmente moviendo la línea inclinada sobre uno), luego agregamos una nueva fila desde el rectángulo inferior al cuadrilátero superior (esencialmente moviendo la línea horizontal hacia abajo por uno )

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 maneja los límites que comprueban que hemos punteado en la versión más simple.

¡Pero no deberías escribir todo este código tú mismo, por supuesto! En su lugar, debe usar el paquete del universe . En Data.Universe.Helpers , hay (+*+) , que empaqueta las funciones 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 puede ver las diagonales en sí mismas si esa estructura se vuelve útil:

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 las choices :: [[a]] -> [[a]] para sus necesidades cartesianas n-dimensionales.

Si sus listas de entrada son del mismo tipo, puede obtener el producto cartesiano de un número arbitrario de listas usando la 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]]

algo como:

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