Что было бы хорошими чисто функциональными структурами данных для текстовых редакторов? Я хочу иметь возможность вставлять отдельные символы в текст и удалять отдельные символы из текста с приемлемой эффективностью, и я хотел бы иметь возможность хранить старые версии, поэтому я могу легко отменить изменения.
Должен ли я просто использовать список строк и повторно использовать строки, которые не меняются от версии к версии?
A Vector[Vector[Char]], вероятно, будет хорошей ставкой. Это IndexedSeq, поэтому имеет достойную производительность обновления/предварительной/обновления, в отличие от List, которую вы упомянули. Если вы посмотрите на Характеристики производительности, то это единственная неизменная коллекция, в которой указано эффективное обновление постоянной продолжительности.
Я не знаю, является ли это предложение "хорошим" для сложных определений "хорошего", но это легко и весело. Я часто задал упражнение, чтобы написать ядро текстового редактора в Haskell, связавшись с кодом рендеринга, который я предоставляю. Модель данных выглядит следующим образом.
Сначала я определяю, что это должен быть курсор внутри списка x -элементов, где информация, доступная в курсоре, имеет некоторый тип m. (x окажется Char или String.)
type Cursor x m = (Bwd x, m, [x])
Эта Bwd вещь - это только отсталые "snoc-lists". Я хочу сохранить сильные пространственные интуиции, поэтому я перехожу в своем коде, а не в свою голову. Идея состоит в том, что материал, ближайший к курсору, наиболее легко доступен. Это дух "Застежки-молнии".
data Bwd x = B0 | Bwd x :< x deriving (Show, Eq)
Я предоставляю бесплатный одноэлементный тип, чтобы действовать как читаемый маркер для курсора...
data Here = Here deriving Show
... и я могу сказать, что это должно быть где-то в String
type StringCursor = Cursor Char Here
Теперь, чтобы представить буфер из нескольких строк, нам нужно String выше и ниже строки с курсором и StringCursor в середине, для строки, которую мы сейчас редактируем.
type TextCursor = Cursor String StringCursor
Этот тип TextCursor используется для представления состояния буфера редактирования. Это двухслойная молния. Я предоставляю студентам код для визуализации окна просмотра в тексте в окне оболочки с поддержкой ANSI, гарантируя, что область просмотра содержит курсор. Все, что им нужно сделать, это реализовать код, который обновляет TextCursor в ответ на нажатия клавиш.
handleKey :: Key -> TextCursor -> Maybe (Damage, TextCursor)
где handleKey должен возвращать Nothing, если нажатие клавиши бессмысленно, но в противном случае доставить Just обновленный TextCursor и "отчет об ущербе", последний из которых является одним из
data Damage
= NoChange -- use this if nothing at all happened
| PointChanged -- use this if you moved the cursor but kept the text
| LineChanged -- use this if you changed text only on the current line
| LotsChanged -- use this if you changed text off the current line
deriving (Show, Eq, Ord)
(Если вам интересно, какая разница между возвратом Nothing и возвратом Just (NoChange, ...), подумайте, хотите ли вы, чтобы редактор издавал звуковой сигнал.) Отчет о повреждении сообщает рендереру, сколько работы ему нужно сделать для обновите отображаемое изображение.
Тип Key просто дает читаемое представление dataype для возможных нажатий клавиш, абстрагируясь от необработанных последовательностей ANSI. Это неприметно.
Я предоставляю студентам большой ключ к тому, чтобы идти вверх и вниз с этой моделью данных, предлагая эти части набора:
deactivate :: Cursor x Here -> (Int, [x])
deactivate c = outward 0 c where
outward i (B0, Here, xs) = (i, xs)
outward i (xz :< x, Here, xs) = outward (i + 1) (xz, Here, x : xs)
Функция deactivate используется для смещения фокуса из Cursor, что дает вам обычный список, но сообщает вам, где находился курсор. Соответствующая функция activate пытается поместить курсор в заданную позицию в список:
activate :: (Int, [x]) -> Cursor x Here
activate (i, xs) = inward i (B0, Here, xs) where
inward _ [email protected](_, Here, []) = c -- we can go no further
inward 0 c = c -- we should go no further
inward i (xz, Here, x : xs) = inward (i - 1) (xz :< x, Here, xs) -- and on!
Я предлагаю учащимся сознательно неправильное и неполное определение handleKey
handleKey :: Key -> TextCursor -> Maybe (Damage, TextCursor)
handleKey (CharKey c) (sz,
(cz, Here, cs),
ss)
= Just (LineChanged, (sz,
(cz, Here, c : cs),
ss))
handleKey _ _ = Nothing
который просто обрабатывает нажатия клавиш обычного характера, но делает текст выходящим назад. Легко видеть, что символ c отображается справа от Here. Я предлагаю им исправить ошибку и добавить функциональность для клавиш со стрелками, возврата, удаления, возврата и т.д.
Это может быть не самое эффективное представление когда-либо, но оно чисто функционально и позволяет коду конкретно соответствовать нашим пространственным интуициям об редактируемом тексте.
Мы используем текстовую застежку-молнию в Yi, серьезную реализацию текстового редактора в Haskell.
Реализация типов неизменяемых состояний описана ниже,
http://publications.lib.chalmers.se/records/fulltext/local_94979.pdf
http://publications.lib.chalmers.se/records/fulltext/local_72549.pdf
и другие документы.
Я предлагаю использовать молнии в сочетании с Data.Sequence.Seq, который основан на деревьях пальцев. Таким образом, вы можете представить текущее состояние как
data Cursor = Cursor { upLines :: Seq Line
, curLine :: CurLine
, downLines :: Seq Line }
Это дает вам сложность O (1) для перемещения курсора вверх/вниз по одной строке, а поскольку splitAt и (><) (union) имеют как O (log (min (n1, n2))) сложность, вы 'll получить сложность O (log (L)) для пропускания L строк вверх/вниз.
У вас может быть аналогичная структура застежки-молнии для CurLine, чтобы сохранить последовательность символов до, после и после курсора.
Line может быть чем-то экономичным, например ByteString.
Я использовал для этого zipper для моей библиотеки vty-ui. Вы можете посмотреть здесь:
https://github.com/jtdaugherty/vty-ui/blob/master/src/Graphics/Vty/Widgets/TextZipper.hs
Сообщество Clojure рассматривает RRB Trees (Relaxed Radix Balanced) как постоянный strcuture данных для векторов данных, которые могут быть эффективно конкатенированный/нарезанный/вставленный и т.д.
Он позволяет выполнять операции конкатенации, вставки и индексирования в режиме O (log N).
Я полагаю, что дерево RRB, специализированное для символьных данных, отлично подходит для больших "редактируемых" текстовых структур данных.
Возможности spring:
Тип "Текст" с числовым индексом. Он сохраняет текст в связанном списке буферов (внутреннее представление UTF16), поэтому теоретически его вычислительная сложность обычно связана с сложным списком (например, индексирование - O (n)), на практике это намного быстрее, чем обычное связанное что вы, вероятно, можете просто забыть о влиянии n, если вы не храните всю Википедию в своем буфере. Попробуйте несколько экспериментов с текстом в 1 миллион символов, чтобы убедиться, что я прав (что-то я на самом деле не сделал, BTW).
Текстовая застежка-молния: сохраните текст после курсора в одном текстовом элементе и текст перед курсором в другом. Чтобы переместить текст перевода курсора с одной стороны на другую.