combinations of a list with Sequence

combinations.ml

#require "sequence";;

open Sequence.Infix;;

(* all the combinations *)
let rec combs = function
| [] -> Sequence.return []
| x :: tail ->
  Sequence.append (combs tail) (combs tail >|= fun l -> x :: l);;

combs [1;2;3;4] |> Sequence.to_list;;
- : int list list = [[]; [4]; [3]; [3; 4]; [2]; [2; 4]; [2; 3]; [2; 3; 4]; [1]; [1; 4]; [1; 3];     [1; 3; 4]; [1; 2]; [1; 2; 4]; [1; 2; 3]; [1; 2; 3; 4]] 

(* a much more efficient version of combs *)
let rec combs2 = function
  | [] -> Sequence.return []
  | x :: tail ->
    combs2 tail >>=
    fun tail' -> Sequence.doubleton tail' (x::tail')

(* combinations of a given length *)
let combs k l =
  let n = List.length l in
  let rec aux k n l = match l with
  | [] when k=0 -> Sequence.return []
  | [] -> Sequence.empty
  | x :: tail ->
    let s1 = if n > k then (aux k (n-1) tail) else Sequence.empty in
    let s2 = if n >= k then (aux (k-1) (n-1) tail >|= fun l->x::l) else Sequence.empty in
    Sequence.append s1 s2
  in
  aux k n l;;

combs 3 [1;2;3;4;5;6] |> Sequence.to_list;;
- : int list list = [[4; 5; 6]; [3; 5; 6]; [3; 4; 6]; [3; 4; 5]; [2; 5; 6]; [2; 4; 6]; [2; 4; 5];   [2; 3; 6]; [2; 3; 5]; [2; 3; 4]; [1; 5; 6]; [1; 4; 6]; [1; 4; 5]; [1; 3; 6];  
 [1; 3; 5]; [1; 3; 4]; [1; 2; 6]; [1; 2; 5]; [1; 2; 4]; [1; 2; 3]]