RE: Combining Bag/OrdList?

[Simon Peyton Jones via ghc-devs]

|  > 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
___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Re: Combining Bag/OrdList?

[Ben Gamari]

Joachim Breitner  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



signature.asc
Description: PGP signature
___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Re: Combining Bag/OrdList?

[Joachim Breitner]

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
  m...@joachim-breitner.de
  http://www.joachim-breitner.de/


signature.asc
Description: This is a digitally signed message part
___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Re: Combining Bag/OrdList?

[Ben Gamari]

Jared Weakly  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


signature.asc
Description: PGP signature
___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

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  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
>
___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Re: Combining Bag/OrdList?

[Ben Gamari]

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


signature.asc
Description: PGP signature
___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

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.

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.


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

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  
> 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
> ghc-devs@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

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

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
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs