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 mailto:kavon@farvard.in 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 mailto:klebinger.andreas@gmx.at 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.