OCaml non decreasing list without List.function

Question

Update: I can't use any List.function stuff.

I'm new to OCaml and I'm learning this course in which I'm supposed to calculate a list of non decreasing values from a list of values.

So for e.g. I have a list [1; 2; 3; 1; 2; 7; 6]

So function mono that takes in a list returns the following:

# mono [1; 2; 3; 1; 2; 7; 6];;
- : int list = [1; 2; 3; 7]

I do the following:

let rec calculateCheck value lst = (
    match lst with
     [] -> true
    | x :: xs -> (
        if (value < x) then
            false
        else
            calculateCheck value xs
    )
);;


let rec reverse_list lst = (

    match lst with
     [] -> []
    | x :: xs -> (
        reverse_list xs @ [x]
    )
);;

let shouldReverse = ref 1;; 

let cancelReverse somelist lst = (
    shouldReverse := 0;
    reverse_list lst
);;

let rec mono lst = (
    let somelist = ref lst in
        if (!shouldReverse = 1) then
            somelist := cancelReverse somelist lst
        else
            somelist := lst;

    match !somelist with
     [] -> []
    | x :: xs -> (
        if (calculateCheck x xs) then
            [x] @ mono xs
        else
            [] @ mono xs
    );
);;

Problem?

1. This only works once because of shouldReverse.
2. I cannot reverse the value; mono list should return non decreasing list.

Question?

1. Any easy way to do this?
2. Specifically how to get a subset of the list. For e.g. for [1; 2; 3; 5; 6], I want [1; 2; 3] as an output for 5 so that I can solve this issue recursively. The other thing, is you can have a list as [1; 2; 3; 5; 6; 5]:: so for the second 5, the output should be [1; 2; 3; 5; 6].

Any ideas?

Thanks

Answer 1

A good way to approach this kind of problem is to force yourself to formulate what you're looking for formally, in a mathematically correct way. With some training, this will usually get you a description that is close to the final program you will write.

We are trying to define a function incr li that contains the a strictly increasing subsequence of li. As Jeffrey Scoffield asked, you may be looking for the longest such subsequence: this is an interesting and non-trivial algorithmic problem that is well-studied, but given that you're a beginner I suppose your teacher is asking for something simpler. Here is my suggestion of a simpler specification: you are looking for all the elements that are greater than all the elements before them in the list.

A good way to produce mathematical definitions that are easy to turn into algorithms is reasoning by induction: define a property on natural numbers P(n) in terms of the predecessor P(n-1), or define a property on a given list in terms of this property on a list of one less element. Consider you want to define incr [x1; x2; x3; x4]. You may express it either in terms of incr [x1; x2; x3] and x4, or in terms of x1 and incr [x2; x3; x4].

• incr [x1;x2;x3;x4] is incr[x1;x2;x3], plus x4 if it is bigger than all the elements before it in the list, or, equivalently, the biggest element of incr[x1;x2;x3]

• incr [x1;x2;x3;x4] is incr[x2;x3;x4] where all the elements smaller than x1 have been removed (they're not bigger than all elements before them), and x1 added

These two precise definitions can of course be generalized to lists of any length, and they give two different ways to write incr.

(* `incr1` defines `incr [x1;x2;x3;x4]` from `incr [x1;x2;x3]`,
   keeping as intermediate values `subli` that corresponds to
   `incr [x1;x2;x3]` in reverse order, and `biggest` the biggest
   value encountered so far. *)
let incr1 li =
  let rec incr subli biggest = function
    | [] -> List.rev subli
    | h::t ->
      if h > biggest
      then incr (h::subli) h t
      else incr subli biggest t
  in
  match li with
    | [] -> []
    | h::t -> incr [h] h t

(* `incr2` defines `incr [x1;x2;x3;x4]` from `incr [x2;x3;x4]`; it
   needs no additional parameter as this is just a recursive call on
   the tail of the input list. *)
let rec incr2 = function
  | [] -> []
  | h::t ->
    (* to go from `incr [x2;x3;x4]` to `incr [x1;x2;x3;x4]`, one
       must remove all the elements of `incr [x2;x3;x4]` that are
       smaller than `x1`, then add `x1` to it *)
    let rec remove = function
      | [] -> []
      | h'::t ->
        if h >= h' then remove t
        else h'::t
    in h :: remove (incr2 t)