Can some one explain how this function recursively picks out the smallest integer?

Learning
1 
let rec small l1 =
    match l1 with
    h::[] -> h
    | (h::t) -> let smallest = small t in
    if h < smallest then h else smallest;;

    small [3;4;2;1];;

So basically what I understand from this function is that it compares the head (3) with the second elementand picks out the smallest?

But how does it recurs from there?
Does it pick out the smallest between 3 and 4 and then compares it to 2 etc.etc…

2

When it gets to the head of the list (3), it recursively finds the smallest element of the tail of the list: that’s 1. It then compares 3 to 1 and picks 1 as the smallest element.

How does it find the smallest element of the tail? When it gets to 4, it recursively finds the smallest element of the tail of the list… You see where this is going. Each suffix of the list is a smaller instance of the same problem. That’s an indication that recursion is a good way to structure a solution.

3

So am I understanding correct that the recursion goes like this?
Smallest(3, Smallest(4, Smallest(2, Smallest(1))))
And then it compares like the following:
2 vs 1 = 1
4 vs 1 = 1
3 vs 1 = 1

Is this how it goes?

Or does the recursion go the opposite way?

4

The #trace operation in the top level show the inputs and results for each call to a function. (I’ve also added a type annotation to small, so that OCaml knows how to print out the list elements):

# let rec small (l1 : int list) =
    match l1 with
    h::[] -> h
    | (h::t) -> let smallest = small t in
    if h < smallest then h else smallest;;
val small : int list -> int = <fun>
# #trace small;;
small is now traced.
# small [3;4;2;1];;
small <-- [3; 4; 2; 1]
small <-- [4; 2; 1]
small <-- [2; 1]
small <-- [1]
small --> 1
small --> 1
small --> 1
small --> 1
- : int = 1
5

Just look at the two match cases you provided:

The first case:

| [h] ->  h

I read this as:
Q: “What is the smallest number in a list with only one number?”
A: “That number”

The second case:

| (h :: t) ->
  let smallest_in_t = small t in
  if h < smallest_in_t then
    h
  else 
    smallest_in_t

I read this as:
Q: “What is the smallest number in a list with many elements?”
A: "Find the smallest number in the tail, t, and compare it to the head, h".

The rest is just implementation details.

2 Likes
6

Thank you for the help!

How would I do this (l1 : int list) with two lists?

For example, this does not work (l1 : int list ,l2 : int list) it needs to be written in a different way?

8

For example, this does not work (l1 : int list ,l2 : int list) it needs to be written in a different way?

Some extra parentheses will do the job: ((l1 : int list), (l2 : int list)).

But it’s more common in OCaml not to pair up the parameters like that. The usual way of writing a multi-argument function is to separate the parameters by spaces, like this:

let rec f (l1 : int list) (l2 : int list) = ...

and then to separate the arguments by spaces when you call the function, like this:

f l1 l2
2 Likes
9

Much appreciated, thank you!