4

For example, list = [1,2,3,4]. listProduct list returns [1,2,3,4,6,8,9,12,16] i.e [(1*1),(1*2),(1*3),(1*4),(2*3),(2*4),(3*3),(3*4),(4*4)]

I remember seeing that there was something that did this, but I can't find that resource any more.

2
  • 2
    Why does your example not include 2*2 in the result? Perhaps you don't want duplicates. But then why does your example not include 3*3 in the result?
    – dave4420
    Jan 23, 2012 at 6:52
  • THat was a typo, thanks! It's updated now
    – ryanmehta
    Jan 24, 2012 at 1:05

4 Answers 4

9

You can write this in a simple manner using a list comprehension:

listProduct xs = [x * y | x <- xs, y <- xs]

However, it's more idiomatic to use the list monad:

import Control.Monad

listProduct = join $ liftM2 (*)

(equivalent to listProduct xs = liftM2 (*) xs xs)

To understand this version, you can think of liftM2 as a kind of generalised Cartesian product (liftM2 (,) is the Cartesian product itself). It's easier to see how this works if you specialise liftM2's definition to the list monad:

liftM2 f mx my = do { x <- mx; y <- my; return (f x y) }
-- expand the do notation
liftM2 f mx my = mx >>= (\x -> my >>= (\y -> return (f x y)))
-- substitute the list monad's definition of (>>=)
liftM2 f mx my = concatMap (\x -> concatMap (\y -> [f x y]) my) mx
-- simplify
liftM2 f mx my = concatMap (\x -> map (\y -> f x y) my) mx
-- simplify again
liftM2 f mx my = concatMap (\x -> map (f x) my) mx

So the monadic definition of listProduct expands to:

listProduct xs = concatMap (\x -> map (x *) xs) xs

(Note that you don't technically need the full list monad here; all that's required is the Applicative instance for lists, and listProduct = join $ liftA2 (*) would work just as well. However, it's easier to show how it works with the monadic definition, since the Applicative instance for lists is defined in terms of the Monad instance.)

5

Why does your example not include 2*2 in the result?

If it's because it's the same as 1*4 --- that is, you don't want duplicates --- then

listProduct xs = nub [x * y | x <- xs, y <- xs]

On the other hand, if you do want duplicates --- if you want to multiply each number by each subsequent number in the list, and include duplicates in the result --- then

listProduct' xs = triangularAutoZipWith (*)

triangularAutoZipWith op = concatMap f . tails
  where f [] = []
        f xs @ (x : _) = map (op x) xs

You could use triangularAutoZipWith in a more efficient version of the first solution:

listProduct = nub . triangularAutoZipWith (*)
1
  • Thanks. I kind of wanted to avoid using nub. It seems like nub has some serious performance repercussions. Though this does work.
    – ryanmehta
    Jan 24, 2012 at 1:49
5

Using...

import Control.Applicative

... with duplicates ...

listProduct list = (*) <$> list <*> list

... and without...

listProduct list = concat (mul <$> list <*> list) where
    mul a b | a <= b = [a*b]
            | otherwise = []

If you are in rube-goldberg-mood, you could use...

listProduct list = concat $ zipWith (map.(*)) list (map ((`filter` list).(<=)) list) 

... or simply ...

import Data.List

listProduct list = concat $ zipWith (map.(*)) list $ tails list 

[Edit]

Another way would be using sequence. With duplicates:

listProduct = map product . sequence . replicate 2

Without:

listProduct = map product . filter(\[a,b] -> a <= b) . sequence . replicate 2   
1

Well, you've already got a few answers, but I'm going to toss in mine because I think the earlier ones, while all accurate, may be insufficiently helpful.

The easiest solution you've gotten for a beginner to understand is the list comprehension:

example1 = [ x*y | x <- list, y <- list ]

This syntax exists in some popular languages like Python, and should be easy to understand in any case: "the list whose elements are the results of x*y where x is an element of list and y is an element of list." You can also add conditions into list comprehensions to filter out some combinations, e.g., if you don't want products where x == y:

example2 = [ x*y | x <- list, y <- list, x /= y ]

The more complex answers have to do with the fact that list comprehensions are equivalent to the List Monad; the implementation of the standard Monad typeclass for the list type. This means that example1 can also be implemented in these ways:

example1' = do x <- list
               y <- list
               return (x*y)

The do-notation is just syntax sugar for this:

example1'' = list >>= (\x -> list >>= (\y -> return (x*y)))

Landei's answer is based on the fact that if you're not using any conditions in your list comprehension, just Cartesian products, you can get away with using the Applicative type class, which is weaker than Monad.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.