Add DList to base

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

Add DList to base

winter
Currently GHC already defined DList for internal use in serveral places. This data type is a nature choice when you need CPS your append, which is a common need. I think base should provide it.

Cheers~
Winter

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

Re: Add DList to base

Ivan Lazar Miljenovic
On 5 June 2017 at 17:58, Dr.Koster <[hidden email]> wrote:
> Currently GHC already defined DList for internal use in serveral places.
> This data type is a nature choice when you need CPS your append, which is a
> common need. I think base should provide it.

It depends if GHC defines DList for use with base or not; if it's
something that's required to use base that _may_ be a semi-valid use
case.

In general though, as annoying as it is to have to add yet another
dependency, build, reload ghci, etc. I prefer to have base to be
smaller and packages split up and the dlist package serves admirably.
If nothing else, it can iterate faster if a new function needs to be
added.

Call this a weak +0.1(only because of GHC defining it).

--
Ivan Lazar Miljenovic
[hidden email]
http://IvanMiljenovic.wordpress.com
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

回复: Add DList to base

winter
Here's a example of Dlist in base: https://github.com/ghc/ghc/blob/master/libraries/base/GHC/Event/PSQ.hs#L468
And here is in GHC module: https://github.com/ghc/ghc/blob/ba597c1dd1daf9643b72dc7aeace8d6b3fce84eb/utils/mkUserGuidePart/DList.hs

It's so simple that people often define it with the code it's used, adding it to base can save these key stokes.

------------------ 原始邮件 ------------------
发件人: "Ivan Lazar Miljenovic";<[hidden email]>;
发送时间: 2017年6月5日(星期一) 晚上6:21
收件人: "Dr.Koster"<[hidden email]>;
抄送: "libraries"<[hidden email]>;
主题: Re: Add DList to base

On 5 June 2017 at 17:58, Dr.Koster <[hidden email]> wrote:
> Currently GHC already defined DList for internal use in serveral places.
> This data type is a nature choice when you need CPS your append, which is a
> common need. I think base should provide it.

It depends if GHC defines DList for use with base or not; if it's
something that's required to use base that _may_ be a semi-valid use
case.

In general though, as annoying as it is to have to add yet another
dependency, build, reload ghci, etc. I prefer to have base to be
smaller and packages split up and the dlist package serves admirably.
If nothing else, it can iterate faster if a new function needs to be
added.

Call this a weak +0.1(only because of GHC defining it).

--
Ivan Lazar Miljenovic
[hidden email]
http://IvanMiljenovic.wordpress.com

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

Re: Add DList to base

David Feuer
In reply to this post by winter
I'm -1 on this. For an abstract DList-style list builder, there's the
dlist package, which you shouldn't fear depending on (its only
dependencies are base and deepseq, both of which are GHC boot
packages). The dlist package defines a DList that's an instance of
MonadPlus, Traversable, IsList, Ord, Read, Show, IsString, Monoid, and
NFData, and provides a variety of functions for working with them.
Many of the instances and functions are, inherently, absurdly
inefficient. This is because there's basically *nothing* you can do to
a DList directly except build one up with `.` and tear one down with
`apply`. DLists are extremely efficient precisely when GHC is able to
optimize them away altogether. As soon as that is not the case,
they're mediocre at best.

Now suppose you want a non-abstract DList type (with the constructor exposed).

newtype DList a = DL { unDL :: [a] -> [a] }

What can that offer in the way of instances? Well, it's clearly not a
Functor, so it's certainly not Applicative, Monad, MonadPlus, or
Traversable. Ouch. There's no way to write matching Read and Show
instances, so you're stuck picking just one. Similarly, IsList and
IsString aren't guaranteed to round-trip properly. NFData is utterly
absurd, of course. So what's left? Foldable, Monoid, and either Read
or Show. The Foldable instance doesn't even interact nicely with the
Monoid instance: there's no guarantee that  foldMap f xs <> foldMap f
ys = foldMap f (xs <> ys). So there's pretty much *nothing going on
here*. DList x just doesn't have much more to offer than Endo [x]. We
already have Endo; ergo, we don't need DList.

On Mon, Jun 5, 2017 at 3:58 AM, Dr.Koster <[hidden email]> wrote:

