[Haskell-cafe] Advice needed on best way to simulate an STL vector

Cale Gibbard cgibbard at gmail.com
Wed Apr 19 15:26:25 EDT 2006

I should perhaps point out that in the development GHC (iirc), there
is a library called Data.Sequence which uses 2-3 finger trees to get
rather nice efficient sequences. Operations on both ends (appending or
dropping) are constant time, while operations in the middle tend to be
on the order of the logarithm of the distance to the closer of the two
ends. For instance, concatenation and splitting at a point both have
complexity proportional to the logarithm of the smaller of the two
parts involved.

 - Cale

On 19/04/06, Brian Hulley <brianh at metamilk.com> wrote:
> Thanks. I might try this if I don't have any luck with finger trees (from
> Udo's post), or if they seem too heavy for the simple thing I'm planning to
> use them for (implementing the text buffer for an edit control which needs a
> mutable array of lines where each line contains a mutable array of character
> info). I don't need non-Int indices so your data type for Vector would be
> fine.
> Best regards, Brian.

More information about the Haskell-Cafe mailing list