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使用类似的概念，除了它是通过字符而不是按行来完成的。缓冲区表示为两个文本块，一个是光标前的块，另一个是光标后的块。移动光标是通过将字符从一个块复制到另一个块来完成的。这里一样的概念。鉴于此，您可能想考虑用单个文本值替换每行的列表。