RFC `abag<'T>`

[krauthaufen]

I'm currently working on abag<'T> in an effort to find some equivalent to seq<'T> for adaptive.

Since order is hard to maintain adaptively (and alist already does that) we need some sort of unordered collection that does not care about duplicate elements (nor hash anything). I coined the term bag but I'm not entirely happy with it, so suggestions would be very welcome.

I implemented all the basic combinators I could come up with here and the current implementation gives rise to a few questions:

1. I need to create unique-ids for all elements in the bag in order to support removal. The only other alternative I could think of is a reference-counting HashSet where we could count the duplicates (but this would require hashing/etc on elements)
2. A clean way of using heterogenous keys would be really nice since alist and amap already contain unique-identifiers for each element but constantly boxing/unboxig all keys could be costly. So either cache unique-ids for each input-key (Index/amap-key) or use obj as key and live with boxing/unboxing in many places

More questions to come but if anyone has ideas/requests or spots problems feel free to comment

[iamim]

I believe that bag is the standard way of naming a collection without any constraints (uniqueness, order, though it makes removal problematic) 👍
I was thinking about similar problems, especially ordering and find/remove: alist ordering is hard to serialize incrementally and removal requires some sort of a key to be performed efficiently. One intuition that I got (but not verified yet) is that amap is the only abstraction that the system needs to implement. It deals with keys in a canonical way while ordering can be conveyed by converting 'value to (uint idx, 'value).
When done this way it becomes closer to a relational database structure. Every item has some sort of identity (primary key <-> amap key). Sets can be represented by amap<'t, unit>. Ordering is more ad-hoc than one may think: when querying a table with an ordered index the results are not guaranteed to be returned in that order (so it's more like a materialized view that you need to include in the query). Additional constraints (indexes) can be verified by keeping an additional data structure that needs to be consulted (if we have amap<int, 't> and there's a uniqueness constraint on 't with 't -> 'constraint we keep amap<'constraint, unit>).
So my point is that maybe encoding constraints as data structures is not the way to go? It seems to me that everything can be done with amap. As an added benefit, it eliminates m*n problem when writing combinators between collections.

[krauthaufen]

Hey, you're conceptually right of course and implementations for amap and alist are very much alike in many aspects. However combinators such as AList.collect : ('a -> alist<'b>) -> alist<'a> -> alist<'b> quicky make clear that maintaining order is anything but trivial.
Also using numbers for indexing doesn't really work with adaptive (would need to re-index everything when changes happen) which is why we're using Index (basically real-numbers via order-maintenance). AList internally handles this complexity without users even knowing much about it, so it definitely adds value there.

Furthermore the set-semantics is also more tricky than one might think at a first glance. Especially when operations like map : ('a -> 'b) -> aset<'a> -> aset<'b> are needed since this requires proper handling of duplicate elements in the set (consider cset [1;2;3;4] |> ASet.map (fun a -> a % 2) where someone removes 2 from the input)

Of course all combinators could be implemented on specialized amaps but that would not really make things simpler. Also the list-structures keep ordered representations internally and therefore don't need to be sorted externally.

While I think your argument is totally valid from a theoretical point-of-view I believe having separate data structures for list, set, map and maybe bag is the "sane" thing to do. Of course from a database perspective amap might be the only interesting thing, but adaptive is also used in rendering applications and UI programming where sets/lists play a much larger role.

Also FSharp.Core itself goes this way via Set, Map and list which could also be implemented using Map<'T, unit> or Map<Index, 'a>