Haskell: List combination for Integers

Question

I have a given list, e.g. [2, 3, 5, 587] and I want to have a complete list of the combination. So want something like [2, 2*3,2*5, 2*587, 3, 3*5, 3*587, 5, 5*587, 587]. Since I am on beginner level with Haskell I am curious how a list manipulation would look like.

Additionally I am curious if the computation of the base list might be expensive how would this influence the costs of the function? (If I would assume the list has limit values, i.e < 20)

Rem.: The order of the list could be done afterwards, but I have really no clue if this is cheaper within the function or afterwards.

Answer 1

The others have explained how to make pairs, so I concern myself here with getting the combinations.

If you want the combinations of all lengths, that's just the power set of your list, and can be computed the following way:

powerset :: [a] -> [[a]]
powerset (x:xs) = let xs' = powerset xs in xs' ++ map (x:) xs'
powerset []     = [[]]

-- powerset [1, 2] === [[],[2],[1],[1,2]]
-- you can take the products:
-- map product $ powerset [1, 2] == [1, 2, 1, 2]

There's an alternative powerset implementation in Haskell that's considered sort of a classic:

import Control.Monad

powerset = filterM (const [True, False])

You could look at the source of filterM to see how it works essentially the same way as the other powerset above.

On the other hand, if you'd like to have all the combinations of a certain size, you could do the following:

combsOf :: Int -> [a] -> [[a]]
combsOf n _ | n < 1 = [[]]
combsOf n (x:xs)    = combsOf n xs ++ map (x:) (combsOf (n - 1) xs)
combsOf _ _         = []

-- combsOf 2 [1, 2, 3] === [[2,3],[1,3],[1,2]]

Answer 2

So it seems what you want is all pairs of products from the list:

ghci> :m +Data.List
ghci> [ a * b | a:bs <- tails [2, 3, 5, 587], b <- bs ]
[6,10,1174,15,1761,2935]

But you also want the inital numbers:

ghci> [ a * b | a:bs <- tails [2, 3, 5, 587], b <- 1:bs ]
[2,6,10,1174,3,15,1761,5,2935,587]

This uses a list comprehension, but this could also be done with regular list operations:

ghci> concatMap (\a:bs -> a : map (a*) bs) . init $ tails [2, 3, 5, 587]
[2,6,10,1174,3,15,1761,5,2935,587]

The latter is a little easier to explain:

• Data.List.tails produces all the suffixes of a list:

  ghci> tails [2, 3, 5, 587]
  [[2,3,5,587],[3,5,587],[5,587],[587],[]]
  

• Prelude.init drops the last element from a list. Here I use it to drop the empty suffix, since processing that causes an error in the next step.

  ghci> init [[2,3,5,587],[3,5,587],[5,587],[587],[]]
  [[2,3,5,587],[3,5,587],[5,587],[587]]
  
  ghci> init $ tails [2, 3, 5, 587]
  [[2,3,5,587],[3,5,587],[5,587],[587]]
  

• Prelude.concatMap runs a function over each element of a list, and combines the results into a flattened list. So

  ghci> concatMap (\a -> replicate a a) [1,2,3]
  [1, 2, 2, 3, 3, 3]
  

• \(a:bs) -> a : map (a*) bs does a couple things.

  1. I pattern match on my argument, asserting that it matches an list with at least one element (which is why I dropped the empty list with init) and stuffs the initial element into a and the later elements into bs.
  2. This produces a list that has the same first element as the argument a:, but
  3. Multiplies each of the later elements by a (map (a*) bs).

Answer 3

You can get the suffixes of a list using Data.List.tails. This gives you a list of lists, you can then do the inner multiplications you want on this list with a function like:

prodAll [] = []
prodAll (h:t) = h:(map (* h) $ t)

You can then map this function over each inner list and concatenate the results:

f :: Num a => [a] -> [a]
f = concat . map prodAll . tails