How to find the second smallest number of a list in OCaml using fold_left?

Question

So far, I have a little code snippet that searches for the minimum value in a list

let sec_small lst =
  let min_helper min curr =
    if (min < curr) then min 
    else curr
  in 
  List.fold_left min_helper (List.hd lst) lst

Which is a bit of code that returns the minimum value of a list. I'm just wondering, how should I proceed to make it so that I can look for the second smallest element of a list?

Answer 1

Instead of remembering one number, remember two of them?

(The code gets surprisingly complicated when you do something like this, by the way. That's perhaps the point of the exercise. If you wanted the third smallest number, you'd almost rather just sort the list and be done with it.)

Answer 2

This is easier if you have some pre-loop code to establish a nice invariant for the fold to work on. In this case it's fairly clear that what you want is to have an ordered pair of the smallest and second-smallest elements seen so far. Matching makes that simple:

let second_smallest list =
  match list with
   | [] | [_] -> failwith "no second element to return"
   | a::b::rest ->
       snd (List.fold_left
              (fun ((sm, ssm) as same) elt ->
                if elt < ssm then
                  if elt < sm then elt, sm else sm, elt
                else same)
              (if a < b then a, b else b, a)
              rest)

Answer 3

Why not do List.drop for the min item that you got first time, and then call your sec_small function again? So, instead calling sec_small function once with lst, I'd have an outer function with sec_small as its inner function, then, call it as

(sec_small (List.drop (lst, sec_small lst)))