scala - 用于文本编辑器的纯函数式数据结构

Question

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

我应该只使用字符串列表并重复使用在版本之间不会更改的行吗？

Answer 1

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

首先，我定义了 x 元素列表中的光标，其中光标处可用的信息具有某种类型 m。 (x 将变为 Char 或 String。)

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

这个Bwd只是向后的“snoc-lists”。我想保持强烈的空间直觉，所以我在代码中扭转局面，而不是在头脑中。这个想法是离光标最近的东西是最容易访问的。这就是《 zipper 》的精神。

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类型是我用来表示编辑缓冲区状态的全部。这是一个两层 zipper 。我为学生提供了在支持 ANSI 转义的 shell 窗口中在文本上渲染视口(viewport)的代码，确保视口(viewport)包含光标。他们所要做的就是实现更新 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的右侧。我邀请他们修复错误并添加箭头键、退格键、删除、返回等功能。

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