Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] "super-compaction" of values
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2001-08-01 (10:20)
From: Markus Mottl <markus@m...>
Subject: [Caml-list] "super-compaction" of values

has anybody already attempted to implement some kind of "super-compaction"
of arbitrary values, e.g.:

  let list_a = [1, 2, 3, 4]
  let list_b =       [3, 4]

Both are in completely distinct parts of the memory. What I'd find
interesting is a module like:

  type 'a t

  val empty : unit -> 'a t
  val add : 'a -> 'a t -> 'a

which, when applied like this:

  let t = empty () in
  let la = add list_a t in
  let lb = add list_b t in

would return "la" unchanged but "lb" would now share the common structure
with list_a (= la) (also when inserted in any other order).

If this worked for arbitrary datastructures, one could exploit this to
produce very compact representations of values by maximizing the amount
of sharing between them.

One could use the "Obj"-module for this purpose. Problems, however, are:

  * Probably not useful for cyclic datastructures (too inefficient), but
    support of acyclic structures only would be ok.

  * Support automatic GC? Or should the user make sure that possible
    administrative memory overhead is prevented by telling "'a t" that
    some value need not be remembered for sharing with further values
    anymore.  The "automatic" version is probably less efficient and
    much more complicated.

An extreme form of this implementation could even have functions +
types like:

  val add : 'a -> t -> 'a

This would even allow sharing between representations of different types.

A correct and efficient implementation is probably everything else but
trivial. If anybody has already tried this crazy idea, I'd be interested
to know!

Markus Mottl

Markus Mottl                                   
Austrian Research Institute
for Artificial Intelligence        
Bug reports:  FAQ:
To unsubscribe, mail  Archives: