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

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
开发者_JAVA技巧    | [] -> 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?

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

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?

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.

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)