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" <drkoster at qq.com> 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";<david.feuer at gmail.com>;
*发送时间:* 2017年6月6日(星期二) 中午11:09
*收件人:* "Dr.Koster"<drkoster at qq.com>;
*抄送:* "libraries"<libraries at haskell.org>;
*主题:* 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 <drkoster at qq.com> 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
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20170614/e8246e4f/attachment.html>