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
is_empty
andtails
because I couldn't find them in theList
module, but maybe they are somewhere else?)Is the style okay, particularly the use of
let
statements 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.concat
and 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)