40

テキスト エディタにとって、純粋に機能的なデータ構造とはどのようなものでしょうか? 1 文字をテキストに挿入したり、テキストから 1 文字を削除したりできる効率を許容できる範囲で維持したいと考えています。また、変更を簡単に元に戻すことができるように、古いバージョンを保持できるようにしたいと考えています。

文字列のリストを使用して、バージョンごとに変更されていない行を再利用する必要がありますか?

4

8 に答える 8

54

「良い」の洗練された定義に対して、この提案が「良い」かどうかはわかりませんが、簡単で楽しいものです。テキストエディタのコア部分を Haskell で記述し、提供するレンダリング コードとリンクさせる演習をよく行います。データモデルは次のとおりです。

最初に、要素のリスト内のカーソルとは何かを定義しますx。ここで、カーソルで利用可能な情報には何らかの type がありますm。(はまたはxになります。)CharString

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

これBwdは単なる後方の「snoc-lists」です。私は強い空間的直感を保ちたいので、頭ではなくコードで物事を好転させます。アイデアは、カーソルに最も近いものに最も簡単にアクセスできるということです。それがThe 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編集バッファーの状態を表すために使用するのは、この型だけです。二層ジッパーです。ANSI エスケープ対応のシェル ウィンドウ内のテキストにビューポートをレンダリングするコードを学生に提供し、ビューポートにカーソルが確実に含まれるようにします。TextCursorキーストロークに応答してを更新するコードを実装するだけです。

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

キーストロークが無意味な場合はどこにhandleKey戻りますが、それ以外の場合は更新された「損傷レポート」を配信します。後者は次のいずれかですNothingJustTextCursor

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( returnとreturn の違いが何であるか疑問に思っている場合は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を見ると、効果的な一定時間の更新があるのは、言及されている唯一の不変コレクションです。

于 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

フィンガーツリーに基づくData.Sequence.Seqと組み合わせてジッパーを使用することをお勧めします。したがって、現在の状態を次のように表すことができます 

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

これにより、カーソルを1行上下に移動するためのO（1）splitAtの複雑さが得られます。また、(><)（union）には両方のO（log（min（n1、n2）））の複雑さがあるため、O（log（L） ）L行を上下にスキップするための複雑さ。

CurLineカーソルの前、前、後の文字のシーケンスを保持するために、同様のジッパー構造を使用できます。

LineByteStringなど、スペース効率の高いものにすることができます。

于 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 ツリー(Relaxed Radix Balanced) を、効率的に連結/スライス/挿入できるデータ ベクトルの永続的なデータ構造として検討しています。

連結、インデックスへの挿入、および分割操作を O(log N) 時間で実行できます。

文字データに特化した RRB ツリーは、大きな「編集可能な」テキスト データ構造に完全に適していると思います。

于 2012-09-12T02:54:48.997 に答える
1

思いつく可能性は次のとおりです。

  1. 数値インデックスを持つ「テキスト」タイプ。バッファの連結リスト (内部表現は UTF16) にテキストを保持するため、理論的には計算の複雑さは通常連結リストの複雑さ (たとえば、インデックス付けは O(n)) ですが、実際には従来の連結リストよりもはるかに高速です。ウィキペディア全体をバッファに保存していない限り、 n の影響をおそらく忘れてしまう可能性があることをリストしてください。私が正しいかどうかを確認するために、100 万文字のテキストでいくつかの実験を試みてください (実際に行ったことはありません)。

  2. テキスト ジッパー: カーソルの後のテキストを 1 つのテキスト要素に格納し、カーソルの前のテキストを別のテキスト要素に格納します。カーソル転送テキストを一方の側から他方の側に移動するには。

于 2012-09-10T22:22:27.823 に答える