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]

CodePudding user response：

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;;

CodePudding user response：

As an alternative to Stef's answer, which is correct, you need to keep track of the last value you added to the output as you iterate, and the current element. This isn't very efficient if we build up the list in the right order, but it is if we build it up in reverse order using a left fold. At the end we then just need to reverse that list.

let keepsorted lst =
  List.fold_left
    (fun i x -> 
       match i with 
       | [] -> x::i 
       | y::_ when x >= y -> x::i 
       | _ -> i) 
    [] 
    lst 
  |> List.rev

If we consider how this works for your test case:

keepsorted [1; 2; 0; 1; 2; 4; 3; 5; 3; 2; 6]
List.fold_left f [] [1; 2; 0; 1; 2; 4; 3; 5; 3; 2; 6]
List.fold_left f [1] [2; 0; 1; 2; 4; 3; 5; 3; 2; 6]
List.fold_left f [2; 1] [0; 1; 2; 4; 3; 5; 3; 2; 6]
List.fold_left f [2; 1] [1; 2; 4; 3; 5; 3; 2; 6]
List.fold_left f [2; 1] [2; 4; 3; 5; 3; 2; 6]
List.fold_left f [2; 2; 1] [4; 3; 5; 3; 2; 6]
List.fold_left f [4; 2; 2; 1] [3; 5; 3; 2; 6]
List.fold_left f [4; 2; 2; 1] [5; 3; 2; 6]
List.fold_left f [5; 4; 2; 2; 1] [3; 2; 6]
List.fold_left f [5; 4; 2; 2; 1] [2; 6]
List.fold_left f [5; 4; 2; 2; 1] [6]
List.fold_left f [6; 5; 4; 2; 2; 1] []
List.rev [6; 5; 4; 2; 2; 1]
[1; 2; 2; 4; 5; 6]

Side benefit: this is naturally tail-recursive, though that won't matter for trivial datasets.