Copyright | (c) Duncan Coutts 2012-2013 Julian Ospald 2022 |
---|---|
License | BSD-style |
Maintainer | hasufell@posteo.de |
Stability | stable |
Portability | ghc only |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
A compact representation suitable for storing short byte strings in memory.
In typical use cases it can be imported alongside Data.ByteString, e.g.
import qualified Data.ByteString as B import qualified Data.ByteString.Short as B (ShortByteString, toShort, fromShort)
Other ShortByteString
operations clash with Data.ByteString or Prelude
functions however, so they should be imported qualified
with a different
alias e.g.
import qualified Data.ByteString.Short as B.Short
Synopsis
- data ShortByteString = SBS ByteArray#
- empty :: ShortByteString
- singleton :: Word8 -> ShortByteString
- pack :: [Word8] -> ShortByteString
- unpack :: ShortByteString -> [Word8]
- fromShort :: ShortByteString -> ByteString
- toShort :: ByteString -> ShortByteString
- snoc :: ShortByteString -> Word8 -> ShortByteString
- cons :: Word8 -> ShortByteString -> ShortByteString
- append :: ShortByteString -> ShortByteString -> ShortByteString
- last :: HasCallStack => ShortByteString -> Word8
- tail :: HasCallStack => ShortByteString -> ShortByteString
- uncons :: ShortByteString -> Maybe (Word8, ShortByteString)
- uncons2 :: ShortByteString -> Maybe (Word8, Word8, ShortByteString)
- head :: HasCallStack => ShortByteString -> Word8
- init :: HasCallStack => ShortByteString -> ShortByteString
- unsnoc :: ShortByteString -> Maybe (ShortByteString, Word8)
- null :: ShortByteString -> Bool
- length :: ShortByteString -> Int
- map :: (Word8 -> Word8) -> ShortByteString -> ShortByteString
- reverse :: ShortByteString -> ShortByteString
- intercalate :: ShortByteString -> [ShortByteString] -> ShortByteString
- foldl :: (a -> Word8 -> a) -> a -> ShortByteString -> a
- foldl' :: (a -> Word8 -> a) -> a -> ShortByteString -> a
- foldl1 :: HasCallStack => (Word8 -> Word8 -> Word8) -> ShortByteString -> Word8
- foldl1' :: HasCallStack => (Word8 -> Word8 -> Word8) -> ShortByteString -> Word8
- foldr :: (Word8 -> a -> a) -> a -> ShortByteString -> a
- foldr' :: (Word8 -> a -> a) -> a -> ShortByteString -> a
- foldr1 :: HasCallStack => (Word8 -> Word8 -> Word8) -> ShortByteString -> Word8
- foldr1' :: HasCallStack => (Word8 -> Word8 -> Word8) -> ShortByteString -> Word8
- all :: (Word8 -> Bool) -> ShortByteString -> Bool
- any :: (Word8 -> Bool) -> ShortByteString -> Bool
- concat :: [ShortByteString] -> ShortByteString
- replicate :: Int -> Word8 -> ShortByteString
- unfoldr :: (a -> Maybe (Word8, a)) -> a -> ShortByteString
- unfoldrN :: Int -> (a -> Maybe (Word8, a)) -> a -> (ShortByteString, Maybe a)
- take :: Int -> ShortByteString -> ShortByteString
- takeEnd :: Int -> ShortByteString -> ShortByteString
- takeWhileEnd :: (Word8 -> Bool) -> ShortByteString -> ShortByteString
- takeWhile :: (Word8 -> Bool) -> ShortByteString -> ShortByteString
- drop :: Int -> ShortByteString -> ShortByteString
- dropEnd :: Int -> ShortByteString -> ShortByteString
- dropWhile :: (Word8 -> Bool) -> ShortByteString -> ShortByteString
- dropWhileEnd :: (Word8 -> Bool) -> ShortByteString -> ShortByteString
- breakEnd :: (Word8 -> Bool) -> ShortByteString -> (ShortByteString, ShortByteString)
- break :: (Word8 -> Bool) -> ShortByteString -> (ShortByteString, ShortByteString)
- span :: (Word8 -> Bool) -> ShortByteString -> (ShortByteString, ShortByteString)
- spanEnd :: (Word8 -> Bool) -> ShortByteString -> (ShortByteString, ShortByteString)
- splitAt :: Int -> ShortByteString -> (ShortByteString, ShortByteString)
- split :: Word8 -> ShortByteString -> [ShortByteString]
- splitWith :: (Word8 -> Bool) -> ShortByteString -> [ShortByteString]
- stripSuffix :: ShortByteString -> ShortByteString -> Maybe ShortByteString
- stripPrefix :: ShortByteString -> ShortByteString -> Maybe ShortByteString
- isInfixOf :: ShortByteString -> ShortByteString -> Bool
- isPrefixOf :: ShortByteString -> ShortByteString -> Bool
- isSuffixOf :: ShortByteString -> ShortByteString -> Bool
- breakSubstring :: ShortByteString -> ShortByteString -> (ShortByteString, ShortByteString)
- elem :: Word8 -> ShortByteString -> Bool
- find :: (Word8 -> Bool) -> ShortByteString -> Maybe Word8
- filter :: (Word8 -> Bool) -> ShortByteString -> ShortByteString
- partition :: (Word8 -> Bool) -> ShortByteString -> (ShortByteString, ShortByteString)
- index :: HasCallStack => ShortByteString -> Int -> Word8
- indexMaybe :: ShortByteString -> Int -> Maybe Word8
- (!?) :: ShortByteString -> Int -> Maybe Word8
- elemIndex :: Word8 -> ShortByteString -> Maybe Int
- elemIndices :: Word8 -> ShortByteString -> [Int]
- count :: Word8 -> ShortByteString -> Int
- findIndex :: (Word8 -> Bool) -> ShortByteString -> Maybe Int
- findIndices :: (Word8 -> Bool) -> ShortByteString -> [Int]
- packCString :: CString -> IO ShortByteString
- packCStringLen :: CStringLen -> IO ShortByteString
- useAsCString :: ShortByteString -> (CString -> IO a) -> IO a
- useAsCStringLen :: ShortByteString -> (CStringLen -> IO a) -> IO a
The ShortByteString
type
data ShortByteString #
A compact representation of a Word8
vector.
It has a lower memory overhead than a ByteString
and does not
contribute to heap fragmentation. It can be converted to or from a
ByteString
(at the cost of copying the string data). It supports very few
other operations.
Instances
Memory overhead
With GHC, the memory overheads are as follows, expressed in words and in bytes (words are 4 and 8 bytes on 32 or 64bit machines respectively).
ByteString
unshared: 8 words; 32 or 64 bytes.ByteString
shared substring: 4 words; 16 or 32 bytes.ShortByteString
: 4 words; 16 or 32 bytes.
For the string data itself, both ShortByteString
and ByteString
use
one byte per element, rounded up to the nearest word. For example,
including the overheads, a length 10 ShortByteString
would take
16 + 12 = 28
bytes on a 32bit platform and 32 + 16 = 48
bytes on a
64bit platform.
These overheads can all be reduced by 1 word (4 or 8 bytes) when the
ShortByteString
or ByteString
is unpacked into another constructor.
For example:
data ThingId = ThingId {-# UNPACK #-} !Int {-# UNPACK #-} !ShortByteString
This will take 1 + 1 + 3
words (the ThingId
constructor +
unpacked Int
+ unpacked ShortByteString
), plus the words for the
string data.
Heap fragmentation
With GHC, the ByteString
representation uses pinned memory,
meaning it cannot be moved by the GC. This is usually the right thing to
do for larger strings, but for small strings using pinned memory can
lead to heap fragmentation which wastes space. The ShortByteString
type (and the Text
type from the text
package) use unpinned memory
so they do not contribute to heap fragmentation. In addition, with GHC,
small unpinned strings are allocated in the same way as normal heap
allocations, rather than in a separate pinned area.
Introducing and eliminating ShortByteString
s
O(1). The empty ShortByteString
.
singleton :: Word8 -> ShortByteString #
O(1) Convert a Word8
into a ShortByteString
Since: bytestring-0.11.3.0
pack :: [Word8] -> ShortByteString #
O(n). Convert a list into a ShortByteString
unpack :: ShortByteString -> [Word8] #
O(n). Convert a ShortByteString
into a list.
fromShort :: ShortByteString -> ByteString #
O(n). Convert a ShortByteString
into a ByteString
.
toShort :: ByteString -> ShortByteString #
O(n). Convert a ByteString
into a ShortByteString
.
This makes a copy, so does not retain the input string.
Basic interface
snoc :: ShortByteString -> Word8 -> ShortByteString infixl 5 #
O(n) Append a byte to the end of a ShortByteString
Note: copies the entire byte array
Since: bytestring-0.11.3.0
cons :: Word8 -> ShortByteString -> ShortByteString infixr 5 #
O(n) cons
is analogous to (:) for lists.
Note: copies the entire byte array
Since: bytestring-0.11.3.0
append :: ShortByteString -> ShortByteString -> ShortByteString #
last :: HasCallStack => ShortByteString -> Word8 #
O(1) Extract the last element of a ShortByteString, which must be finite and non-empty. An exception will be thrown in the case of an empty ShortByteString.
This is a partial function, consider using unsnoc
instead.
Since: bytestring-0.11.3.0
tail :: HasCallStack => ShortByteString -> ShortByteString #
O(n) Extract the elements after the head of a ShortByteString, which must be non-empty. An exception will be thrown in the case of an empty ShortByteString.
This is a partial function, consider using uncons
instead.
Note: copies the entire byte array
Since: bytestring-0.11.3.0
uncons :: ShortByteString -> Maybe (Word8, ShortByteString) #
uncons2 :: ShortByteString -> Maybe (Word8, Word8, ShortByteString) Source #
head :: HasCallStack => ShortByteString -> Word8 #
O(1) Extract the first element of a ShortByteString, which must be non-empty. An exception will be thrown in the case of an empty ShortByteString.
This is a partial function, consider using uncons
instead.
Since: bytestring-0.11.3.0
init :: HasCallStack => ShortByteString -> ShortByteString #
O(n) Return all the elements of a ShortByteString
except the last one.
An exception will be thrown in the case of an empty ShortByteString.
This is a partial function, consider using unsnoc
instead.
Note: copies the entire byte array
Since: bytestring-0.11.3.0
unsnoc :: ShortByteString -> Maybe (ShortByteString, Word8) #
null :: ShortByteString -> Bool #
O(1) Test whether a ShortByteString
is empty.
length :: ShortByteString -> Int #
O(1) The length of a ShortByteString
.
Transforming ShortByteStrings
map :: (Word8 -> Word8) -> ShortByteString -> ShortByteString #
O(n) map
f xs
is the ShortByteString obtained by applying f
to each
element of xs
.
Since: bytestring-0.11.3.0
reverse :: ShortByteString -> ShortByteString #
O(n) reverse
xs
efficiently returns the elements of xs
in reverse order.
Since: bytestring-0.11.3.0
intercalate :: ShortByteString -> [ShortByteString] -> ShortByteString #
O(n) The intercalate
function takes a ShortByteString
and a list of
ShortByteString
s and concatenates the list after interspersing the first
argument between each element of the list.
Since: bytestring-0.11.3.0
Reducing ShortByteString
s (folds)
foldl :: (a -> Word8 -> a) -> a -> ShortByteString -> a #
foldl
, applied to a binary operator, a starting value (typically
the left-identity of the operator), and a ShortByteString, reduces the
ShortByteString using the binary operator, from left to right.
Since: bytestring-0.11.3.0
foldl' :: (a -> Word8 -> a) -> a -> ShortByteString -> a #
foldl1 :: HasCallStack => (Word8 -> Word8 -> Word8) -> ShortByteString -> Word8 #
foldl1
is a variant of foldl
that has no starting value
argument, and thus must be applied to non-empty ShortByteString
s.
An exception will be thrown in the case of an empty ShortByteString.
Since: bytestring-0.11.3.0
foldl1' :: HasCallStack => (Word8 -> Word8 -> Word8) -> ShortByteString -> Word8 #
foldr :: (Word8 -> a -> a) -> a -> ShortByteString -> a #
foldr
, applied to a binary operator, a starting value
(typically the right-identity of the operator), and a ShortByteString,
reduces the ShortByteString using the binary operator, from right to left.
Since: bytestring-0.11.3.0
foldr' :: (Word8 -> a -> a) -> a -> ShortByteString -> a #
foldr1 :: HasCallStack => (Word8 -> Word8 -> Word8) -> ShortByteString -> Word8 #
foldr1
is a variant of foldr
that has no starting value argument,
and thus must be applied to non-empty ShortByteString
s
An exception will be thrown in the case of an empty ShortByteString.
Since: bytestring-0.11.3.0
foldr1' :: HasCallStack => (Word8 -> Word8 -> Word8) -> ShortByteString -> Word8 #
Special folds
all :: (Word8 -> Bool) -> ShortByteString -> Bool #
O(n) Applied to a predicate and a ShortByteString
, all
determines
if all elements of the ShortByteString
satisfy the predicate.
Since: bytestring-0.11.3.0
any :: (Word8 -> Bool) -> ShortByteString -> Bool #
O(n) Applied to a predicate and a ShortByteString
, any
determines if
any element of the ShortByteString
satisfies the predicate.
Since: bytestring-0.11.3.0
concat :: [ShortByteString] -> ShortByteString #
Generating and unfolding ByteStrings
replicate :: Int -> Word8 -> ShortByteString #
O(n) replicate
n x
is a ShortByteString of length n
with x
the value of every element. The following holds:
replicate w c = unfoldr w (\u -> Just (u,u)) c
Since: bytestring-0.11.3.0
unfoldr :: (a -> Maybe (Word8, a)) -> a -> ShortByteString #
O(n), where n is the length of the result. The unfoldr
function is analogous to the List 'unfoldr'. unfoldr
builds a
ShortByteString from a seed value. The function takes the element and
returns Nothing
if it is done producing the ShortByteString or returns
Just
(a,b)
, in which case, a
is the next byte in the string,
and b
is the seed value for further production.
This function is not efficient/safe. It will build a list of [Word8]
and run the generator until it returns Nothing
, otherwise recurse infinitely,
then finally create a ShortByteString
.
If you know the maximum length, consider using unfoldrN
.
Examples:
unfoldr (\x -> if x <= 5 then Just (x, x + 1) else Nothing) 0 == pack [0, 1, 2, 3, 4, 5]
Since: bytestring-0.11.3.0
unfoldrN :: Int -> (a -> Maybe (Word8, a)) -> a -> (ShortByteString, Maybe a) #
O(n) Like unfoldr
, unfoldrN
builds a ShortByteString from a seed
value. However, the length of the result is limited by the first
argument to unfoldrN
. This function is more efficient than unfoldr
when the maximum length of the result is known.
The following equation relates unfoldrN
and unfoldr
:
fst (unfoldrN n f s) == take n (unfoldr f s)
Since: bytestring-0.11.3.0
Substrings
Breaking strings
take :: Int -> ShortByteString -> ShortByteString #
takeEnd :: Int -> ShortByteString -> ShortByteString #
takeWhileEnd :: (Word8 -> Bool) -> ShortByteString -> ShortByteString #
Returns the longest (possibly empty) suffix of elements satisfying the predicate.
is equivalent to takeWhileEnd
p
.reverse
. takeWhile
p . reverse
Since: bytestring-0.11.3.0
takeWhile :: (Word8 -> Bool) -> ShortByteString -> ShortByteString #
Similar to takeWhile
,
returns the longest (possibly empty) prefix of elements
satisfying the predicate.
Since: bytestring-0.11.3.0
drop :: Int -> ShortByteString -> ShortByteString #
dropEnd :: Int -> ShortByteString -> ShortByteString #
dropWhile :: (Word8 -> Bool) -> ShortByteString -> ShortByteString #
Similar to dropWhile
,
drops the longest (possibly empty) prefix of elements
satisfying the predicate and returns the remainder.
Note: copies the entire byte array
Since: bytestring-0.11.3.0
dropWhileEnd :: (Word8 -> Bool) -> ShortByteString -> ShortByteString #
Similar to dropWhileEnd
,
drops the longest (possibly empty) suffix of elements
satisfying the predicate and returns the remainder.
is equivalent to dropWhileEnd
p
.reverse
. dropWhile
p . reverse
Since: bytestring-0.11.3.0
breakEnd :: (Word8 -> Bool) -> ShortByteString -> (ShortByteString, ShortByteString) #
Returns the longest (possibly empty) suffix of elements which do not satisfy the predicate and the remainder of the string.
breakEnd
p
is equivalent to
and to spanEnd
(not . p)(
.takeWhileEnd
(not . p) &&& dropWhileEnd
(not . p))
Since: bytestring-0.11.3.0
break :: (Word8 -> Bool) -> ShortByteString -> (ShortByteString, ShortByteString) #
span :: (Word8 -> Bool) -> ShortByteString -> (ShortByteString, ShortByteString) #
spanEnd :: (Word8 -> Bool) -> ShortByteString -> (ShortByteString, ShortByteString) #
Returns the longest (possibly empty) suffix of elements satisfying the predicate and the remainder of the string.
spanEnd
p
is equivalent to
and to breakEnd
(not . p)(
.takeWhileEnd
p &&& dropWhileEnd
p)
We have
spanEnd (not . isSpace) "x y z" == ("x y ", "z")
and
spanEnd (not . isSpace) sbs == let (x, y) = span (not . isSpace) (reverse sbs) in (reverse y, reverse x)
Since: bytestring-0.11.3.0
splitAt :: Int -> ShortByteString -> (ShortByteString, ShortByteString) #
split :: Word8 -> ShortByteString -> [ShortByteString] #
O(n) Break a ShortByteString
into pieces separated by the byte
argument, consuming the delimiter. I.e.
split 10 "a\nb\nd\ne" == ["a","b","d","e"] -- fromEnum '\n' == 10 split 97 "aXaXaXa" == ["","X","X","X",""] -- fromEnum 'a' == 97 split 120 "x" == ["",""] -- fromEnum 'x' == 120 split undefined "" == [] -- and not [""]
and
intercalate [c] . split c == id split == splitWith . (==)
Note: copies the substrings
Since: bytestring-0.11.3.0
splitWith :: (Word8 -> Bool) -> ShortByteString -> [ShortByteString] #
O(n) Splits a ShortByteString
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 (==97) "aabbaca" == ["","","bb","c",""] -- fromEnum 'a' == 97 splitWith undefined "" == [] -- and not [""]
Since: bytestring-0.11.3.0
stripSuffix :: ShortByteString -> ShortByteString -> Maybe ShortByteString #
O(n) The stripSuffix
function takes two ShortByteStrings and returns Just
the remainder of the second iff the first is its suffix, and otherwise
Nothing
.
Since: bytestring-0.11.3.0
stripPrefix :: ShortByteString -> ShortByteString -> Maybe ShortByteString #
O(n) The stripPrefix
function takes two ShortByteStrings and returns Just
the remainder of the second iff the first is its prefix, and otherwise
Nothing
.
Since: bytestring-0.11.3.0
Predicates
isInfixOf :: ShortByteString -> ShortByteString -> Bool #
Check whether one string is a substring of another.
Since: bytestring-0.11.3.0
isPrefixOf :: ShortByteString -> ShortByteString -> Bool #
O(n) The isPrefixOf
function takes two ShortByteStrings and returns True
Since: bytestring-0.11.3.0
isSuffixOf :: ShortByteString -> ShortByteString -> Bool #
O(n) The isSuffixOf
function takes two ShortByteStrings and returns True
iff the first is a suffix of the second.
The following holds:
isSuffixOf x y == reverse x `isPrefixOf` reverse y
Since: bytestring-0.11.3.0
Search for arbitrary substrings
:: ShortByteString | String to search for |
-> ShortByteString | String to search in |
-> (ShortByteString, ShortByteString) | Head and tail of string broken at substring |
Break a string on a substring, returning a pair of the part of the string prior to the match, and the rest of the string.
The following relationships hold:
break (== c) l == breakSubstring (singleton c) l
For example, to tokenise a string, dropping delimiters:
tokenise x y = h : if null t then [] else tokenise x (drop (length x) t) where (h,t) = breakSubstring x y
To skip to the first occurrence of a string:
snd (breakSubstring x y)
To take the parts of a string before a delimiter:
fst (breakSubstring x y)
Note that calling `breakSubstring x` does some preprocessing work, so you should avoid unnecessarily duplicating breakSubstring calls with the same pattern.
Since: bytestring-0.11.3.0
Searching ShortByteStrings
Searching by equality
elem :: Word8 -> ShortByteString -> Bool #
O(n) elem
is the ShortByteString
membership predicate.
Since: bytestring-0.11.3.0
Searching with a predicate
filter :: (Word8 -> Bool) -> ShortByteString -> ShortByteString #
O(n) filter
, applied to a predicate and a ShortByteString,
returns a ShortByteString containing those characters that satisfy the
predicate.
Since: bytestring-0.11.3.0
partition :: (Word8 -> Bool) -> ShortByteString -> (ShortByteString, ShortByteString) #
O(n) The partition
function takes a predicate a ShortByteString and returns
the pair of ShortByteStrings with elements which do and do not satisfy the
predicate, respectively; i.e.,
partition p bs == (filter p sbs, filter (not . p) sbs)
Since: bytestring-0.11.3.0
Indexing ShortByteStrings
index :: HasCallStack => ShortByteString -> Int -> Word8 #
O(1) ShortByteString
index (subscript) operator, starting from 0.
This is a partial function, consider using indexMaybe
instead.
indexMaybe :: ShortByteString -> Int -> Maybe Word8 #
O(1) ShortByteString
index, starting from 0, that returns Just
if:
0 <= n < length bs
Since: bytestring-0.11.0.0
(!?) :: ShortByteString -> Int -> Maybe Word8 #
O(1) ShortByteString
index, starting from 0, that returns Just
if:
0 <= n < length bs
Since: bytestring-0.11.0.0
elemIndex :: Word8 -> ShortByteString -> Maybe Int #
O(n) The elemIndex
function returns the index of the first
element in the given ShortByteString
which is equal to the query
element, or Nothing
if there is no such element.
Since: bytestring-0.11.3.0
elemIndices :: Word8 -> ShortByteString -> [Int] #
O(n) The elemIndices
function extends elemIndex
, by returning
the indices of all elements equal to the query element, in ascending order.
Since: bytestring-0.11.3.0
count :: Word8 -> ShortByteString -> Int #
count returns the number of times its argument appears in the ShortByteString
Since: bytestring-0.11.3.0
findIndex :: (Word8 -> Bool) -> ShortByteString -> Maybe Int #
O(n) The findIndex
function takes a predicate and a ShortByteString
and
returns the index of the first element in the ShortByteString
satisfying the predicate.
Since: bytestring-0.11.3.0
findIndices :: (Word8 -> Bool) -> ShortByteString -> [Int] #
O(n) The findIndices
function extends findIndex
, by returning the
indices of all elements satisfying the predicate, in ascending order.
Since: bytestring-0.11.3.0
Low level conversions
Packing CString
s and pointers
packCString :: CString -> IO ShortByteString #
O(n). Construct a new ShortByteString
from a CString
. The
resulting ShortByteString
is an immutable copy of the original
CString
, and is managed on the Haskell heap. The original
CString
must be null terminated.
Since: bytestring-0.10.10.0
packCStringLen :: CStringLen -> IO ShortByteString #
O(n). Construct a new ShortByteString
from a CStringLen
. The
resulting ShortByteString
is an immutable copy of the original CStringLen
.
The ShortByteString
is a normal Haskell value and will be managed on the
Haskell heap.
Since: bytestring-0.10.10.0
Using ShortByteStrings as CString
s
useAsCString :: ShortByteString -> (CString -> IO a) -> IO a #
O(n) construction. Use a ShortByteString
with a function requiring a
null-terminated CString
. The CString
is a copy and will be freed
automatically; it must not be stored or used after the
subcomputation finishes.
Since: bytestring-0.10.10.0
useAsCStringLen :: ShortByteString -> (CStringLen -> IO a) -> IO a #
O(n) construction. Use a ShortByteString
with a function requiring a CStringLen
.
As for useAsCString
this function makes a copy of the original ShortByteString
.
It must not be stored or used after the subcomputation finishes.
Since: bytestring-0.10.10.0