Каковы ключевые различия между Finger Tree (Data.Sequence) и Rope (Data.Rope) (Edward Kmett's version или Pierre-Etienne Meunier's version?

В библиотеках Haskell у Data.Sequence больше функций. Я думаю, что веревки более эффективно обрабатывают "блоки".

Как программист, думающий об эффективности работы, скажем, с последовательностью из 7 миллионов символов, где мне нужно делать (a) вставку в любое место, (b) вырезать и вставлять сегменты (splice), (c) искать и заменять подстроки, что эффективнее?

Уточнения в ответ на ehird:

1. Основная часть моего алгоритма - это выполнение тысяч операций поиска-замены, таких как s/(ome)?reg[3]x/blah$1/g, для многократного изменения данных. Поэтому мне нужен эффективный regex-шаблон (возможно, в форме regex-tdfa?)а также сращивание (data[a:b] = newData), где не обязательно (length(newData) == b-a+1)

2. Ленивые байт-строки могут быть в порядке, но что насчет сращивания? Сплайсинг байт-строки - это O(dataSize / chunkSize) линейное время (для поиска), плюс (возможно?) накладные расходы на поддержание постоянного размера кусков. (Могу ошибаться насчет последней части); против O(log(dataSize)) для FingerTree.

3. Мой тип данных "containee" абстрактно представляет собой конечный алфавит. Он может быть представлен конкретно Chars или Bytes или Word8s или даже что-то вроде гипотетического Word4s (nibble). ** У меня есть смежный вопрос о том, как эффективно использовать newtype или data, чтобы мой код мог ссылаться на абстрактный алфавит, но при этом скомпилированная программа оставалась эффективной. (Я должен разместить этот вопрос отдельно).

4. Проблемы производительности: Возможно, Seq намного хуже, чем ByteString (на q значительный постоянный коэффициент). В простых тестах чтение 7 МБ в строгий ByteString и последующая печать его на консоль достигает пика в 60 МБ реального использования памяти (согласно Windows Process Manager), но загрузка этого содержимого в Seq Char и последующая печать использует 400 МБ! (Я должен разместить этот вопрос отдельно, с кодом и деталями профилирования.)

5. Проблемы платформы: Я использую EclipseFP и Haskell Platform. У меня на машине установлен Text, и я хотел попробовать его, но среда Eclipse не может его найти. У меня возникают серьезные проблемы, когда я использую cabal install (устанавливаются несовместимые версии пакетов, --user против --global путаница), поэтому я хочу придерживаться пакетов Platform, которые может найти EclipseFP. Я думаю, что Text войдет в следующую версию Platform, так что это будет здорово.

6. Trifecta: Я мельком видел Trifecta, и это только усилило мое замешательство. (Почему у нее есть собственные новые реализации общих структур данных, которые уже были опубликованы? Они что, лучше? Слишком много почти одинаковых вариантов!)

Отредактировано с более подробной информацией и улучшенными ссылками.

Этот вопрос стал большим.

Резюме @ehird - главный вывод. Веревка, или пальцевое дерево из байт-строк или векторов плюс небольшой пользовательский моноид. В любом случае, мне придется написать простую реализацию regex для склеивания.

Учитывая всю эту информацию, я бы рекомендовал либо Rope, либо построение свою собственную структуру с помощью пакета fingertree, на котором она основана (а не чем Seq, чтобы вы могли правильно реализовать такие вещи, как длина, с помощью класс типа Measured - см. раздел "Моноиды и пальцевые деревья"), при этом данные листьев данные разбиваются на части в виде вектора без коробки. Последний вариант, конечно, требует больше работы, но позволяет оптимизировать специально для вашего случая использования. В любом случае, обязательно оберните это в абстрактный интерфейс.

Я вернусь позже сегодня и разделю новые вопросы. Я разберусь с низкоуровневыми техническими вопросами, а затем вернусь к общему сравнению. Я изменю название вопроса, чтобы оно лучше отражало мою реальную проблему: "Какие модули Haskell обеспечивают или поддерживают операции манипулирования последовательностью, которые мне нужны эффективно?". Спасибо ehird и другим ответившим.