klebinger.andreas at gmx.at
Sat Jun 2 17:03:02 UTC 2018
> 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
But in practice they are almost the same data structure with slightly
> Kavon Farvardin <mailto:kavon at 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 at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the ghc-devs