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
_______________________________________________ Haskell-platform mailing list Haskell-platform@projects.haskell.org http://projects.haskell.org/cgi-bin/mailman/listinfo/haskell-platform
