caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* [Caml-list] weak functional maps and ephemerons
@ 2018-12-20 18:44 Lindsay Errington
  0 siblings, 0 replies; only message in thread
From: Lindsay Errington @ 2018-12-20 18:44 UTC (permalink / raw)
  To: caml-list

[-- Attachment #1: Type: text/plain, Size: 1246 bytes --]

As mentioned in my previous post, I'd like to have weak functional maps.
Keeping it simple, suppose the maps are implemented as binary search trees
of key/value pairs where pairs are wrapped in an ephemeron:

module Eph = Ephemeron.K1
type key = ... (* something boxed and ordered *)
type 'a bst =
  | Empty
  | Node of {left : 'a bst; pair : (key,'a) Eph.t; right : 'a bst}

Cheating a little with pattern matching, if {left; pair=(Some k, Some v);
right} is an entry in a tree and I subsequently drop all references to k,
then my understanding is that following gc, both options will become None.
If I then encounter that node when looking for some k', I'm forced to merge
the left and right subtrees before continuing.

The question is, why does gc clobber the key in the ephemeron? Why not
provide the key when the ephemeron is created and collect the key when the
ephemeron is collected? For the above use-case, it would mean that one
could still search the tree and defer cleaning up the bst until later.

Lindsay

-- 
Caml-list mailing list.  Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list https://inbox.ocaml.org/caml-list
Forum: https://discuss.ocaml.org/
Bug reports: http://caml.inria.fr/bin/caml-bugs

[-- Attachment #2: Type: text/html, Size: 1221 bytes --]

^ permalink raw reply	[flat|nested] only message in thread

only message in thread, other threads:[~2018-12-20 18:45 UTC | newest]

Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-12-20 18:44 [Caml-list] weak functional maps and ephemerons Lindsay Errington

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).