> Currently GHC already defined DList for internal use in serveral places.
> This data type is a nature choice when you need CPS your append, which is a
> common need. I think base should provide it.
>
> Cheers~
> Winter
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add DList to base

Henning Thielemann

On Mon, 5 Jun 2017, David Feuer wrote:

> DList x just doesn't have much more to offer than Endo [x]. We already
> have Endo; ergo, we don't need DList.

I admit that I already used Endo as a quickly available DList replacement.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add DList to base

Tony Morris
Are there any DList specific functions, that are not provided by existing type-classes (such as Foldable), that are typically used? I can think of a few, but they are all in lens.

On Tue, Jun 6, 2017 at 4:24 PM, Henning Thielemann <[hidden email]> wrote:

On Mon, 5 Jun 2017, David Feuer wrote:

DList x just doesn't have much more to offer than Endo [x]. We already have Endo; ergo, we don't need DList.

I admit that I already used Endo as a quickly available DList replacement.

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


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

Re: Add DList to base

Ivan Lazar Miljenovic
On 9 June 2017 at 09:41, Tony Morris <[hidden email]> wrote:
> Are there any DList specific functions, that are not provided by existing
> type-classes (such as Foldable), that are typically used? I can think of a
> few, but they are all in lens.

singleton, cons, snoc

Though if you have singleton (which can be obtained from either Endo
or GHC.Ext.IsList.fromList and `(:[])`; alternatively you could use
pure/return but that is less pleasant IMO than the singleton function
for code legibility purposes) and mappend you can do cons and snoc.

>
> On Tue, Jun 6, 2017 at 4:24 PM, Henning Thielemann
> <[hidden email]> wrote:
>>
>>
>> On Mon, 5 Jun 2017, David Feuer wrote:
>>
>>> DList x just doesn't have much more to offer than Endo [x]. We already
>>> have Endo; ergo, we don't need DList.
>>
>>
>> I admit that I already used Endo as a quickly available DList replacement.
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>



--
Ivan Lazar Miljenovic
[hidden email]
http://IvanMiljenovic.wordpress.com
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Add DList to base

Tony Morris
Yeah, those are in lens, so I am less concerned that they don't appear in base. Specifically, if DList were not to exist in base, and I use the typeclasses that we all know as well as lens, what am I missing out on?

On Fri, Jun 9, 2017 at 10:30 AM, Ivan Lazar Miljenovic <[hidden email]> wrote:
On 9 June 2017 at 09:41, Tony Morris <[hidden email]> wrote:
> Are there any DList specific functions, that are not provided by existing
> type-classes (such as Foldable), that are typically used? I can think of a
> few, but they are all in lens.

singleton, cons, snoc

Though if you have singleton (which can be obtained from either Endo
or GHC.Ext.IsList.fromList and `(:[])`; alternatively you could use
pure/return but that is less pleasant IMO than the singleton function
for code legibility purposes) and mappend you can do cons and snoc.

>
> On Tue, Jun 6, 2017 at 4:24 PM, Henning Thielemann
> <[hidden email]> wrote:
>>
>>
>> On Mon, 5 Jun 2017, David Feuer wrote:
>>
>>> DList x just doesn't have much more to offer than Endo [x]. We already
>>> have Endo; ergo, we don't need DList.
>>
>>
>> I admit that I already used Endo as a quickly available DList replacement.
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>





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

Re: Add DList to base

Ivan Lazar Miljenovic
On 9 June 2017 at 14:15, Tony Morris <[hidden email]> wrote:
> Yeah, those are in lens, so I am less concerned that they don't appear in
> base. Specifically, if DList were not to exist in base, and I use the
> typeclasses that we all know as well as lens, what am I missing out on?

From a brief skim through the DList module documentation, those are
the only functions defined that do not have direct analogues in
existing typeclasses in base.

