This answer has two parts. The first part deals directly with the issue. The second part goes tangentially (literally) to learn the math behind the first part: it may turn out to be difficult material with limited interest, but I thought some extremists might enjoy it.
The answers I've seen so far make careful use of the concepts of a list or their monadic equivalent, but they use equality to exclude duplicates, which requires an additional Eq constraint. Here's a solution that makes all pairs of elements in two different positions.
Firstly, I am writing a convenient function that decorates each element of the list with a list of elements in other positions: all the ways to "choose one and leave the rest." This is very useful when lists are used to collect materials for selection without replacement, and this is what I find, I use a lot.
picks :: [x] -> [(x, [x])] picks [] = [] picks (x : xs) = (x, xs) : [(y, x : ys) | (y, ys) <- picks xs]
Please note that map fst . picks = id map fst . picks = id , so the selected item at each position in the result is an item from that position in the original list: this is what I meant by “decoration”.
Now it’s easy to select two using the same list comprehension method as the other answers. But instead of selecting the first component from the list itself, we can select its picks , while at the same time getting a list of candidates for the second component.
allPairs :: [x] -> [(x, x)] allPairs xs = [(y, z) | (y, ys) <- picks xs, z <- ys]
It's also easy to get triples by picking twice.
allTriples :: [x] -> [(x, x, x)] allTriples ws = [(x, y, z) | (x, xs) <- picks ws, (y, ys) <- picks xs, z <- ys]
For uniformity, it's almost tempting to make the code a little less efficient by writing (z, _) <- picks ys , rather than z <- ys in both.
If there are no duplicates in the input list, you will not get duplicate tuples in the output, because the tuples take their elements from different positions. However you get
Picks> allPairs ["cat", "cat"] [("cat","cat"),("cat","cat")]
To avoid this, feel free to use allPairs . nub allPairs . nub , which removes duplicates before selection and again requires an Eq instance for the item type.
For extremists only: containers, calculus, comonads and combinatorics ahoy!
picks is one example of a more general construction arising from differential calculus. It is a funny fact that for any given cluster form of the functor f its mathematical derivative ∂f represents f structures with one element removed. For example,
newtype Trio x = Trio (x, x, x) -- x^3
has a derivative
data DTrio x = Left3 ((), x, x) | Mid3 (x, (), x) | Right3 (x, x, ()) -- 3*x^2
There may be several operations associated with this design. Imagine that we really can use ∂ (and we can encode it using type families). Then we could say
data InContext fx = (:-) {selected :: x, context :: ∂fx}
to indicate the type of selected items decorated with context. Of course, we should expect that the operation
plug :: InContext fx -> fx -- putting the element back in its place
This plug operation moves us to the root if we get stuck in a tree whose nodes are considered containers of subtrees.
We should also expect that InContext f will be comonad, with
counit :: InContext fx -> x counit = selected
projecting the selected item and
cojoin :: InContext fx -> InContext f (InContext fx)
decorating each element with its context, demonstrating all possible ways of reorienting, choosing another element.
The invaluable Peter Hancock once suggested to me that we should also expect the transition "down" (which means "away from the root"), collecting all possible ways to select an element in context from the whole structure.
picks :: fx -> f (InContext fx)
must decorate every x element in the input f structure with its context. We should expect
fmap selected . picks = id
which was previously law, but also
fmap plug (picks fx) = fmap (const fx) fx
tells us that each decorated element is a decomposition of the original data. We did not have this law above. We had
picks :: [x] -> [(x, [x])]
decorating each element is not quite something like its context: from the entire list of other elements you cannot see where the “hole” is. In truth,
∂[] x = ([x], [x])
splitting the list of elements before the hole from the elements after the hole. Maybe I should have written
picks :: [x] -> [(x, ([x], [x]))] picks [] = [] picks (x : xs) = (x, ([], xs)) : [(y, (x : ys, ys')) | (y, (ys, ys')) <- picks xs]
and this is also a very useful operation.
But what really happens is quite reasonable and only a minor abuse. In the code I originally wrote, I accept locally [] to represent finite sums or unordered lists. Bags are lists with no concept of a specific position, so if you select one item, its context is just a bag of the remaining items. Really
∂Bag = Bag
so the correct concept of picks really
picks :: Bag x -> Bag (x, Bag x)
Introduce Bag to [] and what we had. Moreover, for bags, the plug is simple (:) and, right up to the summation (i.e., permutations), the second law for picks holds.
Another way to look at bags is through a series of power. A bag is a choice of tuples of any size, indicating all possible permutations (n! For size n). Therefore, we can write it combinatorially as a large sum of powers coordinated by factorials, because you must divide by x ^ n by n! to take into account the fact that each of n! orders in which you could choose x give you the same bag.
Bag x = 1 + x + x^2/2! + x^3/3! + ...
So
∂Bag x = 0 + 1 + x + x^2/2! + ...
row offset to the side. Indeed, you could well recognize the power series for Bag as such for exp (or e ^ x), which is famous for its own derivative.
So fu! Like this. The operation, which naturally arises due to the interpretation of the data of an exponential function, which is its own derivative, is a convenient part of the set for solving problems based on selection without replacement.