Getting the two minimum values from a list in OCaml

Question

I need to write a function twoMin: int list → int * int using foldl that returns the two smallest values (not elements) of a list. You may assume that the list contains at least two elements with different values.

let rec foldl f l acc = match l with
  | [] -> acc
  | x :: xs -> foldl f xs (f x acc)

let twoMin lst =
  match lst with
  | [] | [_] -> failwith "List must contain at least two elements with different 
values."
   | x :: y :: rest ->
    let initial_acc = if x < y then (x, y) else (y, x) in
    let (min1, min2) = foldl (fun a b -> if b < fst a then (b, fst a) else if b < snd 
a then (fst a, b) else a) rest initial_acc in
    (min1, min2)

I keep getting error and I do not know what is wrong with the code.

Answer 1

You're close.

The accumulator you're passing to foldl is a tuple of two values. This is fine. However, the result of the function you pass to foldl must have the same type as the accumulator. If we take your code and change some of the names:

let twoMin lst =
  match lst with
  | [] | [_] -> failwith "List must contain at least two elements with different values."
  | x :: y :: rest ->
    let initial_acc = if x < y then (x, y) else (y, x) in
    let (min1, min2) = 
      foldl 
        (fun x acc -> 
           if acc < fst x then (acc, fst x) 
           else if acc < snd x then (fst x, acc) 
           else x) 
        rest 
        initial_acc 
    in
    (min1, min2)

We can see that you're treating each element of the list as the accumulator, and vice versa.

Using fst and snd like this is annoying when we can just use pattern-matching.

let twoMin lst =
  match lst with
  | [] | [_] -> failwith "List must contain at least two elements with different 
values."
   | x :: y :: rest ->
    let initial_acc = if x < y then (x, y) else (y, x) in
    let (min1, min2) = 
      foldl 
        (fun x (min1, min2 as acc) -> 
           if x < min1 then (x, min1) 
           else if x < min2 then (min1, x) 
           else acc) 
        rest 
        initial_acc 
    in
    (min1, min2)

Of course, pattern-matching that tuple, then just rebuilding it and returning it immediately is pointless.

Also, your confusion may be aided by your definition of a left fold, which differs from List.fold_left. Try instead:

let rec foldl f init = 
  function
  | [] -> init
  | x::xs -> foldl f (f init x) xs