Text Editor: Data Structures
The other day, I was implementing a Piece Table in Haskell, and realized a &quot;Piece&quot; is a &quot;Monoid&quot;, and a &quot;Piece Table&quot; (which I call a &quot;Buffer&quot;) is just a list of &quot;Pieces&quot;.<p><pre><code>    -- A Piece is a String, start, and end.
    data Piece a = Piece { list :: [a] -- &#x27;a&#x27; will be &#x27;Char&#x27; 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] -&gt; Piece
        mconcat = foldl mappend mempty
        -- mappend takes two Pieces, and puts them together, resulting in one Piece.
        mappend :: Piece -&gt; Piece -&gt; 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]
</code></pre>
Now we can implement some pure manipulations:<p><pre><code>    -- replace creates a new Piece, and appends it to the Buffer.
    replace :: String -&gt; Int -&gt; Int -&gt; Buffer -&gt; Buffer
    replace text from to buffer = buffer ++ [(Piece text from to)]

    insert :: String -&gt; Int -&gt; Buffer -&gt; Buffer
    insert text at = replace text at 0

    delete :: Int -&gt; Int -&gt; Buffer -&gt; Buffer
    delete from to = replace &quot;&quot; from to
</code></pre>
...and all that is left is to get the text from the buffer<p><pre><code>    bufferText :: Buffer -&gt; String
    -- mconcat folds our Pieces together, resulting in one Piece
    -- list gets the Piece&#x27;s &quot;list&quot; (String = [Char] in Haskell)
    bufferText = list . mconcat
</code></pre>
Now to use it, all we need to do is string our manipulations together:<p><pre><code>    &gt;&gt;&gt; buffer = replace &quot;Hello&quot; 0 7
               $ insert &quot;, world!&quot; 7
               $ insert &quot;Goodbye&quot; 0
               $ mempty

    &gt;&gt;&gt; bufferText buffer
    &quot;Hello, world!&quot;</code></pre>