How to list all possible ways to pair up a list?

Admin 1
Viewed 152

I'm new to Haskell and need to list all possible ways to pair up (even) lists of Ints.

E.g.

[1,2,3,4] -> [[(1,2),(3,4)], [(2,3),(1,4)], [(1,3),(2,4)],  ...]

Generating all possible pairs is easy enough (shown below) but I can't work out how to return only ways to pair up the entire input list.

pairs :: [a] -> [[(a, a)]]
pairs l = [(x,y) | (x:ys) <- tails l, y <- ys]
haskell
2 Answers

I recommend writing a function that nondeterministically chooses an element, returning the rest of the values in the list as well. There are a few possible APIs; the one I suggest below is the most general-purpose one, and one I've used on many occasions for apparently unrelated tasks.

zippers :: [a] -> [([a], a, [a])]

Here's an example of what this function does:

> zippers "abcd"
[("", 'a', "bcd"), ("a", 'b', "cd"), ("ba", 'c', "d"), ("cba", 'd', "")]

Once you have that, you can simply repeatedly non-deterministically choose an element from the ever-shrinking list of available options, making a pair after every other choice.

user_7916040

We can make use of a helper function pick that returns a list of 2-tuples with as first element the item picked, and a second element a list of remaining elements:

pick :: [a] -> [(a, [a])]
pick [] = []
pick (x:xs) = (x, xs) : …

where the … part should make a call to pick with the tail of the list, and prepend each second item of the 2-tuples returned with x.

With this pick function we can then construct all combinations with:

pairs :: [a] -> [[(a, a)]]
pairs [] = [[]]
pairs (x:xs) = [(x,y):tl | (y, zs) <- pick xs, tl <- pairs zs]
user_675790
Related