Hi Sean,

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 <sean.leather@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`, `Traversable`
> instances

Given that the point of dlist is to speed up code where lists are
insufficient,

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

John L.