Am Samstag, 8. Mai 2004 20:58 schrieben Sie:

On Sat, May 08, 2004 at 08:28:37PM +0200, Wolfgang Jeltsch wrote:

...

Am Samstag, 8. Mai 2004 18:37 schrieben Sie:

...

--- Wolfgang Jeltsch wrote:

...

Hello,

I would suspect that in DData.Seq the result of head (singleton 'a' `append` undefined) is 'a' but instead it is _|_. Why is this the case?

I have the invariant that sublists are not empty. There is, for example:

append as None = as

Is this necessary/desirable? I have an application where I think that it can be important for efficiency that the above expression evaluates to 'a'. So I would like it to not result in _|_.

Yes, it's necessary, if you want to maintain any sort of balanced tree (which is crucial for efficiency). In 'append as bs', you need to know how large 'as' and 'bs' are in order to construct the balanced structure.

For what do we need a balanced tree? At least, O(1) concatenation and O(n) conversion to an ordinary list should also work with unbalanced trees.

[...]

Peace, Dylan

Wolfgang

On Sat, May 08, 2004 at 03:18:46PM -0400, Dylan Thurston wrote:

On Sat, May 08, 2004 at 09:10:52PM +0200, Wolfgang Jeltsch wrote:

...

For what do we need a balanced tree? At least, O(1) concatenation and O(n) conversion to an ordinary list should also work with unbalanced trees.

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.

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).

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.

Am Sonntag, 9. Mai 2004 12:40 schrieben Sie:

--- Dylan Thurston 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.

Hi, 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 and append (append d e) f) to not be evaluated at all. Wolfgang

Am Montag, 10. Mai 2004 00:14 schrieben Sie:

--- Wolfgang Jeltsch wrote:

...

Hi,

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 and append (append d e) f) to not be evaluated at all.

Ok, I think was mistaken in this respect.

What do you mean with this? Do you mean: "I think *I* was mistaken [...]"?

The current version behaves ok for sequences mainly constructed with fromList, cons or snoc; a sequence made up of 'append' is strict.

Would it be possible to change this behavior?

Cheers, JP.

Wolfgang

Am Montag, 10. Mai 2004 01:02 schrieben Sie:

[...]

...

...

The current version behaves ok for sequences mainly constructed with fromList, cons or snoc; a sequence made up of 'append' is strict.

Would it be possible to change this behavior?

Sure. I attach the modified version, for reference.

Cheers, JP.

Thanks a lot. Well, the version you attached has an error. Hugs says: ERROR "DData/Seq.hs":472 - Undefined variable "valid" Wolfgang