2

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • You'd have to use `[[Int]]` instead of `[(Int, Int)]`, I think – user Jan 17 '21 at 17:37
  • @user I'm not exactly sure I follow what you mean, sorry im relativley new to haskell –  Jan 17 '21 at 17:39
  • If you want to generalise this to N lists, you won't be able to use tuples because you can't just add an element to a tuple, so you'll need lists. You could perhaps create your own tuple-like construct that you cons and uncons easily, though. (btw this is a cartesian product) – user Jan 17 '21 at 17:44

1 Answers1

2

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

Will Ness
  • 70,110
  • 9
  • 98
  • 181