How lazy is DData.Seq?

Wolfgang Jeltsch wolfgang at
Sun May 9 22:45:46 EDT 2004

Am Sonntag, 9. Mai 2004 12:40 schrieben Sie:
> --- Dylan Thurston <dpt at> wrote:
> > Yes, but DData.Seq is supposed to be a general-purpose library, and I, for
> > one, want most operations (e.g., lookup) to be O(log n).  If you want
> > unbalanced trees, go ahead and code it yourself; it's very easy, much
> > easier than doing balancing correctly.
> >
> > Peace,
> > 	Dylan
> Probably you confuse Set and Seq. The latter is not intended to be "looked
> up". (Indeed, trees are not balanced) Thus, Wolfgang request makes perfect
> sense.
> That said, the slight lack of strictness is not necessary. I introduced it
> to make some algorithms simpler (efficient), and thought it was harmless. I
> is quite a bit of work to change, thus I am willing to argue... :)
> Please note that append is only strict in the "top node", and thus it is
> possible to work with infinite sequences without error.
> Wolfgang, why is it you need the "full laziness"?
> Cheers,
> JP.


meanwhile, I'm not sure if I need lazyness in my concrete example.  But the 
general point is the following:

I have functions for converting values of certain data types to strings.  I 
don't use [Char] but Seq Char as the result type of these functions to allow 
for efficient concatenation.  For one concrete type I want to test if the 
values of this type have a certain property.

I use the to-string conversion function to check for this property because a 
value has the property in question iff the first character of the string 
representation is a letter.  So I want to do something like
    isAlpha $ head $ toString value.
toString value is constructed by multiple applications of append, so it may in 
the end be something like
    append (append a (append b c)) (append (append d e) f).
In this example I'd want the terms
    append b c
    append (append d e) f)
to not be evaluated at all.


More information about the Libraries mailing list