Blog: Mr. Mathiesen

F# - Functors with Record Types (now with map)

March 30, 2016.

Updated

Based on feedback from Joakim, fellow co-founder of the F#unctional Copenhageners Meetup Group - MF#K, in order to be a functor it must define a map function with the follwoing signature map: (‘a -> ‘b) -> ‘a t -> ‘b t. For more info, see References Defining Functors in Scala.

Code Snippet:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

type ('a,'b) Set =
  private
    { empty: 'a t
      add: 'a -> 'a t -> 'a t
      exists: 'a -> 'a t -> bool
      map: ('a -> 'b) -> 'a t -> 'b t }
  member x.Empty = x.empty
  member x.Add y ys = x.add y ys
  member x.Exists y ys = x.exists y ys
  member x.Map f ys = x.map f ys
  static member Functor (orderType) : Set<'a,'b> =
    { empty = { t = Nil }
      add = fun x xs ->
        let rec add y = function
        | Nil         -> Cons(y,Nil)
        | Cons(hd,tl) ->
          match orderType.compare y hd with
          | Less -> Cons(x,xs.t)
          | Equal -> xs.t
          | Greater -> Cons(hd,add y tl)
        { t = add x xs.t }
      exists = fun x xs ->
        let rec exists y = function
        | Nil -> false
        | Cons(hd,tl) ->
          match orderType.compare y hd with
          | Less -> false
          | Equal -> true
          | Greater -> exists y tl
        exists x xs.t
      map = fun f xs -> 
        let rec map = function
        | Nil -> Nil
        | Cons(hd,tl) -> Cons(f hd, map tl)
        { t = map xs.t } }
and ('a) t = private { t : 'a s }
and ('a) s = private Cons of 'a * 'a s | Nil
and ('a) OrderType = { compare: 'a -> 'a -> Comparison }
and Comparison = Less | Equal | Greater

Code output:

> 
type ('a,'b) Set =
  private {empty: 'a t;
           add: 'a -> 'a t -> 'a t;
           exists: 'a -> 'a t -> bool;
           map: ('a -> 'b) -> 'a t -> 'b t;}
  with
    member Add : y:'a -> ys:'a t -> 'a t
    member Exists : y:'a -> ys:'a t -> bool
    member Map : f:('a -> 'b) -> ys:'a t -> 'b t
    member Empty : 'a t
    static member Functor : orderType:'a OrderType -> ('a,'b) Set
  end
and 'a t =
  private {t: 'a s;}
and 'a s =
  private | Cons of 'a * 'a s
          | Nil
and 'a OrderType =
  {compare: 'a -> 'a -> Comparison;}
and Comparison =
  | Less
  | Equal
  | Greater

Code Snippet:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

let set () =
  Set<_,_>.Functor
    { compare = fun x y ->
        if x = y then
          Equal
        else if x < y then
          Less
        else
          Greater }

let stringSet =
  set().Empty
  |> set().Add "42"
  |> set().Add "43"

stringSet |> set().Exists "42"
stringSet |> set().Exists "43"
stringSet |> set().Exists "84"
stringSet |> set().Exists "86"

let intSet =
  stringSet
  |> set().Map (fun x -> int x)
  |> set().Map (fun x -> x + x)

intSet |> set().Exists 42
intSet |> set().Exists 43
intSet |> set().Exists 84
intSet |> set().Exists 86

let floatSet =
  intSet
  |> set().Map (fun x -> float x)

floatSet |> set().Exists 42.
floatSet |> set().Exists 43.
floatSet |> set().Exists 84.
floatSet |> set().Exists 86.

Code output:

> 
val set : unit -> ('a,'b) Set when 'a : comparison

> 
val stringSet : string t

> val it : bool = true
> val it : bool = true
> val it : bool = false
> val it : bool = false
 
> 
val intSet : int t

> val it : bool = false
> val it : bool = false
> val it : bool = true
> val it : bool = true
 
> 
val floatSet : float t

> val it : bool = false
> val it : bool = false
> val it : bool = true
> val it : bool = true

References: