В остальной части этого ответа я буду предполагать, что вы на самом деле пытаетесь хранить необработанные байты , а не символы. Если вы хотите сохранить символы, то вам следует рассмотреть возможность использования text (эквивалент ByteString для текста Unicode) или написания собственной структуры на основе fingertree на его основе. Вы также можете использовать ByteString с модулем Data.ByteString.UTF8 из пакета utf8-string ; Я думаю, что это может оказаться более эффективным, но оно гораздо менее полнофункционально, чем Text для текста Unicode.
Что ж, пакет веревки, который вы связали, хранит только эквивалент ByteString s, тогда как Seq является общим и может обрабатывать данные любого типа; первый, вероятно, будет более эффективным для хранения строк байтов.
Я подозреваю, что это та же самая существенная древовидная структура, что и в веревке, реализующей "цепочки пальцев из байтов", а Seq - это дерево из 2-3 пальцев; это зависит от (и предположительно использует) пакета fingertree , который по сути такой же, как Data.Sequence, но более общий. Вполне вероятно, что веревка упаковывает данные в короткие ByteString с, что невозможно сделать с Seq (без прерывания таких операций, как length и т. Д.).
В целом, веревка кажется лучшей структурой, если вы храните данные строки байтов, и у нее, кажется, есть причудливая функциональность для «аннотирования» сегментов строки; однако в последний раз он обновлялся в июле, и новая библиотека комбинатора синтаксического анализатора trifecta того же автора (впервые выпущенная в августе) содержит собственный набор собственных модулей веревки , поэтому неразумно основывать на нем новый код. Конечно, изменения, внесенные для trifecta, могут не иметь отношения к общему использованию, и, вероятно, было бы не слишком сложно выделить их как новую версию веревки; возможно, единственная причина, по которой они этого не сделали, заключается в том, что у trifecta уже есть куча зависимостей:)
Но, если вам нужен универсальный тип контейнера в любой точке вашей обработки (например, анализ байтов в последовательность некоторого более богатого представления), или вы хотите придерживаться того, что в платформе Haskell, то вам нужно будет использовать Seq.
Вы уверены, что ByteString или Text (так как вы упомянули символы) не подходят для того, что вы делаете? Они хранят поля смещения и длины, так что взятие подстроки не вызывает никакого копирования. Если ваши операции вставки достаточно редки, то это может сработать. Стоит рассмотреть и некую структуру на основе IntMap.
В ответ на ваш обновленный вопрос:
- Регулярные выражения для пользовательских типов строк: Имейте в виду, что для использования существующей реализации регулярных выражений с "необычным" типом строки вам придется реализовать поддержку самостоятельно , чтобы склеить это к существующему коду regex-tdfa. Я не уверен, что результат будет в результате.
- Сращивание с ленивыми
ByteString s: Обратите внимание, что ленивые ByteString s по умолчанию используют куски по 64 КиБ, и вы можете использовать куски любого размера, используя fromChunks вручную. Но вы правы, пальчиковое дерево, вероятно, лучше подходит; это просто больше работы, которая уже выполняется для вас с помощью lazy ByteString s.
- Конечный алфавит: ОК; Я бы посоветовал вам абстрагироваться (с
newtype) от типа, представляющего последовательность этого алфавита. Таким образом, вы можете опробовать различные реализации, надеясь при этом локализовать работу, которую необходимо выполнить, так что вы можете выбирать, основываясь на реальных данных о производительности, а не на догадках :) Конечно, при написании новой реализации все еще есть первоначальные затраты. Что касается вашего дополнительного вопроса, newtype удаляются во время компиляции, поэтому newtype имеет такое же представление во время выполнения, что и тип, который он переносит. Короче говоря: не беспокойтесь об упаковке вещей в newtype s. - Производительность Seq: Ну, это не удивительно.
Seq Char полностью ленивый и в штучной упаковке, и не будет «ломаться» Char s вместе, как Rope;вероятно, это даже менее эффективно, чем String.Нечто подобное Seq ByteString может выполнить лот лучше, но если ваши куски не имеют постоянного размера, вы потеряете способность получить значимую длину и т. Д., Не проходя через все это. - Проблемы с пакетом EclipseFP: Я бы не выбрал, какое представление использовать, исходя из таких простых проблем с инструментами, как этот;Я рекомендую задать новый вопрос.
- Trifecta: Я не думаю, что trifecta имеет отношение к вашей проблеме;он просто написан тем же автором, что и веревка, поэтому он имеет отношение к дальнейшему развитию веревки.Это просто библиотека комбинатора синтаксических анализаторов, такая как Parsec, и она больше фокусируется на диагностике и тому подобном, а не на производительности, поэтому я не думаю, что она может заменить ваши регулярные выражения.
Что касается # 3,вместо ByteString вы можете рассмотреть без коробки Vector;таким образом, вы можете использовать свой абстрактный тип алфавита, вместо того, чтобы взламывать вещи в ByteString * * * * * * * *. * * * *
интерфейсе.
*1093* Учитывая всю эту информацию, я бы порекомендовал либо
Rope, либо создание собственногоструктура с пакетом
fingertree , на котором он основан (а не
Seq, так что вы можете правильно реализовать такие вещи, как
length с классом типа
Measured - см.
Monoids иПальцевые деревья ), с листовыми данными, разбитыми на нераспакованные
Vector.Последнее, конечно, больше работы, но позволяет оптимизировать специально для вашего случая использования.В любом случае, определенно оберните его в абстрактный интерфейс.
Кстати, регулярные выражения не так хорошо поддерживаются в экосистеме Haskell, как могли бы;возможно, стоит подумать об использовании чего-то другого, если есть возможность сделать это.Но от конкретной детали вашей программы зависит слишком много, чтобы дать конкретную рекомендацию.