Recursively recursive Haskell product
I know how to use a list comprehension to do this, but how can I implement a function that will recursively calculate the Cartesian product given by two sets?
Here's where I'm stuck (and I'm noob)
crossProd :: [Int] -> [Int] -> [(Int,Int)]
crossProd xs ys | xs == [] || ys == [] = []
| otherwise = (head xs, head ys) : crossProd (tail xs) (ys)
The result of this gives me
[(1.4), (1.5), (1.6)]
If sets [1,2,3]
and [4,5,6]
respectively. How can I get the rest?
I only know guard
and if then else
, therefore, please, with me.
source to share
This can be done in one function:
crossProd :: [a] -> [b] -> [(a, b)]
crossProd (x:xs) ys = map (\y -> (x, y)) ys ++ crossProd xs ys
crossProd _ _ = []
Note that I've generalized your types so that this works for any a
and b
, not just Int
s.
The key to this function is understanding that you want to concatenate every item in the first list with every item in the second. So this solution takes one element x
from the first list and matches it against each one in ys
. This is done by mapping a function that takes each value y
from ys
and turns it into a pair (x, y)
. We'll add this to the beginning of the recursion with the rest of the list xs
.
In the basic case, the pair has nothing to lie, so the output is empty.
source to share