Re: [Caml-list] Sparse structure

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

From: Chris King <colanderman@gmail.com>

> I'm trying to create a sparse structure; i.e. a large structure which
> doesn't allocate storage for "unused" fields.  Given a structure:
> 
> type foo = { a: int option; b: float option }
> 
> the best solution I can come up with, short of using Obj.magic, is to
> use a hash table like this:
> 
> type foo_key = A_key | B_key
> type foo_value = A_value of int | B_value of float
> type sparse = (foo_key, foo_value) Hashtbl.t
> 
> which works, but the extra variant type required means more CPU time
> and more keystrokes.  Is there a better solution than this?
> 
> The structure will have hundreds of fields, each with a different
> type.  Most of the fields will be unused, but usage will be determined
> at runtime so using objects is not an option.

This is a classical problem, with no good solution that I know.

If you want to avoid Obj.magic, then your solution seems OK, yet
* if your values are really sparse, Map might be better than Hashtbl
  (more compact representation)
* if you have really hundreds of fields, then you have better switch
  to polymorphic variants, as normal ones only allow about 240 cases.

If you are ready to use a bit of Obj, then there are some other
solutions.
For instance, you could do something like this.

module Int = struct type t = int let compare : int -> int -> int = compare end
module M = Map.Make(Int)
type +'a elt
type 'a map = 'a elt M.t

let addA (x : 'a) (m : [> `A of 'a] map) =
  M.add (Obj.magic `A) (Obj.magic x) m

let addB (x : 'a) (m : [> `B of 'a] map) =
  M.add (Obj.magic `B) (Obj.magic x) m

let getA (m : [> `A of 'a] map) : 'a =
  Obj.magic (M.find (Obj.magic `A) m)

let getB (m : [> `B of 'a] map) : 'a =
  Obj.magic (M.find (Obj.magic `B) m)

Note that the result is completely type safe, and you don't need all
maps to contain the same potential fields.
The downside is that you need to define set and get for all fields.
On the other hand, it should be easy to define camlp4 macros
enforcing the same type annotations, avoiding such definitions.

(Polymorphic variants here are only used as phantom types. Note
however that this choice is useful: it ensures that two keys cannot
conflict, as if `A and `B had the same hash values, this would be
detected when constructing the type [> `A of 'a | `B of 'b])

Jacques Garrigue