Structures de données purement fonctionnelles pour les éditeurs de texte

Question

Quelles seraient les bonnes structures de données purement fonctionnelles pour les éditeurs de texte ? Je veux être capable d'insérer des caractères uniques dans le texte et de supprimer des caractères uniques du texte avec une efficacité acceptable, et j'aimerais pouvoir conserver les anciennes versions, afin de pouvoir annuler facilement les modifications.

Devrais-je simplement utiliser une liste de chaînes de caractères et réutiliser les lignes qui ne changent pas d'une version à l'autre ?

Answer 1

Je ne sais pas si cette suggestion est "bonne" pour les définitions sophistiquées du "bon", mais elle est facile et amusante. Je fais souvent un exercice consistant à écrire le noyau d'un éditeur de texte en Haskell, en le liant au code de rendu que je fournis. Le modèle de données est le suivant.

Tout d'abord, je définis ce que c'est qu'un curseur à l'intérieur d'une liste de x -éléments, où l'information disponible au curseur est d'un certain type m . (Le x s'avérera être Char o String .)

type Cursor x m = (Bwd x, m, [x])

Este Bwd est juste l'arrière "snoc-lists". Je veux garder de fortes intuitions spatiales, donc je tourne les choses dans mon code, pas dans ma tête. L'idée est que les éléments les plus proches du curseur sont les plus facilement accessibles. C'est l'esprit de la fermeture éclair.

data Bwd x = B0 | Bwd x :< x deriving (Show, Eq)

Je fournis un type singleton gratuit pour agir comme un marqueur lisible pour le curseur...

data Here = Here deriving Show

...et je peux donc dire ce que c'est que d'être quelque part dans une String

type StringCursor = Cursor Char Here

Maintenant, pour représenter un tampon de plusieurs lignes, nous avons besoin de String au-dessus et au-dessous de la ligne où se trouve le curseur, et d'une touche StringCursor au milieu, pour la ligne que nous sommes en train d'éditer.

type TextCursor = Cursor String StringCursor

Este TextCursor est tout ce que j'utilise pour représenter l'état du tampon d'édition. C'est une fermeture éclair à deux couches. Je fournis aux étudiants du code pour rendre une fenêtre d'affichage sur le texte dans une fenêtre shell compatible avec l'escape ANSI, en veillant à ce que la fenêtre d'affichage contienne le curseur. Tout ce qu'ils ont à faire est d'implémenter le code qui met à jour le tampon d'édition. TextCursor en réponse à des frappes au clavier.

handleKey :: Key -> TextCursor -> Maybe (Damage, TextCursor)

donde handleKey devrait retourner Nothing si la frappe est dénuée de sens, mais sinon, délivrer Just une mise à jour TextCursor et un "rapport d'avarie", ce dernier étant l'un des documents les plus importants de l'Union européenne.

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)

(Si vous vous demandez quelle est la différence entre renvoyer Nothing et renvoyant Just (NoChange, ...) si vous souhaitez également que l'éditeur émette un bip). Le rapport de dommages indique au moteur de rendu la quantité de travail qu'il doit effectuer pour mettre à jour l'image affichée.

El Key donne simplement une représentation lisible des données pour les frappes possibles, en faisant abstraction des séquences d'échappement ANSI brutes. Ce n'est pas remarquable.

Je donne aux étudiants un indice important sur la façon de monter et descendre avec ce modèle de données en leur proposant ces éléments :

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)

El deactivate est utilisée pour déplacer le focus hors d'un Cursor en vous donnant une liste ordinaire, mais en vous indiquant où se trouve le curseur. était . La valeur correspondante activate tente de placer le curseur à une position donnée dans une liste :

activate :: (Int, [x]) -> Cursor x Here
activate (i, xs) = inward i (B0, Here, xs) where
  inward _ c@(_, 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!

Je propose aux étudiants une définition délibérément incorrecte et incomplète de 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

qui se contente de traiter les frappes de caractères ordinaires, mais qui fait en sorte que le texte apparaisse à l'envers. Il est facile de voir que le caractère c apparaît droite de Here . Je les invite à corriger le bogue et à ajouter des fonctionnalités pour les touches fléchées, le retour arrière, la suppression, le retour, etc.

Ce n'est peut-être pas la représentation la plus efficace qui soit, mais elle est purement fonctionnelle et permet au code de se conformer concrètement à nos intuitions spatiales concernant le texte en cours d'édition.

Answer 2

A Vector[Vector[Char]] serait probablement un bon pari. C'est un IndexedSeq a donc des performances décentes en matière de mise à jour / prépaiement / mise à jour, à la différence de l'option List que vous mentionnez. Si vous regardez Caractéristiques de performance Il s'agit de la seule collection immuable mentionnée qui dispose d'une mise à jour efficace en temps constant.

Answer 3

Nous utilisons une fermeture éclair de texte dans Yi, une implémentation sérieuse d'éditeur de texte en Haskell.

L'implémentation des types d'états immuables est décrite dans ce qui suit,

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

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

et d'autres documents.

Answer 4

• Fingertrees
• Cordes
• scala.collection.immutable.IndexSeq

Answer 5

Je suggère d'utiliser fermetures éclair en combinaison avec Données.Séquence.Seq qui est basé sur arbres à doigts . On pourrait donc représenter l'état actuel comme

data Cursor = Cursor { upLines :: Seq Line
                     , curLine :: CurLine
                     , downLines :: Seq Line }

Cela vous donne O(1) complexité pour déplacer le curseur vers le haut/bas d'une seule ligne, et puisque splitAt y (><) (union) ont à la fois O(log(min(n1,n2))) complexité, vous obtiendrez O(log(L)) complexité pour le saut L lignes haut/bas.

Vous pourriez avoir une structure de fermeture éclair similaire pour CurLine pour conserver une séquence de caractères avant, pendant et après le curseur.

Line pourrait être quelque chose de peu encombrant, comme Chaine d'octets .