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

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.