rupert
February 23, 2023, 4:24pm
8
With Arrays I iterated over a slice using Array.get:
{-| Iterates forward over a region of the buffer.
This is the most efficient way to extract and map data from the buffer. For
example, you would use this when rendering the visible contents of a `GapBuffer`
to Html. The implementation does not create intermediate data structures to hold
the extracted elements, and it only iterates over the range you specify.
-}
foldlSlice : (Int -> a -> acc -> acc) -> acc -> Int -> Int -> GapBuffer a b -> acc
foldlSlice fn acc from to buffer =
List.foldl
(\idx resAcc ->
case get idx buffer of
Just val ->
fn idx val resAcc
Nothing ->
resAcc
)
This was used to implement a GapBuffer for a text editor. I certainly found that doing it this way was efficient enough to get a UI that scrolled smoothly. But yes, the Array.get access is O(Log n), so not as fast as it could be:
If a simple Array is used to hold lines of text, whenever a line is edited, the array will need to be sliced, lines modified, then put back together again. It works fine up to a limit at which point the editor becomes noticeably unresponsive.
I scratched my head over this one for a while, thinking about various tree structures, or skip lists, and so on. Then the answer came to me - make a data structure like a zip list, but use arrays instead of lists. There are lots of packages implementing zi…
Demo: https://kind-colden-ebafc2.netlify.app/
1 Like