aeson and dlist in HP 2013.4.0.0

[John Lato]

Hi Sean,

Since I've raised this issue before as well, I decided to write some tests.

At this time, I've written/run criterion tests, and I have some hand-wavey
theoretical arguments.  The theoretical stuff came first (presented below)
and isn't influenced by the test results, which I haven't attempted to
analyze beyond the most superficial level.  If anyone else really cares
strongly, please feel free to develop this further.

https://github.com/JohnLato/dlist-test/
http://htmlpreview.github.io/?https://github.com/JohnLato/dlist-test/blob/master/testout.html

I think more research is warranted, since there are a few anomalies I can't
currently explain.

On Mon, Nov 18, 2013 at 7:15 AM, Sean Leather <sean.leather at gmail.com>wrote:

> Hi Joachim,
>
> On Mon, Nov 18, 2013 at 11:21 AM, Joachim Breitner wrote:
>
> Am Montag, den 18.11.2013, 10:04 +0200 schrieb Sean Leather:
>> > * Maintenance and development taken over by Sean Leather
>> > * Migrate repository from http://code.haskell.org/~dons/code/dlist/ to
>> >   https://github.com/spl/dlist
>> > * Add `Eq`, `Ord`, `Read`, `Show`, `Alternative`, `Foldable`,
>> `Traversable`
>> >   instances
>>
>> Given that the point of dlist is to speed up code where lists are
>> insufficient,
>
>
> To be a bit more precise, it is not that lists are "insufficient," the
> problem is the `(++)` operator (a.k.a. append). To be even more precise,
> the problem is left-nested appends, e.g. the expression `(x ++ y) ++ z` may
> have a worse traversal time than `x ++ (y ++ z)`. Such an arrangement can
> (and probably will) result in multiple traversals of the left argument(s).
>
> would it make sense to only provide those instances that
>> can be implemented without converting to and from lists?
>>
>
> In my opinion, no. It makes sense to have as many reasonable instances as
> possible to make the library more attractive and usable. The fact that the
> instances convert to and from lists does not detract from their usefulness
> because the conversions are not necessarily inefficient (see next response).
>
> If there are instances that cannot be implemented idiomatically with
>> dlists, maybe they should be left out, to signal the user that he will
>> not get the benefits of DLists for these.
>>
>
> I think it is an unproven myth that conversion between lists and dlists is
> always inefficient. Consider the conversion functions:
>
> > fromList    :: [a] -> DList a
> > fromList    = DL . (++)
>
> > toList      :: DList a -> [a]
> > toList      = ($[]) . unDL
>
> Converting from a list is like prepending (++) to a list. This introduces
> a linear traversal of the argument (assuming a complete evaluation of the
> converted list).
>
>  Converting to a list is like "finishing it off" with an empty list. The
> operation itself is trivial, but traversing the result would evaluate all
> the `(++)` from the previous `fromList`s. Fortunately, all of the
> `fromList`ed lists are left-arguments to `(++)`, so each will only be
> traversed once (which is the primary reason of dlists).
>

This overlooks the cost of evaluating the DList function itself, which can
be significant.  DLists are usually formed by snoc'ing/appending k
elements/chunks, which means that the total DList is a composition of k
separate functions.  This structure must be traversed in order to evaluate
the resulting list, which makes 'toList' have complexity O(k).  If the
DList was formed by repeated 'snoc' calls (maybe a common case, maybe not),
k==n.

calling 'toList' isn't so bad on its own, as typically it only happens
once.  My concern stems from situations such as using DList as a key in a
map, for which many comparisons will be performed and toList will be called
multiple times on some elements.

Even considering this, I'm not particularly opposed to these instances, but
I think users should be aware that they can lead to repeated non-trivial
computations.

John L.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20131118/ffd1ae35/attachment.html>