Edit Question - KnowledgeHub

Title Body

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: 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) 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. My "containee" data type is abstractly a finite alphabet . It could be represented concretely Char s or Byte s or Word8 s or even something like a hypothetical Word4 s (nibble). ** I have a related question about how to efficiently use a newtype or data so that my code can refer to the

Tags (comma-separated) Cancel