CODEWITHSUNDEEP
haskell
ryanmehta
ryanmehta

Reputation: 344

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

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.

Upvotes: 4

Views: 3714

Answers (4)

Landei
Landei

Reputation: 54574

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

Upvotes: 5

Luis Casillas
Luis Casillas

Reputation: 30227

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.

Upvotes: 1

ehird
ehird

Reputation: 40787

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

Upvotes: 9

dave4420
dave4420

Reputation: 47052

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 (*)

Upvotes: 5

Related Questions