dstring (empty) → 0.1
raw patch · 4 files changed
+178/−0 lines, 4 filesdep +basedep +dlistsetup-changed
Dependencies added: base, dlist
Files
- Data/DString.hs +120/−0
- LICENSE +30/−0
- Setup.lhs +4/−0
- dstring.cabal +24/−0
+ Data/DString.hs view
@@ -0,0 +1,120 @@+-----------------------------------------------------------------------------+-- |+-- Module : Data.DString+-- Copyright : (c) 2009 Bas van Dijk+-- License : BSD-style (see the file LICENSE)+--+-- Maintainer : Bas van Dijk <v.dijk.bas@gmail.com>+-- Stability : experimental+-- Portability : portable (Haskell 98)+--+-- 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.+--+-----------------------------------------------------------------------------++module Data.DString+ ( DString++ -- * Conversion+ , fromDList+ , toDList+ , toString+ , fromShowS+ , toShowS++ -- * Basic functions+ , empty+ , singleton+ , cons+ , snoc+ , append+ , concat+ , list+ , head+ , tail+ , unfoldr+ , foldr+ )+ where++import Prelude hiding (concat, foldr, head, tail)+import qualified Data.DList as D+import Data.Monoid+import Data.String++newtype DString = DS { toDList :: D.DList Char -- ^ Convert a difference string to a difference list+ }++-- | Convert a difference list of Chars to a difference string+fromDList :: D.DList Char -> DString+fromDList = DS++instance Monoid DString where+ mempty = empty+ mappend = append++instance IsString DString where+ fromString = fromDList . D.fromList++-- | Convert a difference string back to a normal String+toString :: DString -> String+toString = D.toList . toDList++-- | Convert a ShowS to a difference string+fromShowS :: ShowS -> DString+fromShowS = fromDList . D.DL++-- | Convert a difference string to a ShowS+toShowS :: DString -> ShowS+toShowS = D.unDL . toDList++-- | Create a difference string containing no characters+empty :: DString+empty = fromDList D.empty++-- | Build a difference string from a single Char+singleton :: Char -> DString+singleton = fromDList . D.singleton++-- | /O(1)/, Prepend a Char to a difference string+cons :: Char -> DString -> DString+cons c ds = fromDList $ D.cons c (toDList ds)++-- | /O(1)/, Append a Char to a difference string+snoc :: DString -> Char -> DString+snoc ds c = fromDList $ D.snoc (toDList ds) c++-- | /O(1)/, Appending difference strings+append :: DString -> DString -> DString+x `append` y = fromDList (toDList x `D.append` toDList y)++-- | /O(spine)/, Concatenate difference strings+concat :: [DString] -> DString+concat = fromDList . D.concat . map toDList++-- | /O(length ds)/, difference list elimination, head, tail.+list :: b -> (Char -> DString -> b) -> DString -> b+list nill consit ds =+ case toString ds of+ [] -> nill+ x : xs -> consit x $ fromString xs++-- | Return the head of the difference string+head :: DString -> Char+head = list (error "Data.DString.head: empty list") const++-- | Return the tail of the difference string+tail :: DString -> DString+tail = list (error "Data.DString.tail: empty list") (flip const)++-- | Unfoldr for difference strings+unfoldr :: (b -> Maybe (Char, b)) -> b -> DString+unfoldr pf b = fromDList $ D.unfoldr pf b++-- | Foldr over difference strings+foldr :: (Char -> b -> b) -> b -> DString -> b+foldr f b = D.foldr f b . toDList
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright (c) 2009, Bas van Dijk+All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are+met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution.++ * Neither the name of Bas van Dijk nor the names of its+ contributors may be used to endorse or promote products derived+ from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ Setup.lhs view
@@ -0,0 +1,4 @@+#! /usr/bin/env runhaskell+ +> import Distribution.Simple+> main = defaultMain
+ dstring.cabal view
@@ -0,0 +1,24 @@+Name: dstring+Version: 0.1+Synopsis: Difference strings.+Description:+ 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.++Category: Data+License: BSD3+License-file: LICENSE+Author: Bas van Dijk <v.dijk.bas@gmail.com>+Maintainer: Bas van Dijk <v.dijk.bas@gmail.com>+Copyright: 2009 Bas van Dijk <v.dijk.bas@gmail.com>+Cabal-version: >= 1.2+Build-Type: Simple+Stability: experimental++Library+ Build-Depends: base, dlist+ Exposed-modules: Data.DString+ Ghc-options: -O2 -Wall