Haskell「字符串移動」函數

Question

我想用Haskell，hscurses和Data.Text來構建一個簡單的文本編輯器。我對Haskell很新。

這裏是我的代碼片段：

data Cursor = Cursor { 
    position :: Int, 
    line  :: Int, 
    column :: Int 
} deriving (Eq, Show) 

isNewline :: Char -> Bool 
isNewline c = c == '\n' 

onNewline :: T.Text -> Int -> Bool 
onNewline buf pos 
    | pos >= T.length buf = False 
    | otherwise   = isNewline $ T.index buf pos 

findIndex :: (Char -> Bool) -> T.Text -> Int -> Maybe Int 
findIndex pred buf pos 
    | buf == T.empty = Just 0 
    | otherwise  = rightWhile pos 
    where rightWhile pos 
      | pos > bufMax buf  = Nothing 
      | pred $ T.index buf pos = Just pos 
      | otherwise    = rightWhile (pos + 1) 

findIndexLeft :: (Char -> Bool) -> T.Text -> Int -> Maybe Int 
findIndexLeft pred buf pos = leftWhile pos 
    where leftWhile pos 
      | pos < 0    = Nothing 
      | pred $ T.index buf pos = Just pos 
      | otherwise    = leftWhile (pos - 1) 

startOfLine :: T.Text -> Int -> Int 
startOfLine buf pos = case findIndexLeft isNewline buf (pos - 1) of 
    Nothing -> 0 
    Just p -> p + 1 

endOfLine :: T.Text -> Int -> Int 
endOfLine buf pos = case findIndex isNewline buf pos of 
    Nothing -> 1 + bufMax buf 
    Just p -> p 

lineOffset :: T.Text -> Int -> Int 
lineOffset buf pos = pos - startOfLine buf pos 

lineLength :: T.Text -> Int -> Int 
lineLength buf pos = endOfLine buf pos - startOfLine buf pos 

bufMax :: T.Text -> Int 
bufMax buf = max 0 $ T.length buf - 1 

bufLines :: T.Text -> Int 
bufLines = T.foldl (\acc c -> if isNewline c then (acc+1) else acc) 0 

moveCursorRight :: T.Text -> Cursor -> Cursor 
moveCursorRight buf c@(Cursor pos line col) 
    | buf == T.empty = c 
    | otherwise  = Cursor newPos newLine newCol 
    where end  = 1 + bufMax buf 
     onEnd  = pos == end 
     newPos = clip (pos + 1) 0 end 
     newLine = if onNewline buf pos && not onEnd 
        then line + 1 
        else line 
     newCol = lineOffset buf newPos 

moveCursorLeft :: T.Text -> Cursor -> Cursor 
moveCursorLeft buf (Cursor pos line col) = 
    Cursor newPos newLine newCol 
    where onStart = pos == 0 
     newPos = clipLow (pos - 1) 0 
     newLine = if onNewline buf newPos && not onStart 
        then line - 1 
        else line 
     newCol = lineOffset buf newPos 

-- More movement functions follow... 

這段代碼的問題是，對於那些成千上萬行的長的緩衝區，它會非常緩慢。這可能是因爲使用索引函數，例如O（n）而不是常量時間，例如它們將在C中。

一個經驗豐富的哈斯克勒會如何處理這個問題？在Haskell中的字符串中實現「移動」是一種合理有效的方式？運動也應該是組合的，那就是，我想能夠在「向下移動一行」條款實施「向下翻頁」等

編輯：更新

如若有誰需要這個，這是我結束了。

type Line = T.Text 

data BufferContext = BufferContext { 
    before :: [Line], 
    at  :: Line, 
    after :: [Line] 
} deriving (Eq, Show) 

moveCursorRight :: Cursor -> Cursor 
moveCursorRight c@(Cursor pos line col bc@(BufferContext before at after)) 
    | col >= T.length at = moveCursorDown c 
    | otherwise   = Cursor (pos+1) line (col+1) bc 

moveCursorLeft :: Cursor -> Cursor 
moveCursorLeft c@(Cursor pos line col bc@(BufferContext before at after)) 
    | col <= 0 = upCursor { column = if null before then 0 else T.length $ head before } 
    | otherwise = Cursor (pos-1) line (col-1) bc 
    where upCursor = moveCursorUp c 

moveCursorDown :: Cursor -> Cursor 
moveCursorDown c@(Cursor _ _ _ (BufferContext _ _ [])) = c 
moveCursorDown c@(Cursor _ cLine _ (BufferContext before at (l:ls))) = 
    c { line = cLine+1, 
     column = 0, 
     context = BufferContext (at:before) l ls 
    } 

moveCursorUp c@(Cursor _ _ _ (BufferContext [] _ _)) = c 
moveCursorUp c@(Cursor _ cLine _ (BufferContext (l:ls) at after)) = 
    c { line = cLine-1, 
     column = 0, 
     context = BufferContext ls l (at:after) 
    } 

該實現在100萬行上非常實用，對我來說這已經夠用了。但是，這種方法仍然存在一個問題。如果我想跳到一條隨機線，我必須逐個移動，這可能會很慢。但是，與原始方法相比，這是一個很大的改進。

我也曾嘗試執行上下文

data BufferContext = BufferContext { 
    before :: T.Text, 
    at  :: Char, 
    after :: T.Text 
} deriving (Eq, Show) 

但這並不能幫助太多，因爲「在」必須「之前」與consed，並根據該文件，T.cons是O（ n）...而且，當實際顯示完成時，以線爲中心的方法更好。

感謝所有幫助過的人！

Answer 1

正如gallais在評論中所說，你想使用拉鍊。這個想法是，你的「光標」，實際上是一種數據結構是這樣的：

type Line = T.Text 

data TextZipper = TextZipper { 
    textBefore :: [Line], 
    currentLine :: Line, 
    textAfter :: [Line] 
} 

的訣竅是「textBefore」包含以相反的順序光標以上的線路。因此，要下移你把「currentLine」在「textBefore頭」行，並獲得新的「currentLine」出「textAfter」的，就像這樣：

moveDown :: TextZipper -> Maybe TextZipper 
moveDown tzip = case textAfter tzip of 
    [] -> Nothing -- Already at the bottom of the file. 
    t:ts -> TextZipper { 
     textBefore = currentLine tzip : textBefore tzip, 
     currentLine = t, 
     textAfter = ts 
    } 

爲moveUp將是非常相似的。您還需要一個textZipperToList函數來提取用於保存的zipper的內容，以及一個textZipperFromList函數。

我記得在某處讀到Emacs使用類似的概念，除了它是通過字符而不是按行來完成的。緩衝區表示爲兩個文本塊，一個是光標前的塊，另一個是光標後的塊。移動光標是通過將字符從一個塊複製到另一個塊來完成的。這裏一樣的概念。鑑於此，您可能想考慮用單個文本值替換每行的列表。