Fast Sequences

[Ross Paterson]

On Sun, Mar 26, 2006 at 04:11:13PM -0500, Jim Apple wrote:
> The proposed Data.Sequence (
> http://www.soi.city.ac.uk/~ross/software/html/Data.Sequence.html ) has
> O(n) reverse.

Now at

http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Sequence.html

> Section 6 of http://citeseer.ist.psu.edu/560336.html
> claims that it can be faster.

The same trick would work with Data.Sequence, but it would double the
size of the code.  It's not clear that it's worth it, especially since
the cost of reverse can only be observed by traversing the whole sequence.

> Also, according to http://citeseer.ist.psu.edu/kaplan96purely.html ,
> there is a sequence type with (><) of O(log log n).

I don't think K&T provide enough details to establish the amortization
argument for that representation.  I understand that they're working
on a new version, though.

> The latter one of these doesn't support the stated time bounds for
> different versions of the same structure.

I'm not sure what this sentence means.

> Do 2-3 finger trees support that?

They don't support O(log log (min(m,n))) append.  On the other
hand, it's quite hard to tell the difference in a lazy language,
e.g. building a sequence with appends costs O(n) whether append is
O(1) or O(log(min(m,n))).