How lazy is DData.Seq?

[Robert Will]

----- Original Message ----- 
From: "Simon Marlow" <simonmar at microsoft.com>

> The reason to prefer a sequence with an O(N) 'last' over one with O(log
> N) 'last' would be if the O(N) version had lower constant factor
> overhead and you didn't need to use the O(N) operations.

That argument can be generalised: 
IF you don't need some operations which are overly inefficient in implementation X
THEN any advantage of X will suffice to make it your preference over an implementation without any overly inefficient operations.

Given an appropriate precondition (the IF part..) almost any data structure can be one's (objective!) preference. I think however that the idea of general-purpose data structures is to impose as little preconditions as possible. (According to the motto "Preliminary optimisation...".) Truly general-purpose data structures can be used before or even without thinking about all those preconditions, and they can be kept, even if preconditions change (adaptability, portability).

The built-in lists (and other more concrete data types) have more advantages than constant factors, but all together with some preconditions that one has to learn and to master. We all know that functional programming is easier to learn than imperative programming, but that it is actually harder if one knows already imperative programming. Similarly I think that programming with (democratic) abstract data structures is easier (to learn and to do), but actually harder when one is used to preconditioned concreteness. Nothing against algebraic lists and other data structures, I just say that they shouldn't come first when learning and shouldn't be the default when programming.

Robert