Data.DString

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 IsString DString' so we can write overloaded string literals of type DString.

Documentation

data DString

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) append 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 make use of some functions from the string-combinators package: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/string-combinators)

 {-# LANGUAGE OverloadedStrings #-}

 import Data.DString
 import Data.String.Combinators ((<+>), fromShow, paren)

 data Tree a = Leaf a | Branch (Tree a) (Tree a)

 instance Show a => Show (Tree a) where
     show = toString . go
         where
           go (Leaf x)     = "Leaf" <+> fromShow x
           go (Branch l r) = "Branch" <+> paren (go l) <+> paren (go r)

Instances

IsString DString

Monoid DString

Conversion

fromDList :: DList Char -> DString

Convert a difference list of Chars to a difference string

toDList :: DString -> DList Char

Convert a difference string to a difference list

toString :: DString -> String

Convert a difference string back to a normal String

fromShowS :: ShowS -> DString

Convert a ShowS to a difference string

toShowS :: DString -> ShowS

Convert a difference string to a ShowS

Basic functions

empty :: DString

Create a difference string containing no characters

singleton :: Char -> DString

Build a difference string from a single Char

cons :: Char -> DString -> DString

O(1), Prepend a Char to a difference string

snoc :: DString -> Char -> DString

O(1), Append a Char to a difference string

append :: DString -> DString -> DString

O(1), Appending difference strings

concat :: [DString] -> DString

O(spine), Concatenate difference strings

list :: b -> (Char -> DString -> b) -> DString -> b

O(length ds), difference list elimination, head, tail.

head :: DString -> Char

Return the head of the difference string

tail :: DString -> DString

Return the tail of the difference string

unfoldr :: (b -> Maybe (Char, b)) -> b -> DString

Unfoldr for difference strings

foldr :: (Char -> b -> b) -> b -> DString -> b

Foldr over difference strings