Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member GetSlice : startIndex:int option * endIndex:int option -> 'T list
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val filter : predicate:('T -> bool) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.filter
val x : int
val toArray : list:'T list -> 'T []

Full name: Microsoft.FSharp.Collections.List.toArray
module Array

from Microsoft.FSharp.Collections
val reduce : reduction:('T -> 'T -> 'T) -> array:'T [] -> 'T

Full name: Microsoft.FSharp.Collections.Array.reduce
val a : int
val y : f:(int -> 'a) -> 'a * 'a

Full name: Typeclassish.y
val f : (int -> 'a)
val a : 'a
val b : 'a
type BinaryTree<'T> =
  | Element of 'T
  | Tree of 'T * BinaryTree<'T> * BinaryTree<'T>
  member Map : f:('T -> 'a) -> BinaryTree<'a>

Full name: Typeclassish.BinaryTree<_>
union case BinaryTree.Element: 'T -> BinaryTree<'T>
union case BinaryTree.Tree: 'T * BinaryTree<'T> * BinaryTree<'T> -> BinaryTree<'T>
val this : BinaryTree<'T>
Multiple items
member BinaryTree.Map : f:('T -> 'a) -> BinaryTree<'a>

Full name: Typeclassish.BinaryTree`1.Map

--------------------
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
val f : ('T -> 'a)
val x : 'T
val left : BinaryTree<'T>
val right : BinaryTree<'T>
member BinaryTree.Map : f:('T -> 'a) -> BinaryTree<'a>
val t1 : BinaryTree<int>

Full name: Typeclassish.t1
val t2 : BinaryTree<int>

Full name: Typeclassish.t2
Multiple items
union case Vector2D.Vector2D: 'a * 'a -> Vector2D<'a>

--------------------
type Vector2D<'a> =
  | Vector2D of 'a * 'a
  static member ( ~-. ) : Vector2D<'a0> -> Vector2D<'a0> (requires member ( ~- ))

Full name: Typeclassish.Vector2D<_>
val a1 : 'a (requires member ( ~- ))
val a2 : 'a (requires member ( ~- ))
Multiple items
union case Vector3D.Vector3D: 'a * 'a * 'a -> Vector3D<'a>

--------------------
type Vector3D<'a> =
  | Vector3D of 'a * 'a * 'a
  static member ( ~-. ) : Vector3D<'a0> -> Vector3D<'a0> (requires member ( ~- ))

Full name: Typeclassish.Vector3D<_>
val a3 : 'a (requires member ( ~- ))
val a : Vector2D<float>

Full name: Typeclassish.a
val b : Vector3D<float>

Full name: Typeclassish.b
namespace Coletto
namespace Coletto.TypeClassish
module Collections

from Coletto.TypeClassish
module Base

from Coletto.TypeClassish.Collections
val amap : int list

Full name: Typeclassish.amap
val simplemap : f:('a -> 'b) -> x:'c -> 'M (requires member ( ?<- ))

Full name: Coletto.TypeClassish.Collections.Base.simplemap
val bmap : int array

Full name: Typeclassish.bmap
val cmap : int option

Full name: Typeclassish.cmap
union case Option.Some: Value: 'T -> Option<'T>
Multiple items
union case Fmap.Fmap: Fmap

--------------------
type Fmap =
  | Fmap
  static member ( $ ) : Fmap:Fmap * x:'a array -> (('a -> 'b) -> 'b [])
  static member ( $ ) : Fmap:Fmap * x:'a list -> (('a -> 'b) -> 'b list)
  static member ( $ ) : Fmap:Fmap * x:'a option -> (('a -> 'b) -> 'b option)

Full name: Typeclassish.Fmap
val x : 'a array
type 'T array = 'T []

Full name: Microsoft.FSharp.Core.array<_>
val f : ('a -> 'b)
val map : mapping:('T -> 'U) -> array:'T [] -> 'U []

Full name: Microsoft.FSharp.Collections.Array.map
val x : 'a list
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val x : 'a option
type 'T option = Option<'T>

Full name: Microsoft.FSharp.Core.option<_>
module Option

from Microsoft.FSharp.Core
val map : mapping:('T -> 'U) -> option:'T option -> 'U option

Full name: Microsoft.FSharp.Core.Option.map
val map : f:'a -> x:'b -> 'c (requires member ( $ ))

Full name: Typeclassish.map
val f : 'a
val x : 'b (requires member ( $ ))
val exampleFunction : a:int -> b:int -> int

Full name: Typeclassish.exampleFunction
val b : int
val x : int

Full name: Typeclassish.x
val y : int

Full name: Typeclassish.y
val exampleFunction' : a:'a -> b:'b -> 'c (requires member ( + ))

Full name: Typeclassish.exampleFunction'
val a : 'a (requires member ( + ))
val b : 'b (requires member ( + ))
val x' : int

Full name: Typeclassish.x'
val y' : float

Full name: Typeclassish.y'
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
module Seq

from Microsoft.FSharp.Collections
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
Multiple items
union case Tree.Tree: 't * Tree<'t> * Tree<'t> -> Tree<'t>

--------------------
type Tree<'t> =
  | Tree of 't * Tree<'t> * Tree<'t>
  | Leaf of 't

Full name: Typeclassish.Tree<_>
union case Tree.Leaf: 't -> Tree<'t>
Multiple items
union case ThreeMap.ThreeMap: ThreeMap

--------------------
type ThreeMap =
  | ThreeMap
  static member ( ?<- ) : x:'a array * _Blank:ThreeMap * 'b array -> (('a -> 'b) -> 'b array)
  static member ( ?<- ) : x:'a list * _Blank:ThreeMap * 'b list -> (('a -> 'b) -> 'b list)
  static member ( ?<- ) : x:'a option * _Blank:ThreeMap * 'b option -> (('a -> 'b) -> 'b option)
  static member ( ?<- ) : x:Tree<'a> * _Blank:ThreeMap * Tree<'b> -> (('a -> 'b) -> Tree<'b>)

Full name: Typeclassish.ThreeMap
val x : Tree<'a>
val loop : (('a -> 'b) -> Tree<'a> -> Tree<'b>)
val x : 'a
val t1 : Tree<'a>
val t2 : Tree<'a>
val threemap : f:('a -> 'b) -> x:'a0 -> 'M (requires member ( ?<- ))

Full name: Typeclassish.threemap
val x : 'a (requires member ( ?<- ))
module Unchecked

from Microsoft.FSharp.Core.Operators
val defaultof<'T> : 'T

Full name: Microsoft.FSharp.Core.Operators.Unchecked.defaultof
val ma : int list

Full name: Typeclassish.ma
val mb : int array

Full name: Typeclassish.mb
val mc : int option

Full name: Typeclassish.mc
val mt : Tree<int>

Full name: Typeclassish.mt
type Default2

Full name: Typeclassish.Default2
type Default1 =
  inherit Default2

Full name: Typeclassish.Default1
Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map =
  inherit Default1
  static member Invoke : mapping:('T -> 'U) -> source:'A -> 'B (requires member Map)
  static member InvokeOnInstance : mapping:('T -> 'U) -> source:'A -> 'B (requires member Map)

Full name: Typeclassish.Map

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
static member Map.Invoke : mapping:('T -> 'U) -> source:'A -> 'B (requires member Map)

Full name: Typeclassish.Map.Invoke
val mapping : ('T -> 'U)
val source : 'A (requires member Map)
val call : ('M * 'I * 'R -> 'a) (requires member Map)
val mthd : 'M (requires member Map)
val source : 'I (requires member Map)
static member Map.InvokeOnInstance : mapping:('T -> 'U) -> source:'A -> 'B (requires member Map)

Full name: Typeclassish.Map.InvokeOnInstance
static member Map.InvokeOnInstance : mapping:('T -> 'U) -> source:'A -> 'B (requires member Map)
val iter : action:('T -> unit) -> source:seq<'T> -> unit

Full name: Microsoft.FSharp.Collections.Seq.iter
active recognizer KeyValue: System.Collections.Generic.KeyValuePair<'Key,'Value> -> 'Key * 'Value

Full name: Microsoft.FSharp.Core.Operators.( |KeyValue| )
static member Map.Invoke : mapping:('T -> 'U) -> source:'A -> 'B (requires member Map)
module Mapping

from Coletto.TypeClassish.Collections
Multiple items
type SealedAttribute =
  inherit Attribute
  new : unit -> SealedAttribute
  new : value:bool -> SealedAttribute
  member Value : bool

Full name: Microsoft.FSharp.Core.SealedAttribute

--------------------
new : unit -> SealedAttribute
new : value:bool -> SealedAttribute

Type Classes in FSharp

FSharp logo Prolucid logo
  • William Coletto
  • @willisbueller
  • github/angrydexterous

More intro

Type-Classes

Why should I care?

Simplest Example
1: 
2: 
3: 
4: 
5: 
6: 
[1..100]
|> List.map ((+) 10)
|> List.filter (fun x -> (x % 2) = 0)
|> List.map ((*) 2)
|> List.toArray
|> Array.reduce (fun a x -> a + x)

Ah Crap! I wanted to start with a seq

Slightly more complex example

Courtesy Eugene Tolmachev, Fyodor Soikin, Gustavo Leon

I want to pass in f which can operate on multiple datatypes

1: 
2: 
3: 
4: 
let y f =
    let a = f 1
    let b = f 2L
    (a,b)

No good.
f is automatically inferred by the first call (with type int)

Complex Example

Monad Transformers

...You're going to have to read 5 blog articles (Here's a good one to start with) and a few academic papers on the subject, but the gist of it is below (taken from that example), and it's doable in FSharp today with the FSharpPlus library

Basically though, you can stack Monads.
For instance -> Stack a IO (async) with a Reader to do configuration injection on an async server you're writing.

So what are type classes?

They are Ad-Hoc Polymorphism

  • Operator or function overloading with constraints
    • "This function will run on Type X if Type X implements foo"
  • Contrasts with Parametric Polymorphism
    • Generics, where type is parameterized by caller

Parametric Polymorphism (Not Type Classes)

Parametric polymorphism (...), allows a single piece of code to be typed “generically,” using variables in place of actual types, and then instantiated with particular types as needed. Parametric definitions are uniform: all of their instances behave the same. (...)

TAPL , §23.2:

Parametric Polymorphism (Not Type Classes)

Example rosettacode

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
type BinaryTree<'T> = 
    | Element of 'T 
    | Tree of 'T * BinaryTree<'T> * BinaryTree<'T>
    member this.Map(f) =
    match this with
    | Element(x) -> Element(f x)
    | Tree(x,left,right) -> Tree((f x), left.Map(f), right.Map(f))

let t1 = Tree(2, Element(1), Tree(4,Element(3),Element(5)) )
let t2 = t1.Map(fun x -> x * 10)

Ad-Hoc Polymorphism (Type Classes)

TAPL

Ad-hoc polymorphism, by contrast, allows a polymorphic value to exhibit different behaviors when “viewed” at different types. The most common example of ad-hoc polymorphism is overloading, which associates a single function symbol with many implementations; the compiler (or the runtime system, depending on whether overloading resolution is static or dynamic) chooses an appropriate implementation for each application of the function, based on the types of the arguments.

TAPL , §23.2:

Ad-Hoc Polymorphism (Type Classes)

Example Operator Overloading Gustavo Leon

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 
type Vector2D<'a> = Vector2D of 'a * 'a with
    static member inline (~-.) (Vector2D(a1,a2))    = 
        Vector2D (-a1 , -a2)
 
type Vector3D<'a> = Vector3D of 'a * 'a * 'a with
    static member inline (~-.) (Vector3D(a1,a2,a3)) = 
        Vector3D (-a1, -a2, -a3)
let a =   -. (Vector2D (1.0,2.0))
let b =   -. (Vector3D (1.0,2.0,3.0))
Vector2D (-1.0,-2.0)
Vector3D (-1.0,-2.0,-3.0)

Extending this to mimic Haskell Type Classes

1: 
2: 
3: 
4: 
5: 
6: 
#r "../src/build/PresentationCode.dll"
open Coletto.TypeClassish.Collections.Base

let amap = simplemap ((+) 10) [1..3]
let bmap = simplemap ((+) 10) [|1..3|]
let cmap = simplemap ((+) 10) (Some 3)
[11; 12; 13]
[|11; 12; 13|]
Some 13

What???

How'd that work?

1: 
2: 
3: 
4: 
5: 
6: 
type Fmap = Fmap with
    static member ($) (Fmap, x:array<_>) = fun f -> Array.map f x
    static member ($) (Fmap, x:list<_>  ) = fun f -> List.map f x
    static member ($) (Fmap, x:option<_>  ) = fun f -> Option.map f x

let inline map f x = (Fmap $ x) f

How that works

Operator Overloading

They have a particular behavior, at operator resolution the compiler looks in every operand class, so for example if we have a binary operator $ : (‘a,’b) -> ‘c it looks first into class ‘a then into class ‘b for the operator definition. So the trick is we will use an intermediary class with an operator with overloads for the second parameter. Gustavo Leon

Digression: Inline Methods with Operator Overloading

Introduction Anton Tayanovskyy

To cut the long story short, before compiling to .NET F# expands methods declared inline and does overload resolution. This was intended to support flexible operator overloading, but opens up the door for interesting hacks. Even code that generalizes over higher kinds and therefore cannot exist at .NET level can with these hacks exist at the inline F# level.

Non-Inline Problem Example

1: 
2: 
3: 
let exampleFunction a b = a + b
let x = exampleFunction 1 2
let y = exampleFunction 1.0 2.0 // Error

val exampleFunction : a:int -> b:int -> int //Determined by first call

severity: 'Error' message: 'This expression was expected to have type 'int' but here has type 'float'

Corrected with inline

1: 
2: 
3: 
let inline exampleFunction' a b = a + b
let x' = exampleFunction' 1 2
let y' = exampleFunction' 1.0 2.0 
3
3.0

Statically resolved:

val inline exampleFunction' : a: ^a -> b: ^b -> ^c when ( ^a or ^b) : (static member ( + ) : ^a * ^b -> ^c)

So back to type classes

1: 
2: 
3: 
4: 
5: 
6: 
type Fmap = Fmap with
    static member ($) (Fmap, x:array<_>) = fun f -> Array.map f x
    static member ($) (Fmap, x:list<_>  ) = fun f -> List.map f x
    static member ($) (Fmap, x:seq<_>  ) = fun f -> Seq.map f x

let inline map f x = (Fmap $ x) f

val inline map :
f:'a -> x: ^b -> 'c
when (Fmap or ^b) : (static member ( $ ) : Fmap * ^b -> 'a -> 'c)

Type classes allow you to define a set of functionality a type must provide so that a function can be run on the type.
- Note our map function requires static member $ with a particular signature. That's how we're getting type class support

Going Deeper

We have an ability to now match on a function with a single input type, and no mention of an output type.

What if we only have an output type? Or what if we care about input and output type?

Use a 3 parameter operator and overload it. The ternary operator fits the bill.
For unary functions we can just ignore an extra parameter. In the below case we are using the 3rd param just to match with the output type of the mapping function, and then ignoring it (see unchecked.defaultof below)

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
type Tree<'t> =
    | Tree of 't * Tree<'t> * Tree<'t>
    | Leaf of 't
type ThreeMap = ThreeMap with
    static member inline (?<-) (x:array<'a>, _Blank:ThreeMap,_:array<'b>) = 
        fun f -> Array.map f x : 'b array
    static member inline (?<-) (x:list<'a>, _Blank:ThreeMap,_:list<'b>) = 
        fun f -> List.map f x : 'b list
    static member inline (?<-) (x:option<'a>, _Blank:ThreeMap,_:option<'b>) = 
        fun f -> Option.map f x : 'b option
    static member inline (?<-) (x:Tree<'a>, _Blank:ThreeMap,_:Tree<'b>) = 
        fun (f:'a->'b) -> 
            let rec loop f = function
                | Leaf x -> Leaf (f x)
                | Tree (x, t1, t2) -> Tree (f x, loop f t1, loop f t2)
            loop f x      
let inline threemap (f:'a->'b) x :^M = (x ? (ThreeMap) <- Unchecked.defaultof< ^M>) f

Applying with the new map function

1: 
2: 
3: 
4: 
let ma = threemap ((*) 10) [1..3]
let mb = threemap ((*) 10) [|1..3|]
let mc = threemap ((*) 10) (Some 3) 
let mt = threemap ((*) 10) (Tree(6, Tree(2, Leaf 1, Leaf 3), Leaf 9))
[10; 20; 30]
[|10; 20; 30|]
Some 30
Tree (60,Tree (20,Leaf 10,Leaf 30),Leaf 90)

But what if we want to add our own new types?

You can't add new operator overloads through extension types
So we must go deeeper

Going Deeper

Looking at FsharpPlus by Gustavo Leon

  • Solid up-to-date library
  • Support for a ton of types build-in, with common functions defined (plus a whole lot more)
  • Actively maintained by Gustavo
  • Gustavo contributed PR's in F# 4.1 to fix bugs and speed things up related to this work
  • Moves from operator overloading to method overloading

Stripping away everything - A Brief Peek at FSharpPlus

Getting to a minimal subset of code in the library to get an idea of how it works

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
type Default2 = class end
type Default1 = class inherit Default2 end

type Map =
    inherit Default1

    static member inline Invoke (mapping :'T->'U) (source : 'A) : 'B = 
        let inline call (mthd : ^M, source : ^I, _output : ^R) = ((^M or ^I or ^R) : 
                                (static member Map: _*_*_ -> _) source, mapping, mthd)
        call (Unchecked.defaultof<Map>, source, Unchecked.defaultof<'B>)

    static member inline InvokeOnInstance (mapping :'T->'U) (source : 'A) : 'B = 
        (^A : (static member Map: _ * _ -> _) source, mapping)

Code Cont'd

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
static member inline Map (x : 'A , f : 'T->'U, _impl:Default1) = 
    Map.InvokeOnInstance f x : 'B
static member Map (x : seq<_>    , f : 'T->'U, _impl:Default2) = 
    Seq.map f x              : seq<'U>
static member Map (x : option<_> , f : 'T->'U, _mthd : Map)    = 
    Option.map  f x
static member Map (x : list<_>   , f : 'T->'U, _mthd : Map)    = 
    List.map f x             : list<'U>
static member Map (x : _ []      , f : 'T->'U, _mthd : Map)    = 
    Array.map   f x

// Restricted -- needed for seq
static member Map (x : Dictionary<_,_>, f : 'T->'U, _mthd : Map) = 
    let d = Dictionary() in Seq.iter 
        (fun (KeyValue(k, v)) -> d.Add(k, f v)) x; d: Dictionary<'Key,'U>
static member Map (x : Expr<'T>       , f : 'T->'U, _mthd : Map) = 
    Expr.Cast<'U>(Expr.Application(Expr.Value(f),x))

The heart of it all

Map

1: 
let inline map (f:'T->'U) (x:'A) :'B = Map.Invoke f x

Before we dive in

A demo

1: 
2: 
3: 
4: 
5: 
6: 
#r "../src/build/PresentationCode.dll"
open Coletto.TypeClassish.Collections.Mapping

let afp = fpmap ((+) 10) (Some 3)
let bfp = fpmap ((+) 10) [|1..3|]
let cfp = fpmap ((+) 10) {1..3} 
Some 13
[|11; 12; 13|]
seq [11; 12; 13]

Demo Cont'd

1: 
2: 
3: 
4: 
5: 
6: 
7: 
type TestType<'a> = TestType of 'a*'a with
    static member Map (x:TestType<_>, f : 'T->'U) = 
        let (TestType(a,b)) = x
        TestType(f a,f b)

let dfp = fpmap ((*) 10.0) (TestType(5.,5.))
let efp = fpmap ((*) 10) (TestType(5,5))
TestType (50.0,50.0)
TestType (50,50)

Demo Cont'd

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
type Tree<'t> =
    | Tree of 't * Tree<'t> * Tree<'t>
    | Leaf of 't
    static member Map (x:Tree<'a>, f) = 
        let rec loop f = function
            | Leaf x -> Leaf (f x)
            | Tree (x, t1, t2) -> Tree (f x, loop f t1, loop f t2)
        loop f x

let ffp = fpmap ((*) 10) (Tree(6, Tree(2, Leaf 1, Leaf 3), Leaf 9))
Tree (60,Tree (20,Leaf 10,Leaf 30),Leaf 90)

Looking at the help functions in FSharpPlus

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
// Handles Types with overloaded Map
static member inline Invoke (mapping :'T->'U) (source : 'A) : 'B = 
    let inline call (mthd : ^M, source : ^I, _output : ^R) = ((^M or ^I or ^R) : 
                            (static member Map: _*_*_ -> _) source, mapping, mthd)
    call (Unchecked.defaultof<Map>, source, Unchecked.defaultof<'B>)

// Handles Types with a single Map
static member inline InvokeOnInstance (mapping :'T->'U) (source : 'A) : 'B = 
    (^A : (static member Map: _ * _ -> _) source, mapping)

// Related to the single map case
static member inline Map (x : 'A , f : 'T->'U, _impl:Default1) = 
    Map.InvokeOnInstance f x : 'B

Let's focus on the case of generic Map on your own Type

With a non-overloaded Map member

Deeper dive on Types with Single Map member

Define a function that allows us to map on our own Types

1: 
2: 
let inline nsmap (mapping :'T->'U) (source : 'A) : 'B =  
    (^A : (static member Map: _ * _ -> _) source, mapping)

That's it.

Take a function 'T->'U and a source type 'A and spit back out 'B Static member constraint specified that type A has to define Map with type _*_ -> _

Let's run our tree through it

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
let inline nsmap (mapping :'T->'U) (source : 'A) : 'B =  
    (^A : (static member Map: _ * _ -> _) source, mapping)
type Tree<'t> =
    | Tree of 't * Tree<'t> * Tree<'t>
    | Leaf of 't
    static member Map (x:Tree<'a>, f) = 
        let rec loop f = function
            | Leaf x -> Leaf (f x)
            | Tree (x, t1, t2) -> Tree (f x, loop f t1, loop f t2)
        loop f x

let nsres = nsmap ((*) 10) (Tree(6, Tree(2, Leaf 1, Leaf 3), Leaf 9))
Tree (60,Tree (20,Leaf 10,Leaf 30),Leaf 90)

Good!

Clean up the sig

We can use quotations to clean the signature up a little if we like too

Let's bring that back into a type as a helper function

...which brings it back identically to the helper type in FSharpPlus's Map Type

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
type Map =
    static member inline InvokeOnInstance (mapping :'T->'U) (source : 'A) : 'B = 
        (^A : (static member Map: _ * _ -> _) source, mapping)

let inline fsmap (f:'T->'U) (x:'A) :'B = Map.InvokeOnInstance f x

//Re-Use the old Tree Type
let ffs = fsmap ((*) 10) (Tree(6, Tree(2, Leaf 1, Leaf 3), Leaf 9))
Tree (60,Tree (20,Leaf 10,Leaf 30),Leaf 90)

Now let's work on Types with overloads

The important bits in FSharpPlus

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
type Default2 = class end
type Default1 = class inherit Default2 end

[<Extension;Sealed>]
type Map =
    inherit Default1

    static member inline Invoke (mapping :'T->'U) (source : 'A) : 'B = 
        let inline call (mthd : ^M, source : ^I, _output : ^R) = 
            ((^M or ^I or ^R) : (static member Map: _*_*_ -> _) source, mapping, mthd)
        call (Unchecked.defaultof<Map>, source, Unchecked.defaultof<'B>)

let inline fpmap (f:'T->'U) (x:'A) :'B = Map.Invoke f x
1: 
2: 
type Default2 = class end
type Default1 = class inherit Default2 end

Are used to help the compiler align which overloads to call. Let's take a look at how this works in FSharpPlus

1: 
2: 
3: 
4: 
static member Map (x : seq<_>    , f : 'T->'U, _impl:Default2) = 
    Seq.map f x              : seq<'U>
static member Map (x : option<_> , f : 'T->'U, _mthd : Map)    = 
    Option.map  f x
  • The third parameter is an unused param of type Default2(where Default2 <- Default1 <- Map).
    -- In most cases it's typed to the current class.
  • In seq's case, it's kicked up the class hierarchy to default2.

I still can't say why for sure at this point, but this appears to be used to type methods back to this class, and in some cases massage the type checker and compiler back into compliance with what we're trying to do.
More on the last part in the next slide...

Seq messed things up. Other things probably do too.

Having seq in the mix messes up the typing of the generic map function by forcing it to be constrained to the seq type. We actually hit this problem in our above operator overloading methods, but I cut sequence out to save the discussion for this slide.

1: 
2: 
3: 
4: 
5: 
6: 
// Restricted -- needed for seq
static member Map (x : Dictionary<_,_>, f : 'T->'U, _mthd : Map) = 
    let d = Dictionary() in Seq.iter 
        (fun (KeyValue(k, v)) -> d.Add(k, f v)) x; d: Dictionary<'Key,'U>
static member Map (x : Expr<'T>       , f : 'T->'U, _mthd : Map) = 
    Expr.Cast<'U>(Expr.Application(Expr.Value(f),x))

The above code fixes the type inference on map when seq is added... Not entire sure why. But it does.
Without it, map won't work for anything other than a sequence

That's it.

With the code we just covered we're back at the minimum generic mapping Type we showed code to earlier

The End

FSharp logo Prolucid logo
Questions?
  • William Coletto
  • @willisbueller
  • github/angrydexterous