>
> On Fri, Jun 9, 2017 at 10:30 AM, Ivan Lazar Miljenovic
> <[hidden email]> wrote:
>>
>> On 9 June 2017 at 09:41, Tony Morris <[hidden email]> wrote:
>> > Are there any DList specific functions, that are not provided by
>> > existing
>> > type-classes (such as Foldable), that are typically used? I can think of
>> > a
>> > few, but they are all in lens.
>>
>> singleton, cons, snoc
>>
>> Though if you have singleton (which can be obtained from either Endo
>> or GHC.Ext.IsList.fromList and `(:[])`; alternatively you could use
>> pure/return but that is less pleasant IMO than the singleton function
>> for code legibility purposes) and mappend you can do cons and snoc.
>>
>> >
>> > On Tue, Jun 6, 2017 at 4:24 PM, Henning Thielemann
>> > <[hidden email]> wrote:
>> >>
>> >>
>> >> On Mon, 5 Jun 2017, David Feuer wrote:
>> >>
>> >>> DList x just doesn't have much more to offer than Endo [x]. We already
>> >>> have Endo; ergo, we don't need DList.
>> >>
>> >>
>> >> I admit that I already used Endo as a quickly available DList
>> >> replacement.
>> >>
>> >> _______________________________________________
>> >> Libraries mailing list
>> >> [hidden email]
>> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> >
>> >
>> >
>> > _______________________________________________
>> > Libraries mailing list
>> > [hidden email]
>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>> >
>>
>>
>>
>> --
>> Ivan Lazar Miljenovic
>> [hidden email]
>> http://IvanMiljenovic.wordpress.com
>
>



--
Ivan Lazar Miljenovic
[hidden email]
http://IvanMiljenovic.wordpress.com
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

回复: Add DList to base

winter
In reply to this post by David Feuer

> What can that offer in the way of instances? Well, it's clearly not a
> Functor, so it's certainly not Applicative, Monad, MonadPlus, or
> Traversable. Ouch. There's no way to write matching Read and Show
> instances, so you're stuck picking just one. Similarly, IsList and
> IsString aren't guaranteed to round-trip properly. NFData is utterly
> absurd, of course. So what's left? Foldable, Monoid, and either Read
> or Show. The Foldable instance doesn't even interact nicely with the
> Monoid instance: there's no guarantee that  foldMap f xs <> foldMap f
> ys = foldMap f (xs <> ys). So there's pretty much *nothing going on
> here*. DList x just doesn't have much more to offer than Endo [x]. We
> already have Endo; ergo, we don't need DList.
I think that's OK:

1) If we're concerning those inefficient instances(My understanding is those defined using `toList`, such as `Foldable` and `Functor`), we can just don't add them. 
2) Even `type DList a = Endo [a]` is OK, what i'm asking is CPSed operations (such as cons, replicate...) working on this type, not those instances. 

BTW. Isn't current `NFData`instance in dlist package problematic? We should directly `seq` the function IMHO.



------------------ 原始邮件 ------------------
发件人: "David Feuer";<[hidden email]>;
发送时间: 2017年6月6日(星期二) 中午11:09
收件人: "Dr.Koster"<[hidden email]>;
抄送: "libraries"<[hidden email]>;
主题: Re: Add DList to base

I'm -1 on this. For an abstract DList-style list builder, there's the
dlist package, which you shouldn't fear depending on (its only
dependencies are base and deepseq, both of which are GHC boot
packages). The dlist package defines a DList that's an instance of
MonadPlus, Traversable, IsList, Ord, Read, Show, IsString, Monoid, and
NFData, and provides a variety of functions for working with them.
Many of the instances and functions are, inherently, absurdly
inefficient. This is because there's basically *nothing* you can do to
a DList directly except build one up with `.` and tear one down with
`apply`. DLists are extremely efficient precisely when GHC is able to
optimize them away altogether. As soon as that is not the case,
they're mediocre at best.

Now suppose you want a non-abstract DList type (with the constructor exposed).

newtype DList a = DL { unDL :: [a] -> [a] }

What can that offer in the way of instances? Well, it's clearly not a
Functor, so it's certainly not Applicative, Monad, MonadPlus, or
Traversable. Ouch. There's no way to write matching Read and Show
instances, so you're stuck picking just one. Similarly, IsList and
IsString aren't guaranteed to round-trip properly. NFData is utterly
absurd, of course. So what's left? Foldable, Monoid, and either Read
or Show. The Foldable instance doesn't even interact nicely with the
Monoid instance: there's no guarantee that  foldMap f xs <> foldMap f
ys = foldMap f (xs <> ys). So there's pretty much *nothing going on
here*. DList x just doesn't have much more to offer than Endo [x]. We
already have Endo; ergo, we don't need DList.

