One language feature I like most in Haskell is type class. It was originally conceived as a way of implementing overloaded arithmetic and equality operators. It is a clever trick to support ad-hoc polymorphism, which does not require extensive modifications of the compiler or the type system.

F# does not provide type class, but we can emulate it with other F# language features such as operator overloading and inline function. Type Classes for F# shows this trick. Here’s the Functor example taken from the blog:

type Fmap = Fmap with static member ($) (Fmap, x:option<_>) = fun f -> Option.map f x static member ($) (Fmap, x:list<_> ) = fun f -> List.map f x let inline fmap f x = Fmap $ x <| f

Here, `fmap`

function must be inline because inline functions can have statically resolved type parameters. Without the `inline`

modifier, type inference forces the function to take a specific type. In this case, the compiler can’t decide between `option`

and `list`

and emits an error.

You can use it as in the following:

> fmap ((+) 2) [1;2;3] ;; val it : int list = [3; 4; 5] > fmap ((+) 2) (Some 3) ;; val it : int option = Some 5

I transliterated the TreeRec example of Simon Thompson’s paper, Higher-order + Polymorphic = Reusable into F# by emulating type class in this way.

type Tree<'a> = | Leaf | Node of 'a * Tree<'a> * Tree<'a> type LeafClass = LeafClass with static member ($) (LeafClass, t:'a list) = [] static member ($) (LeafClass, t:Tree<'a>) = Leaf let inline leaf () : ^R = (LeafClass $ Unchecked.defaultof< ^R> ) type NodeClass = NodeClass with static member ($) (NodeClass, l1:'a list) = fun a l2 -> List.concat [l1; [a]; l2] static member ($) (NodeClass, t1:Tree<'a>) = fun a t2 -> Node(a, t1, t2) let inline node a x1 x2 = (NodeClass $ x1) a x2 type TreeRecClass = TreeRecClass with static member ($) (TreeRecClass, l:'a list) = fun f st -> let listToTree = function | [] -> failwith "listToTree" | a::x -> let n = List.length x / 2 let l1 = Seq.take n x |> Seq.toList let l2 = Seq.skip n x |> Seq.toList (a, l1, l2) let rec treeRec' = function | [] -> st | l -> let a, t1, t2 = listToTree l let v1 = treeRec' t1 let v2 = treeRec' t2 f v1 v2 a t1 t2 treeRec' l static member ($) (TreeRecClass, t:Tree<'a>) = fun f st -> let rec treeRec' f st = function | Leaf -> st | Node(a, t1, t2) -> f (treeRec' f st t1) (treeRec' f st t2) a t1 t2 treeRec' f st t let inline treeRec f st x = (TreeRecClass $ x) f st let inline tSort x = // FIXME: Implement sorting! let mVal sort1 sort2 v = List.concat [sort1; sort2; [v]] let mergeVal sort1 sort2 v t1 t2 = mVal sort1 sort2 v treeRec mergeVal [] x

One problem with this approach is that we no longer can group related operations together into a single class. It can’t express that Tree-like type t* has three operations: `leaf`

, `node`

and `treeRec`

. We end up having three distinct types `LeafClass`

, `NodeClass`

and `TreeRecClass`

.