Behaviour of greater than (and equivalent) for Opt

Question

I'm working on something for an image processing task (it's not greatly relevant here), and I stumbled across behaviour of F#'s Option type that surprised me, regarding performing greater than (>) comparisons. I couldn't find anything that directly explained what I should expect (more on that below) on Stack Overflow, the F# docs or the wider web.

The specific part I am looking at looks something like:

let sort3Elems (arr: byte option []) = 
    if arr.[0] > arr.[1] then swap &arr.[0] &arr.[1]
    if arr.[1] > arr.[2] then swap &arr.[1] &arr.[2]
    if arr.[0] > arr.[1] then swap &arr.[0] &arr.[2]

where I will be passing in arrays of four byte options (if you're wondering why this looks weird and is super-unfunctional, right now I'm deliberately trying to re-implement the non-functional-language implementation of an algorithm in a textbook). I was expecting this to cause a compiler error, where it would complain that the options couldn't be directly compared. To my surprise, this compiled fine. Intrigued, I tested it out in F# Interactive, the results of which look something like the below:

let arr: byte option [] = Array.zeroCreate 4;;
val arr : byte option [] = [|None; None; None; None|]

> arr.[0] <- Some(127uy);;
val it : unit = ()

> arr.[2] <- Some(55uy);;
val it : unit = ()

> arr.[0] > arr.[2];;
val it : bool = true

> arr.[0] < arr.[2];;
val it : bool = false

> arr.[0] < arr.[1];;
val it : bool = false

> arr.[0] > arr.[1];;
val it : bool = true

> arr.[2] > arr.[1];;
val it : bool = true

> arr.[3] > arr.[1];;
val it : bool = false

> arr.[3] < arr.[1];;
val it : bool = false

> arr.[3] > arr.[1];;
val it : bool = false

It seems to me that essentially the comparison operators must always return true (false) when asking whether a Some is greater (less) than a None, two Nones always return false, and two Somes of the same contained type compare the contained values (assuming that they can be compared I imagine). This makes sense, though I was surprised.

Wanting to confirm this, I attempted to track something down that would explain the behaviour I should expect, but I couldn't find anything that addressed the point. The Option page in the MS F# Guide docs doesn't make any mention of it, and I couldn't find anything in places like F# for fun and profit. I couldn't even manage to find a page about Option anywhere in the MS API docs... Looking at the source for Option in the F# GitHub repo doesn't tell me anything. The best I could find was a blog post by Don Syme from years ago, which didn't actually answer my question. There were a smattering of Stack Overflow questions that discussed topics to do with the comparison operators or Option types, but I didn't find anything that dealt with the combination of the two.

So, my question is, does performing greater than/less than comparisons on the Option type return the results I have speculated about above? I'm guessing that this is reasonably common knowledge amongst F# programmers, but it was news to me. As a sub-/related question, does anyone know where I could/should have looked to for more information? Thanks.

Answer 1

The F# compiler automatically generates comparison for discriminated unions and record types. Since option is just a discriminated union, this also means that you get an automatic comparison for unions. I'm not sure if there is a good web page documenting this, but you can find a description in section 8.15.4 in the F# specification:

8.15.4 Behavior of the Generated CompareTo Implementations

For a type T, the behavior of the generated System.IComparable.CompareTo implementation is as follows:

• Convert the y argument to type T . If the conversion fails, raise the InvalidCastException.
• If T is a reference type and y is null, return 1.
• If T is a struct or record type, invoke FSharp.Core.Operators.compare on each corresponding pair of fields of x and y in declaration order, and return the first non-zero result.
• If T is a union type, invoke FSharp.Core.Operators.compare first on the index of the union cases for the two values, and then on each corresponding field pair of x and y for the data carried by the union case. Return the first non-zero result.

As documented in the last case, the case for option first compares the cases. None has an index smaller than Some so a None value will always be smaller than any Some value. If the cases match, then None = None and Some n with Some m are compared based on n and m.