Как наиболее эффективно вернуть два самых больших элемента в списке OCaml int?

Question

Я новичок в Caml и не всегда понимаю все, что я делаю. В домашнем задании меня просят написать функцию, которая, учитывая l список из n целых чисел и max функцию, которая возвращает наибольшее целое число из двух, возвращает два самых больших элемента в l, вызывая функцию max в самое 2н-3 раза. Я уже сделал max_in_list функцию, которая возвращает наибольшее значение, если это может быть полезно:

let max a1 a2 = if a1>a2 then a1 else a2;;

let rec max_in_list l = match l with
    | [] -> 0
    | [a] -> a
    | a::q -> max a (max_in_list q)
;;

Как я мог решить эту проблему?

Answer 1

Поскольку вы можете вызывать функцию max только столько раз (требование назначения), я бы начал с изменения функции max, чтобы вы могли отслеживать, сколько раз она вызывается. Примерно так:

let times = ref 0

let max a1 a2 =
  times := (!times) + 1;
  if a1 > a2
  then
    a1
  else
    a2

let () = print_endline (string_of_int (!times))

Когда вы получите рабочее решение, вы можете удалить счетчик из функции max.