What's the closest thing to Haskell's typeclasses in OCaml?

Question

What are some ways that I can accomplish what Haskell's typeclasses do in OCaml? Basically, I want to write a polymorphic function without writing too much code. The typical way to do polymorphism is to supply an additional argument telling the function is what type it is currently working on. For example, let's say I want to sort a list of ints, I have to pass an additional comparator to the function.

type comparison = Lesser | Equal | Greater

my_sort : (a' -> a' -> comparison) -> 'a list -> 'a list

Is there anyway to tell OCaml that my type is comparable without writing a comparator function for every type that I want to sort? Which means that my sorting function would look just like this:

my_sort : 'a list -> 'a list

Solution 1

It really depends what you want to achieve.

If you are happy with the OCaml polymorphic comparison function (which will not work on cyclic and functional values), you can simply write:

let my_sort l = List.sort Pervasives.compare l

The more generic way to mimic type classes is to use functors:

module type COMPARABLE = sig
  type t
  val compare: t -> t -> int
end

module MySort (C: COMPARABLE) = struct
  let sort l = List.sort C.compare l
end

(* You can now use instantiate the functor *)
module IntAscending = struct
  type t = int
  let compare = (-)
end
module IntDescending = struct
  type t = int
  let compare x y = y - x (* Reverse order *)
end

module SortAsc = MySort(IntAscending)
module SortDesc = MySort(IntDescending)

Solution 2

This is explained in detail in "Modular Type Classes" by Derek Dreyer, Robert Harper, and Manuel M. T. Chakravarty. In Proceedings of The 34th Annual ACM SIGPLAN - SIGACT Symposium on Principles of Programming Languages, ACM Press, 2007. From the abstract:

ML modules and Haskell type classes have proven to be highly effective tools for program structuring. Modules emphasize explicit configuration of program components and the use of data abstraction. Type classes emphasize implicit program construction and ad hoc polymorphism. In this paper, we show how the implicitly-typed style of type class programming may be supported within the framework of an explicitly-typed module language by viewing type classes as a particular mode of use of modules. This view offers a harmonious integration of modules and type classes, where type class features, such as class hierarchies and associated types, arise naturally as uses of existing module-language constructs, such as module hierarchies and type components. In addition, programmers have explicit control over which type class instances are available for use by type inference in a given scope. We formalize our approach as a Harper-Stone-style elaboration relation, and provide a sound type inference algorithm as a guide to implementation.

Solution 3

I came across a really nice article demonstrating the translation between types and type classes in Haskell and modules and module types in OCaml: http://conway.rutgers.edu/~ccshan/wiki/blog/posts/Translations/

Basically, as @Thomas showed, type classes in Haskell become module types in OCaml with a type (the type implementing the type class) and a bunch of values using that type.

Then, corresponding to an "instance" of the type class in Haskell, you have a module in OCaml that implements the module type, with the type being the type of the instance, and the values being the implementation of the values in the type class.

And then, every time you have a function that "uses" a type constrained by that type class in Haskell, you need to wrap that function inside a module in OCaml. This module (actually a functor) will take an argument module which corresponds to the instance of the type class we are using.

And every time you use that function, you will need to first create an appropriate module using that functor and passing it the right instance of the type class.

You will notice that a big difference in the Haskell and OCaml ways of doing it, is that in Haskell, when you use that last function, the compiler infers the proper instance of the type class for you; whereas with the OCaml way of doing it, the user must explicitly specify the instance to use.

Solution 4

Although not as close to Haskell as modules, class types over the hierarchy of object classes are not clearly explained.

See class type definitions.

Update: working example:

type comparison = Lesser | Equal | Greater

class type comparable = object ('a)
  method compareTo: 'a -> comparison
end ;;

class type textualizable = object
  method toString: string
end ;;

(* this corresponds in Haskell to a multiparameter type class *)
class type ['b] printable = object ('a)
  constraint 'b = #textualizable         
  method printWithPrefix: 'b -> unit
end ;;

class type ['b] comparableAndPrintable = object ('a)
  inherit comparable
  inherit ['b] printable
end ;;

(* -------------- *)

class textile (str_init:string): textualizable = object
   val str = str_init
   method toString = str
end ;;

class comparableAndPrintableImpl1 (x_init: int) = object (this:'a)

  constraint 'a = 'b #comparableAndPrintable    (* interface implementation requirement *)
  constraint 'b = textualizable (* concrete type parameter *)

  val x = x_init
  method getx = x
  method compareTo (that:'a) = let r = this#getx - that#getx in
                               match r with
                               | 0 -> Equal
                               | _ when r < 0 -> Lesser
                               | _ -> Greater

  method printWithPrefix (pref: 'b)  = Printf.printf "%s %d\n" pref#toString x
end ;;

let boxSort (pivot: #comparable) (lows, equals, highs) (x: #comparable) =
      match x#compareTo pivot with
                    | Lesser -> x :: lows, equals, highs
                    | Equal -> lows, x :: equals, highs
                    | Greater -> lows, equals, x :: highs
      ;;

let rec qsort (li : #comparable list) =
      match li with
          [] | [_] -> li
          | [a;b] -> (match a#compareTo b with
                     Lesser | Equal -> [a;b]
                     | Greater -> [b;a]
                     )
          | x :: xs -> let (lows, equals, highs) = List.fold_left (boxSort x) ([], [], []) xs in
                       qsort lows @ (x :: equals) @ qsort highs
  ;;


let print_myList (prefix: 'a) (li: 'a #printable list) =
    let print_it it = it#printWithPrefix prefix in
    print_endline "\nlist: " ;
    List.iter print_it li
    ;;

let intlist (lfrom: int) (lto: int) =
   let open BatLazyList in
   to_list (range lfrom lto)              (* lazy range generator from BatLazyList *)
   ;;

let myComparableAndPrintableList =
  List.map (new comparableAndPrintableImpl1) (List.rev (intlist 1 5))
  ;;

let myprefix = new textile "x ="

let sortAndPrint (li: 'a #comparableAndPrintable list) =
   let sorted = qsort li in
   print_myList myprefix li ;
   print_myList myprefix sorted
   ;;

sortAndPrint myComparableAndPrintableList ;;

compile and link:

ocamlfind ocamlc -package batteries -linkpkg test.ml -o test

Solution 5

In general, since OCaml doesn't support implicit parameters, you need some kind of dictionary parameter to pass in type class instances explicitly. This can be implemented in terms of polymorphic records, first-class modules, or objects. I have a sample project showing a way using modules: https://github.com/hongchangwu/ocaml-type-classes

View more solutions

Comments

[rgrinberg]

Matias Giovanni shows how to do this in detail: alaska-kamtchatka.blogspot.ca/2009/08/fun-with-type-class.ht‌​ml

[Jason Yeo]

this looks the closest to what I wanna achieve! But, what does the BatList module do?

[Gabriel Riba]

I tried BatList from batteries because I wanted to use a list generator from BatLazyList named range wich acts as [from..to] in haskell, but I dismissed it ; you can change open BatList with open List and it works too.

[unhammer]

See also the "Modular Implicits" paper by White and Bour (which cites that paper as inspiration).

[Samuele Giraudo]

Interesting. A type in Haskell can derive several type classes (for example for types that are both showable and readable). Can OCaml modules and/or functors emulate this?