Recursive bubble sort in OCaml

I'm new in OCaml and just want to be sure that I write code in "ocaml way". My other first programs in OCaml was imperative and looks like python-code. So I decided to write simple code and share it for review.

let print lst =
    List.map string_of_int lst
        |> String.concat " "
        |> print_endline
;;

let rec sort lst =
    let sorted = match lst with
    | hd1 :: hd2 :: tl ->
        if hd1 > hd2 then
            hd2 :: sort (hd1 :: tl)
        else
            hd1 :: sort (hd2 :: tl)
    | tl -> tl
    in
    if lst = sorted then
        lst
    else
        sort sorted
;;

let () =
    let lst1 = [3; 4; 2; 1] in
    print lst1;
    sort lst1 |> print;

    let lst2 = [5; 6; 7; 0; 1; 4; 2; 9; 3; 8] in
    print lst2;
    sort lst2 |> print;
;;

Result:

3 4 2 1
1 2 3 4
5 6 7 0 1 4 2 9 3 8
0 1 2 3 4 5 6 7 8 9

Your code is easy to understand, so I can only suggest minor changes. The first thing is just a preference of mine: if a function body is nothing but a match ... with expression, I use the function keyword, instead. The second, more important recommendation is to use three clauses in the match body so you don't build a new, temporary list (hd2 :: tl) as you recurse. With both of these minor changes, sort looks like this:

let rec sort lst =
  let sorted = function
  | hd1 :: hd2 :: tl when hd1 > hd2 ->
        hd2 :: sort (hd1 :: tl)
  | hd1 :: tl ->
        hd1 :: sort tl
  | tl -> tl
in
if lst = sorted then
    lst
else
    sort sorted

As the list gets more and more sorted, the second pattern gets matched more often and simply travels down the list. Your version continues to build a new list -- even when the list is sorted.

One other thing: OCaml has an equality operator that tests for physical equality (in addition to structural equality.) So we can avoid building a new list in the second case, if it's not necessary:

| (hd1 :: tl) as lst ->
    let tl' = sort tl in
    if tl' == tl then
        lst
    else
        hd1 :: tl'

Both these changes will prevent a lot of temporary objects from being created. Unfortunately, it's still a bubble sort, so it's never going to be a speed-demon. :D

StackExchange Code Review Q#125571, answer score: 3