This post originated from an RSS feed registered with Ruby Buzz by Eigen Class. Original Post: Heterogeneous containers in OCaml Feed Title: Eigenclass Feed URL: http://feeds.feedburner.com/eigenclass Feed Description: Ruby stuff --- trying to stay away from triviality. Latest Ruby Buzz Posts Latest Ruby Buzz Posts by Eigen Class Latest Posts From Eigenclass

There's a not that well known trick to implement heterogeneous, type-safe containers in OCaml (and friends: MLton uses them to decorate ASTs in different passes), known as property lists. Every once in a while I see people asking for how to do such a thing, so I'll show here a reasonably efficient implementation of mine here in order to refer to it later.

Property lists work very much like hash tables, allowing you to associate a value to a key. Unlike regular hash tables, though, they allow you to associate values of arbitrary types, possibly of different types for each key.

The key idea is to turn the key into a value that holds the type of the corresponding value. The signature of a property list is

module type PROPERTY_LIST =
sig
  type t

  val create : unit -> t
  val new_property : unit -> (t -> 'a -> unit) * (t -> 'a option)
end

A property is but a pair of functions which when given a property list either set or retrieve the property value. (The get function returns an option type because the value might not have been set.)

A module P with that signature would be used this way:

let get t (set, get) = get t
let set t (set, get) x = set t x

let name = P.new_property
let age = P.new_property

let table = P.create ()

(* ... *)

set table name "J.R. Hacker"

(* ... *)

print_endline (match get table name with None -> "<anon>" | Some x -> x)

Implementation

There are two ways to implement property lists: by using polymorphic exceptions, and via a reference (this is not thread-safe, but can be easily made so). The former are not available in OCaml, so we have to do with the latter. Without further ado, here's my implementation, which differs from the others you'll find in the ocaml-list archives in that set/get are constant-time operations, regardless of the number of elements in the property list:

module MappedList : PROPERTY_LIST =
struct
  type t = (int, unit -> unit) Hashtbl.t

  let create () = Hashtbl.create 13

  let new_id : unit -> int =
    let id = ref 0 in
      fun () -> incr id; !id

  let new_property () =
    let id = new_id () in
    let v = ref None in

    let set t x =
      Hashtbl.replace t id (fun () -> v := Some x) in

    let get t =
      try
        (Hashtbl.find t id) ();
        match !v with
            Some x as s -> v := None; s
          | None -> None
      with Not_found -> None
    in
      (set, get)
end

If you don't see why the above works, this "classic" (and inefficient, as said above) implementation might be easier to understand:

Read more...