Generating combinations

Have you ever needed to generate the Cartesian product of some things? Let’s use the term combination to mean an element from the Cartesian product. In imperative languages generating combinations always seemed like a pain to me. We are going to explore how Haskell can make combination generation easier.

First, write this function:

allPairs :: [a] -> [b] -> [(a,b)]

This function should generate all possible pairs of items from each of the two input lists. This means it should NOT have this behavior:

allPairs [1,2,3] [4,5,6] == [(1,4),(2,5),(3,6)]

That’s the zip function and it’s not what we are looking for here. Instead, your function should generate this:

allPairs [1,2] [3,4] == [(1,3),(1,4),(2,3),(2,4)]

Here is another test case:

allPairs [1..3] [6..8] == [(1,6),(1,7),(1,8),(2,6),(2,7),(2,8),(3,6),(3,7),(3,8)]

Note that because of the way we set up the project template you cannot use list comprehensions to solve this. That’s intentional. You should solve it with explicit recursion.

Previous Page - Next Page