Blog

OCaml QuickCheck: Translating QuickCheck from Haskell Type Classes to OCaml Modules

Posted by on January 16th, 2009.

One of the things I miss the most making the switch from Haskell to OCaml is Haskell’s type classes. Instead, OCaml has higher-order modules, which is a fancy way of saying modules that can take other modules as parameters. The main advantage of type classes is that the compiler infers them automatically which saves considerable typing and makes them easier to modify.

There is a direct translation of type classes into modules. So as an experiment, I translated the Haskell QuickCheck library, which uses type classes heavily, into OCaml. The translation was a more or less mechanical conversion of the Haskell type class based code into the equivalent OCaml modules.

Translation Overview

Type Classes Become Module Types

The first step is to convert every type class in the Haskell code into a module signature. For example, here is a simplified declaration for the standard type class Show:

class Show a where
    show :: a -> String

which just says that instances of Show have a function show that converts them into a string. The equivalent module signature looks like this:

module type SHOW = sig
  type t
  val show : t -> string
end
Instances Become Modules

In Haskell if you want a type to have a definition for show you need to declare that it is an instance of the Show class.

instance Show Int where
    show = ... -- omitted since the Show Int instance is built-in

In OCaml we just create a module that happens to have the right stuff

module ShowInt = struct
  type t = int
  let show = string_of_int
end
Callers Get Wrapped In Functors

Functions that use type classes do not need to do anything special in Haskell. Just by calling show the Haskell compiler can infer that the input type needs to be an instance of Show. Here is a (badly written) Haskell function that makes a string from a list of elements with newlines after each one:

onePerLine       :: Show a => [a] -> String
onePerLine []    = ""
onePerLine (h:t) = show h ++ "n" ++ onePerLine t

The type signature at the top is not strictly necessary because the compiler can infer it, but it shows what it looks like when a type is an instance of a type class.

Unfortunately, in OCaml to write a function that is parameterized on the implementation of show we need to put it inside a functor (a module that takes an argument) and pass the show implementation in to the module as a parameter:

module OnePerLine(S:SHOW) = struct
  let rec onePerLine : S.t list -> string =
    function
        []   -> ""
      | h::t -> S.show h ^ "n" ^ onePerLine t
end

In this case, the declaration that module S conforms to the SHOW signature is required.

Every Caller Thereafter Instantiates Modules

When we call our function in Haskell, the compiler automatically figures out which instances are involved, so all the programmer has to do is use the function.

x = onePerLine [1,2,3,4]

However, in OCaml you must manually instantiate the version of the function that you want to use.

module X = OnePerLine(ShowInt)
let x = X.onePerLine [1; 2; 3; 4]

The OCaml QuickCheck Library

Because of the need to explicitly instantiate the modules, in practice the OCaml translation of QuickCheck is probably too verbose to use. For example, here is a simple test of list reversal written in Haskell

import Test.QuickCheck

prop_RevRev :: [Int] -> Bool
prop_RevRev xs = reverse (reverse xs) == xs

main = quickCheck prop_RevRev

Pretty straightforward right? There is a property and the call to quickCheck to validate the property. You can’t tell from this source code, but there is a lot of work being done by the compiler under the hood. Check out the signature for the quickCheck function:

quickCheck :: Testable a => a -> IO ()

Basically, its a function that takes anything Testable which includes boolean values, functions that return boolean values, etc. Our property is and instance of Testable because any function from an instance of Arbitrary (meaning we can generate values at random) to something Testable is also Testable and Bool is Testable. The compiler automatically strings together all those instances and just lets you call quickCheck without having to think about it. The only notable restriction in this code is that the type of prop_RevRev needs to be monomorphic (no type variables) so that the compiler can nail down what instances to use.

Here is the equivalent test using OCaml QuickCheck.

open QuickCheck

let prop_revrev : 'a list -> bool =
  fun xs -> List.rev (List.rev xs) = xs

(* for generating random int lists *)
module AL = Arbitrary_list(Arbitrary_int) ;;
(* for printing out int lists *)
module SL = PShow_list(PShow_int) ;;
(* for being able to test (int list -> bool) *)
module Testable_list_to_bool =
  Testable_fun
    (AL)
    (SL)
    (Testable_bool) ;;
module C = Check(Testable_list_to_bool)
let () = C.quickCheck prop_revrev

In the OCaml version we need to explicitly instantiate all of the modules necessary to parameterize quickCheck. These modules mirror the type classes that are automatically inferred in the Haskell example.

In OCaml the property is just as easy to write, but actually testing it is quite a pain. However, if you have a number of properties with the same signature, then the pain of instantiating quickCheck could be diluted enough to be worth it.

Feel free to use OCaml QuickCheck in your own projects if its useful to you. Bug reports, enhancement requests and code submissions are always welcome. The code is hosted at GitHub so you can follow any changes there as well as fork your own copy.

Posted in Al Falloon | Tagged in ,, | Print | Email