Last active
April 16, 2021 20:57
-
-
Save Savelenko/e73c19bbe881bb17960c81d4528e3ddf to your computer and use it in GitHub Desktop.
Intro to type classes using fantasy F# syntax
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment