Produit cartésien de 2 listes en Haskell

Question

Je souhaite réaliser le produit cartésien de 2 listes en Haskell, mais je n'arrive pas à trouver comment le faire. Le produit cartésien donne toutes les combinaisons des éléments de la liste :

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

Il ne s'agit pas d'une vraie question de devoir et elle n'est pas liée à une telle question, mais la façon dont ce problème est résolu peut aider à résoudre un problème sur lequel je suis bloqué.

Answer 1

C'est très facile avec les compréhensions de listes. Pour obtenir le produit cartésien des listes xs y ys nous avons juste besoin de prendre le tuple (x,y) pour chaque élément x en xs et chaque élément y en ys .

Cela nous donne la liste de compréhension suivante :

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

Answer 2

Comme d'autres réponses l'ont noté, l'utilisation d'une liste de compréhension est la façon la plus naturelle de le faire en Haskell.

Si vous apprenez Haskell et que vous souhaitez développer des intuitions sur les classes de types telles que Monad Cependant, c'est un exercice amusant que de comprendre pourquoi cette définition légèrement plus courte est équivalente :

import Control.Monad (liftM2)

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

Vous ne voudrez probablement jamais écrire cela dans du code réel, mais l'idée de base est quelque chose que vous verrez en Haskell tout le temps : nous utilisons liftM2 pour lever la fonction non monadique (,) dans une monade, dans ce cas précis la monade liste.

Si cela n'a aucun sens ou n'est pas utile, oubliez-le - c'est juste une autre façon d'aborder le problème.

Answer 3

Si vos listes d'entrée sont du même type, vous pouvez obtenir le produit cartésien d'un nombre arbitraire de listes en utilisant sequence (en utilisant le List monade). Vous obtiendrez ainsi une liste de listes au lieu d'une liste de tuples :

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

Answer 4

Il existe une manière très élégante de le faire avec les foncteurs applicatifs :

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

L'idée de base est d'appliquer une fonction sur des arguments "enveloppés", par ex.

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

Dans le cas des listes, la fonction sera appliquée à toutes les combinaisons, il suffit donc de les "tupler" avec (,) .

Voir http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors ou (plus théorique) http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf pour les détails.

Answer 5

La bonne façon de procéder est d'utiliser les compréhensions de listes, comme d'autres personnes l'ont déjà souligné, mais si vous voulez le faire sans utiliser les compréhensions de listes pour quelque raison que ce soit, vous pouvez faire ceci :

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