> we are free to improve the implementation of Bag in the future so that it doesn’t preserve order

Imo we lost that ability by exposing consBag & snocBag which imply that there is a front and a back.
Which at first glance also seem to be already used in GHC with that behavior in mind.

I agree with the thought that not guaranteeing an ordering might have benefits.
But in practice they are almost the same data structure with slightly different interfaces.
Kavon Farvardin
Samstag, 2. Juni 2018 18:00
If we have an algorithm that only needs a Bag, then we are free to improve the implementation of Bag in the future so that it doesn’t preserve order under the hood (e.g, use a hash table). So, I personally think it’s useful to have around.

Sent from my phone.


Andreas Klebinger
Samstag, 2. Juni 2018 12:13
We have OrdList which does:

Provide trees (of instructions), so that lists of instructions
can be appended in linear time.

And Bag which claims to be:

an unordered collection with duplicates

However the actual implementation of Bag is also a tree if things.
Given that we have snocBag, consBag that implies to me it's
also an ordered collection.

I wondered if besides of someone having to do it if there is a reason why these couldn't be combined
into a single data structure? Their implementation seems similar enough as far as I can tell.