I wanted to write a small but non-trivial function in OCaml to test my understanding. I have only a basic understanding of the libraries, and no idea at all of what is considered good style. The function computes all combinations of size
k from a list, where
0 <= k <= length lst.
Would someone mind commenting on
Whether the function is generally well written (have I covered all cases, are there opportunities for tail recursion that I've missed?)
Have I made good use of libraries (e.g. I defined
tailsbecause I couldn't find them in the
Listmodule, but maybe they are somewhere else?)
Is the style okay, particularly the use of
letstatements and indentation?
The code is:
let rec tails = function |  ->  | _ :: t as l -> l :: tails t let is_empty = function |  -> true | _ -> false let rec combnk k lst = if k = 0 then [] else let f = function |  ->  (* I think this is unnecessary, but I get a pattern match warning o/w *) | x :: xs -> List.map (fun z -> x :: z) (combnk (k-1) xs) in if is_empty lst then  else List.concat (List.map f (tails lst))
Based on the excellent comments by amon (see below) I have written to what I think is the most readable version of this function, which is the one that inlines the definition of
tails and gets rid of
is_empty completely, but doesn't go all the way to removing the use of
List.map, because I believe in using library functions to simplify the code wherever possible.
In particular, the layout guidelines make the structure of the function much clearer, and I think that in this version it is obvious what algorithm is being used, whereas it is somewhat obfuscated in the original. Thanks, amos!
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)