F # returns pairs of items in a list

Question

I was looking for an elegant way to write a function that takes a list of elements and returns a list of tuples with all possible pairs of individual elements, not taking into account the order, i.e. (a, b) and (b, a) should be considered the same, and only one of them should be returned. I am sure that this is a fairly standard algorithm, and this is probably an example from the title page of the F # documentation, but I can’t find it, I don’t even search the Internet for SML or Caml. I came up with 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); (13); (fourteen); (fifteen); (16); (2, 3); (2, 4); (2, 5); (2, 6); (3, 4); (3, 5); (3, 6); (4, 5); (4, 6); (5, 6)], but it looks terribly uniomatic. I do not need to go through the sequence expression and then convert back to a list, there should be an equivalent solution that includes only operations with the base list or library calls ...

Edited by:

I also have this

 let test = [1;2;3;4;5;6] let rec pairs2 l = let rec pht = match t with | hx::tx -> (h, hx)::ph tx | _ -> [] match l with | h::t -> pht @ pairs2 t | _ -> [] test |> pairs2 |> Seq.toList |> printfn "%A" 

It also works, but, like the first, it seems overly involved and complicated, given the rather light problem. To my question, in fact, my question is about style, and if someone can come up with a two-liner for this.

Answer 1

Here is 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) 

Answer 2

I think your code is actually pretty close to the idiomatic version. The only change I would make is that I would use for in a sequence expression instead of using yield! in combination with Seq.map . I also usually format the code in different ways (but this is only a personal preference), so I would write the following:

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

It’s almost the same as Brian. If you want to get the list as a result, you can simply wrap it all in [ ... ] instead of seq { ... } .

However, in reality this is not so much - under the cover, the compiler still uses the sequence, and it simply adds the conversion to the list. I think it may actually be a good idea to use sequences until you need a list (because sequences are evaluated by lazilly, so you can avoid evaluating unnecessary things).

If you want to make this a little easier, abstracting part of the behavior into a separate (usually useful) function, you can write a function, for example. splits , which returns all list items along 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 ] will give [(1, [2; 3]); (2, [3]); (3, [])]. When you have this function, implementing the original problem becomes much simpler - you can simply 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 a given set.

Answer 3

You seem to shake too much. Why even use seq if you need a list? What about

 let rec pairs lst = match lst with | [] -> [] | h::t -> List.map (fun elem -> (h, elem)) t @ pairs t let _ = let test = [1;2;3;4;5;6] printfn "%A" (pairs test)