CODEWITHSUNDEEP
listsortingrecursionocaml
user3187131
user3187131

Reputation: 273

Check if the list is sorted in Ocaml

Why the code below is wrong? Even though the first two results are correct but the last one should return false, it returns true instead. Why so?

let rec is_sorted x = match x with
|h::h2::[] -> if h <= h2 then true else false
|h::h2::t -> if h <= h2 then is_sorted h2::t else false

# is_sorted [4;5;6;5;9];;
- : bool = false
# is_sorted [4;5;6;7;9];;
- : bool = true
# is_sorted [4;5;6;18;9];;
- : bool = true

Upvotes: 1

Views: 4819

Answers (4)

Nyi Nyi
Nyi Nyi

Reputation: 788

The following will check if an int list is sorted in ascending or descending:

let is_sorted l =
    let rec aux l cmp = 
    match l with
    | [] | [_] -> true
    | x :: ((y :: _) as t) -> cmp x y && aux t cmp
    in 
    aux l ( <= ) || aux l ( >= )

Upvotes: 0

Gustin
Gustin

Reputation: 191

This is how I would do it.

let rec sorted x =
   match x with
   | [] -> true
   | [_] -> true
   | a::b::t when a <= b -> sorted (b::t)
   | _ -> false
;;

Upvotes: 0

Aristide
Aristide

Reputation: 3994

A bit shorter:

let rec is_sorted = function
  | x::y::l -> x <= y && is_sorted (y::l)
  | _ -> true

Upvotes: 0

hivert
hivert

Reputation: 10667

I'll write the following:

let rec is_sorted x = match x with
  | [] -> true
  | h::[] -> true
  | h::h2::t -> if h <= h2 then is_sorted (h2::t) else false;;

Then:

# is_sorted [];;
- : bool = true
# is_sorted [1];;
- : bool = true
# is_sorted [4;5;6;5;9];;
- : bool = false
# is_sorted [4;5;6;7;9];;
- : bool = true
# is_sorted [4;5;6;18;9];;
- : bool = false

Upvotes: 1

Related Questions