usados unidad todos tipos textos texto son sirve significado que puro programar procesador por paso para organizacion mundo mas los lista lineales libros introduccion hola historia gratis funciones estructuras estructura entre ejemplos editores ecured diferencia descargar datos cuales caracteristicas bien basicas aprender aprende algoritmos actualidad scala haskell data-structures functional-programming text-editor

scala - unidad - Estructuras de datos puramente funcionales para editores de texto



tipos de datos en haskell (8)

Implementé una cremallera para este propósito para mi biblioteca vty-ui . Puedes dar un vistazo aqui:

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

¿Cuáles serían las estructuras de datos puramente funcionales para los editores de texto? Quiero poder insertar caracteres individuales en el texto y eliminar caracteres individuales del texto con una eficiencia aceptable, y me gustaría poder conservar las versiones anteriores, así puedo deshacer los cambios con facilidad.

¿Debo simplemente usar una lista de cadenas y reutilizar las líneas que no cambian de una versión a otra?

La comunidad de Clojure está mirando RRB Trees (Relaxed Radix Balanced) como una estructura de datos persistente para vectores de datos que se pueden concatenar / cortar / insertar de manera eficiente, etc.

Permite las operaciones de concatenación, inserción en el índice y división en el tiempo O (log N).

Me imagino que un RRB Tree especializado para datos de caracteres sería perfectamente adecuado para grandes estructuras de datos de texto "editables".

Las posibilidades que vienen a la mente son:

  1. El tipo "Texto" con un índice numérico. Mantiene el texto en una lista vinculada de almacenamientos intermedios (la representación interna es UTF16), así que, aunque en teoría su complejidad computacional suele ser la de una lista vinculada (por ejemplo, la indexación es O (n)), en la práctica es mucho más rápido que un enlace convencional enumera que probablemente podrías olvidarte del impacto de n a menos que estés almacenando toda la Wikipedia en tu memoria intermedia. Pruebe algunos experimentos con texto de 1 millón de caracteres para ver si estoy en lo cierto (algo que en realidad no he hecho, por cierto).

  2. Una cremallera de texto: almacena el texto después del cursor en un elemento de texto y el texto anterior al cursor en otro. Para mover el cursor, transfiera el texto de un lado a otro.

No sé si esta sugerencia es "buena" para definiciones sofisticadas de "bueno", pero es fácil y divertida. A menudo establezco un ejercicio para escribir el núcleo de un editor de texto en Haskell, vinculando con el código de representación que proporciono. El modelo de datos es el siguiente.

Primero, defino lo que es ser un cursor dentro de una lista de elementos x , donde la información disponible en el cursor tiene algún tipo m . (La x resultará ser Char o String ).

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

Esta cosa de Bwd es solo la "lista snoc" atrasada. Quiero mantener fuertes intuiciones espaciales, así que cambio las cosas en mi código, no en mi cabeza. La idea es que el material más cercano al cursor sea el más fácilmente accesible. Ese es el espíritu de The Zipper.

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

Proporciono un tipo de singleton gratuito para actuar como un marcador legible para el cursor ...

data Here = Here deriving Show

... y puedo decir lo que es estar en algún lugar de una String

type StringCursor = Cursor Char Here

Ahora, para representar un buffer de múltiples líneas, necesitamos String s arriba y debajo de la línea con el cursor, y un StringCursor en el medio, para la línea que estamos editando actualmente.

type TextCursor = Cursor String StringCursor

Este tipo de TextCursor es todo lo que uso para representar el estado del buffer de edición. Es una cremallera de dos capas. Proporciono a los alumnos el código para representar una ventana gráfica en el texto en una ventana de shell habilitada para ANSI-escape-enabled, asegurando que la ventana gráfica contenga el cursor. Todo lo que tienen que hacer es implementar el código que actualiza el TextCursor en respuesta a las pulsaciones de teclas.

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

donde handleKey debería devolver Nothing si la pulsación de tecla no tiene sentido, pero si no, entregue Just un TextCursor actualizado y un "informe de daños", siendo este último uno de

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 se está preguntando cuál es la diferencia entre devolver Nothing y devolver Just (NoChange, ...) , considere si también desea que el editor Just (NoChange, ...) pitido). El informe de daños le dice al renderizador cuánto trabajo necesita hacer para traer la imagen mostrada al día.

El tipo de Key simplemente brinda una representación legible de tipo de datos a las posibles combinaciones de teclas, abstrayendo de las secuencias de escape ANSI en bruto. No tiene nada de especial.

Ofrezco a los alumnos una gran pista sobre cómo subir y bajar con este modelo de datos al ofrecer estas piezas del kit:

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)

La función de deactivate se usa para cambiar el foco de un Cursor , proporcionándole una lista ordinaria, pero indicándole dónde estaba el cursor. La función de activate correspondiente intenta colocar el cursor en una posición determinada en una lista:

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!

Ofrezco a los estudiantes una definición deliberadamente incorrecta e incompleta 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

que solo maneja las pulsaciones de teclas de caracteres comunes pero hace que el texto salga hacia atrás. Es fácil ver que el carácter c aparece a la derecha de Here . Los invito a corregir el error y agregar la funcionalidad para las teclas de flecha, retroceder, eliminar, regresar, y así sucesivamente.

Puede que no sea la representación más eficiente de la historia, pero es puramente funcional y permite que el código se ajuste concretamente a nuestras intuiciones espaciales sobre el texto que se está editando.

Sugeriría utilizar zippers en combinación con Data.Sequence.Seq que se basa en árboles de dedo . Entonces, podría representar el estado actual como

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

Esto le da O (1) complejidad para mover el cursor arriba / abajo en una sola línea, y como splitAt y (><) (unión) tienen complejidad O (log (min (n1, n2))) , obtendrá O (log (L)) complejidad para omitir las líneas L arriba / abajo.

Podría tener una estructura de cierre similar para CurLine para mantener una secuencia de caracteres antes, en y después del cursor.

Line podría ser algo eficiente en el uso del espacio, como ByteString .

Un Vector[Vector[Char]] probablemente sea una buena apuesta. Es un IndexedSeq así que tiene un IndexedSeq decente de actualización / prepend / update, a diferencia de la List que mencionas. Si observa las características de rendimiento , es la única colección inmutable mencionada que tiene una actualización efectiva en tiempo constante.