Cartesian product of 2 lists in Haskell
Solution 1
This is very easy with list comprehensions. To get the cartesian product of the lists xs
and ys
, we just need to take the tuple (x,y)
for each element x
in xs
and each element y
in ys
.
This gives us the following list comprehension:
cartProd xs ys = [(x,y) | x <- xs, y <- ys]
Solution 2
As other answers have noted, using a list comprehension is the most natural way to do this in Haskell.
If you're learning Haskell and want to work on developing intuitions about type classes like Monad
, however, it's a fun exercise to figure out why this slightly shorter definition is equivalent:
import Control.Monad (liftM2)
cartProd :: [a] -> [b] -> [(a, b)]
cartProd = liftM2 (,)
You probably wouldn't ever want to write this in real code, but the basic idea is something you'll see in Haskell all the time: we're using liftM2
to lift the non-monadic function (,)
into a monad—in this case specifically the list monad.
If this doesn't make any sense or isn't useful, forget it—it's just another way to look at the problem.
Solution 3
If your input lists are of the same type, you can get the cartesian product of an arbitrary number of lists using sequence
(using the List
monad). This will get you a list of lists instead of a list of 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]]
Solution 4
There is a very elegant way to do this with Applicative Functors:
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)]
The basic idea is to apply a function on "wrapped" arguments, e.g.
(+) <$> (Just 4) <*> (Just 10)
-- Just 14
In case of lists, the function will be applied to all combinations, so all you have to do is to "tuple" them with (,)
.
See http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors or (more theoretical) http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf for details.
Solution 5
Other answers assume that the two input lists are finite. Frequently, idiomatic Haskell code includes infinite lists, and so it is worthwhile commenting briefly on how to produce an infinite Cartesian product in case that is needed.
The standard approach is to use diagonalization; writing the one input along the top and the other input along the left, we could write a two-dimensional table that contained the full Cartesian product like this:
1 2 3 4 ...
a a1 a2 a3 a4 ...
b b1 b2 b3 b4 ...
c c1 c2 c3 c4 ...
d d1 d2 d3 d4 ...
. . . . . .
. . . . . .
. . . . . .
Of course, working across any single row will give us infinitely elements before it reaches the next row; similarly going column-wise would be disastrous. But we can go along diagonals that go down and to the left, starting again in a bit farther to the right each time we reach the edge of the grid.
a1
a2
b1
a3
b2
c1
a4
b3
c2
d1
...and so on. In order, this would give us:
a1 a2 b1 a3 b2 c1 a4 b3 c2 d1 ...
To code this in Haskell, we can first write the version that produces the two-dimensional table:
cartesian2d :: [a] -> [b] -> [[(a, b)]]
cartesian2d as bs = [[(a, b) | a <- as] | b <- bs]
An inefficient method of diagonalizing is to then iterate first along diagonals and then along depth of each diagonal, pulling out the appropriate element each time. For simplicity of explanation, I'll assume that both the input lists are infinite, so we don't have to mess around with bounds checking.
diagonalBad :: [[a]] -> [a]
diagonalBad xs =
[ xs !! row !! col
| diagonal <- [0..]
, depth <- [0..diagonal]
, let row = depth
col = diagonal - depth
]
This implementation is a bit unfortunate: the repeated list indexing operation !!
gets more and more expensive as we go, giving quite a bad asymptotic performance. A more efficient implementation will take the above idea but implement it using zippers. So, we'll divide our infinite grid into three shapes like this:
a1 a2 / a3 a4 ...
/
/
b1 / b2 b3 b4 ...
/
/
/
c1 c2 c3 c4 ...
---------------------------------
d1 d2 d3 d4 ...
. . . . .
. . . . .
. . . . .
The top left triangle will be the bits we've already emitted; the top right quadrilateral will be rows that have been partially emitted but will still contribute to the result; and the bottom rectangle will be rows that we have not yet started emitting. To begin with, the upper triangle and upper quadrilateral will be empty, and the bottom rectangle will be the entire grid. On each step, we can emit the first element of each row in the upper quadrilateral (essentially moving the slanted line over by one), then add one new row from the bottom rectangle to the upper quadrilateral (essentially moving the horizontal line down by one).
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]
Although this looks a bit more complicated, it is significantly more efficient. It also handles the bounds checking that we punted on in the simpler version.
But you shouldn't write all this code yourself, of course! Instead, you should use the universe package. In Data.Universe.Helpers
, there is (+*+)
, which packages together the above cartesian2d
and diagonal
functions to give just the Cartesian product operation:
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)]
You can also see the diagonals themselves if that structure becomes useful:
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)]
If you have many lists to product together, iterating (+*+)
can unfairly bias certain lists; you can use choices :: [[a]] -> [[a]]
for your n-dimensional Cartesian product needs.
Related videos on Youtube
Callum Rogers
I am interested in Functional Programming, Compilers, Programming Languages, Interpreters and Reactive Programming. Github
Updated on July 05, 2022Comments
-
Callum Rogers almost 2 years
I wish to produce the Cartesian product of 2 lists in Haskell, but I cannot work out how to do it. The cartesian product gives all combinations of the list elements:
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)]
This is not an actual homework question and is not related to any such question, but the way in which this problem is solved may help with one I am stuck on.
-
Chuck over 13 yearsAn easier way without list comprehensions is
cartProd xs ys = xs >>= \x -> ys >>= \y -> [(x,y)]
-
Callum Rogers over 13 yearsProbably a good idea to learn what monads actually do first :P
-
Yitz over 13 yearsInstead of
map (\y -> (x,y))
you can writemap ((,) x)
. -
Callum Rogers over 13 yearsThanks, so simple yet elegant, really helped with the other problem :)
-
Stuart Golodetz over 13 years@Chuck: Nice :) It's been a while for me Haskell-wise, which is why I err on the side of simplistic solutions...
-
Stuart Golodetz over 13 years@Yitz: Yup, good call. I'd forgotten about that (see above on the "it's been a while")...
-
Dacav over 12 yearsGood also for Erlang, thanks. Little changing in syntax: cartProd(Xs, Ys) -> [{X,Y} || X <- Xs, Y <- Ys].
-
Travis Brown over 10 yearsAs a footnote (three years later): I'd guess now that I originally used the monadic
liftM2
here for the sake of clarity (more people have heard about monads than applicative functors?), but all you need is the applicative functor instance for lists, soliftA2
will work equivalently. -
Daniel Wagner almost 8 yearsHow about
crossProduct = sequence
? -
Landon Poch over 7 years@Stuart List comprehensions may be the "right way" but is there really any downside to doing it this way? Seems fine to me, and it helps a beginner wrap their minds around a simple implementation of cartesian products. +1
-
Landon Poch over 7 years@Stuart I guess maybe the issue with this implementation is how do you flatten it if you need to take the product of 3 or more lists. I can see the hint of a monad here.
-
Landon Poch over 7 yearsPretty cool that you can actually expand the tuple as needed: (,,) <$> [1..3] <*> [4..6] <*> [7..9]
-
dfeuer over 6 yearsWhat if the list is empty? I'm guessing you identified the wrong base case here.
-
fp_mora almost 5 yearsI just installed Universe-1.1 and It is fabulous. Thank you so very much. Yeah, your name is all over it so we know to trust it. The value is uncalculable. I was doing diagonals and these initial results look spot-on. Cartesian products are a pain but you are a pain killer. Thank you again.
-
Daniel Wagner almost 5 years@fp_mora Glad to hear you're enjoying it!
-
fp_mora almost 5 years@Daniel Wagner It is a godsend. I was not clear. It's the infinite lists that are a pain. You handle them adroitly.