listfunctional-programmingocaml

Keepsorted function

I'm trying to solve a problem on a function called "keepsorted";

This function has to keep a sub-list of growing number form a list called l1.

For example if I have let l1 = [1; 2; 0; 1; 2; 4; 3; 5; 3; 2; 6] the return is a list with the numbers [1; 2; 2; 4; 5; 6]

I tried many solution but I don't understand.

My last solution is:

let rec keepsorted l = 
  match l with
  | [] -> [] 
  | a1::a2::r when a1 >= a2 -> a1::keepsorted r 
  | a::r -> a::keepsorted r;;

and the result is:

- : int list = [1; 2; 1; 2; 4; 5; 2; 6]
Solution

  • You have two issues with this line:

    a1::a2::r when a1 >= a2 -> a1::keepsorted r

    The first issue is that you're removing a1 from the recursive call, so the next number will always be accepted without begin compared to a1.

    For instance, consider the list 10 :: 9 :: 8 :: r:

    keepsorted (10::9::8::r)
10 :: keepsorted (8::r)
10 :: 8 :: ...

    10 was never compared to 8.

    You can fix that issue easily by doing instead:

    a1::a2::r when a1 >= a2 -> keepsorted (a1::r)

    Now a1 can be compared with the next element of r

    The second issue is that you're discarding a2 when a1 >= a2, but your example says that you only want to discard a2 when a1 > a2. In case of equality, keep both.

    Final function:

    let rec keepsorted l = 
  match l with
  |[] -> [] 
  |a1::a2::r when a1 > a2 -> keepsorted (a1::r) 
  |a::r -> a::keepsorted r;;