I guess the specific example of my Actor-State does have an ordering relation, since the keys are all keyword symbols.
Oh, an ordering relation can be defined for almost anything. FSet has a generic function 'compare' that can be easily extended for new types.
Functional red-black trees are a fine choice. FSet has long used an older kind of balanced trees, called weight-balanced. More recently, I've added a relatively new hash-based data structure called CHAMP.
I track 15 MHz carriers to <100 μHz precision.
Impressive!
I did this implementation because a friend of mine involved in Actors machines suggested the JavaScript JSON Dictionary - which I find to be enormously redundant and noisy. Just a simple PList with keyword keys could fully replace them and great simplification. And so my Actor-State was an attempt to prove that out.
I fear that Purely Functional Red-Black Trees would be even more costly, but maybe not. I should look into it, or your FSet.
Haha, if you want small and simple, FSet might not be to your taste. My goal was to make it easy to use and featureful. It's pretty fast, though.
-- Scott
I guess the specific example of my Actor-State does have an ordering relation, since the keys are all keyword symbols. So good point on that O(log n). My simple implementation is just a copy / replace, which is O(n).
Yes, good points O(log n) cost. But that implies that elements have an ordering relation, no? Partial or total order. I have such structures that I use often, red-black trees that are purely functional implementations. So I understand your points here. But many times my data does not have any order relation, just an equality.
> BECOME takes a functional closure, which contains its state within the closure vars. But I have become frustrated with too many BOA args, and I also implemented a kind of dictionary to carry state with items labeled by a keyword.
Right. I saw your file 'actor-state.lisp' and thought "Ah! This is a functional map. This man needs FSet."
Yes, the state is in the closure vars, but that doesn't preclude it being large and complex. With functional data structures, you can efficiently prepare an updated version of a large structure without invalidating the previous version. If something goes wrong before the BECOME takes effect, no harm has been done; the tentative new version simply becomes garbage. The trick is to use only O(log n) space each time, where n is the size of the previous version.
-- Scott