FSharpPlus divRem - how does it work?

Your implementation is just fine, it's actually the same as the 2nd overload, which correspond to the default implementation.

F#+ is an F# base library, similar to F# core, and it also uses a fallback mechanism. F# core uses static optimizations and fakes some type constraints in a non-safe way, but this technique is not possible outside the F# compiler project, so F#+ achieve the same effect with a trait call to an overloaded method, without need to fake static constraints.

So, the only difference between your implementation and the one in F#+ is that F#+ will first look (at compile-time) for a DivRem static member defined in the class of the numeric type being used, with a standard .NET signature (using a return value and a reference, instead of a tuple) which is the 3rd overload. This method could have an optimized, specific implementation. I mean, it is assumed that if this method exists it will be at worst equally optimal than the default definition.

If this method does not exists, it will fallback to the default definition, which as I said it's the 2nd overload.

The 1st overload will never match and it's there only to create the necessary ambiguity in the overload set.

This technique, is not well documented at the moment, as the example in the docs from Microsoft is a bit unfortunate since it doesn't really work, (probably because it doesn't have enough ambiguity), but @rmunn answer has a very detailed explanation.

EDIT

Regarding your question update: That's not the way the F# compiler works, at least right now. Static constraints are being solved after overload resolution, and it doesn't backtrack when these constraints are not fulfilled.

Adding another method with constraints complicates enough the problem in a way that forces the compiler to do some constraint solving before the final overload resolution.

These days we're having some discussions questioning whether this behavior should be corrected, which doesn't seem to be a trivial thing.

First let's look at the documentation on overloaded methods, which doesn't have that much to say:

Overloaded methods are methods that have identical names in a given type but that have different arguments. In F#, optional arguments are usually used instead of overloaded methods. However, overloaded methods are permitted in the language, provided that the arguments are in tuple form, not curried form.

(Emphasis mine). The reason for requiring the arguments to be in tuple form is because the compiler must be able to know, at the point where the function is called, which overload is being called. E.g., if we had:

let f (a : int) (b : string) = printf "%d %s" a b
let f (a : int) (b : int) = printf "%d %d" a b

let g = f 5

Then the compiler wouldn't be able to compile the g function since it wouldn't know at this point in the code which version of f should be called. So this code would be ambiguous.

Now, looking at those three overloaded static methods in the DivRem class, they have three different type signatures:

static member inline DivRem (x:^t when ^t: null and ^t: struct, y:^t, _thisClass:DivRem)
static member inline DivRem (D:'T, d:'T, [<Optional>]_impl:Default1)
static member inline DivRem (D:'T, d:'T, [<Optional>]_impl:DivRem  )

At this point, you might be asking yourself how the compiler would choose between these static overloads: the second and third would seem to be indistinguishable if the third parameter is omitted, and if the third parameter is given but is an instance of DivRem, then it looks ambiguous with the first overload. At this point, pasting that code into an F# Interactive session can help, as F# Interactive will generate more specific type signatures that might explain it better. Here's what I got when I pasted that code into F# Interactive:

type DivRem =
  class
    inherit Default1
    static member
      DivRem : x: ^t * y: ^t * _thisClass:DivRem -> ^t *  ^t
                 when ^t : null and ^t : struct
    static member
      DivRem : D: ^T * d: ^T * _impl:Default1 -> ^a *  ^c
                 when ^T : (static member ( / ) : ^T * ^T -> ^a) and
                      ( ^T or  ^b) : (static member ( - ) : ^T * ^b -> ^c) and
                      ( ^a or  ^T) : (static member ( * ) : ^a * ^T -> ^b)
    static member
      DivRem : D: ^T * d: ^T * _impl:DivRem -> 'a * ^T
                 when ^T : (static member DivRem : ^T * ^T * byref< ^T> -> 'a)
    static member
      Invoke : D: ^T -> d: ^T -> ^T *  ^T
                 when (DivRem or ^T) : (static member DivRem : ^T * ^T * DivRem -> ^T * ^T)
  end

The first DivRem implementation here is the easiest to understand; its type signature is the same as the one defined in the FSharpPlus source code. Looking at the documentation on constraints, the null and struct constraints are opposite: the null constraint means "the provided type must support the null literal" (which excludes value types), and the struct constraint means "the provided type must be a .NET value type". So the first overload can never actually be chosen; as Gustavo points out in his excellent answer, it only exists so that the compiler will be able to handle this class. (Try omitting that first overload and calling divRem 5m 3m: you'll find that it fails to compile with the error:

The type 'decimal' does not support the operator 'DivRem'

So the first overload exists only to trick the F# compiler into doing the right thing. We'll then ignore it and pass on to the second and third overloads.

Now, the second and third overloads differ in the type of the third parameter. The second overload has the parameter being a base class (Default1), and the third overload has the parameter being a derived class (DivRem). These methods will always be called with a DivRem instance as the third parameter, so why would the second method ever be chosen? The answer lies in the automatically-generated type signature for the third method:

static member
  DivRem : D: ^T * d: ^T * _impl:DivRem -> 'a * ^T
             when ^T : (static member DivRem : ^T * ^T * byref< ^T> -> 'a)

The static member DivRem parameter constraint here was generated by the line:

(^T: (static member DivRem: _ * _ -> _ -> _) (D, d, &r)), r

This happens because of how the F# compiler treats calls to functions with out parameters. In C#, the DivRem static method that's being looked for here is one with parameters (a, b, out c). The F# compiler turns that signature into the signature (a, b) -> c. So this type constraint looks for a static method like BigInteger.DivRem and calls it with the parameters (D, d, &r) where &r in F# is like out r in C#. The result of that call is the quotient, and it assigns the remainder to the out parameter given to the method. So this overload just calls the DivRem static method on the provided type, and returns a tuple of quotient, remainder.

Finally, if the provided type doesn't have a DivRem static method, then the second overload (the one with Default1 in its signature) is the one that ends up being called. This one looks for overloaded *, - and / operators on the provided types and uses them to calculate a quotient and remainder.

In other words, as Gustavo's much shorter answer explains, the DivRem class here will follow the following logic (in the compiler):

• If there is a static DivRem method on the types being used, call it since it's assumed that it may be optimized for that type.
• Otherwise, calculate the quotient q as D / d, then calculate the remainder as D - q * d.

That's it: the rest of the complexity is just to force the F# compiler to do the right thing, and end up with a nice-looking divRem function that's as efficient as possible.