Ответ 1

Для остальной части этого ответа, я предполагаю, что вы на самом деле пытаетесь сохранить сырые байты, а не символы. Если вы хотите хранить символы, вам следует рассмотреть возможность использования text (эквивалент ByteString для текста в Юникоде) или написание собственного текста основанная на нем. Вы также можете использовать ByteString с Data.ByteString.UTF8 из utf8-string; Я думаю, что это может оказаться более эффективным, но гораздо менее полно, чем Text для текста в Юникоде.

Ну, связанный вами пакет веревок хранит эквивалент ByteString s, тогда как Seq является общим и может обрабатывать любые типы данных; первая, вероятно, будет более эффективной для хранения, ну, строк байтов.

Я подозреваю, что это та же самая важная древовидная структура, поскольку веревка реализует "кончики пальцев", а Seq - это 2-3 пальца; это зависит от (и, предположительно, использует) пакет fingertree, который по существу совпадает с Data.Sequence, но более общим. Вероятно, что веревка упаковывает данные в короткие ByteString s, что невозможно сделать с Seq (без прерывания операций, таких как length и т.д.).

В целом, веревка кажется лучшей структурой, если вы храните данные о байтовой строке и, как представляется, имеют фантастическую функциональность для "аннотирования" сегментов строки; однако последний раз он был обновлен в июле, а новая библиотека корректоров парсеров trifecta того же автора (впервые выпущенная в августе) содержит ее собственный набор канатных модулей, поэтому может быть неразумно создавать новый код на нем. Конечно, изменения, сделанные для trifecta, могут не иметь отношения к общему использованию, и, вероятно, было бы не так сложно разделить их как новую версию веревки; возможно, единственная причина, по которой они не были, состоит в том, что у trifecta уже есть тонна зависимостей:)

Но если вам нужен общий тип контейнера в любой момент вашей обработки (например, разбор байтов в последовательности более богатого представления) или хотите придерживаться того, что на платформе Haskell, тогда вам нужно будет использовать Seq.

Вы уверены, что ByteString или Text (так как вы упомянули персонажей) не подходят для того, что вы делаете? Они хранят поля смещения и длины, так что взятие подстроки не вызывает никакого копирования. Если ваши операции с вставкой не так редки, то это может сработать. Возможно, стоит рассмотреть и структуру на основе IntMap.

В ответ на ваш обновленный вопрос:

• Регулярные выражения для пользовательских типов строк: Имейте в виду, что для использования существующей реализации регулярного выражения с "необычным" строковым типом вам нужно реализовать поддержку, чтобы приклеить ее к существующему коду regex-tdfa. Я не уверен, какова будет конечная производительность.
• Склеивание с ленивым ByteString s: Обратите внимание, что lazy ByteString по умолчанию использует 64 KiB куска, и вы можете использовать куски как можно больше, используя fromChunks вручную. Но вы правы, пальцевое дерево, вероятно, лучше подходит; это просто больше работы, которая уже обрабатывается для вас с ленивыми ByteString s.
• Конечный алфавит: ОК; Я бы предложил вам абстрагировать (с newtype) тип, представляющий последовательность этого алфавита. Таким образом, вы можете попробовать различные реализации, надеясь локализовать работу, которая должна быть выполнена, поэтому вы можете выбирать на основе реальных данных о производительности, а не догадки:) Конечно, все еще стоит авансовый расход на создание новой реализации. Что касается вашего дополнительного вопроса, newtype удаляются во время компиляции, поэтому newtype имеет такое же представление времени выполнения, как и тип, который он обертывает. Короче говоря, не волнуйтесь об обертывании вещей в newtype s.
• Производительность Seq: Ну, это не удивительно. Seq Char полностью ленив и помещен в коробку и не будет "chunking" Char вместе, как Rope; он, вероятно, даже менее эффективен с точки зрения памяти, чем String. Что-то вроде Seq ByteString может работать намного лучше, но если ваши куски не имеют постоянного размера, вы потеряете возможность получить значимую длину и т.д., Не пройдя все это.
• Проблемы с пакетом EclipseFP: Я бы не выбрал, какое представление использовать на основе простых проблем с инструментами; Я рекомендую задать новый вопрос.
• Trifecta:Я не думаю, что trifecta имеет отношение к вашей проблеме; это просто написано тем же автором, что и веревка, поэтому он имеет отношение к продолжению развития веревки. Это просто библиотека парсера-анализатора, такая как Parsec, и она больше фокусируется на диагностике и т.д., А не на производительности, поэтому я не думаю, что она может заменить ваши регулярные выражения.

Что касается # 3, вместо ByteString вам может потребоваться unboxed Vector; Таким образом, вы можете использовать свой абстрактный алфавитный тип, а не взламывать вещи в интерфейс ByteString Word8.

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

Кстати, регулярные выражения не так хорошо поддерживаются в экосистеме Хаскелла, как могли бы быть; возможно, стоит подумать о том, чтобы использовать что-то еще, если есть возможность сделать это. Но это зависит от конкретных деталей вашей программы, чтобы дать конкретную рекомендацию.