Stability | experimental |
---|---|
Maintainer | Bas van Dijk <v.dijk.bas@gmail.com> |
Difference strings: a data structure for O(1) append on strings. Note that a
DString
is just a newtype wrapper around a DList
Char
. The reason we
need a new type instead of just a type synonym is that we can have an
instance
without using language extensions
(IsString
DString
TypeSynonymInstances
or FlexibleInstances
) so we can write overloaded
string literals of type DString
.
- data DString
- fromDList :: DList Char -> DString
- toDList :: DString -> DList Char
- fromShowS :: ShowS -> DString
- toShowS :: DString -> ShowS
- singleton :: Char -> DString
- cons :: Char -> DString -> DString
- snoc :: DString -> Char -> DString
- concat :: [DString] -> DString
- list :: α -> (Char -> DString -> α) -> DString -> α
- head :: DString -> Char
- tail :: DString -> DString
- unfoldr :: (α -> Maybe (Char, α)) -> α -> DString
- foldr :: (Char -> α -> α) -> α -> DString -> α
Documentation
A difference string is a function that given a string, returns the original contents of the difference string prepended at the given string.
This structure supports O(1) mappend
en snoc
operations on strings making
it very usefull for append-heavy uses such as logging and pretty printing.
You can use it to efficiently show a tree for example: (Note that we use some
handy functions from the string-combinators
package)
{-# LANGUAGE OverloadedStrings #-} import Data.DString (toShowS, fromShowS) import Data.String.Combinators ((<+>), paren) data Tree a = Leaf a | Branch (Tree a) (Tree a) instance Show a => Show (Tree a) where showsPrec prec = showParen (prec >= funAppPrec) . toShowS . go where go (Leaf x) = "Leaf" <+> fromShowS (showsPrec funAppPrec x) go (Branch l r) = "Branch" <+> paren (go l) <+> paren (go r) funAppPrec = 10
Note that a DString
can be converted from and to a String
using the
fromString
and toString
methods from the IsString
and ToString
classes respectively.
Conversion
fromDList :: DList Char -> DStringSource
O(1) Convert a difference list of Char
s to a difference string.