At 15:04 -0400 98/05/07, S. Alexander Jacobson wrote:
>> > o it uses (++) to catenate the results of the recursive calls (note that
>> > (++) takes time proportional to the length of its first argument).
>
>This also seems wierd. Concatenation is a frequent enough operation on
>lists. Give such frequency, shouldn't the internal representation of a
>list include a pointer to its last element just to ensure that
>concatenation is constant time?
This sounds as a question of the internal representation of lists that
Haskell uses. Unfortunately, the best representation depends on the task at
hand. For example, arrays (fixed size memory blocs) are generally faster
than say a double linked list if the array has to recopied and the size is
small. So if small lists are frequent, it is better to use arrays than
double linked lists.
So, one variation could be that Haskell uses double linked arrays, and
itself figures out a suitable size for the arrays. One could also represent
lists as trees, and get improved performance on some operations for large
lists.
Or perhaps Haskell could use a single list interface, giving the user the
chance to optimize these things. Is this against the spirit of Haskell?
Hans Aberg
* Email: Hans Aberg <mailto:[EMAIL PROTECTED]>
* Home Page: <http://www.matematik.su.se/~haberg/>
* AMS member listing: <http://www.ams.org/cml/>
