В очередной лекции упоминалась сортировка выбором, и я решил сделать её реалзизацию в функциональном стиле на OCaml, насколько это вообще возможно.

В этот раз у меня были такие цели:

• написать проверочный код в чисто императивном стиле;
• написать вариант со списками и с рекурсией, пусть и не хвостовой.

В этот раз решение без разделения на разные программы и передачу данных через stdin и stdout.

Итак, первый и самый простой вариант - императивный:

let imp_sel_sort lst =
    let data = List.to_array lst in
    let last_index = Array.length data - 1 in
    for i = 0 to last_index do
        let ind = ref i in
        for j = (i + 1) to last_index do
            if data.(j) < data.(!ind) then
                ind := j;
        done;
        if !ind <> i then
            Array.swap data i !ind;
    done;
    Array.to_list data

Тут всё, как в описании алгоритма. Ищем минимальный элемент и ставим его в очередную позицию. Для поиска индекса использовал изменяемое значение let ind = ref i in.

Следующая реализация - сортировка списка с рекурсией и разбором списка до элементарных значений.

let fun_sel_sort lst =
    let rec find_min = function
        | [] -> assert false
        | [hd] -> (hd, [])
        | hd :: tl -> (
            let hd', tl' = find_min tl in
            if hd < hd' then
                hd, hd' :: tl'
            else
                hd', hd :: tl'
        )
    in

    let rec sort _lst =
        let m, rest = find_min _lst in
        match rest with
        | [] -> [m]
        | _ -> m :: sort rest
    in

    match lst with
    | [] | [_] -> lst
    | lst -> sort lst

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

Пока писал функциональный вариант, решил попробовать написать новый вариант императивной сортировки, но при этом ограничиться только одной изменяемой переменной - массивом, а индекс минимального значения сделать обычной переменной, без ref.

let imp_rec_sel_sort lst =
    let data = List.to_array lst in
    let last_index = Array.length data - 1 in
    for i = 0 to last_index do
        let min_index =
            let rec find imin current =
                if current > last_index then
                    imin
                else begin
                    let imin = match compare data.(imin) data.(current) with
                    | 1 -> current
                    | _ -> imin
                    in

                    if current = last_index then
                        imin
                    else
                        find imin (current + 1)
                end
            in

            find i (i + 1)
        in
        if min_index <> i then
            Array.swap data i min_index;
    done;
    Array.to_list data

Для запуска всех этих функций мне потребовался небольшой тестовый код, который позволил мне проверить, что всё работает так, как я ожидал:

let list2str x = x |> List.to_string ~f:string_of_int


let () =

   (* Код для первоначальной проверки работоспособности *)
   imp_sel_sort [3; 4; 8; 1; 2]
       |> list2str
       |> printf "%s\n";

   fun_sel_sort [3; 4; 8; 1; 2]
       |> list2str
       |> printf "%s\n";

   imp_rec_sel_sort [3; 4; 8; 1; 2]
       |> list2str
       |> printf "%s\n";

Полный листинг программы с тестом и выводом ошибок:

open Core.Std


let fun_sel_sort lst =
    let rec find_min = function
        | [] -> assert false
        | [hd] -> (hd, [])
        | hd :: tl -> (
            let hd', tl' = find_min tl in
            if hd < hd' then
                hd, hd' :: tl'
            else
                hd', hd :: tl'
        )
    in

    let rec sort _lst =
        let m, rest = find_min _lst in
        match rest with
        | [] -> [m]
        | _ -> m :: sort rest
    in

    match lst with
    | [] | [_] -> lst
    | lst -> sort lst


let imp_sel_sort lst =
    let data = List.to_array lst in
    let last_index = Array.length data - 1 in
    for i = 0 to last_index do
        let ind = ref i in
        for j = (i + 1) to last_index do
            if data.(j) < data.(!ind) then
                ind := j;
        done;
        if !ind <> i then
            Array.swap data i !ind;
    done;
    Array.to_list data


let imp_rec_sel_sort lst =
    let data = List.to_array lst in
    let last_index = Array.length data - 1 in
    for i = 0 to last_index do
        let min_index =
            let rec find imin current =
                if current > last_index then
                    imin
                else begin
                    let imin = match compare data.(imin) data.(current) with
                    | 1 -> current
                    | _ -> imin
                    in

                    if current = last_index then
                        imin
                    else
                        find imin (current + 1)
                end
            in

            find i (i + 1)
        in
        if min_index <> i then
            Array.swap data i min_index;
    done;
    Array.to_list data


let list2str x = x |> List.to_string ~f:string_of_int


let rec test deep =
    let render_error lst =
        [
            "Error!";
            "Origin: " ^ (lst |> list2str);
            "Imperative: " ^ (lst |> imp_sel_sort |> list2str);
            "Functional: " ^ (lst |> fun_sel_sort |> list2str);
            "Imperative with recursion: " ^ (lst |> imp_rec_sel_sort |> list2str);
        ]
    in

    let rec create_random_list num =
        match num with
        | 0 -> []
        | _ -> Random.int 10:: create_random_list (num - 1)
    in

    let random_list = create_random_list deep in
    let imp_sorted = imp_sel_sort random_list in
    if imp_sorted <> (fun_sel_sort random_list) || imp_sorted <> (imp_rec_sel_sort random_list) then
        random_list |> render_error |> List.fold ~init:"" ~f:(fun accum s -> accum ^ s ^ "\n")
    else if deep > 0 then
        test (deep - 1)
    else
        "Ok"


let () =
    (*
    (* Код для первоначальной проверки работоспособности *)
    imp_sel_sort [3; 4; 8; 1; 2]
        |> list2str
        |> printf "%s\n";

    fun_sel_sort [3; 4; 8; 1; 2]
        |> list2str
        |> printf "%s\n";

    imp_rec_sel_sort [3; 4; 8; 1; 2]
        |> list2str
        |> printf "%s\n";
    *)

    test 100 |> printf "%s"