# Compelling Higher Kinded Types and Type Classes in F#¶

There is no parameterized module in F#, however, as the result of the existance of some other power infrastructures, it becomes much easier for F# to express higher abstractions tersely.

The secret of the F#’s conciseness comes from the following 2 parts.

- Active Patterns help to avoid write
`inj`

and`prj`

manually. If you’ve never heard of

`inj`

and`prj`

before, there is a prerequisite article for you to figure out what they are and some necessary knowledge about Higher Kined Types and Type Classes.If you cannot get along with that prerequisite article, you might need to try Haskell language to learn about Functor and Monad to get some related basic knowledge.

- Active Patterns help to avoid write
- Static Resolved Type Parameters help to support resolution for implicit arguments.
That’s the way to achieve something similar to modular implicits in OCaml.

FYI, this repo provides an actual implementation.

## Active Pattern¶

- Temporary enumerations

```
let (|IsWhatIWant|NotWhatIWant|) x =
if x > 10 then IsWhatIWant
else NotWhatIWant
let checkNumber():
match 10 with
| IsWhatIWant -> failwith "fatal!"
| _ -> ()
```

- Temporary recognizers

```
let (|Dec|) x =
if x > 0 then Some <| x - 1
else None
let test(): int option =
match 1 with
| Dec x -> x
```

- Simulating datatypes

