I am trying to understand deeply nested recursion in OCaml by using the sorting list algorithm. For this reason I am tracing the below code which has a recursive function sort and calls another function insert.
let rec sort (lst : int list) =
match lst with [] -> [] | head :: tail -> insert head (sort tail)
and insert elt lst =
match lst with
| [] -> [ elt ]
| head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
I understand the first recursive calls for sort, but after that I cannot follow.
For instance, suppose we have the list [6, 2, 5, 3]. After sorting the tail of this list as 2,3,5 where in the code the head 6 is compared to each element of this tail? Can somebody provide a hint for the trace results?
utop # sort [6; 2; 5; 3];;
> sort <-- [6; 2; 5; 3]
> sort <-- [2; 5; 3]
> sort <-- [5; 3]
> sort <-- [3]
> sort <-- []
> sort --> []
> insert <-- 3
> insert -->
> insert* <-- []
> insert* --> [3]
> sort --> [3]
> insert <-- 5
> insert -->
> insert* <-- [3]
> insert <-- 5
> insert -->
> insert* <-- []
> insert* --> [5]
> insert* --> [3; 5]
> sort --> [3; 5]
> insert <-- 2
> insert -->
> insert* <-- [3; 5]
> insert* --> [2; 3; 5]
> sort --> [2; 3; 5]
> insert <-- 6
> insert -->
> insert* <-- [2; 3; 5]
> insert <-- 6
> insert -->
> insert* <-- [3; 5]
> insert <-- 6
> insert -->
> insert* <-- [5]
> insert <-- 6
> insert -->
> insert* <-- []
> insert* --> [6]
> insert* --> [5; 6]
> insert* --> [3; 5; 6]
> insert* --> [2; 3; 5; 6]
> sort --> [2; 3; 5; 6]
>
> - : int list = [2; 3; 5; 6]**
CodePudding user response：
In a sort by insertion, it is the insertion function that performs the comparisons between the element to be inserted and the currently sorted list. You can see that your trace inserts the elements of your list in reverse order:
insert <-- 3
...
insert <-- 5
...
insert <-- 5
...
insert <-- 2
...
insert <-- 6
...
insert <-- 6
...
insert <-- 6
...
insert <-- 6
...
A possible next step is to figure why insert is called four times with 6 as an argument and only once with 2 as an argument.
CodePudding user response：
First of all, there's no reason to have insert and sort being mutually recursive since insert doesn't depend on sort. So you could write it like this:
let rec insert elt lst =
match lst with
| [] -> [ elt ]
| head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
let rec sort (lst : int list) =
match lst with [] -> [] | head :: tail -> insert head (sort tail)
Now, what happens in insert? The function tries to insert an element elt in a sorted list with the invariant that all elements before it should be smaller and all the elements after should be higher.
Two cases happen:
- if the list is empty, the invariant in ensure if you just return a list containing the element you were trying to insert.
- if the list is not, it's composed of an element we'll call
headand the rest of the list that we'll calltail. Now we have two new cases:- if
elt <= headthen all the elements of the list are higher thaneltso you just returnelt :: list(for example if you callinsert 1 [2; 3; 4]you'll return[1; 2; 3; 4] - otherwise,
head < eltso we need to addheadin front of the list that will be returned by insertingelttotail, hence the recursive call toinsert elt tail
- if
Now, when you call sort you call it like this:
insert head (sort tail)
Why so? Because the invariant only works if the list you're trying to insert head into is sorted (hence the bold sorted before). So you need to sort tail before inserting head into it.
If you have the following list: [3; 2; 1], you'll call
insert 3 (sort [2; 1])
which is transformed in
insert 3 (insert 2 (sort [1]))
which is transformed in
insert 3 (insert 2 (insert 1 (sort [])))
which is resolved in
insert 3 (insert 2 [1])
which is resolved in
insert 3 [1; 2]
which is resolved in
[1; 2; 3]
And your list is sorted.
[EDIT]
Here's the code with some printing to see what's happening:
let pp_sep ppf () = Format.fprintf ppf "; "
let rec insert elt lst =
Format.printf "@[<v 2>(Insert %d in [%a]" elt
Format.(pp_print_list ~pp_sep (fun ppf d -> fprintf ppf "%d" d))
lst;
let l =
match lst with
| [] -> [ elt ]
| head :: tail ->
if elt <= head then elt :: lst
else (
Format.printf "@,";
head :: insert elt tail)
in
Format.printf ")@]";
l
let rec sort (lst : int list) =
match lst with
| [] -> []
| head :: tail ->
Format.printf "@[<v 2>(Sort [%a] then insert %d@,"
Format.(pp_print_list ~pp_sep (fun ppf d -> fprintf ppf "%d" d))
tail head;
let l = insert head (sort tail) in
Format.printf ")@]@,";
l
# sort [3;2;1];;
(Sort [2; 1] then insert 3
(Sort [1] then insert 2
(Sort [] then insert 1
(Insert 1 in []))
(Insert 2 in [1]
(Insert 2 in [])))
(Insert 3 in [1; 2]
(Insert 3 in [2]
(Insert 3 in []))))
- : int list = [1; 2; 3]