Implementing Haskell classes in F#

Haskell got a nice system of classes. Though the name reminds us of the OOP term, these “classes” are very different in their use. Here is an example for people who are not familiar with Haskell classes:

class Eq a where 
  (==) :: a -> a -> Bool

(==) :: (Eq a) => a -> a -> Bool

instance Eq Integer where 
  x == y = x `integerEq` y

Ideally, our F# code would look like:

class 'a eq =
	val (==) : 'a -> 'a -> bool

// the type of (==) is:
// "'a -> 'a -> bool if 'a eq exists"

implement int eq with
	let (==) a b = a = b

Without editing the compiler (I am going to consider writing an article about a compiler modification which adds support for Haskell classes), we won’t get such a good result, so we’ll have to give up (some of) the sugar. This is the first prototype I wrote:

type type'(t : System.Type) =
  member this.T = t
  interface System.IComparable with
    member this.CompareTo v =
      (t.ToString() :> System.IComparable).CompareTo((v :?> type').T.ToString())

module eq =
  let mutable private map : Map<type', obj> = [] |> Map.ofList
  let register t f = map <- map.Add(type'(t), f)
  let get t = unbox map.[type'(t)]

eq.register typeof<int> (fun (a : int, b) -> a = b)

let (==) a b = ((eq.get (a.GetType())) (a, b)) : bool

Ugly, limited – but imitates its Haskell equivalent. The next step would be to build scaffolding in order to minimize the code for each class. Here is the scaffolding:

type type'(t : System.Type) =
  member this.T = t
  interface System.IComparable with
    member this.CompareTo v =
      (t.ToString() :> System.IComparable).CompareTo((v :?> type').T.ToString())

module classes =
  let mutable private map : Map<string, Map<type', obj>> = [] |> Map.ofList

  let define name = map <- map.Add(name, [] |> Map.ofList)

  let register class' t r =
    let t = type'(t)
    let mutable class'' = map.[class']
    match class''.TryFind t with
    | None ->
      ()
    | Some _ ->
      class'' <- class''.Remove t
      map <- map.Remove(class').Add(class', class''.Add(t, r))

  let get class' t = unbox map.[class'].[type'(t)]

And the code for the eq class itself:

classes.define "eq"

type 'a eq = { f : ('a * 'a -> bool) }

let (==) a b = (((classes.get "eq" (a.GetType())) : 'a eq).f (a, b)) : bool

classes.register "eq" typeof<int> { f = (fun (a : int, b) -> a = b) }

We first define the class eq in the “classes” module. We then define the eq record. We then define the F# operator (==) to access the eq’s function. Next step is implementing the int eq instance. Only thing that is left is to put friendly error messages – but you don’t need me for that.

This entry was posted on Saturday, October 23rd, 2010 at 11:31 AM and is filed under Default. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

Leave a Reply