How lazy is DData.Seq?

[Robert Will]

Hi all,

Sorry I'm adding my 2c so late, but the problem is an instance of a
general tradeoff between data structural abstraction and "lazyness",
which is explained at
http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/principles.html
(search for "lazy").

In short, we can only have concrete lazy data structures, since *any*
optimisation (re-arrangement) will destroy some lazyness.

So the problem of DData.Seq is that it has no clear design guidelines that
specify whether it is to be thought of as a concrete structures (i.e.
users know the Data Constructors, as for the built-in Haskell lists), or
an abstract structure (which is the only way to provide worst-case time
bounds independent from the construction of the sequence, only dependent
from its size).

On Sun, 9 May 2004, Ross Paterson wrote:
>
> You don't need a balanced tree, but the O(n) bound requires the invariant
> that no proper subtree is empty.  Otherwise, a tree containing n elements
> can be of unbounded size, and take an unbounded time to convert to a list.


> I suspect there is no satisfactory general-purpose sequence implementation
> (DData.Seq isn't trying to be one -- it does no balancing.)  A balanced
> tree would make most things O(log n), but other implementations give
> you O(1) for various subsets of operations (and the smaller the subset,
> the smaller the constant factor, as a rule of thumb).  It seems essential
> to offer a range of implementations.


On Tue, 11 May 2004, Simon Marlow wrote:

> But, the tradeoff is strictness in append.  It may be that we need
> multiple versions of Seq, but I suspect that not much would be gained by
> having all three:
>
>   1. ordinary lists with lazy append
>   2. Seq with O(1) lazy append
>   3. Seq with O(1) strict append and O(n) toList
>
> If we have 1 & 3, then I'm guessing that 2 would be very rarely
> required.

Well, Dessy has only 1 and 3 and that for good reason.

In fact, this discussion does somehow miss the point, since none of these
three are most "general-purpose Sequences", with a lot of unnecessary O(N)
operations (e.g. for 'last' and (!!)).  I think the most general
implementation are Democratic Sequences (with O(log N) bounds for all
operations that allow that) followed by Deques (with O(1) bounds for all
tip-based operations, which I think are all that allow that).  Write-Only
Sequences (as DData.Seq) are already an "optimised case" that should only
be used when needed, since the user has to take into account, that every
"read access" implies some kind of O(N) "conversion" that is not shared
among those calls.

When using Dessy, one has the advantage of a good design: each data
structure is optimal in some sense.  Streams are optimal for laziness, all
others are different optima in time (and space) bounds.  Dessy is at the
edge of what is possible, so you never have to ask questions like "could
we make this a little more lazy?".

I would appreciate if someone could appreciate this ;-)

Robert