<div dir="ltr"><div><div>Hi Sean,<br><br></div>Since I've raised this issue before as well, I decided to write some tests.<br><br></div>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.<br><br><a href="https://github.com/JohnLato/dlist-test/">https://github.com/JohnLato/dlist-test/</a><br><a href="http://htmlpreview.github.io/?https://github.com/JohnLato/dlist-test/blob/master/testout.html">http://htmlpreview.github.io/?https://github.com/JohnLato/dlist-test/blob/master/testout.html</a><br>
<div class="gmail_extra"><br></div><div class="gmail_extra">I think more research is warranted, since there are a few anomalies I can't currently explain.<br></div><div class="gmail_extra"><br><div class="gmail_quote">
On Mon, Nov 18, 2013 at 7:15 AM, Sean Leather <span dir="ltr"><<a href="mailto:sean.leather@gmail.com" target="_blank">sean.leather@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div dir="ltr">Hi Joachim,<div class="gmail_extra"><br></div><div class="gmail_extra"><div class="gmail_quote">On Mon, Nov 18, 2013 at 11:21 AM, Joachim Breitner wrote:<div class="im"><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Am Montag, den 18.11.2013, 10:04 +0200 schrieb Sean Leather:<br>
<div>> * Maintenance and development taken over by Sean Leather<br>
> * Migrate repository from <a href="http://code.haskell.org/~dons/code/dlist/" target="_blank">http://code.haskell.org/~dons/code/dlist/</a> to<br>
> <a href="https://github.com/spl/dlist" target="_blank">https://github.com/spl/dlist</a><br>
> * Add `Eq`, `Ord`, `Read`, `Show`, `Alternative`, `Foldable`, `Traversable`<br>
> instances<br>
<br>
</div>Given that the point of dlist is to speed up code where lists are<br>
insufficient,</blockquote><div><br></div></div><div>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).</div>
<div class="im">
<div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">would it make sense to only provide those instances that<br>
can be implemented without converting to and from lists?<br></blockquote><div><br></div></div><div>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).</div>
<div class="im">
<div>
<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">If there are instances that cannot be implemented idiomatically with<br>
dlists, maybe they should be left out, to signal the user that he will<br>
not get the benefits of DLists for these.<br></blockquote><div><br></div></div><div>I think it is an unproven myth that conversion between lists and dlists is always inefficient. Consider the conversion functions:</div>
<div><br>
</div><div><div><div>> fromList :: [a] -> DList a<br></div></div></div><div><div>> fromList = DL . (++)</div><div><br></div><div><div>> toList :: DList a -> [a]<br></div><div>> toList = ($[]) . unDL</div>
<div><br></div></div><div></div><div>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).<br></div><div><br>
</div>
<div>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).</div>
</div></div></div></div></blockquote><div><br></div><div>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.<br>
<br></div><div>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.<br>
<br></div><div>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.<br><br></div><div>John L.<br></div></div>
</div></div>