On Mon, Jun 5, 2017 at 3:58 AM, Dr.Koster <[hidden email]> wrote:

> Currently GHC already defined DList for internal use in serveral places.
> This data type is a nature choice when you need CPS your append, which is a
> common need. I think base should provide it.
>
> Cheers~
> Winter
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>

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

Re: 回复: Add DList to base

David Feuer
The current NFData instance in dlist is the best you can do. seq on a function (very) rarely does what you want. The instance the package defines guarantees that the DList represents a list that can be reduced to normal form. The semantics are right. Efficiency-wise, it's lousy, but there's no way to fix it (without changing the underlying representation).

On Jun 13, 2017 11:26 PM, "Dr.Koster" <[hidden email]> wrote:

> What can that offer in the way of instances? Well, it's clearly not a
> Functor, so it's certainly not Applicative, Monad, MonadPlus, or
> Traversable. Ouch. There's no way to write matching Read and Show
> instances, so you're stuck picking just one. Similarly, IsList and
> IsString aren't guaranteed to round-trip properly. NFData is utterly
> absurd, of course. So what's left? Foldable, Monoid, and either Read
> or Show. The Foldable instance doesn't even interact nicely with the
> Monoid instance: there's no guarantee that  foldMap f xs <> foldMap f
> ys = foldMap f (xs <> ys). So there's pretty much *nothing going on
> here*. DList x just doesn't have much more to offer than Endo [x]. We
> already have Endo; ergo, we don't need DList.
I think that's OK:

1) If we're concerning those inefficient instances(My understanding is those defined using `toList`, such as `Foldable` and `Functor`), we can just don't add them. 
2) Even `type DList a = Endo [a]` is OK, what i'm asking is CPSed operations (such as cons, replicate...) working on this type, not those instances. 

BTW. Isn't current `NFData`instance in dlist package problematic? We should directly `seq` the function IMHO.



------------------ 原始邮件 ------------------
发件人: "David Feuer";<[hidden email]>;
发送时间: 2017年6月6日(星期二) 中午11:09
收件人: "Dr.Koster"<[hidden email]>;
抄送: "libraries"<[hidden email]>;
主题: Re: Add DList to base

I'm -1 on this. For an abstract DList-style list builder, there's the
dlist package, which you shouldn't fear depending on (its only
dependencies are base and deepseq, both of which are GHC boot
packages). The dlist package defines a DList that's an instance of
MonadPlus, Traversable, IsList, Ord, Read, Show, IsString, Monoid, and
NFData, and provides a variety of functions for working with them.
Many of the instances and functions are, inherently, absurdly
inefficient. This is because there's basically *nothing* you can do to
a DList directly except build one up with `.` and tear one down with
`apply`. DLists are extremely efficient precisely when GHC is able to
optimize them away altogether. As soon as that is not the case,
they're mediocre at best.

Now suppose you want a non-abstract DList type (with the constructor exposed).

newtype DList a = DL { unDL :: [a] -> [a] }

What can that offer in the way of instances? Well, it's clearly not a
Functor, so it's certainly not Applicative, Monad, MonadPlus, or
Traversable. Ouch. There's no way to write matching Read and Show
instances, so you're stuck picking just one. Similarly, IsList and
IsString aren't guaranteed to round-trip properly. NFData is utterly
absurd, of course. So what's left? Foldable, Monoid, and either Read
or Show. The Foldable instance doesn't even interact nicely with the
Monoid instance: there's no guarantee that  foldMap f xs <> foldMap f
ys = foldMap f (xs <> ys). So there's pretty much *nothing going on
here*. DList x just doesn't have much more to offer than Endo [x]. We
already have Endo; ergo, we don't need DList.

On Mon, Jun 5, 2017 at 3:58 AM, Dr.Koster <[hidden email]> wrote:

> Currently GHC already defined DList for internal use in serveral places.
> This data type is a nature choice when you need CPS your append, which is a
> common need. I think base should provide it.
>
> Cheers~
> Winter
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>


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