aeson and dlist in HP 2013.4.0.0

[Sean Leather]

Hi John,

On Tue, Nov 19, 2013 at 3:32 AM, John Lato wrote:

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

Great! Thanks!

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

Definitely.

On Mon, Nov 18, 2013 at 7:15 AM, Sean Leather wrote:
>
>> 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.
>

True, and nicely put.

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

Indeed. I would hope there would be sharing in those cases, but I'm not
sure right now.

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

Agreed.

Regards,
Sean
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://projects.haskell.org/pipermail/haskell-platform/attachments/20131119/b7edb543/attachment.htm>