Чисто функциональные структуры данных для текстовых редакторов

Ответ 1

A Vector[Vector[Char]], вероятно, будет хорошей ставкой. Это IndexedSeq, поэтому имеет достойную производительность обновления/предварительной/обновления, в отличие от List, которую вы упомянули. Если вы посмотрите на Характеристики производительности, то это единственная неизменная коллекция, в которой указано эффективное обновление постоянной продолжительности.

Ответ 2

Я не знаю, является ли это предложение "хорошим" для сложных определений "хорошего", но это легко и весело. Я часто задал упражнение, чтобы написать ядро ​​текстового редактора в 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. Я предлагаю им исправить ошибку и добавить функциональность для клавиш со стрелками, возврата, удаления, возврата и т.д.

Это может быть не самое эффективное представление когда-либо, но оно чисто функционально и позволяет коду конкретно соответствовать нашим пространственным интуициям об редактируемом тексте.

Ответ 3

Мы используем текстовую застежку-молнию в Yi, серьезную реализацию текстового редактора в Haskell.

Реализация типов неизменяемых состояний описана ниже,

http://publications.lib.chalmers.se/records/fulltext/local_94979.pdf

http://publications.lib.chalmers.se/records/fulltext/local_72549.pdf

и другие документы.

Ответ 4

• Fingertrees
• Канаты
• scala.collection.immutable.IndexSeq

Ответ 5

Я предлагаю использовать молнии в сочетании с 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.

Ответ 6

Я использовал для этого zipper для моей библиотеки vty-ui. Вы можете посмотреть здесь:

https://github.com/jtdaugherty/vty-ui/blob/master/src/Graphics/Vty/Widgets/TextZipper.hs

Ответ 7

Сообщество Clojure рассматривает RRB Trees (Relaxed Radix Balanced) как постоянный strcuture данных для векторов данных, которые могут быть эффективно конкатенированный/нарезанный/вставленный и т.д.

Он позволяет выполнять операции конкатенации, вставки и индексирования в режиме O (log N).

Я полагаю, что дерево RRB, специализированное для символьных данных, отлично подходит для больших "редактируемых" текстовых структур данных.

Ответ 8

Возможности spring:

• Тип "Текст" с числовым индексом. Он сохраняет текст в связанном списке буферов (внутреннее представление UTF16), поэтому теоретически его вычислительная сложность обычно связана с сложным списком (например, индексирование - O (n)), на практике это намного быстрее, чем обычное связанное что вы, вероятно, можете просто забыть о влиянии n, если вы не храните всю Википедию в своем буфере. Попробуйте несколько экспериментов с текстом в 1 миллион символов, чтобы убедиться, что я прав (что-то я на самом деле не сделал, BTW).

• Текстовая застежка-молния: сохраните текст после курсора в одном текстовом элементе и текст перед курсором в другом. Чтобы переместить текст перевода курсора с одной стороны на другую.