CODEWITHSUNDEEP
listhaskell
megabowser56
megabowser56

Reputation: 47

Getting combination pairs of list elements

I am trying to get all combinations of a list. The result for [1,2,3] should be [(1,2),(1,3),(2,3)]. My implementation below, however, gives [(1,2),(2,3)].

parings [d] = []
parings (y:ys) = (y, head ys): parings ys

Upvotes: 1

Views: 266

Answers (3)

duplode
duplode

Reputation: 34378

Here is one implementation using tails from Data.List:

import Data.List

pairings :: [a] -> [(a, a)]
pairings = concatMap makePairs . tails
    where
    makePairs [] = []
    makePairs (x:xs) = fmap ((,) x) xs

Notes:

  • I don't know whether tails counts as a "special import" for you -- though it is not in the Prelude, it can be found in the base library, which is always available.

  • To see what tails does, try tails [1..3].

  • ((,) x) is just a compact way of writing (\y -> (x, y)). If you find it ugly, you can write the longer version instead, or enable the TupleSections extension and spell it as (x,).

  • makePairs might be written without explicit recursion as...

    makePairs = maybe [] (\(x, xs) -> fmap ((,) x) xs) . uncons

    ... with uncons also being found in Data.List.

  • All the implementations in the answers here have a not insignificant problem: they retain consumed list segments in memory. To see what I'm talking about, watch the memory usage as you run head . drop 8000000 $ pairings [1..] in GHCi. I'm not confident about there being a workaround for that -- a simple concat . tails, for instance, appears to run into the same issue, while fmap makePairs . tails doesn't (even head . drop (10^9) . head . drop (10^9) . fmap makePairs . tails $ [1..] won't eat up all your memory).

Upvotes: 1

Silvio Mayolo
Silvio Mayolo

Reputation: 70267

The list comprehension mentioned in 9000's answer can be trivially factored into a map call.

pairwise :: [a] -> [(a, a)]
pairwise [] = []
pairwise (x:xs) = map (\y -> (x, y)) xs ++ pairwise xs

Every list comprehension can be factored into some combination of map, filter, and concatMap, possibly with some let bindings interspersed. Doing so is a good exercise for learning how to manipulate functions.

Upvotes: 3

9000
9000

Reputation: 40884

I don't know why you're opposed to list comprehensions; with them, the solution is trivial:

pairwise :: [a] -> [(a, a)]
pairwise [] = []
pairwise (x:xs) = [(x, y) | y <- xs] ++ pairwise xs

You can factor out the comprehension into a separate function with explicit tail recursion if you want.

(The whole thing can be made tail-recursive, too, by keeping parameters for both sides of the ++ and having an accumulator parameter.)

Upvotes: 1

Related Questions