On Fri, Feb 18, 2011 at 1:14 AM, Sebastian Fischer <[email protected]>wrote:
> So far the best I've found is Data.Sequence.Seq, which in my tests >> outperforms mutable vectors, but only for reads from the head or tail of the >> sequence. Indexing into the middle of the sequence is relatively slow. >> > > Data.Sequence is implemented as a finger tree which is the culmination > point of Ralf Hinzes talk on Number Systems and Data Structures [1]. Finger > trees are versatile but also complicated. Maybe one of the simpler > structures presented there (like random access lists) provides faster > indexing. > > Sebastian > > [1]: http://www.cs.nott.ac.uk/~gmh/bctcs-slides/hinze.pdf > Thanks very much for this useful link. It's given me some items to think about. I believe the difficulty with random access lists is in dropping references to old data. I don't see how to do so efficiently. Since finger trees support efficient access to both ends, they work well in this regard. It's only accessing data in the middle which is a problem. I also haven't tried an IntMap yet, which may be better still. Thanks, John
_______________________________________________ haskell-art mailing list [email protected] http://lists.lurk.org/mailman/listinfo/haskell-art
