Data-Rope-0.2: Ropes, an alternative to (Byte)Strings.




Implementation of the ideas in Inspired also by Data.Map and the OCaml version of ropes.


The Rope type

Introducing and eliminating Ropes

empty :: RopeSource

O(1) The empty Rope

singleton :: Word8 -> RopeSource

O(1) Convert a Word8 into a Rope

pack :: [Word8] -> RopeSource

O(n) Convert a list of Word8 into a Rope

unpack :: Rope -> [Word8]Source

O(n) Inverse conversion

fromByteString :: ByteString -> RopeSource

O(n) Conversion from a strict ByteString

toByteString :: Rope -> ByteStringSource

O(n) Conversion to a strict ByteString

Basic interface

cons :: Word8 -> Rope -> RopeSource

O(log n). Appends the specified byte at the beginning of the Rope.

snoc :: Rope -> Word8 -> RopeSource

O(log n). Appends the specified byte at the end of the Rope.

append :: Rope -> Rope -> RopeSource

O(log n) Concatenates two Ropes

head :: Rope -> Word8Source

O(log n) First element of the Rope. Raises an error if the argument is empty.

uncons :: Rope -> Maybe (Word8, Rope)Source

O(log n). Returns the first element of the Rope, and the Rope of the remaining elements.

last :: Rope -> Word8Source

O(log n). Last element of a Rope.

tail :: Rope -> RopeSource

O(log n) The elements after the head. An error is raised if the Rope is empty.

init :: Rope -> RopeSource

O(log n) The elements in the Rope except the last one.

null :: Rope -> BoolSource

O(1) Tests whether a Rope is empty.

length :: Rope -> IntSource

O(1) Length of a Rope.

Transforming Ropes

map :: (Word8 -> Word8) -> Rope -> RopeSource

O(n). map f r applies f on each element of r and returns the concatenation of the result.

reverse :: Rope -> RopeSource

O(n) efficient way to reverse a Rope.

intercalate :: Rope -> [Rope] -> RopeSource

O(n) intercalate an element between each element of the list of Ropes and concatenates the result.


insert :: Rope -> Int -> Rope -> RopeSource

O(log n) insert a i b inserts Rope a in Rope b after the ith element of b.

Reducing Ropes

foldl :: (a -> Word8 -> a) -> a -> Rope -> aSource

O(n). fold over a Rope. This implementation is not tail-recursive but never pushes more than O(log n) calls on the stack.

foldl' :: (a -> Word8 -> a) -> a -> Rope -> aSource

O(n). like foldl but strict.

foldr :: (Word8 -> a -> a) -> a -> Rope -> aSource

O(n). Right fold. Again not tail-recursive but never uses more than O(log n) on the stack.

Breaking Ropes

splitAt :: Int -> Rope -> (Rope, Rope)Source

O(log n). splitAt n xs is equivalent to (take n xs, drop n xs), but a little faster.

breakByte :: Word8 -> Rope -> (Rope, Rope)Source

O(n). breakByte c r breaks Rope r before the first occurence of c.

breaks :: Word8 -> Rope -> [Rope]Source

O(n). breaks w r breaks Rope r between each occurence of w (non-inclusive). This function is not tail-recursive, uses memchr and constructs the list in parallel using par.

lines :: Rope -> [Rope]Source

O(n). Satisfies lines r == breaks 0x0a r.

Indexing Ropes

index :: Rope -> Int -> CharSource

O(log n) returns the Word8 at given index in the Rope

elemIndex :: Word8 -> Rope -> Maybe IntSource

O(n) returns the index of the first element equal to the query element. This implementation uses memchr at leaves, and explores the rope in parallel (with par).

elemIndex' :: Word8 -> Rope -> Maybe IntSource

O(n) Same as elemIndex, but explores the Rope sequentially. Useful for Ropes loaded lazily with readFile.

elemIndices :: Word8 -> Rope -> [Int]Source

O(n) returns the list of all positions where the queried elements occurs in the Rope. This implementation uses memchr.

Input and Output

readFile :: FilePath -> IO RopeSource

Lazy file reading, using mmap.

hGet :: Handle -> Int -> IO RopeSource

Strict hGet. The whole rope is constructed.

hGetLine :: Handle -> IO RopeSource

Returns the next line in the input Handle. If you need to iterate hGetLine, it may be more efficient to first mmap the file using readFile, or even load it with then iterate breakByte 0x0a : hGetLine allocates a buffer to read the file and may waste most of this space if the lines are shorter than the standard buffer size of this module.

hGetContents :: Handle -> IO RopeSource

Reads the contents of a file handle strictly, then closes it.

hPut :: Handle -> Rope -> IO ()Source

Writes the contents of the Rope on the specified Handle.

hPutStrLn :: Handle -> Rope -> IO ()Source

like hPut, but with a newline character at the end of the output

hPutStr :: Handle -> Rope -> IO ()Source

synonym for hPut.

putStrLn :: Rope -> IO ()Source

like putStr but with a newline character at the end of the output

putStr :: Rope -> IO ()Source

Writes the contents of the Rope on the standard output.