<div dir="ltr">Hi Joachim,<div class="gmail_extra"><br></div><div class="gmail_extra">I did not want to derail the conversation about the pros and cons of dlist, so I started a separate thread about it on the haskell-platform list [1], but perhaps I should have included the libraries list [2]. Since a few people have mentioned concerns about dlist/list conversion, I will respond below.</div>
<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:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;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>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><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;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>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>
<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;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>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><br></div><div>Looking at the instances in the master branch, most of them use `toList`, which we have established is trivial. The only instances to use `fromList` are `Read` and `Traversable`. Each of these reuses the list instance and involves at least one list traversal, so the extra traversal implied by `fromList` means a constant factor increase in time.</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">In particular, it seems that the Show instance could be improved.<br>
Currently it says<br>
showsPrec p dl = showParen (p > 10) $<br>
showString "fromList " . shows (toList dl)<br>
i.e. goes via a list. But this is constructing a ShowS (which is String<br>
-> String) value, i.e. another difference list. Shouldn’t it be possible<br>
to stay in the world of difference lists when implementing this?<br></blockquote><div><br></div><div><div>Perhaps you might expect this:</div><div><br></div><div><div>> showsPrec' :: Int -> DList Char -> ShowS</div>
<div>> showsPrec' p dl = showParen (p > 10) $</div><div>> showString "fromList " . unDL dl</div></div><div><br></div></div><div>But that won't work, because we have a `Show a => DList a`, not a `DList Char`. The `Show` instance for lists is for `Show a => [a]`, not `[Char]`. See Bas' dstring library for `DList Char`.</div>
<div><br></div><div>The underlying representation of dlists is `[a] -> [a]`, so what we might want is a function with the type `Show a => ([a] -> [a]) -> ShowS`. But we don't need or want to map `String` to `Show a => [a]` as one might think the higher-order function requires. What we do is finish off the function with `[]` (which is appended to the end of the resulting list). Then, we're left with something of type `Show a => [a]`, to which we can apply `showList`. Looking back at the instance, `toList` finishes the function and `shows` for `[a]` is equivalent to `showList` for `a`.</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">(Or maybe I’m overly worried, and I admit that I did not run benchmarks<br>
so far.)<br></blockquote><div><br></div><div>I definitely think benchmarks [3] would help resolve these questions. And there might be cases where rewrite rules and fusion play a role. But until then, I remain unconvinced that the added instances are anything but helpful.</div>
<div><br></div><div>Regards,</div><div>Sean</div><div><br></div><div><div class="gmail_extra">[1] <a href="http://projects.haskell.org/pipermail/haskell-platform/2013-November/002750.html" target="_blank">http://projects.haskell.org/pipermail/haskell-platform/2013-November/002750.html</a></div>
<div class="gmail_extra"><br></div><div class="gmail_extra">[2] I assumed the discussion for a library being added (or not) to the Platform should happen on haskell-platform and not libraries. But perhaps libraries has more eyes and interest. The fact that many of these emails are being sent to both lists adds to my confusion about where discussion should take place.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">[3] <a href="https://github.com/spl/dlist/issues/3" target="_blank">https://github.com/spl/dlist/issues/3</a></div>
</div></div></div></div>