ARec can't be grown/shrunk

[typedrat]

ARec has a fixed size, meaning that when an element needs to be added or removed we have to round-trip to Rec. Even if we can stay on one side or the other with few switches, it still requires using the complex (honestly, beyond me) Rec-type generic interface.

[acowley]

I’d welcome input. The considerations are that Rec is an efficient structure if you want to add elements to the front of it, while ARec is great for random reads. We can do like the C++ std::vector and maintain separate size and capacity, but that more naturally adds elements to the back.

If we go that route, should we then arrange that elements are stored in reverse order in the array from the type-level list (so as to present a more consistent API between Rec and ARec)?

At the type-level, cons’ing to the front of the list of types is certainly less work than appending to the end, so offering a back-insertion API for ARec would present challenges on the type level.

Lastly, do we care about the extra memory use needed to reasonably amortize the cost of adding elements as is done with std::vector? Probably we don’t, but we should probably add a trim function that duplicates an ARec while setting the duplicate’s capacity exactly to its size.

What do you think? This would result in a function (name tbd) with type f a -> ARec f rs -> ARec f (a ‘: rs).

Edit: I managed to bury the lede here, actually. That kind of approach generally requires unsafe operations. Doing it purely would require something more like a rope than an array structure. I left out this API before because going through Rec was an option. The model in my mind is to effectively “thaw” an ARec into a Rec, perform your additions, then “freeze” the Rec into an ARec. I’m not entirely against providing an unsafe API that does the std::vector thing, or providing an ST API to support this kind of thing, but either of those is a departure from usual record operations in Haskell.

[typedrat]

Wouldn't doing something analogous to Vector Any rather than Array Int Any work? I don't see how that'd be unsafe.

[acowley]

It’s the efficiency that’s at question. We can use Vector, but Data.Vector.cons is O(n) while the corresponding Rec constructor is O(1).

[typedrat]

Oh, I know the difference in complexities, it's more that I don't really care, because the number of lookups (potentially one per bind in a given monad) is way, way, way bigger than the number of changes, which are 95% of the time just up front but it does need to support adding things after the fact.

[acowley]

Fair enough; let’s do it. Any thoughts on naming? I don’t want to do anything clever, so perhaps calling it cons is worth the potential quibbles at import sites. Will you open a PR?

[typedrat]

Any thoughts on naming?

cons or acons is fine with me.

Will you open a PR?

I can try and get it taken care of soon, but admittedly I'm very busy right now and this isn't priority zero for me.