caml-list - the Caml user's mailing list
 help / Atom feed
* [Caml-list] weak functional maps and ephemerons
@ 2018-12-20 18:44 Lindsay Errington
  0 siblings, 0 replies; 1+ messages 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.


Caml-list mailing list.  Subscription management and archives:
Bug reports:

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

^ permalink raw reply	[flat|nested] 1+ messages in thread

only message in thread, back to index

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

caml-list - the Caml user's mailing list

Archives are clonable:
	git clone --mirror
	git clone --mirror

Newsgroup available over NNTP:

AGPL code for this site: git clone public-inbox