Comment by thomastjeffery

9 years 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!"

One 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.

  • If 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.

    • > 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.

      1 reply →