Does the order of mutually exclusive clauses matter in function or match expressions

Question

When clauses in function and match statements aren't mutually exclusive, the order clearly matters. However when clauses are mutually exclusive they can be written in any order. E.g., to find the minimum element in a list, the following are functionally equivalent:

let rec minElt =
    function
    | [] -> failwith "empty list"
    | [x0] -> x0
    | x0::xtl -> min x0 (minElt xtl)

let rec minElt =
    function
    | [x0] -> x0
    | x0::xtl -> min x0 (minElt xtl)
    | [] -> failwith "empty list"

I prefer the first one stylistically, because the patterns are listed in increasing order of size / the base cases are first. However is there any advantage for the second one? In particular, is the second one more efficient because the exceptional case will never be checked in the course of normal evaluation?

Answer 1

I don't think there is any established idiomatic style. I would focus on making the code readable and understandable first - I think this depends on personal preferences, but I guess you could write:

• Special cases first (anything that needs special handling, or handles special but valid values)
• Most common cases next (the typical path, such as x::xs for lists)
• Exceptional cases (anything that means invalid input)

I guess this is how I generally tend to write pattern matching (because this is the order in which I think about the possible cases).

I would not worry too much about the performance. I tested your function just out of curiosity. I called it 1000 times on lists from length 1 to 100 (so that's 100000 iterations) and the first one was about 895ms while the second one 878ms so the difference is 2%. Does not sound like something that would matter over readability (this was in F# Interactive, so the difference might be even smaller).

Answer 2

I typically put the finishing case of a recursive function first. This is usually either the 0 case or the 1 case. Next I put the case which recurses (assuming there is only one), followed by any exceptional cases.

The reasoning behind this is that it's how I understand inductive reasoning: i.e. I understand the base case (how the recursion ends), following by how that base case is used to prove the correctness of the algorithm (how the recursion reaches the end). I put exceptional cases last because they don't add to my understanding of the logic behind the recursion. Recursion is more difficult to understand if you start in the middle of the argument than if you start at the end (and since recursion doesn't have a well-defined beginning point, you can't very well start there).

This reasoning leans heavily on the mathematical foundations of functional programming, so if that isn't how you approach functional programming, then maybe some other ordering would make more sense to you.