A time and space-efficient implementation of byte vectors using packed Word8 arrays, suitable for high performance use, both in terms of large data quantities, or high speed requirements. Byte vectors are encoded as strict Word8 arrays of bytes, held in a ForeignPtr, and can be passed between C and Haskell with little effort.

This module is intended to be imported qualified, to avoid name clashes with Prelude functions. eg.

 import qualified Data.ByteString as B

Original GHC implementation by Bryan O'Sullivan. Rewritten to use UArray by Simon Marlow. Rewritten to support slices and use ForeignPtr by David Roundy. Polished and extended by Don Stewart.

O(n) Convert a '[Word8]' into a ByteString.

For applications with large numbers of string literals, pack can be a bottleneck. In such cases, consider using packAddress (GHC only).

O(n) replicate n x is a ByteString of length n with x the value of every element. The following holds:

 replicate w c = unfoldr w (\u -> Just (u,u)) c

This implemenation uses memset(3)

O(n) The unfoldrN function is analogous to the List 'unfoldr'. unfoldrN builds a ByteString from a seed value. The function takes the element and returns Nothing if it is done producing the ByteString or returns Just (a,b), in which case, a is a prepending to the ByteString and b is used as the next element in a recursive call.

To preven unfoldrN having O(n^2) complexity (as prepending a character to a ByteString is O(n), this unfoldr requires a maximum final size of the ByteString as an argument. cons can then be implemented in O(1) (i.e. a poke), and the unfoldr itself has linear complexity. The depth of the recursion is limited to this size, but may be less. For lazy, infinite unfoldr, use unfoldr (from List).

Examples:

 unfoldrN 10 (\x -> Just (x, chr (ord x + 1))) '0' == "0123456789"

The following equation connects the depth-limited unfoldr to the List unfoldr:

 unfoldrN n == take n $ List.unfoldr

spanEnd behaves like span but from the end of the ByteString. We have

 spanEnd (not.isSpace) "x y z" == ("x y ","z")

and

 spanEnd (not . isSpace) ps
    == 
 let (x,y) = span (not.isSpace) (reverse ps) in (reverse y, reverse x) 

breakByte breaks its ByteString argument at the first occurence of the specified byte. It is more efficient than break as it is implemented with memchr(3). I.e.

 break (=='c') "abcd" == breakByte 'c' "abcd"

spanByte breaks its ByteString argument at the first occurence of a byte other than its argument. It is more efficient than 'span (==)'

 span  (=='c') "abcd" == spanByte 'c' "abcd"

O(n) breakFirst breaks the given ByteString on the first occurence of w. It behaves like break, except the delimiter is not returned, and Nothing is returned if the delimiter is not in the ByteString. I.e.

 breakFirst 'b' "aabbcc" == Just ("aa","bcc")

 breakFirst c xs ==
 let (x,y) = break (== c) xs 
 in if null y then Nothing else Just (x, drop 1 y))

O(n) breakLast behaves like breakFirst, but from the end of the ByteString.

 breakLast ('b') (pack "aabbcc") == Just ("aab","cc")

and the following are equivalent:

 breakLast 'c' "abcdef"
 let (x,y) = break (=='c') (reverse "abcdef") 
 in if null x then Nothing else Just (reverse (drop 1 y), reverse x)

O(n) Break a ByteString into pieces separated by the byte argument, consuming the delimiter. I.e.

 split '\n' "a\nb\nd\ne" == ["a","b","d","e"]
 split 'a'  "aXaXaXa"    == ["","X","X","X"]
 split 'x'  "x"          == ["",""]

and

 join [c] . split c == id
 split == splitWith . (==)

As for all splitting functions in this library, this function does not copy the substrings, it just constructs new ByteStrings that are slices of the original.

O(n) Splits a ByteString into components delimited by separators, where the predicate returns True for a separator element. The resulting components do not contain the separators. Two adjacent separators result in an empty component in the output. eg.

 splitWith (=='a') "aabbaca" == ["","","bb","c",""]
 splitWith (=='a') []        == []

Like splitWith, except that sequences of adjacent separators are treated as a single separator. eg.

 tokens (=='a') "aabbaca" == ["bb","c"]

The group function takes a ByteString and returns a list of ByteStrings such that the concatenation of the result is equal to the argument. Moreover, each sublist in the result contains only equal elements. For example,

 group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]

It is a special case of groupBy, which allows the programmer to supply their own equality test. It is about 40% faster than groupBy (==)

O(n) The elemIndexLast function returns the last index of the element in the given ByteString which is equal to the query element, or Nothing if there is no such element. The following holds:

 elemIndexLast c xs == 
 (-) (length xs - 1) `fmap` elemIndex c (reverse xs)

count returns the number of times its argument appears in the ByteString

 count = length . elemIndices

But more efficiently than using length on the intermediate list.

O(n) A first order equivalent of filter . (==), for the common case of filtering a single byte. It is more efficient to use filterByte in this case.

 filterByte == filter . (==)

filterByte is around 10x faster, and uses much less space, than its filter equivalent

O(n) A first order equivalent of filter . (/=), for the common case of filtering a single byte out of a list. It is more efficient to use filterNotByte in this case.

 filterNotByte == filter . (/=)

filterNotByte is around 2x faster than its filter equivalent.

O(n) The find function takes a predicate and a ByteString, and returns the first element in matching the predicate, or Nothing if there is no such element.

 find f p = case findIndex f p of Just n -> Just (p ! n) ; _ -> Nothing

O(n) The isSuffixOf function takes two ByteStrings and returns True iff the first is a suffix of the second.

The following holds:

 isSuffixOf x y == reverse x `isPrefixOf` reverse y

However, the real implemenation uses memcmp to compare the end of the string only, with no reverse required..

The sortBy function is the non-overloaded version of sort.

Try some linear sorts: radix, counting Or mergesort.

sortBy :: (Word8 -> Word8 -> Ordering) -> ByteString -> ByteString sortBy f ps = undefined

A variety of head for non-empty ByteStrings. unsafeHead omits the check for the empty case, so there is an obligation on the programmer to provide a proof that the ByteString is non-empty.

Given the maximum size needed and a function to make the contents of a ByteString, generate makes the ByteString. The generating function is required to return the actual final size (<= the maximum size), and the resulting byte array is realloced to this size. The string is padded at the end with a null byte.

generate is the main mechanism for creating custom, efficient ByteString functions, using Haskell or C functions to fill the space.

O(n) Pack a null-terminated sequence of bytes, pointed to by an Addr# (an arbitrary machine address assumed to point outside the garbage-collected heap) into a ByteString. A much faster way to create an Addr# is with an unboxed string literal, than to pack a boxed string. A unboxed string literal is compiled to a static char [] by GHC. Establishing the length of the string requires a call to strlen(3), so the Addr# must point to a null-terminated buffer (as is the case with string# literals in GHC). Use unsafePackAddress if you know the length of the string statically.

An example:

 literalFS = packAddress "literal"#

Read entire handle contents into a ByteString.

As with hGet, the string representation in the file is assumed to be ISO-8859-1.

Special forms of loop arguments

• These are common special cases for the three function arguments of gen and loop; we give them special names to make it easier to trigger RULES applying in the special cases represented by these arguments. The INLINE [1] makes sure that these functions are only inlined in the last two simplifier phases.
• In the case where the accumulator is not needed, it is better to always explicitly return a value `()', rather than just copy the input to the output, as the former gives GHC better local information.

Element function expressing a mapping only