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: -- (:)
From: Thorsten Ohl <ohl@h...>
Subject: [Caml-list] "super-compaction" of values
Markus Mottl writes:

> has anybody already attempted to implement some kind of
> "super-compaction" [...] 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.

I'm sure that one can not beat the combinatorial complexity of the
general case.  For example, I work with algebraic expressions that
grow in size like (2n-1)!! = (2n-1)(2n-3)(2n-5)... if represented as
trees, but can be rewritten as DAGs of size 10**(n/2) [see and in particular
the chapter Directed Acyclical Graphs in].

In my experience, one can beat the combinatorial complexity only if
one understands the genesis of such values with high sharing
potential.  Then one can construct algorithms that start from building
all possible combinations in a highly condensed representation and
select the interesting ones later.  This will be much more efficient
than building only the interesting ones and searching for shared nodes

But this is never a general solution, because it requires a good
unterstanding of the structure of possible terms.
Thorsten Ohl, Physics Department, TU Darmstadt -- [<=== PGP public key here]
Bug reports:  FAQ:
To unsubscribe, mail  Archives: