Продолжаю слушать курс по алгоритмам на coursera. В этот раз в лекции объяснялся принцип работы сортировки слиянием. Мне, как обычно, стало интересно, как я смогу реализовать этот алгоритм на OCaml.

В этот раз условия такие:

• на вход и выход - списки
• своя сортировка в функциональном стиле
• постараться использовать хвостовую рекурсию там, где получится
• проверочная функция - List.sort
• подсветка сообщений об ошибках

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

В этот раз я записал процесс разработки в asciinema.org. Процесс разработки занял около 40 минут, и это при том, что я уже знал, что хочу написать. Ещё я довольно долго пытался объединить две операции в блок if .. then внутри функции тестирования, чтобы продолжать тесты только если не было ошибки, но так и не вспомнил, как это сделать, поэтому переписал кусок кода на match .. with

Полный исходник выглядит так:

open Core.Std


let merge_sort list =
    let rec merge accum a b =
        match a, b with
        | ([], []) -> accum
        | ([], h :: tl) -> List.rev accum @ b
        | (h :: tl, []) -> List.rev accum @ a
        | (h :: tl, h' :: tl') -> (
            match compare h h' with
            | -1 -> merge (h :: accum) tl b
            | _ -> merge (h' :: accum) a tl'
        )
    in

    let rec sort list =
        let length = List.length list in
        match length with
        | 0 | 1 -> list
        | _ -> (
            let m = length / 2 in
            let a', b' = List.split_n list m in
            merge [] (sort a') (sort b')
        )
    in

    sort list


let create_test_data = function
    | 0 -> []
    | size -> List.init size ~f:(fun i -> Random.int 10)


let render color text =
    sprintf "\027[38;5;%dm%s\027[0m\n" color text


let render_success test_data sorted_by_merge sorted_by_std =
    let color = 2 in
    let message = "Ok" in
    if List.length test_data < 20 then
        [
            message;
            "Test data: " ^ (List.to_string test_data ~f:string_of_int);
            "Merge sort: " ^ (List.to_string sorted_by_merge ~f:string_of_int);
            "List sort: " ^ (List.to_string sorted_by_std ~f:string_of_int);
        ] |> List.map ~f:(fun str -> render color str) |> String.concat ~sep:""
    else
        render color message


let render_error test_data sorted_by_merge sorted_by_std =
    let color = 1 in
    let message = "Error"in
    [
        message;
        "Test data: " ^ (List.to_string test_data ~f:string_of_int);
        "Merge sort: " ^ (List.to_string sorted_by_merge ~f:string_of_int);
        "List sort: " ^ (List.to_string sorted_by_std ~f:string_of_int);
    ] |> List.map ~f:(fun str -> render color str) |> String.concat ~sep:""


let rec test size =
    let test_data = create_test_data size in
    let sorted_by_merge = merge_sort test_data in
    let sorted_by_std = List.sort test_data ~cmp:compare in

    match compare sorted_by_merge sorted_by_std with
    | 0 -> (
        printf "%s%!" (render_success test_data sorted_by_merge sorted_by_std);
        if size > 0 then
            test (size - 1)
    )
    | _ -> printf "%s%!" (render_error test_data sorted_by_merge sorted_by_std)


let () =
    printf "wait...\n%!";
    test 1000