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.

It looks to me like many of the applications of snocBag should really be using OrdList.

Do you think there's benefit in refactoring to use ordList and then removing snoc/cons from the bag API (instead providing only operations that make no assumptions about ordering)? Jared On Sat, Jun 2, 2018, 10:39 AM Ben Gamari wrote:

Andreas Klebinger writes:

...

...

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.

It looks to me like many of the applications of snocBag should really be using OrdList.

In my opinion we should keep the two types apart and simply be more careful about when we use each. There is value in being precise about whether or not ordering of a structure is relevant, even if we don't take advantage of this in the structure's representation.

Cheers,

- Ben _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Hi, Am Samstag, den 02.06.2018, 10:55 -0700 schrieb Jared Weakly:

...

It looks to me like many of the applications of snocBag should really be using OrdList.

Do you think there's benefit in refactoring to use ordList and then removing snoc/cons from the bag API (instead providing only operations that make no assumptions about ordering)?

would you remove `toList` (which has to fix an ordering)? Cheers, Joachim -- Joachim Breitner mail@joachim-breitner.de http://www.joachim-breitner.de/

| > Imo we lost that ability by exposing consBag & snocBag which imply | > that there is a front and a back. Excellent point! I agree with Ben here. * We should rename consBag/snocBag to extendBag * And use OrdList instead of Bag in any places where the order matters. Figuring out which those places are would require a little study. Simon | -----Original Message----- | From: ghc-devs On Behalf Of Ben Gamari | Sent: 02 June 2018 18:39 | To: Andreas Klebinger ; Kavon Farvardin | | Cc: ghc-devs@haskell.org | Subject: Re: Combining Bag/OrdList? | | Andreas Klebinger writes: | | > > 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. | > | It looks to me like many of the applications of snocBag should really | be using OrdList. | | In my opinion we should keep the two types apart and simply be more | careful about when we use each. There is value in being precise about | whether or not ordering of a structure is relevant, even if we don't | take advantage of this in the structure's representation. | | Cheers, | | - Ben