Intro to type classes using fantasy F# syntax

TypeClasses.fs

// Type classes (a.k.a. traits in Rust or protocols in Swift) are similar to interfaces. Main
// difference: an "implementation" can be provided separately from a type definition itself,
// retroactively. In this example using hypothetical F# syntax we both define TC and their
// implementations next to each other, but this is not required.

trait Equality<'a> with
    equals : 'a -> 'a -> bool
    
// This definition says: "Type 'a belongs to a class (as in classification, characterization)
// of types which support equality. For every such type there is a function 'equals' with the
// given signature". Note that this introduces overloading of 'equals', while function
// overloading is currently not allowed in F#. Next, let's define a simple data type:

type Person = {
    Name : string
    Age : int
}

// In F# this definition also gives us equality derived by the compiler for free in the form
// of overriden 'Equals' member (and 'GetHashCode'). In Haskell and PureScript (not sure about
// Rust and Swift), equality is opt-in, not opt-out as in F#. This amounts to providing an
// "instance" (implementation) of the 'Equality' type class; a TC instance serves as evidence
// that the respective type indeed supports whatever functionality the TC defines.
// In F# this could look like this, somewhat (ab/re)using the extension syntax and 'interface'
// keyword:

type Person with
    interface Equality<_> with
        equals { Name = n1; Age = a1} { Name = n2; Age = a2 } = n1 = n2 && a1 = a2
        
// It is worth repeating that this instance could be provided in a completely different
// module, in a completely different assembly. There are some important details to this, but
// I omit them here.
// However, F# is smart enough to derive equality for algebraic data types and that could be
// utilized to reduce boilerplate code like the instance above. Indeed, Haskell, PureScript
// and Rust can derive TC instances (no idea about Swift). Using fantasy syntax again, this
// could look like

[<Derive(Equality<_>)>]
type Person = { .. } // as above

// What can we do with all of this? The main point is that type classes introduce constraints
// which we can use in our own functions (or library functions). Here is how F# Core library
// could define the usual '=' operator, without the built-in magical 'equality' constraint:

let (=) (x : 'a when Equality<'a>) y = equals x y

// Of course, f-n 'equals' can be used normally too. The "stand-alone" type of 'equals' itself
// is interesting because the TC constraint would surface there:

equals<'a when Equality<'a>> : 'a -> 'a -> bool

// This is kind of similar to current signature of (=) where the magical equality constraint
// shows up, only without the ad-hoc constraint built into the compiler.

// Let's define a second type class, as a hypothetical replacement of 'ToString'. To avoid
// confusion I will name it 'AsString'. Also, I will "redefine" function 'string' from F#
// Core in terms of this TC.

trait AsString<'a> with
    string : 'a -> string
    
// When used with the induced constraint this removes all possible confusion and "dangers"
// of using 'ToString'. Namely, a type either implements 'AsString' or it does not; there is
// no ever-present 'ToString' member which may or may not be overriden. If you attempt to
// use 'string' on a type for which there is no instance of this TC, the program will simply
// not build. Similarly to 'Equality', instances of 'AsString' could be easily derived by
// the compiler for some types.

// There is much more to tell about type class goodness, but here is a last property which
// illustrates how TCs support modularity. Suppose we are serializing values to JSON. Support
// for serialization can be expressed nicely as a type class:

trait Json<'a> with
    toJson : 'a -> Json
    
// With type classes "conditional instances" are possible. That is, if there is some instance
// for a type, then the programmer can define that there is automatically some other instance
// for the same (or other type). For example, if a value can be converted to a string, then
// surely it can be serialized to JSON. Here is some new fantasy syntax:

type 'a when AsString<'a> with
    interface Json<_> with
        toJson v = toJson (string v)
    
// Several interesting things are happening here. First, 'toJson' on the left is for 'a, while
// 'toJson' on the right is for 'string': function overloading! Second, this definition assumes
// that there is a 'Json<string>' instance, usually provided by the JSON serialization library,
// which would define type class 'Json' itself (and probably also this conditional instance).
// Third and most interesting, this instance is "active" on 'a only when 'AsString<'a>' constraint
// is true, otherwise it is ignored. As the instance is polymorphic (generic), it will work for
// some types and not for other simultaneously. The compiler performs deep checks to ensure that
// types have the required (conditional) instances.
// Here is something more useful: if 'a is serializable, then so are lists of 'a. Nice and easy:

type List<'a when Json<'a>> with
    interface Json<_> with
        toJson vs = // some expression using toJson on 'a here
        
// Again, the constraint on 'a allows applying 'toJson' on values of type 'a in the definition
// of 'toJson' for the "bigger" type 'List<'a>'. This is checked by the compiler even when
// such conditional instances are deeply chained. For example, a list of lists of 'a is
// automatically serializable whenever 'a is serializable by the same definition.