list - sobre - potencia en haskell

Todas las combinaciones de elementos de dos listas en Haskell.

Question

Dadas dos listas, [a, b] y [c, d] , me gustaría obtener el siguiente resultado:

[(a,c), (a,d), (b,c), (b,d)]

¿Cómo puedo hacer esto en Haskell? ¿Hay una función incorporada para esto, o debo implementar una yo mismo?

Answer 1

¡Estilo aplicativo hasta el final!

λ> :m + Control.Applicative
λ> (,) <$> [''a'',''b''] <*> [''c'',''d'']
[(''a'',''c''),(''a'',''d''),(''b'',''c''),(''b'',''d'')]

(He evitado cualquier tipo de azúcar sintáctica de String para permanecer cerca de tu ejemplo).

Para información, (,) es una sintaxis especial para una función que toma dos argumentos y hace un par de ellos:

λ> :t (,)
(,) :: a -> b -> (a, b)

Edición: Como lo señaló sobre su comentario , también puede usar liftA2 :

λ> :m + Control.Applicative
λ> let combine = liftA2 (,)
λ> combine "ab" "cd"
[(''a'',''c''),(''a'',''d''),(''b'',''c''),(''b'',''d'')]

Answer 2

¿Cómo puedes hacer esto en un pseudocódigo imperativo?

for each element x in [a,b]:
for each element y in [c,d]:
produce (x,y)

En Haskell, esto está escrito como

outerProduct xs ys =
do
x <- xs -- for each x drawn from xs:
y <- ys -- for each y drawn from ys:
return (x,y) -- produce the (x,y) pair

(siguiendo los comentarios de leftaroundabout) esto es, por supuesto, muy liftM2 a cómo se define el combinador monádico liftM2 , así que de hecho

outerProduct = liftM2 (,)

que es lo mismo que liftA2 (,) , y sus diferentes reescrituras en términos de comprensión de lista, función concatMap , >>= , <$> y <*> operadores.

Conceptualmente, a pesar de que esta es la materia del Applicative , que se denominaría mejor Pairing , porque este emparejamiento de los elementos de dos "contenedores" "portadores" ⁄ sea lo que sea ​​exactamente de lo que se trata Applicative Functor. Da la casualidad de que la notación do de Haskell funciona para las mónadas y no ( todavía ) para los aplicativos .

En cierto sentido , los bucles anidados en tiempo de compilación son Aplicativos ⁄ Pares de functors; Las mónadas agregan la capacidad de crear bucles anidados sobre la marcha, dependiendo de los valores producidos por una enumeración "externa".

Answer 3

Lo más inuitivo sería usar la comprensión de lista, otros enfoques incluyen el uso de funtores aplicativos:

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

Entonces que hace esto?

Recuerde que (,) :: a -> b -> (a, b) Toma dos argumentos y devuelve una tupla.

<$> es acutally fmap, (<$>) :: Functor f => (a -> b) -> fa -> fb Toma una función y la levanta. En este caso, toma (,) y levántelo para trabajar en la lista. Entonces let x = (,) <$> [1,2] generaría x :: [b -> (Integer, b)] que es la lista de funciones que toma b y devuelve tupla con un argumento fijo (Integer, segundo). Finalmente lo aplicamos usando <*> para generar todas las combinaciones.

Answer 4

utilizar la comprensión de la lista:

s = [a,b]
s'' = [c,d]
all_combinations = [(x,y) | x <- s, y <- s'']

Answer 5

[ (x,y) | x<-[a,b], y<-[c,d] ]

Esto realmente no requiere ninguna explicación adicional, ¿verdad?