Cartesian product set generation-CodePudding

I am trying to create a Haskell function to generate a Cartesian product of two lists

Here's my attempt:

cartesianProduct :: (a -> b -> c) -> [a] -> [b] -> [c]
cartesianProduct f x [] = x
cartesianProduct f y [] = y
cartesianProduct = f x y unionHelper func1 f xs ys

CodePudding user response：

If you're in a hurry, then the function is called liftA2 and it's actually built-in.

sort $ liftA2 (*) [1,2,4] [1,3,9] -- [1,2,3,4,6,9,12,18,36]

But, of course, that's not very enlightening, so let's talk about how we might do it ourselves.

The list type, [], is a functor. We can implement fmap directly using recursion.

fmap :: (a -> b) -> [a] -> [b]
fmap _ [] = []
fmap f (x:xs) = f x : fmap f xs

Now we have a way of to do something for each element of a list. Great, that's how we'll apply our final operation, but we need to generate all of the argument lists as well. Specifically, we want to produce the Cartesian product.

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

And we can do so recursively as well, using our fmap function to help out.

cross :: [a] -> [b] -> [(a, b)]
cross [] _ = []
cross (x:xs) ys = fmap ((,) x) ys    cross xs ys

Recursion on the first element. If the first argument is empty, then the Cartesian product is empty. If the first argument is nonempty, then the result should consist of the head paired with each (via fmap) element of the second argument, followed by the Cartesian product of the tail with the second list.

Now we have a way to get a [(Int, Int)]. And we want to multiply those elements, so it's just a matter of tying it all together.

apply2 :: (a -> b -> c) -> [a] -> [b] -> [c]
apply2 f xs ys = fmap (\(x, y) -> f x y) $ cross xs ys

Take the Cartesian product of the two lists, then apply our function f (uncurried) to each element.

This gives us our result, in a slightly different order than in your example. But it looks like you're sorting the results anyway, rather than producing them in an algorithmic order.

sort $ apply2 (*) [1,2,4] [1,3,9] -- [1,2,3,4,6,9,12,18,36]

Now, let's talk about why liftA2 works. The list type is an example of an applicative functor, represented by the Applicative typeclass. Whereas fmap (which is part of Functor) takes a single function and maps it over a functor (in our case, over several elements of a list), the fundamental applicative operation is <*> (pronounced "ap"), whose signature is

fmap  :: Functor f     =>   (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

Instead of mapping a single simple function over a functor value f a, we're mapping a function inside the functor f (a -> b) over a value also inside the functor f a. Now, this is a jumble of words, but in the case of lists it looks like

fmap  :: (a -> b) -> [a] -> [b]
(<*>) :: [a -> b] -> [a] -> [b]

Rather than applying a single function to several elements, we're applying several functions to several elements. (<*>) is actually just our cross function written in a slightly different way. It's combining two lists using every combination to produce a result of some type. (In fact, the relationship between our cross and the applicative (<*>) is rather deep mathematically, due to the fact that (->) and (,) are adjoint to each other, but that's getting off track)

So (<*>) is just cross by another name. And liftA2 is defined as (something equivalent to)

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 f a b = fmap f a <*> b

It's just doing fmap and (<*>), which is basically what our apply2 function was doing to begin with. Again, it's slightly shuffled around since we're using (->) rather than (,) (since our "ap" operator applies a function rather than building a tuple), but it's exactly the same idea.

Certainly, the liftA2 approach is snazzy and short, but don't let it blind you. There's nothing wrong with a recursive approach, especially as you're learning. If apply2 makes more sense to you and my explanation above of the applicative functors was nonsense, then go for it. You can go a long way in Haskell learning about recursion and data structures before really grokking functors, and that's fine. But when you're ready, I recommend Typeclassopedia for an excellent summary of the Haskell typeclasses that represent functors, applicative functors, monads, and all of the other lesser-known abstractions available to the programmer.

Good luck, and happy coding!