How lazy is DData.Seq?
wolfgang at jeltsch.net
Sun May 9 22:45:46 EDT 2004
Am Sonntag, 9. Mai 2004 12:40 schrieben Sie:
> --- Dylan Thurston <dpt at exoskeleton.math.harvard.edu> 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
> 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"?
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