aeson and dlist in HP 2013.4.0.0
jwlato at gmail.com
Tue Nov 19 01:32:52 UTC 2013
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
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`,
>> > instances
>> Given that the point of dlist is to speed up code where lists are
> 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),
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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Libraries