F# return element pairs in list

Question

I have been looking for an elegant way to write a function that takes a list of elements and returns a list of tuples with all the possible pairs of distinct elements, not taking into account order, i.e. (a,b) and (b,a) should be considered the same and only one of them be returned. I am sure this is a pretty standard algorithm, and it's probably an example from the cover page of the F# documentation, but I can't find it, not even searching the Internet for SML or Caml. What I have come up with is the following:

let test = [1;2;3;4;5;6]

let rec pairs l = 
    seq { 
        match l with
        | h::t -> 
            yield! t |> Seq.map (fun elem -> (h, elem))
            yield! t |> pairs
        | _ -> ()
        }

test |> pairs |> Seq.toList |> printfn "%A"

This works and returns the expected result [(1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (2, 3); (2, 4); (2, 5); (2, 6); (3, 4); (3, 5); (3, 6); (4, 5); (4, 6); (5, 6)] but it looks horribly unidiomatic. I should not need to go through the sequence expression and then convert back into a list, there must be an equivalent solution only involving basic list operations or library calls...

Edited:

I also have this one here

let test = [1;2;3;4;5;6]

let rec pairs2 l =
    let rec p h t =
        match t with
        | hx::tx -> (h, hx)::p h tx
        | _ -> []
    match l with
    | h::t -> p h t @ pairs2 t
    | _ -> []


test |> pairs2 |> Seq.toList |> printfn "%A"

Also working, but like the first one it seems unnecessarily involved and complicated, given the rather easy problem. I guess my question is mor about style, really, and if someone can come up with a two-liner for this.

Answer 1

I think that your code is actually pretty close to an idiomatic version. The only change I would do is that I would use for in a sequence expression instead of using yield! in conjunction with Seq.map. I also usually format code differently (but that's just a personal preference), so I would write this:

let rec pairs l = seq {  
    match l with 
    | h::t -> for e in t do yield h, elem
              yield! pairs t
    | _ -> () } 

This is practically the same thing as what Brian posted. If you wanted to get a list as the result then you could just wrap the whole thing in [ ... ] instead of seq { ... }.

However, this isn't actually all that different - under the cover, the compiler uses a sequence anyway and it just adds conversion to a list. I think that it may be actually a good idea to use sequences until you actually need a list (because sequences are evaluated lazilly, so you may avoid evaluating unnecessary things).

If you wanted to make this a bit simpler by abstracting a part of the behavior into a separate (generally useful) function, then you could write a function e.g. splits that returns all elements of a list together with the rest of the list:

let splits list = 
  let rec splitsAux acc list =
    match list with 
    | x::xs -> splitsAux ((x, xs)::acc) xs
    | _ -> acc |> List.rev
  splitsAux [] list

For example splits [ 1 .. 3 ] would give [(1, [2; 3]); (2, [3]); (3, [])]. When you have this function, implementing your original problem becomes much easier - you can just write:

[ for x, xs in splits [ 1 .. 5] do
    for y in xs do yield x, y ]

As a guide for googling - the problem is called finding all 2-element combinations from the given set.

Answer 2

Here's one way:

let rec pairs l =
    match l with
    | [] | [_] -> []
    | h :: t -> 
        [for x in t do
            yield h,x
         yield! pairs t]
let test = [1;2;3;4;5;6] 
printfn "%A" (pairs test)