How to parameterise a tree structure?


#1

I would like to be able to define a tree data structure (essentially as a map) and associated functions, such that the internal references can be type-parameterised to be either Rc<Node> or Arc<Node>, where Node is itself type-parameterised on the key and value types. My intent is that a tree structure that is managed solely by an active object need not use atomic operations when managing reference counts.

Is this achievable?


#2

Are you sure you even need ref-counting in a tree-structure? My approach for spatial trees in acacia was to use simple ownership models. I’m interested in generalizing this, too, but I haven’t gotten around to it yet. Last time I checked this was blocked on a bug in the type system.

My use case is a little bit different, but I think that type-system-wise, it is comparable. In essence, parametrizing over such types is feasible but you probably need to create your own trait to do that. This would be nicer with higher-kinded types, but with associated types you can kind of hack your way around that. See RFC 195 for how to do that.


#4

Yes, I want the API to be functional, and the various roots will be retained while the application needs them ie while a client is accessing the implied snapshot. Use-counting is arguably the simplest solution.