Combinations of size k from a list in OCaml
Your tails is very beatiful, your is_empty useless, and combnk a mess.

In combnk, your indentation obfuscates the actual structure of the code. Here is a better indentation:

let rec combnk k lst =
  if k = 0 then
    [[]]
  else
    let f = function
      | []      -&gt; []
      | x :: xs -&gt; List.map (fun z -&gt; x :: z) (combnk (k - 1) xs)
    in
      if is_empty lst then
        []
      else
        List.concat (List.map f (tails lst))


Now there are some interesting observations to be made here: The branch if is_empty lst then [] does not access f, so we could move this test outside of the let:

let rec combnk k lst =
  if k = 0 then
    [[]]
  else if is_empty lst then
    []
  else
    let f = function
      | []      -&gt; []
      | x :: xs -&gt; List.map (fun z -&gt; x :: z) (combnk (k - 1) xs)
    in
      List.concat (List.map f (tails lst))


But is the is_empty test actually necessary? tails [] produces an empty list, List.map f [] produces an empty list for any function f, and List.concat [] also produces an empty list. We now have:

let rec combnk k lst =
  if k = 0 then
    [[]]
  else
    let f = function
      | []      -&gt; []
      | x :: xs -&gt; List.map (fun z -&gt; x :: z) (combnk (k - 1) xs)
    in
      List.concat (List.map f (tails lst))


How can this be improved? We can move the tails definitions inside the else-branch let so that it's restricted to the only scope where it is used:

let rec combnk k lst =
  if k = 0 then
    [[]]
  else
    let rec tails = function
      | []          -&gt; []
      | _ :: t as l -&gt; l :: tails t
    and f = function
      | []      -&gt; []
      | x :: xs -&gt; List.map (fun z -&gt; x :: z) (combnk (k - 1) xs)
    in
      List.concat (List.map f (tails lst))


Regarding the question whether the case [] -&gt; [] in f is necessary except for the type system: The answer is no, as the list produced by tails cannot contain another empty list – l :: [] is l again. This would change when you swap [] -&gt; [] in tails for [] -&gt; [[]], which would be arguably more correct.

Now that f and tails are so close together you may notice some similarities.  Indeed, we can combine the two directly, thus getting rid of one map:

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


Of course, inner could be made partially tail recursive (but this reverses the order of combinations):

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


There is still an indirect recursion through combnk, more obvious if we rewrite it like this:

let rec combnk k lst =
  let rec inner acc k lst =
    match k with
    | 0 -&gt; [[]]
    | _ -&gt;
      match lst with
      | []      -&gt; List.flatten acc
      | x :: xs -&gt;
        let this_length = List.map (fun z -&gt; x :: z) (inner [] (k - 1) xs)
        in
          inner (this_length :: acc) k xs
  in
    inner [] k lst


Now all that is left to do is to write a map that takes an external accumulator, thus also removing the need for flatten or concat:

let rec combnk k lst =
  let rec inner acc k lst =
    match k with
    | 0 -&gt; [[]]
    | _ -&gt;
      match lst with
      | []      -&gt; acc
      | x :: xs -&gt;
        let rec accmap acc f = function
          | []      -&gt; acc
          | x :: xs -&gt; accmap ((f x) :: acc) f xs
        in
          let newacc = accmap acc (fun z -&gt; x :: z) (inner [] (k - 1) xs)
          in
            inner newacc k xs
    in
      inner [] k lst