F# a function to check if a list is sorted or not

Question

I have to write a function, that returns true if a given list is sorted in ascending order. The empty and 1-element lists are sorted. Also, [5,12,12] should return true.

I've written a function that seems to work:

let rec isSorted (l: int list) = 
    match l with
    | [] -> true
    | [x] -> true
    | [x;y] -> x <= y
    | x::y::xr -> if x > y then false else isSorted([y] @ xr);

But it seems a bit off... I'm thinking there must be an easier way to do this? I hate that I have to match 4 cases, but I cant figure out how to make it any smarter.

Any better solutions?

Answer 1

Well, never say

[y] @ xr

when

y :: xr

will do just as well. (In general, @ is a code smell.)

Kinda nitpicky, but the last line could be

| x::((y::_)as t) -> if x > y then false else isSorted(t)

and save you from doing any allocation.

Now, do you need the third case? What happens if you remove it?

Answer 2

you can combine existing functions:

let isAscending l = l |> Seq.pairwise |> Seq.forall (fun (a, b) -> a <= b)

printfn "%b" (isAscending []) // true
printfn "%b" (isAscending [1]) // true
printfn "%b" (isAscending [5;12]) // true
printfn "%b" (isAscending [5;12;12]) // true
printfn "%b" (isAscending [5;12;12;11]) // false

Answer 3

This is a particularly bad solution in terms of efficiency, so I'd never use this in the real world, but here is a nifty functional way of looking at the problem that I came up with as part of a blog example:

let isSorted l = l = (l|>List.sort)

Answer 4

Getting back to the original code (as opposed to the suggested library calls), I'd say you can make a few improvements:

• The third match case isn't really needed (was already mentioned).
• In the second case you don't want to give the value a name, you're not accessing it.
• In the forth case, it doesn't look right to take apart y::xr just to stitch it together again with [y] @ xr (or y::xr). An as expression seems nicer.
• You are just combining two logical results, the if..then looks a bit out of place.

I have come up with the following revised version:

let rec isSorted l =
    match l with
    | [] | [_] -> true
    | h1::(h2::_ as tail) -> h1 <= h2 && isSorted tail

I doubt it's more efficient than the original, but it's easier on the eye.