Admin
1
In order to combine 2 lists the following code could be used.
[(x,y) | x <- [1, 2, 3], y <- [4, 5, 6]]
Or
(,) <$> [1,2,3] <*> [4,5,6]
Which produce
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
How could this be done where given a list of N lists rather than 2 lists they would be combined in such a way?
Preferebly using list comprehenison if possible as I find it the easiest to interpret.
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a) does that:
> 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]]
> sequence [[1,2,3] , [4,5,6] , [7]]
[[1,4,7],[1,5,7],[1,6,7],[2,4,7],[2,5,7],[2,6,7],[3,4,7],[3,5,7],[3,6,7]]
There's no arbitrary-length tuples in Haskell though, so lists must be used to collect the resulting "tuples", instead.
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a) is actually enough here, but lists' applicative functors and monads are the same, so it doesn't matter.
If any of the lists could be infinite, some diagonalization scheme must be employed if more fair enumeration is desired (see e.g. Cartesian product of infinite lists in Haskell etc.).
To implement it yourself, recursion must be employed,
ncart :: [[a]] -> [[a]]
ncart (xs:t) = [ x:r | x <- xs, r <- ncart t]
ncart [] = [[]]
(but see haskell running out of memory with finite lists for an important discussion).
