Produit cartésien de 2 listes dans Haskell

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

Si vous apprenez Haskell et que vous voulez travailler sur le développement d'intuitions sur les classes de type comme Monad, cependant, c'est un exercice amusant pour 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 voudriez probablement jamais écrire ceci en code réel, mais l'idée de base est quelque chose que vous verrez dans Haskell tout le temps: nous utilisons liftM2 pour soulever le fonction non monadique (,) dans une monade-dans ce cas spécifiquement la monade de liste.

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

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 la monade List). Ainsi, vous obtenez 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]]

Il existe une façon 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 exemple

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

Dans le cas des listes, la fonction sera appliquée à toutes les combinaisons, donc tout ce que vous avez à faire est de les "tuple" 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 plus de détails.

La bonne façon est d'utiliser les compréhensions de liste, comme d'autres l'ont déjà souligné, mais si vous vouliez le faire sans utiliser les compréhensions de liste pour une raison quelconque, alors vous pouvez le faire:

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

Une autre façon d'y parvenir est d'utiliser des applicatifs:

import Control.Applicative

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

Encore une autre façon, en utilisant la notation do:

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

D'autres réponses supposent que les deux listes d'entrée sont finies. Souvent, le code idiomatique Haskell inclut des listes infinies, et il est donc utile de commenter brièvement la façon de produire un produit cartésien infini au cas où cela serait nécessaire.

L'approche standard consiste à utiliser la diagonalisation; en écrivant une entrée le long du haut et l'autre entrée le long de la gauche, nous pourrions écrire une table à deux dimensions contenant le produit cartésien complet comme ceci:

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

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

Bien sûr, travailler sur n'importe quelle ligne nous donnera infiniment des éléments avant d'atteindre la ligne suivante; de même, aller en colonne serait désastreux. Mais nous pouvons suivre des diagonales qui descendent et à gauche, en repartant un peu plus loin vers la droite chaque fois que nous atteignons le bord de la grille.

a1

   a2
b1

      a3
   b2
c1

         a4
      b3
   c2
d1

...et ainsi de suite. Dans l'ordre, cela nous donnerait:

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

Pour coder cela dans Haskell, nous pouvons d'abord écrire la version qui produit la table à deux dimensions:

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

Un la méthode inefficace de diagonalisation consiste à itérer d'abord le long des diagonales, puis le long de la profondeur de chaque diagonale, en retirant l'élément approprié à chaque fois. Pour simplifier l'explication, je suppose que les deux listes d'entrée sont infinies, donc nous n'avons pas à jouer avec la vérification des limites.

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

Cette implémentation est un peu malheureuse: l'opération d'indexation de liste répétée {[9] } devient de plus en plus coûteuse au fur et à mesure, donnant une assez mauvaise performance asymptotique. Un plus une mise en œuvre efficace prendra l'idée ci-dessus mais l'implémentera en utilisant des fermetures à glissière. Donc, nous allons diviser notre grille infinie en trois formes comme ceci:

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

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

Le triangle supérieur gauche sera les bits que nous avons déjà émis; le quadrilatère supérieur droit sera des lignes qui ont été partiellement émises mais qui contribueront toujours au résultat; et le rectangle inférieur sera des lignes que nous n'avons pas encore commencé à émettre. Pour commencer, le triangle supérieur et supérieur quadrilatère sera vide, et le rectangle du bas sera la grille entière. À chaque étape, nous pouvons émettre le premier élément de chaque rangée dans le quadrilatère supérieur( déplaçant essentiellement la ligne inclinée par un), puis Ajouter une nouvelle rangée du rectangle inférieur au quadrilatère supérieur (déplaçant essentiellement la ligne horizontale par un).

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]

Bien que cela semble un peu plus compliqué, il est nettement plus efficace. Il gère également les limites en vérifiant que nous avons pointé dans le plus simple version.

Mais vous ne devriez pas écrire tout ce code vous-même, bien sûr! Au lieu de cela, vous devriez utiliser le paquetuniverse . Dans Data.Universe.Helpers, Il y a (+*+), quels paquets ensemble les fonctions cartesian2d et diagonal ci-dessus pour donner juste le fonctionnement du produit cartésien:

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

Vous pouvez également voir les diagonales elles-mêmes si cette structure devient utile:

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 vous avez plusieurs listes à produire ensemble, itérer (+*+) peut injustement biaiser certaines listes; vous pouvez utiliser choices :: [[a]] -> [[a]] pour vos besoins de produits cartésiens à n Dimensions.

Eh bien, un moyen très facile de le faire serait avec des compréhensions de liste:

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

Ce que je suppose est la façon dont je ferais cela, bien que je ne sois pas un expert Haskell (par tous les moyens).

Quelque Chose comme:

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

C'est un travail pour sequenceing. Une implémentation monadique de celui-ci pourrait être:

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

Comme vous pouvez le remarquer, ce qui précède ressemble à l'implémentation de map par des fonctions pures mais de type monadique. En conséquence, vous pouvez le simplifier jusqu'à

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

Voici ma mise en œuvre du produit cartésien n-ary:

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

Il suffit D'ajouter un moyen de plus pour l'enthousiaste, en utilisant uniquement la correspondance de motif récursif.

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