How can I multiply the elements of a list by all the other elements?

Question

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.

Answer 1

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