99.ml

(* Define monadic operations for a list *)
let return x = [x]

let (>>=) lst f = List.concat (List.map f lst)


(* Generate the combinations of k distinct objects from a list *)

(* Simple version 

let rec combnk k lst =
  if k = 0 then
    [[]]
  else
    let rec inner = function
      | []      -> []
      | x :: xs -> List.map (fun z -> x :: z) (combnk (k - 1) xs) :: inner xs in
    List.concat (inner lst)
*)

let rec combnk k lst =
  if k = 0 then
    [[]]
  else
    match lst with
    | []      -> []
    | x :: xs -> (combnk (k - 1) xs >>= fun comb ->
                  return (x :: comb)) @ combnk k xs
                  
(* Set difference for lists *)

let rec set_diff xs ys = match xs with
  | []     -> []
  | h :: t -> if List.mem h ys then
                set_diff t ys
              else
                h :: set_diff t ys
                
(*

Sort a list into subgroups of specific sizes. For example,
  # group ["a";"b";"c";"d"] [2;1];;
  - : string list list list =
  [[["a"; "b"]; ["c"]]; [["a"; "c"]; ["b"]]; [["b"; "c"]; ["a"]];
   [["a"; "b"]; ["d"]]; [["a"; "c"]; ["d"]]; [["b"; "c"]; ["d"]];
   [["a"; "d"]; ["b"]]; [["b"; "d"]; ["a"]]; [["a"; "d"]; ["c"]];
   [["b"; "d"]; ["c"]]; [["c"; "d"]; ["a"]]; [["c"; "d"]; ["b"]]]

*)

let rec group lst sizes = match sizes with
  | []     -> [[]]
  | h :: t -> combnk h lst               >>= fun grp  ->
              group (set_diff lst grp) t >>= fun grps ->
              return (grp :: grps)
              

(* I belive that the non-monadic code looks something like this:

let rec group (lst : 'a list) (sizes : int list) : 'a list list list =
  match sizes with
  | []     -> [[]]
  | h :: t -> let f gr = List.map (fun z -> gr :: z) (group (set_diff lst gr) t) in
              let grps = combnk h lst in
              List.concat (List.map f grps)

*)