Finger Tree (Data.Sequence) vs Rope (Data.Rope) (Haskell, or in general)

Question

What are the key differences between a Finger Tree (Data.Sequence) and a Rope (Data.Rope) (Edward Kmett's version or Pierre-Etienne Meunier's version?

In the Haskell libraries, Data.Sequence has more functions. I think ropes handle "blocks" more efficiently.

As a programmer considered about efficiency dealing with, say a sequence of 7 million characters, where I need to do (a) insert anywhere, (b) cut and paste segments (splice), (c) search and replace for substrings, which is more efficient?

Clarifications in response to ehird:

1. The bulk of my algorithm is running thousands of search-replace operations, like s/(ome)?reg[3]x/blah$1/g, to repeatedly mutate the data. So I need efficient regex pattern matching (perhaps form regex-tdfa?) as well as splicing (data[a:b] = newData), where not necessarily (length(newData) == b-a+1)

2. Lazy ByteStrings might be OK, but what about splicing? Splicing a ByteString is O(dataSize / chunkSize) linear time (for the search), plus (perhaps?) overhead for maintaining the constant-size chunks. (Could be wrong about the latter part); vs O(log(dataSize)) for FingerTree.

3. My "containee" data type is abstractly a finite alphabet. It could be represented concretely Chars or Bytes or Word8s or even something like a hypothetical Word4s (nibble). ** I have a related question about how to efficiently use a newtype or data so that my code can refer to the abstract alphabet, but the compiled program can still be efficient. (I should post this question separately.)

4. Performance concerns: Perhaps Seq is far worse than ByteString (by q significant constant factor). In simple tests, reading 7MB into a strict ByteString and then printing it to console peaks at 60MB real mem usage (according to Windows Process Manager), but loading that content into a Seq Char and then printing uses 400MB! (I should post this question separately, with code and profiling details.)

5. Platform concerns: I'm using EclipseFP and Haskell Platform. I have Text installed on my machine, and I wanted to try it, but my Eclipse environment can't find it. I get in serious trouble whenever I use cabal install (incompatible versions of packages get installed, --user vs --global confusion), so I want to stick with Platform packages that EclipseFP can find. I think Text is going into the next version of Platform, so that will be nice.

6. Trifecta: I saw Trifecta briefly, and that just added to my confusion. (Why does it have its own new implementations of general data structures that have already been published? Are they better? Too many nearly-identical options!)

Edited with more details and improved links.

This question got big.

@ehird's summary is the main take-home point. Rope, or Finger Tree of ByteStrings or Vectors plus a small custom monoid. Either way, I'll have to write a simple regex implementation to glue in.

Given all this information, I would recommend either Rope, or building your own structure with the fingertree package it's based on (rather than Seq, so that you can implement things like length properly with the Measured type-class — see Monoids and Finger Trees), with the leaf data chunked into an unboxed Vector. The latter is, of course, more work, but lets you optimise specially for your use-case. Either way, definitely wrap it up in an abstract interface.

I will come back later today and split into new questions. I will get the low-level technical questions sorted out, and then come back to the overall comparison. I will change the question title to better reflect my real concern "Which Haskell modules provide or support the sequence manipulation operations I need efficiently?" Thanks go to ehird and other responders.

Answer 1

For the rest of this answer, I'll assume you're actually trying to store raw bytes, not characters. If you want to store characters, then you should consider using text (the equivalent of ByteString for Unicode text) or writing your own fingertree-based structure based on it. You could also use a ByteString with the Data.ByteString.UTF8 module from the utf8-string package; I think that can end up being more efficient, but it's much less fully-featured than Text for Unicode text.

Well, the rope package you linked only stores the equivalent of ByteStrings, whereas Seq is generic and can handle any type of data; the former is likely to be more efficient for storing, well, strings of bytes.

I suspect it's the same essential tree structure, as rope implements "fingertrees of bytestrings", and Seq is a 2-3 finger tree; it depends on (and so presumably uses) the fingertree package, which is essentially the same as Data.Sequence but more general. It's likely that rope packs the data into short ByteStrings, which is impossible to do with Seq (without breaking operations like length, etc.).

All in all, rope seems like a better structure if you're storing byte-string data, and it seems to have fancy functionality for "annotating" segments of the string; however, it was last updated in July, and the new trifecta parser combinator library by the same author (first released in August) contains its own set of rope modules, so it may be unwise to base new code on it. Of course, the changes made for trifecta may not be relevant for general use, and it probably wouldn't be too difficult to split those out as a new version of rope; perhaps the only reason they haven't been is because trifecta already has a ton of dependencies :)

But, if you need a generic container type at any point in your processing (e.g. parsing the bytes into a sequence of some richer representation), or want to stick to what's in the Haskell Platform, then you'll need to use Seq.

Are you sure that ByteString or Text (since you mentioned characters) aren't suitable for what you're doing? They store offset and length fields, so that taking a substring doesn't cause any copying. If your insert operations are infrequent enough, then it could work out. An IntMap-based structure of some sort might be worth considering, too.

---

In response to your updated question:

1. Regexes on custom string types: Bear in mind that to use an existing regex implementation with an "unusual" string type, you'll have to implement the support yourself to glue it to the existing regex-tdfa code. I'm not sure what the resulting performance would be.
2. Splicing with lazy ByteStrings: Note that lazy ByteStrings use 64 KiB chunks by default, and you can use chunks as large as you wish by using fromChunks manually. But you're right, a finger tree is probably better suited; it's just more work to do that's already handled for you with lazy ByteStrings.
3. Finite alphabet: OK; I'd suggest that you abstract out (with a newtype) a type representing a sequence of this alphabet. That way, you can try various implementations out while hopefully localising the work that has to be done, so you can choose based on real performance data rather than guesswork :) Of course, there's still an upfront cost to writing a new implementation. As far as your additional question, newtypes are erased at compile-time, so a newtype has the same runtime representation as the type it's wrapping. In short: don't worry about wrapping things in newtypes.
4. Seq performance: Well, that's not surprising. Seq Char is fully lazy and boxed, and won't be "chunking" Chars together like Rope would; it's probably even less memory-efficient than String. Something like Seq ByteString might perform a lot better, but unless your chunks are constant-sized, you'll lose the ability to get a meaningful length, etc. without traversing the whole thing.
5. EclipseFP package problems: I wouldn't choose which representation to use based on simple tool problems like that; I recommend asking a new question.
6. Trifecta: I don't think trifecta is relevant to your problem; it's just written by the same author as rope, which is why it's relevant with regards to rope's continued development. It's just a parser combinator library like Parsec, and it focuses more on diagnostics and the like rather than performance, so I don't think it could replace your regexes.

As far as #3 goes, instead of ByteString, you might want to consider an unboxed Vector; that way, you can use your abstract alphabet type rather than hacking things into ByteString's Word8-based interface.

Given all this information, I would recommend either Rope, or building your own structure with the fingertree package it's based on (rather than Seq, so that you can implement things like length properly with the Measured type-class — see Monoids and Finger Trees), with the leaf data chunked into an unboxed Vector. The latter is, of course, more work, but lets you optimise specially for your use-case. Either way, definitely wrap it up in an abstract interface.

By the way, regexes aren't as well-supported in the Haskell ecosystem as they could be; it might be worth considering using something else if there's any option of doing so. But it depends too much on specific details of your program to give a specific recommendation.