```
let (|Just|Nothing|) (a: 'a option) =
match a with
| Some a -> Just a
| None a -> Nothing
let Just (a: 'a): 'a option = Some a
let Nothing<'a>: 'a option = None
// Now you can use `Just` and `Nothing` to replace
// constructors `Some` and `None` of type `'a option`.
let bind (m:'a option) (k: 'a -> 'b option):
match m with
| Nothing -> Nothing
| Just x -> k x
```

Above snippets are about some use cases of Active Patterns, which might not be exhaustive but sufficent for today’s topic:

**Allow to inject extra logics when destructuring data**,

subsequently, which is the key to implement LHKT in F#.

## Statically Resolved Type Parameters¶

In the language reference of F#, statically resolved type parameters are not well documented, but you might want to check it firstly.

Here I’m to bring more cases to tell you how to take advantage of it.

The first case is about structural typing.

In structural typing, an element is considered to be compatible with another if,for each feature within the second element’s type, a corresponding and identical feature exists in the first element’s type.[3]

So let’s imagine a case that we want to make some functions for all objects/types that have a common specific behavior.

Let’s think about the sound of animals, which could be taken as the behavior.

Firstly, let’s define the enumerate some sounds:

```
type Sound = Ooooh | Uhhh | Ahhh | QAQ | Woke | Wa | Ding | Miao
```

Then we define some intuitive active patterns to make natural-language-like notations:

```
let (|LessThan|_|) param value =
if value > param then Some ()
else None
// 1 is less than 20
assert (match 1 with LessThan 20 -> true | _ -> false)
```

```
type CatSpecies = ScottishFold | RussianBlue | MeoGirl
type Cat = {
weight : int
species : CatSpecies
} with
static member sound: Cat -> Sound =
function
| {weight = LessThan 20; species = ScottishFold} -> Miao
| {weight = LessThan 40; species = RussianBlue} -> Uhhh
| {weight = LessThan 100; species = RussianBlue} -> Wa
| {weight = LessThan 100} -> QAQ
| {species = MeoGirl} -> Ding
type Color = Black | Brown | White
type Scale = {height : int, thickness : int}
type Dog = {
color : Color
scale : Scale
} with
static member sound : Dog -> Sound =
function
| {height = LessThan 30; thickness = LessThan 10} -> Wa
| {height = LessThan 30} -> Woke
| {height = LessThan 50} -> Ooooh
| _ -> failwith "a fat wolf detected"
```

Now I want to a function, which takes an animal as input, and output its sound.

For we didn’t use the discriminated union/ADT to represent animals, how can we make this polymorphic function?

Here you are:

```
let sound(a : ^a when ^a: (static member sound: ^a -> ^b)) =
(^a : (static member sound: ^a -> ^b) a)
assert sound {weight = 100; species = MeoGirl} = Ding
assert sound {height = 40; thickness = 15} = Ooooh
```

Another case could be more formal and quite related to our topic.

Firstly, to represent higher kinded types, we use

```
type hkt<'K, 'T> = interface end
```

Here, the `hkt<'K, 'T>`

is something that emulates the application of type constructor `'K`

on `'T`

, and
the kind ascription of `'K`

is(at least) `* -> *`

(e.g.,
a concrete type `List<int>`

is the application of type constructor `List`

on type `int`

, so semantically it could be written as `hkt<List, int>`

).

If any problem, refer to this prerequisite article.

Now, we’re to make some type constructors to substitute the type variable `'K`

, like `List`

,
`Array`

, `Maybe`

/ `Option`

, etc. These type constructors(also types) can have some
common features, e.g., could be applied with a `map`

function,

```
type 'a Maybe = 'a Option
let map_maybe : ('a -> 'b) -> 'a Maybe -> 'b Maybe = ..
let map_list : ('a -> 'b) -> 'a List -> 'b List = ..
let map_array : ('a -> 'b) -> 'a Array -> 'b Array = ..
```

which could extracted as a useful concept, the functor. The functor is a **Type Class**,
which is introduced to make abstractions on types(including the higher kinded types).

So, how can we emulate the functor, in another words, how can we assign the expected features to the corresponding type constructors
(`List`

, `Array`

, etc.)?

I’d like to directly give a solution below that was figured out on my own:

```
[<AbstractClass>]
type functor<'F>() =
abstract member fmap<'a, 'b> :
('a -> 'b) -> hkt<'F, 'a> -> hkt<'F, 'b>
```

Now you might have lots of questions about above codes,

- How can it help with implementing type classes?
- Why we have to use
`AbstractClass`

instead of ML Style records, or interfaces that’re more lightweighted? - Why we should use such a shape
`functor<'F>`

instead of straightforward`functor`

?

I’ll answer above questions in the following sections, but in terms of this section’s topic, I should answer the first one here.

Firstly we need some infrastructures:

```
let inline wrap<'o, ^f, 'a when ^f : (static member wrap : 'o -> hkt<'f, 'a>)>
(o: 'o) : hkt< ^f, 'a> =
(^f : (static member wrap : 'o -> hkt<'f, 'a>) o)
let inline unwrap<'o, ^f, 'a when ^f : (static member unwrap : hkt<'f, 'a> -> 'o)>
(f : hkt< ^f, 'a>) : 'o =
(^f : (static member unwrap : hkt<'f, 'a> -> 'o) f)
[<GeneralizableValue>]
let getsig<'a> :'a = failwith "" // the implementation would be given subsequently.
```

Then we make an instance of `functor`

for `List`

.

```
type mkList<'L>() =
inherit functor<mkList<'L>>()
static member wrap<'a> (x : List<'a>): hkt<mkList<'L>, 'a> =
{wrap = x} :> _
static member unwrap<'a> (x : hkt<mkList<'L>, 'a>): List<'a> =
(x :?> _).wrap
override member __.fmap<'a, 'b> (f : 'a -> 'b) (m : hkt<mkList<'L>, 'a>) : hkt<mkList<'L>, 'b> =
List.map f <| unwrap m |> unwrap
and listData<'L, 'a> =
{wrap : List<'a>}
interface hkt<mkList<'L>, 'a>
let fmap<'a, 'b, 'F when 'F :> functor<'F>> :
('a -> 'b) -> hkt<'F, 'a> -> hkt<'F, 'b> =
getsig<'F>.fmap
```

Now we can use `fmap`

on instances of `hkt<mkList<'L>, 'a>`

where `'L <: mkList<'L>`

.

```
type MyList() =
inherit mkList<MyList>()
// you can interface other type classes here.
type MyList = mkList<MyList>
assert [2, 3, 4] = (
let lst : hkt<MyList, _> = wrap [1, 2, 3]
in unwrap <| fmap (fun x -> x + 1) lst
)
```

Also the `Maybe`

functor:

```
type mkMaybe<'M> =
inherit functor<mkMaybe<'M>>()
static member wrap<'a> (x : Option<'a>): hkt<mkMaybe<'M>, 'a> =
{wrap = x} :> _
static member unwrap<'a> (x : hkt<mkMaybe<'M>, 'a>): Option<'a> =
(x :?> _).wrap
override member __.fmap<'a, 'b> (f : 'a -> 'b) (m : hkt<mkMaybe<'M>, 'a>) : hkt<mkMaybe<'M>, 'b> =
let m = unwrap m
wrap <|
match m with
| Some m -> Some <| f m
| None -> None
type MyMaybe() =
inherit mkMaybe<MyMaybe>()
// you can interface other type classes here.
type MyMaybe = mkMaybe<MyMaybe>
assert Some 2 = (
let m : hkt<MyMaybe, _> = wrap <| Some 1
in unwrap <| fmap (fun x -> x + 1) m)
```

Something deserved to be mentioned here is, we are capable of simplifying this via active patterns:

```
let Just<'M, 'a> (a: 'a) : hkt<mkMaybe<'M>, 'a> = wrap <| Some a
[<GeneralizableValue>]
let Nothing<'M, 'a> : hkt<mkMaybe<'M>, 'a> = wrap <| None
let (|Just|Nothing|) (m: hkt<mkMaybe<'M>, 'a>) =
let s: 'a Option = unwrap m
match s with
| Some m -> Just m
| None -> Nothing
assert Some 2 = (
let m : hkt<MyMaybe, _> = Just 1
in unwrap <| fmap (fun x -> x + 1) m
)
assert 2 = match Just 2 with
| Just a -> a
| _ -> failwith ""
```

Now we have introduced how to use active patterns and static resolved type parameters to implement type classes, but there are some problem remained here need to be answered.

## The *getsig* Function and Implicits¶

The `getsig`

function makes it more convenient for F# to achieve type classes than OCaml(without modular implicits[4]).

With a glance of the polymorphic `map`

in OCaml, which is implemented in this article:

```
type 'a mappable_impl = (module Mappable with type t = 'a)
let map (type t) (m: t mappable_impl) (f: 'a -> 'b) (a: ('a, t) app) =
let module M = (val m : Mappable with type t = t) in
M.map f a
let lst_mapped : (int, ListApp.t) app = map (module MapList) (fun x -> x + 1) lst_data_hkt
let arr_mapped : (int, ArrayApp.t) app = map (module MapArray) (fun x -> x + 1) arr_data_hkt
```

We could find that the explicit argument `m : t mappable_impl`

of `map`

is redundant. In fact, it could be
inferred through the latter argument `a : ('a, t) app`

. If there is a way in OCaml to automatically create an instance
typed `t mappable_impl`

from the given argument `a : ('a, t) app`

, then it could reach the presence of F#.

Finally, I’d present an implementation of `getsig`

here:

```
open System
open System.Reflection
let private ts = Array.zeroCreate<Type> 0
[<GeneralizableValue>]
let getsig<'a> =
let t = typeof<'a>
let f = t.GetConstructor(
BindingFlags.Instance ||| BindingFlags.Public,
null,
CallingConventions.HasThis,
ts,
null)
let o = f.Invoke([||])
o :?> 'a
```

## Why AbstractClass?¶

This is required for we need

- Default implementations of type classes
- Inheritances among type classes(such as
`Monad <: Applicative <: Functor`

)

These two features are necessary, if you have any problem about this point, please check Functor.fs, Applicative.fs, and Monad.fs.

So the questions above could be answered here:

**Q**:Why cannot we use records instead of abstract classes?

**A**:Records(in F#) conflict against type classes’ Inheritances.

**Q**:Why cannot we **always** use interfaces instead of abstract classes?

**A**:Currently there is no support for interfaces with default methods in F#. I’ve heard that C# 8 has supported this feature, but it hasn’t been introduced into F# yet.

Moveover, there is a related story about **Traits**, which is a concept equivalent to type classes.
Type classes could be implemented more smoothly via interfaces with default methods, which is leveraged by Scala language[5].

## Why *Functor<’F>* instead of the straightforward *Functor*¶

You might have thought of this:

```
[<AbstractClass>]
type functor() =
abstract member fmap<'a, 'b, 'F <: functor> :
('a -> 'b) -> hkt<'F, 'a> -> hkt<'F, 'b>
```

There is something wrong with above codes.

Firstly, it mixes up inheritances among type classes with making instances of type classes.

If we have `List <: functor`

, and `Applicative <: functor`

, isn’t it saying `Applicative`

is in the same
category as the `List`

?

Furthermore, static resolved type parameters cannot tell you which interface/abstract class your type has extended with:

```
type mkList() =
inherit Functor()
// ...
let fmap<'a, 'b, 'F when 'F :> functor> :
('a -> 'b) -> hkt<'F, 'a> -> hkt<'F, 'b> =
getsig<'F>.fmap
```

The `getsig`

used above is impossible to implement in F#.

`'F when 'F :> functor`

doesn’t work with instance resolution, for the F# compiler won’t make assumptions that `'F`

has the abstract methods of `functor`

, but
`'F when 'F :> functor<'F>`

is okay.

Therefore, we should use `functor<'F>`

.

## References and Further Reading¶

[1] Haskell ViewPatterns: https://ghc.haskell.org/trac/ghc/wiki/ViewPatterns

[2] Haskell ViewPatterns vs F# Active Patterns: https://mail.haskell.org/pipermail/haskell-cafe/2009-January/053643.html

[3] Structural-Typing: https://en.wikipedia.org/wiki/Structural_type_system#Description

[4] OCaml Modular Implicits : https://discuss.ocaml.org/t/modular-implicits/144

[5] Scala compiles traits to interfaces with default methods: https://github.com/scala/scala/pull/5003