40

对于文本编辑器来说，什么是好的纯功能数据结构？我希望能够以可接受的效率将单个字符插入文本并从文本中删除单个字符，并且我希望能够保留旧版本，以便轻松撤消更改。

我应该只使用字符串列表并重用不会随版本变化的行吗？

4

8 回答 8

54

对于“好”的复杂定义，我不知道这个建议是否“好”，但它既简单又有趣。我经常设置一个练习，用 Haskell 编写文本编辑器的核心，并与我提供的渲染代码链接。数据模型如下。

首先，我在 -elements 列表中定义什么是游标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在光标所在行的上方和下方使用 s，StringCursor在中间需要 a 来表示我们当前正在编辑的行。

type TextCursor = Cursor String StringCursor

我只使用这种TextCursor类型来表示编辑缓冲区的状态。这是一个两层拉链。我为学生提供了在支持 ANSI 转义的 shell 窗口中呈现文本视口的代码，确保视口包含光标。他们所要做的就是实现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类型只是为可能的击键提供可读的数据类型表示，从原始的 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 _ 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!

我故意给学生一个不正确和不完整的定义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我邀请他们修复错误并添加箭头键、退格、删除、返回等功能。

它可能不是有史以来最有效的表示，但它纯粹是功能性的，并且使代码能够具体地符合我们对正在编辑的文本的空间直觉。

于 2012-09-11T00:27:49.490 回答
10

AVector[Vector[Char]]可能是一个不错的选择。与您提到的不同，它IndexedSeq具有不错的更新/前置/更新性能。List如果您查看Performance Characters，它是唯一提到的具有有效恒定时间更新的不可变集合。

于 2012-09-10T19:34:54.600 回答
8

我们在 Yi 中使用文本拉链，这是 Haskell 中的一个严肃的文本编辑器实现。

不可变状态类型的实现如下所述，

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

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

和其他论文。

于 2012-09-11T17:01:22.253 回答
6
于 2012-09-11T02:07:49.953 回答
4

我建议将zippers与基于手指树的Data.Sequence.Seq结合使用。所以你可以将当前状态表示为 

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

这为您在单行向上/向下移动光标提供了O(1)splitAt复杂度，并且由于和(><)(union) 都具有O(log(min(n1,n2)))复杂度，您将得到O(log(L) )向上/向下跳过L行的复杂度。

你可以有一个类似的拉链结构CurLine来保持光标之前、之后和之后的字符序列。

Line可能是节省空间的东西，例如ByteString。

于 2012-09-13T09:55:55.323 回答
4

为此，我为我的vty-ui库实现了一个拉链。你可以看看这里：

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

于 2012-10-19T19:42:09.793 回答
2

Clojure 社区正在将RRB 树（松弛基数平衡）视为可以有效连接/切片/插入等数据向量的持久数据结构。

它允许在 O(log N) 时间内进行连接、插入索引和拆分操作。

我想专门用于字符数据的 RRB 树将非常适合大型“可编辑”文本数据结构。

于 2012-09-12T02:54:48.997 回答
1

浮现在脑海中的可能性是：

  1. 带有数字索引的“文本”类型。它将文本保存在缓冲区的链表中（内部表示为 UTF16），因此虽然理论上它的计算复杂度通常是链表的计算复杂度（例如索引是 O(n)），但实际上它比传统的链表快得多列出您可能会忘记 n 的影响，除非您将整个 Wikipedia 存储在缓冲区中。尝试对 100 万个字符的文本进行一些实验，看看我是否正确（顺便说一句，我实际上还没有做过）。

  2. 文本拉链：将光标后的文本存储在一个文本元素中，将光标前的文本存储在另一个文本元素中。将光标从一侧传输到另一侧。

于 2012-09-10T22:22:27.823 回答