Как найти второе наименьшее число из списка в OCaml с помощью fold_left?

Question

До сих пор, у меня есть небольшой фрагмент кода, который ищет минимальное значение в списке

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 

Что немного кода, который возвращает минимальное значение списка. Мне просто интересно, как мне следует сделать так, чтобы я мог найти второй наименьший элемент списка?

Answer 1

Вместо того, чтобы запомнить один номер, помните два из них?

(Код кажется удивительно сложным, когда вы делаете что-то вроде этого, между прочим. Это, пожалуй, точка упражнения. Если вы хотите третье наименьшее число, вы почти просто сортируете список и делаете это с помощью это.)

Answer 2

Почему бы не сделать List.drop для элемента min, который вы получили в первый раз, а затем снова вызвать функцию sec_small? Таким образом, вместо вызова функции sec_small один раз LST, я бы внешнюю функцию с sec_small как своей внутренней функции, то вызовите его как

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

Answer 3

Это проще, если у вас есть код предварительного цикла, чтобы установить хороший инвариант для фолда. В этом случае довольно ясно, что вы хотите иметь упорядоченную пару самых маленьких и вторых наименьших элементов, которые были обнаружены до сих пор. Соответствие делает это простым:

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)