aeson and dlist in HP 2013.4.0.0
sean.leather at gmail.com
Tue Nov 19 09:37:56 UTC 2013
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.
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 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),
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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Libraries