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' without using language extensions (TypeSynonymInstances or FlexibleInstances) 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

Show DString

IsString DString

Monoid DString

ToString 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

fromShowS :: ShowS -> DString

Convert a ShowS to a difference string

toShowS :: DString -> ShowS

Convert a difference string to a ShowS

Basic functions

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

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