All picks of a list in F# - more elegant and simple

Question

Could someone propose better and/or more elegant implementation of this:

let each xs = 
    let rec each' acc left right = 
        match right with
        | [] -> acc
        | right ->  let new_left  = left @ [List.hd right]
                    let next   = List.tl right
                    let result = (List.hd right), left @ next
                    each' (result::acc) new_left next
    each' [] [] xs

It do that:

> each [1..3];;
val it : (int * int list) list = [(3, [1; 2]); (2, [1; 3]); (1, [2; 3])]

This function could return the result in reverse direction, too. The idea is to get all elements as tuples with an element and list of rest elements.

Answer 1

The semantic is slightly different here, but from the example you give Set might be a good fit:

let each xs =
    let X = set xs                           
    [ for x in xs -> (x, X - set [x]) ]


> fsi.AddPrinter( fun (x:Set<int>) -> sprintf "%A" (Set.to_list x))
> each [1..3];;
> val it : (int * Set<int>) list = [(1, [2; 3]); (2, [1; 3]); (3, [1; 2])]

// Edited as per comments.

Answer 2

How about:

let rec each = function
| x :: xs -> (x,xs) :: (each xs |> List.map (fun (y,ys) -> (y,x::ys)))
| [] -> []

Or a tail recursive equivalent (producing the lists in reverse order):

let each lst =
  let rec helper acc seen = function
  | [] -> acc
  | x :: xs -> 
      helper ((x,seen)::(acc |> List.map (fun (y,ys) -> (y,x::ys)))) (x::seen) xs
  helper [] [] lst

Answer 3

let each l = l |> List.map (fun x -> x, List.filter (fun y -> y <> x) l)

Note: this function is O(n^2). Consider using Seq.map and Seq.filter instead:

let each l = l |> Seq.map (fun x -> x, Seq.filter (fun y -> y <> x) l)

Seq version has a performance of O(n).

Answer 4

This is not much better, if any, than the original solution, but here it goes. This version avoids the list appends by using a utility function to merge the reversed left list with the tail of the right. Also, it uses pattern matching instead of the head and tail functions.

let rec ljoin revleft right =  
  match revleft with 
       | [] -> right 
       | (x::xs) -> ljoin xs (x::right)                                                                                   
let each xs =
    let rec each' acc left right =
       match right with
       | [] -> acc
       | (y::ys) ->
           let result = y, ljoin left ys 
           each' (result::acc) (y::left) ys
    each' [] [] xs

Answer 5

Other proposition of mine using Fold. It is linear function O(N). But definitely not so elegant and simple as DannyAsher's solution:

let each5 xs =  let fu (left, next, acc) x = left@[x], List.tl next, (x, left@(List.tl next))::acc
                let (x, y, res) = List.fold fu ([], xs, []) xs
                res