3 ms·
The other day, I was implementing a Piece Table in Haskell, and realized a "Piece" is a "Monoid", and a "Piece Table" (which I call a "Buffer") is just a list o
by thomastjeffery 9y ago
The other day, I was implementing a Piece Table in Haskell, and realized a "Piece" is a "Monoid", and a "Piece Table" (which I call a "Buffer") is just a list of "Pieces".
-- A Piece is a String, start, and end.
data Piece a = Piece { list :: [a] -- 'a' will be 'Char' later, but we can support any type here.
, start :: Int
, size :: Int
} deriving (Show)
-- Pieces are Monoids, like Lists, Trees, etc.
-- note that the type declarations here are not allowed (Monoid defines them already). I put them there for your leisure.
instance Monoid (Piece a) where
-- mempty is an empty Piece.
mempty :: Piece
mempty = Piece mempty 0 0
-- mconcat takes a list of Pieces, and condenses them into one Piece.
mconcat :: [Piece] -> Piece
mconcat = foldl mappend mempty
-- mappend takes two Pieces, and puts them together, resulting in one Piece.
mappend :: Piece -> Piece -> Piece
mappend (Piece firstList firstStart firstSize)
(Piece nextList nextStart nextSize) =
let start = fst $ splitAt nextStart firstList
middle = nextList
end = snd $ splitAt nextSize firstList
in Piece (concat [start, middle, end]) firstStart firstSize
type Buffer = [Piece Char]
Now we can implement some pure manipulations:
-- replace creates a new Piece, and appends it to the Buffer.
replace :: String -> Int -> Int -> Buffer -> Buffer
replace text from to buffer = buffer ++ [(Piece text from to)]
insert :: String -> Int -> Buffer -> Buffer
insert text at = replace text at 0
delete :: Int -> Int -> Buffer -> Buffer
delete from to = replace "" from to
...and all that is left is to get the text from the buffer
bufferText :: Buffer -> String
-- mconcat folds our Pieces together, resulting in one Piece
-- list gets the Piece's "list" (String = [Char] in Haskell)
bufferText = list . mconcat
Now to use it, all we need to do is string our manipulations together:
>>> buffer = replace "Hello" 0 7
$ insert ", world!" 7
$ insert "Goodbye" 0
$ mempty
>>> bufferText buffer
"Hello, world!"
- thomastjeffery 9y agoOne advantage that is obvious now is that "Char" isn't specified until we define "Buffer", meaning a "Piece" can deal with any datatype, so you can easily get your Piece Table to deal with any character format from ASCII, UTF-8, UTF-16, etc. to raw bytes, Hex values, etc. It's even fairly obvious how to merge buffers that use different character formats. The strongest point I see regarding Piece Tables is that Pieces are so discrete. You can define a Piece to be whatever you want it to be, as long as you implement "mappend" for it, or you can put the Piece in a box with other data, and make your buffer a list of boxes, and define "mappend" for the rest of the "box"'s data. Another fairly obvious implementation is an undo/redo tree (like Vim has): Instead of Buffer being a List of Pieces, it can be a Tree of Pieces. The buffer is merged by merging the leftmost leaves of the tree, and "undo" is done by swapping the last left Leaf with an empty Leaf. Redo is done by rotating the last left node's leaves. A final note regarding the above implementation: This simple mappend can only merge Pieces in order. If a Piece tries to edit part of another Piece that doesn't exist (out of bounds), it will be appended, or prepended without any filler, because that is how "splitAt" handles edge cases (rather than being implemented with Maybe). It wouldn't be too difficult to implement "mappend" for these edge cases, but you would need to decide on a filler character like space, or you would have to implement some kind of lazy merge that just keeps the second Piece around until it can be merged.
- eru 9y agoIf you use persistent data structures in your implementation (like would be the default in Haskell), your data structures themselves don't need to know about undo/redo. Just keep references to the old state around (in an undo tree or a linear structure for simplicity), and just switch back to them if necessary. Don't explicitly manipulate your data structures. Sharing will take care of keeping the overheads low.
- thomastjeffery 9y ago> Don't explicitly manipulate your data structures. Sharing will take care of keeping the overheads low. Immutability is one of the strong points of Piece Tables. Don't forget that this is the most simple implementation of a Piece Table. If you are in any way concerned about performance, you can quite easily implement caching, sharing, etc.
- eru 9y agoI suspect we are in violent agreement. I was just taking aim at > [...] "undo" is done by swapping the last left Leaf with an empty Leaf. Redo is done by rotating the last left node's leaves. Which is more complicated than you need to be in an immutable setting to implement undo/redo.