Combining Bag/OrdList?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Combining Bag/OrdList?

Andreas Klebinger
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.

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Combining Bag/OrdList?

Kavon Farvardin
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.

> On Jun 2, 2018, at 5:13 AM, Andreas Klebinger <[hidden email]> wrote:
>
> 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.
> _______________________________________________
> ghc-devs mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Combining Bag/OrdList?

Andreas Klebinger
> 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.
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.


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.


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Combining Bag/OrdList?

Ben Gamari-2
Andreas Klebinger <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Combining Bag/OrdList?

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)?

Jared

On Sat, Jun 2, 2018, 10:39 AM Ben Gamari <[hidden email]> wrote:
Andreas Klebinger <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Combining Bag/OrdList?

Ben Gamari-2
Jared Weakly <[hidden email]> writes:

>> 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)?
>
Absolutely. I think that is the right direction to move. Please do give
it a stab if you would like!

Cheers,

- Ben

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Combining Bag/OrdList?

Joachim Breitner-2
In reply to this post by Jared Weakly
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
  [hidden email]
  http://www.joachim-breitner.de/

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Combining Bag/OrdList?

Ben Gamari-2
Joachim Breitner <[hidden email]> writes:

> 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)?
>
Yes, this seems unavoidable. However, the documentation would make it
clear that the returned order is arbitrary.

Cheers,

- Ben


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

RE: Combining Bag/OrdList?

GHC - devs mailing list
In reply to this post by Ben Gamari-2
|  > 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 <[hidden email]> On Behalf Of Ben Gamari
|  Sent: 02 June 2018 18:39
|  To: Andreas Klebinger <[hidden email]>; Kavon Farvardin
|  <[hidden email]>
|  Cc: [hidden email]
|  Subject: Re: Combining Bag/OrdList?
|  
|  Andreas Klebinger <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs