Главная » Haskell » Модуль ByteString

0

содержит определения программных сущностей для работы с байтовыми векторами, основанными на использовании  массивов элементов типа Word8. Эти определения являются достаточно эффективными с точки зрения используемого для вычислений времени и занимаемой памяти. Кроме того, байтовые массивы являются строгими, для них существует указатель для использования во внешних программных модулях и библиотеках (написанных на других языках программирования).

В рассматриваемом модуле используется очень много функций, которые имеют те же наименования, что и в стандартном модуле Prelude.  Поэтому импортирование модуля должно производиться с квалификацией имени. Например:

import qualified  Data.ByteString as B

необходимо использовать вместо модуля  PackedString,  который  объявлен устаревшим и постепенно будет  выводиться из пакета стандартных модулей языка Haskell.

Основной и единственный алгебраический тип данных, описанный в этом модуле,  — ByteString.

Тип: ByteString

Описание: эффективная реализация строгого вектора, состоящего  из  значений типа Word8. Этот тип данных содержит только восьмибитовые значения. Определение:

Тип определён в виде примитива.

Для типа ByteString реализованы экземпляры следующих классов: Eq, Ord,

Data, Monoid,  Read, Show, Typeable.

Функция: empty

Описание: возвращает пустую восьмибитовую строку. Эффективность — O(1).

Определение:

empty :: ByteString

Функция определена в виде примитива.

Функция: singleton

Описание: конвертирует заданное значение типа Word8 в восьмибитовую строку с эффективностью O(1).

Определение:

singleton :: Word8 ->  ByteString

singleton c  = unsafeCreate  1 $ \p ->  poke p c

Функция: pack

Описание: конвертирует  список значений типа Word8 в восьмибитовую  строку. Работает с эффективностью O(n), где n — количество элементов в исходном списке. Для программ с большим количеством строковых литералов использование этой функции может стать неэффективным.  Для компилятора  GHC в данном случае рекомендуется использование функции packAddress.

Определение:

pack :: [Word8]  ->  ByteString

pack str = unsafeCreate  (P.length str)  $ \p ->  go p str where

go _ []     =  return ()

go p (x:xs) = poke p x  >> go (p  ‘plusPtr‘ 1)  xs

Функция: unpack

Описание: функция, обратная к функции pack. Конвертирует заданную восьмибитовую строку в список значений типа Word8. Преобразование совершает с эффективностью  O(n), где n — количество символов в исходной строке. Определение:

unpack :: ByteString ->  [Word8]

unpack (PS _

_ 0)  = []

unpack (PS ps s  l) = inlinePerformIO $ withForeignPtr ps  $ \p -> go (p  ‘plusPtr‘ s) (l 1)  []

where

go a b c  | a ‘seq‘ b ‘seq‘ c  ‘seq‘ False  = undefined

go p 0 acc  = peek p                  >>= \e ->  return (e  : acc)

go p n acc  = peekByteOff  p n >>= \e ->  go p (n  1)  (e  : acc)

Функция: cons

Описание: добавляет заданный символ типа Word8 в начало строки. Аналог конструктора (:) для списков, однако сложность исполнения — O(n).

Определение:

cons :: Word8 ->  ByteString  ->  ByteString

cons c  (PS x  s  l) = unsafeCreate  (l  +  1)  $ \p -> withForeignPtr  x  $ \f ->

do poke p c

memcpy  (p  ‘plusPtr‘ 1)  (f ‘plusPtr‘ s) (fromIntegral  l)

Функция: snoc

Описание: добавляет  заданный символ типа Word8 в конец  строки.  Функция по действию аналогична функции cons. Сложность — O(n), где n — длина строки.

Определение:

snoc :: ByteString ->  Word8  ->  ByteString

snoc (PS x  s  l) c  = unsafeCreate  (l+1) $ \p -> withForeignPtr  x  $ \f ->

do memcpy  p (f ‘plusPtr‘ s)  (fromIntegral l) poke (p  ‘plusPtr‘ l) c

Функция: append

Описание: конкатенирует две восьмибитовые строки. Сложность — O(n), где n — сумма длин двух заданных строк.

Определение:

append :: ByteString ->  ByteString  ->  ByteString append xs  ys  | null xs      =  ys

|  null  ys      =  xs

| otherwise = concat  [xs, ys]

Функция: head

Описание: возвращает первый символ заданной восьмибитовой строки.  Сложность — O(1).

Определение:

head :: ByteString ->  Word8

head (PS x  s  l) | l <= 0       = errorEmptyList  "head"

| otherwise =  inlinePerformIO  $ withForeignPtr  x  $

\p ->  peekByteOff  p  s

Функция: last

Описание: возвращает последний символ заданной восьмибитовой строки. Сложность — O(1).

Определение:

last :: ByteString ->  Word8

last ps@(PS  x  s  l) | null ps     = errorEmptyList "last"

| otherwise =  inlinePerformIO  $ withForeignPtr  x  $

\p ->  peekByteOff  p (s + l 1)

Функция: tail

Описание: возвращает  заданную восьмибитовую строку  без первого  символа.

Сложность — O(1).

Определение:

tail :: ByteString ->  ByteString

tail (PS p s  l) | l <= 0       = errorEmptyList "tail"

| otherwise = PS  p (s + 1)  (l 1)

Функция: last

Описание: возвращает заданную восьмибитовую строку без последнего символа.

Сложность — O(1).

Определение:

last :: ByteString ->  Word8

last ps@(PS  x  s  l) | null ps     = errorEmptyList "last"

| otherwise =  inlinePerformIO  $ withForeignPtr  x  $

\p ->  peekByteOff  p (s + l 1)

Функция: null

Описание: возвращает значение True, если заданная восьмибитовая строка пуста.

Сложность — O(1).

Определение:

null ::  ByteString ->  Bool

null (PS _ _ l) = assert (l >=  0)  $ l <= 0

Функция: length

Описание: возвращает длину заданной восьмибитовой строки.

Определение:

length ::  ByteString ->  Int

length (PS _ _ l) = assert  (l >= 0)  $ l

Функция: map

Описание: применяет заданную функцию к каждому символу исходной восьмибитовой строки. Сложность — O(n), где n — длина строки.

Определение:

map  :: (Word8 ->  Word8) ->  ByteString ->  ByteString map  f = loopArr . loopMap f

Функция: reverse

Описание: обращает  заданную восьмибитовую строку  со  сложностью работы

O(n), где n — длина строки.

Определение:

reverse :: ByteString ->  ByteString reverse (PS x  s  l) = unsafeCreate  l $

\p ->  withForeignPtr x  $

\f ->  c_reverse p (f ‘plusPtr‘  s) (fromIntegral l)

Функция: intersperse

Описание: возвращает восьмибитовую строку, между каждыми символами которой вставляется заданный первым аргументом символ типа Word8. Сложность — O(n), где n — длина строки.

Определение:

intersperse :: Word8 ->  ByteString ->  ByteString intersperse c  ps@(PS  x  s  l) |  length ps < 2   = ps

| otherwise          = unsafeCreate  (2  * l 1)  $

\p ->  withForeignPtr x  $

\f ->  c_intersperse p (f  ‘plusPtr‘  s) (fromIntegral  l) c

Функция: transpose

Описание: транспонирует матрицу, составленную из восьмибитовых строк.

Определение:

transpose :: [ByteString]  ->  [ByteString]

transpose ps = P.map pack (List.transpose (P.map  unpack ps))

Функция: foldl

Описание: сворачивает заданную восьмибитовую строку при помощи заданного бинарного оператора и начального значения. Функция работает со строкой слева направо.

Определение:

foldl :: (a  ->  Word8 ->  a)  ->  a ->  ByteString ->  a foldl f z  = loopAcc  .  loopUp (foldEFL f) z

Функция: foldl’

Описание: вариант функции foldl, являющийся строгим относительно аргумента, выполняющего роль аккумулятора. Для восьмибитовых строк функция foldl также является строгой относительно  аккумулятора, поэтому данная функция создана исключительно  ради совместимости.

Определение:

foldl’ :: (a  ->  Word8 ->  a)  ->  a ->  ByteString ->  a foldl’ = foldl

Функция: foldl1

Описание: вариант функции foldl, берущий в качестве начального значения первый символ восьмибитовой строки.

Определение:

foldl1 :: (Word8 ->  Word8 ->  Word8) ->  ByteString ->  Word8 foldl1 f ps | null ps     =  errorEmptyList "foldl1"

| otherwise = foldl f (unsafeHead  ps)  (unsafeTail ps)

Функция: foldl1’

Описание: вариант функции foldl1,  являющийся строгим  относительно аргумента, выполняющего роль аккумулятора.

Определение:

foldl1’ :: (Word8 ->  Word8 ->  Word8) ->  ByteString ->  Word8 foldl1’ f ps | null ps     =  errorEmptyList "foldl1’"

| otherwise = foldl’ f (unsafeHead  ps)  (unsafeTail ps)

Функция: foldr

Описание: сворачивает заданную восьмибитовую строку при  помощи  заданного бинарного оператора и начального значения.  Функция  работает со строкой справа налево.

Определение:

foldr :: (Word8 ->  a ->  a)  ->  a ->  ByteString ->  a foldr k  z  = loopAcc  .  loopDown (foldEFL (flip k)) z

Функция: foldr’

Описание: вариант функции foldr, являющийся строгим относительно аргумента, выполняющего роль аккумулятора.

Определение:

foldr’ :: (Word8 ->  a ->  a)  ->  a ->  ByteString ->  a foldr’ k  v  (PS x  s  l) =  inlinePerformIO $

withForeignPtr x  $

\ptr ->  go v  (ptr ‘plusPtr‘ (s + l 1)) (ptr  ‘plusPtr‘ (s 1))

where

go a b c  | a ‘seq‘ b ‘seq‘ c  ‘seq‘ False  =  undefined go z  p q | p == q       = return  z

| otherwise = do c  < peek p

go (c ‘k‘  z) (p  ‘plusPtr‘ (-1)) q

Функция: foldr1

Описание: вариант функции foldr, берущий в качестве начального значения первый символ восьмибитовой строки.

Определение:

foldr1 :: (Word8 ->  Word8 ->  Word8) ->  ByteString  ->  Word8 foldr1 f ps | null ps     = errorEmptyList  "foldr1"

| otherwise = foldr f (last ps)  (init ps)

Функция: foldr1’

Описание: вариант функции foldr1,  являющийся строгим  относительно  аргумента, выполняющего роль аккумулятора.

Определение:

foldr1’ :: (Word8 ->  Word8 ->  Word8) ->  ByteString  ->  Word8 foldr1’ f ps | null ps     = errorEmptyList  "foldr1"

| otherwise = foldr’ f (last ps)  (init ps)

Функция: concat

Описание: конкатенирует  строки  из заданного списка восьмибитовых  строк.

Сложность — O(n), где n — сумма длин всех строк в списке.

Определение:

concat  :: [ByteString]  ->  ByteString concat  []     =  empty

concat  [ps]    = ps

concat  xs         = unsafeCreate  len  $ \ptr ->  go  xs  ptr where

len  = P.sum . P.map length $ xs

go a b | a ‘seq‘ b ‘seq‘ False  =  undefined go []            _     =  return ()

go (PS p s  l:ps) ptr = do withForeignPtr p $ \fp ->  memcpy  ptr (fp  ‘plusPtr‘  s) (fromIntegral  l)

go ps (ptr  ‘plusPtr‘ l)

Функция: concatMap

Описание: применяет функцию  к каждому символу заданной  восьмибитовой строки, после чего сращивает результаты применения в одну строку.

Определение:

concatMap :: (Word8 ->  ByteString) ->  ByteString ->  ByteString concatMap f = concat  . foldr ((:) . f)  []

Функция: any

Описание: возвращает значение True, если хотя бы один символ восьмибитовой строки удовлетворяет заданному предикату. Сложность — O(n), где n — длина заданной  строки.

Определение:

any :: (Word8 ->  Bool)   ->  ByteString ->  Bool any _ (PS _ _  0)  = False

any f (PS x  s  l) =  inlinePerformIO  $ withForeignPtr  x  $

\ptr ->  go (ptr ‘plusPtr‘ s) (ptr  ‘plusPtr‘ (s+l))

where

go a b | a ‘seq‘ b ‘seq‘ False  =  undefined go p q | p == q        =  return  False

| otherwise = do  c  < peek  p if  f  c

then  return  True

else  go (p  ‘plusPtr‘ 1)  q

Функция: all

Описание: возвращает значение True, если все символы  восьмибитовой строки удовлетворяют заданному предикату. Сложность — O(n), где n — длина заданной  строки.

Определение:

all :: (Word8 ->  Bool)   ->  ByteString ->  Bool all _ (PS _ _  0)  = True

all f (PS x  s  l) =  inlinePerformIO  $ withForeignPtr  x  $

\ptr ->  go (ptr ‘plusPtr‘ s) (ptr ‘plusPtr‘ (s+l))

where

go a b | a ‘seq‘ b ‘seq‘ False  = undefined

go p q | p == q         = return True   -end of list

| otherwise   = do c  < peek  p if  f  c

then  go (p  ‘plusPtr‘ 1)  q else  return  False

Функция: maximum

Описание: возвращает значение наибольшего (по коду) символа в заданной восьмибитовой строке. Сложность — O(n), где n — длина заданной строки. Определение:

maximum  :: ByteString ->  Word8

maximum  xs@(PS  x  s  l) | null xs     = errorEmptyList "maximum"

| otherwise =  inlinePerformIO  $ withForeignPtr  x  $

\p ->  c_maximum  (p  ‘plusPtr‘ s)  (fromIntegral  l)

Функция: minimum

Описание: возвращает значение наименьшего (по коду) символа в заданной восьмибитовой строке. Сложность — O(n), где n — длина заданной строки. Определение:

minimum  :: ByteString ->  Word8

minimum  xs@(PS x  s  l) | null xs     = errorEmptyList "minimum"

| otherwise =  inlinePerformIO  $ withForeignPtr  x  $

\p ->  c_minimum (p  ‘plusPtr‘ s)  (fromIntegral  l)

Функция: scanl

Описание: функция, аналогичная функции foldl, однако возвращающая список всех промежуточных значений. Последним значением в таком списке будет как раз значение функции foldl, которое она вернула бы на тех же входных аргументах.

Определение:

scanl   :: (Word8 ->  Word8 ->  Word8) ->  Word8 ->  ByteString ->  ByteString scanl   f z  ps = loopArr . loopUp (scanEFL f) z  $ (ps  ‘snoc‘ 0)

Функция: scanl1

Описание: вариант функции scanl,  работающий  без начального значения. В качестве начального значения принимается первый символ восьмибитовой строки. Определение:

scanl1  :: (Word8 ->  Word8 ->  Word8) ->  ByteString ->  ByteString scanl1  f ps | null ps     = empty

| otherwise = scanl   f (unsafeHead  ps)  (unsafeTail ps)

Функция: scanr

Описание: функция, аналогичная функции foldr, однако возвращающая список всех промежуточных значений. Последним значением в таком списке будет как раз значение функции foldr, которое она вернула бы на тех же входных аргументах.

Определение:

scanr  :: (Word8 ->  Word8 ->  Word8) ->  Word8 ->  ByteString ->  ByteString scanr  f z  ps = loopArr . loopDown (scanEFL (flip  f)) z  $ (0  ‘cons‘ ps)

Функция: scanr1

Описание: вариант функции scanr, работающий  без начального значения. В качестве начального значения принимается первый символ восьмибитовой строки. Определение:

scanr1  :: (Word8 ->  Word8 ->  Word8) ->  ByteString ->  ByteString scanr1  f ps | null ps     = empty

| otherwise = scanr  f (last ps)  (init ps)

Функция: mapAccumL

Описание: данная функция ведёт себя как комбинация  функций  map  и foldl. Она применяет заданную функцию к каждому символу восьмибитовой строки, собирает значения слева направо, после чего возвращает пару, состоящую из аккумулирующего параметра и результирующей строки.

Определение:

mapAccumL  :: (acc  ->  Word8 ->  (acc, Word8))  ->  acc  ->  ByteString ->  (acc,  ByteString) mapAccumL  f z  = unSP . loopUp (mapAccumEFL  f) z

Функция: mapAccumR

Описание: данная функция ведёт себя как комбинация  функций map  и  foldк. Она применяет заданную функцию к каждому символу восьмибитовой строки, собирает значения справа налево, после чего возвращает пару, состоящую из аккумулирующего параметра и результирующей строки.

Определение:

mapAccumR  :: (acc  ->  Word8 ->  (acc, Word8))  ->  acc  ->  ByteString ->  (acc,  ByteString) mapAccumR  f z  = unSP . loopDown (mapAccumEFL  f) z

Функция: mapIndexed

Описание: применяет заданную индексирующую функцию к восьмибитовой строке. Сложность — O(n), где n — длина заданной строки.

Определение:

mapIndexed :: (Int ->  Word8 ->  Word8) ->  ByteString ->  ByteString mapIndexed f = loopArr . loopUp (mapIndexEFL  f)  0

Функция: replicate

Описание: возвращает восьмибитовую строку, состоящую из заданного количества заданного символа. Сложность — O(n), где n — длина результата. Определение:

replicate :: Int ->  Word8 ->  ByteString replicate w  c  | w  <=  0       = empty

| otherwise = unsafeCreate  w  $

\ptr ->  memset  ptr c  (fromIntegral w) >> return ()

Функция: unfoldr

Описание: разворачивает начальное значение в восьмибитовую строку. Является обратной по отношению к функции foldr.  Сложность —  O(n), где n — длина  результата.

Определение:

unfoldr :: (a  ->  Maybe (Word8,  a)) ->  a ->  ByteString unfoldr  f = concat  . unfoldChunk  32  64

where

unfoldChunk  n n’ x  = case unfoldrN n  f  x  of (s,  Nothing) ->  s  :  []

(s, Just  x’) ->  s  : unfoldChunk  n’ (n  + n’) x’

Функция: unfolrdN

Описание: вариант функции unfoldr, который  в любом случае  ограничивает длину результата значением, переданным в качестве первого параметра. Сложность — O(n), где n — длина результата.

Определение:

unfoldrN :: Int ->  (a  ->  Maybe (Word8,  a)) ->  a ->  (ByteString, Maybe a) unfoldrN i f x0 | i < 0         = (empty,  Just  x0)

| otherwise = unsafePerformIO   $ createAndTrim’ i $ \p ->  go p  x0 0

where

go a b c  | a ‘seq‘ b ‘seq‘ c  ‘seq‘ False  =  undefined go p x  n = case f x  of

Nothing            ->  return (0, n, Nothing)

Just  (w,  x’) | n == i   ->  return (0, n, Just  x)

| otherwise ->  do poke p w

go (p  ‘plusPtr‘ 1)  x’ (n  +  1)

Функция: take

Описание: возвращает восьмибитовую  строку, представляющую  собой первые

n символов строки-источника. Сложность — O(1).

Определение:

take  :: Int ->  ByteString ->  ByteString take  n ps@(PS  x  s  l) | n <= 0       = empty

| n >= l   = ps

| otherwise = PS  x  s  n

Функция: drop

Описание: возвращает восьмибитовую строку, представляющую  собой исходную строку без первых n символов строки-источника. Сложность — O(1). Определение:

drop    :: Int ->  ByteString  ->  ByteString drop  n ps@(PS  x  s  l) | n <= 0       = ps

| n >= l   = empty

| otherwise = PS  x  (s + n)  (l n)

Функция: splitAt

Описание: возвращает пару восьмибитовых строк, первым  элементом которой является результат функции take  на тех же входных параметрах, а вторым — результат функции drop соответственно. Сложность — O(1).

Определение:

splitAt :: Int ->  ByteString ->  (ByteString,  ByteString) splitAt n ps@(PS  x  s  l) | n <= 0       =  (empty, ps)

| n >= l   = (ps,  empty)

| otherwise = (PS x  s  n, PS  x  (s + n)  (l n))

Функция: takeWhile

Описание: возвращает подстроку заданной восьмибитовой строки,  состоящую из тех символов в начале исходной строки, которые  удовлетворяют входному предикату. Как только функция находит символ, который не удовлетворяет предикату, процесс выборки подстроки заканчивается.

Определение:

takeWhile :: (Word8 ->  Bool)   ->  ByteString ->  ByteString takeWhile f ps = unsafeTake  (findIndexOrEnd (not  . f) ps)  ps

Функция: dropWhile

Описание: возвращает подстроку заданной восьмибитовой строки,  состоящую из тех символов в конце  исходной строки, которые  не  удовлетворяют входному предикату. Как  только функция находит символ, который не удовлетворяет предикату, процесс выборки подстроки заканчивается, результатом возвращается остаток входной строки.

Определение:

dropWhile  :: (Word8 ->  Bool)   ->  ByteString ->  ByteString dropWhile  f ps = unsafeDrop  (findIndexOrEnd (not  . f) ps)  ps

Функция: span

Описание: возвращает пару восьмибитовых строк, первым элементом  которой является результат функции takewhile на тех же  входных  параметрах, а вторым — результат функции dropWhile соответственно.

Определение:

span :: (Word8 ->  Bool)   ->  ByteString ->  (ByteString,  ByteString) span p ps = break  (not . p)  ps

Функция: spanEnd

Описание: вариант функции span, который действует с конца заданной строкиисточника.

Определение:

spanEnd :: (Word8 ->  Bool)   ->  ByteString ->  (ByteString,  ByteString) spanEnd  p ps = splitAt (findFromEndUntil  (not  . p)  ps)  ps

Функция: break

Описание: вариант функции span, в котором входной предикат обращён.

Определение:

break  :: (Word8 ->  Bool)   ->  ByteString ->  (ByteString, ByteString)

break  p ps = case findIndexOrEnd p ps of n ->  (unsafeTake  n ps,  unsafeDrop  n  ps)

Функция: breakEnd

Описание: вариант функции break, который действует с конца заданной строкиисточника.

Определение:

breakEnd :: (Word8 ->  Bool)   ->  ByteString ->  (ByteString,  ByteString) breakEnd   p ps = splitAt (findFromEndUntil p  ps)  ps

Функция: group

Описание: возвращает список восьмибитовых строк, являющихся  подстроками входной строки, состоящих из последовательных одинаковых символов. Определение:

group  :: ByteString ->  [ByteString] group  xs  |  null xs     = []

| otherwise = ys  : group  zs

where (ys, zs)  = spanByte  (unsafeHead  xs)  xs

Например,          вызов          group  "Mississippi"        вернёт           список

["M", "i", "ss", "i", "ss", "i", "pp", "i"].

Функция: groupBy

Описание:  более общий вариант функции group, в который передаётся функция для вычисления равенства (первым аргументом).

Определение:

groupBy :: (Word8 ->  Word8 ->  Bool)   ->  ByteString ->  [ByteString] groupBy k  xs  | null xs     = []

| otherwise = unsafeTake  n xs  : groupBy k  (unsafeDrop  n xs)

where

n = 1 + findIndexOrEnd (not  . k  (unsafeHead  xs))  (unsafeTail xs)

Функция: inits

Описание: возвращает все начальные подстроки  заданной восьмибитовой строки.

Сложность — O(n), где n — длина строки.

Определение:

inits :: ByteString ->  [ByteString]

inits (PS x  s  l) = [PS x  s  n | n < [0..l]]

Функция: tails

Описание: возвращает  все конечные подстроки заданной восьмибитовой строки.

Сложность — O(n), где n — длина строки.

Определение:

tails :: ByteString ->  [ByteString] tails p | null  p        = [empty]

| otherwise = p : tails (unsafeTail p)

Функция: split

Описание: разделяет входную восьмибитовую строку на подстроки при помощи заданного символа (сам символ никогда не входит в финальные строки). Сложность — O(n), где n — длина строки.

Определение:

split :: Word8 ->  ByteString ->  [ByteString] split _ (PS _ _ 0)  = []

split w  (PS x  s  l) =  inlinePerformIO  $ withForeignPtr  x  $

\p ->  do let ptr = p  ‘plusPtr‘  s

loop  a | a ‘seq‘ False  =  undefined loop  n = let q =  inlinePerformIO $

memchr  (ptr ‘plusPtr‘ n)

w  (fromIntegral  (l n)) in  if q == nullPtr

then  [PS x  (s + n)  (l  n)] else  let i = q  ‘minusPtr‘ ptr

in  PS  x  (s + n)  (i n):loop  (i + 1)

return  (loop  0)

Функция: splitWith

Описание: вариант функции split,  в котором  предикат для  разбиения входной восьмибитовой строки на подстроки передаётся первым аргументом. Сложность — O(n), где n — длина строки.

Определение:

splitWith :: (Word8 ->  Bool)   ->  ByteString ->  [ByteString] splitWith _ (PS _ _ 0)  = []

splitWith p ps  = loop  p ps where

loop  a b | a ‘seq‘ b ‘seq‘ False  =  undefined loop  q qs = if null  rest

then  [chunk]

else  chunk : loop  q (unsafeTail rest)

where

(chunk, rest)  = break  q qs

Функция: join

Описание: принимает на вход строку и список строк, возвращает восьмибитовую строку, составленную из строк входного списка, перемеженных первым аргументом. Функция является обратной к функции split. Сложность — O(n), где n — длина строки.

Определение:

join :: ByteString ->  [ByteString]  ->  ByteString join  s  = concat  .  (List.intersperse s)

Функция: isPrefixOf

Описание: возвращает значение True, если первый аргумент является началом второго. Сложность — O(n), где n — длина меньшей строки.

Определение:

isPrefixOf :: ByteString ->  ByteString ->  Bool isPrefixOf (PS  x1  s1 l1) (PS x2 s2 l2)

| l1 == 0     = True

| l2 < l1    = False

| otherwise = inlinePerformIO $ withForeignPtr x1 $ \p1  ->  withForeignPtr  x2  $

\p2  ->  do i < memcmp  (p1  ‘plusPtr‘ s1)  (p2  ‘plusPtr‘  s2) (fromIntegral  l1)

return $! i == 0

Функция: isSuffixOf

Описание: возвращает значение True, если первый аргумент является окончанием второго. Сложность — O(n), где n — длина меньшей строки.

Определение:

isSuffixOf :: ByteString ->  ByteString  ->  Bool isSuffixOf (PS x1 s1 l1) (PS  x2  s2 l2)

| l1 == 0     = True

| l2 < l1    = False

| otherwise =  inlinePerformIO  $ withForeignPtr  x1 $

\p1  ->  withForeignPtr x2 $

\p2  ->  do i < memcmp  (p1  ‘plusPtr‘  s1)

(p2  ‘plusPtr‘ s2 ‘plusPtr‘  (l2  l1)) (fromIntegral l1)

return $! i == 0

Функция: isSubstringOf

Описание: возвращает значение True, если первая строка является подстрокой второго аргумента.

Определение:

isSubstringOf :: ByteString ->  ByteString ->  Bool isSubstringOf p s  = not  $ P.null $  findSubstrings p s

Функция: findSubstring

Описание: возвращает позицию первого вхождения первого аргумента во второй.

Определение:

findSubstring :: ByteString ->  ByteString ->  Maybe Int findSubstring = (listToMaybe .) .  findSubstrings

Функция: findSubstrings

Описание: возвращает список позиций всех вхождений первого аргумента в качестве подстроки во второй.

Определение:

findSubstrings :: ByteString ->  ByteString ->  [Int] findSubstrings pat@(PS  _ _ m) str@(PS _ _  n)  = search  0 0

where

patc  x  = pat  ‘unsafeIndex‘ x strc  x  = str  ‘unsafeIndex‘  x

kmpNext = listArray (0,m)  (-1:kmpNextL  pat  (-1)) kmpNextL p _ |  null p = []

kmpNextL p j = let j’ = next  (unsafeHead  p)  j +  1 ps = unsafeTail p

x  = if not  (null ps)  &&  unsafeHead  ps  == patc  j’ then  kmpNext  Array.! j’

else  j’

in    x:kmpNextL ps j’ search  i j = match ++ rest

where

match = if j == m

then  [(i   j)] else  []

rest  =  if  i  ==  n then  []

else  search  (i+1) (next (strc i) j + 1)

next  c  j | j >= 0 &&  (j == m   || c  /=  patc  j) = next  c  (kmpNext Array.! j)

| otherwise = j

Функция: elem

Описание: возвращает значение True, если заданный символ входит в восьмибитовую строку. Сложность — O(n), где n — длина строки.

Определение:

elem :: Word8 ->  ByteString ->  Bool elem  c  ps = case elemIndex  c  ps of

Nothing  ->  False

_             ->  True

Функция: notElem

Описание: возвращает значение False, если заданный символ не входит в восьмибитовую строку. Сложность — O(n), где n — длина строки.

Определение:

notElem :: Word8 ->  ByteString ->  Bool notElem  c  ps = not  (elem  c  ps)

Функция: find

Описание: возвращает первый элемент восьмибитовой строки, который удовлетворяет заданному предикату. Сложность — O(n), где n — длина строки.

Определение:

find :: (Word8 ->  Bool)   ->  ByteString ->  Maybe Word8 find f p = case findIndex f p of

Just  n ->  Just  (p  ‘unsafeIndex‘ n)

_           ->  Nothing

Функция: filter

Описание: фильтрует входную восьмибитовую строку при помощи заданного предиката, оставляя в ней только те символы, которые этому предикату удовлетворяют. Сложность — O(n), где n — длина строки.

Определение:

filter :: (Word8 ->  Bool)   ->  ByteString ->  ByteString filter f = loopArr . loopFilter f

Функция: index

Описание: возвращает символ на заданной позиции в восьмибитовой строке (индексация символов начинается с 0. Сложность — O(1).

Определение:

index  :: ByteString ->  Int  ->  Word8 index  ps n

| n < 0                  = moduleError  "index" ("negative index: " ++ show n)

| n >= length ps = moduleError  "index" ("index too  large: " ++ show  n ++ ", length = " ++ show  (length ps))

| otherwise          = ps ‘unsafeIndex‘ n

Функция:  elemIndex

Описание: возвращает позицию первого элемента в восьмибитовой строке, который равен заданному. Сложность — O(n), где n — длина строки.

Определение:

elemIndex  :: Word8 ->  ByteString ->  Maybe Int elemIndex  c  (PS x  s  l) =  inlinePerformIO $

withForeignPtr x  $

\p ->  do let p’ = p ‘plusPtr‘  s

q < memchr  p’ c  (fromIntegral l) return  $!  if q == nullPtr

then  Nothing

else  Just  $! q ‘minusPtr‘ p’

Функция: elemIndices

Описание: возвращает список позиций заданного символа в восьмибитовой строке. Сложность — O(n), где n — длина строки.

Определение:

elemIndices :: Word8 ->  ByteString ->  [Int] elemIndices w  (PS x  s  l) = inlinePerformIO $

withForeignPtr x  $

\p ->  do let ptr = p ‘plusPtr‘  s

loop  a | a ‘seq‘ False  =  undefined loop  n =  let  q =  inlinePerformIO  $

memchr  (ptr  ‘plusPtr‘  n)

w  (fromIntegral (l n)) in    if  q == nullPtr

then  []

else  let i = q  ‘minusPtr‘  ptr in  i :  loop  (i + 1)

return  $!  loop  0

Функция: findIndex

Описание: обобщённый вариант функции elemIndex, в котором поиск позиции осуществляется при помощи заданного предиката.

Определение:

findIndex :: (Word8 ->  Bool)   ->  ByteString  -> Maybe Int findIndex k  (PS x  s  l) =  inlinePerformIO $

withForeignPtr x  $

\f ->  go (f ‘plusPtr‘ s) 0

where

go a b | a ‘seq‘ b ‘seq‘ False  =  undefined go ptr n | n >= l        =  return  Nothing

| otherwise = do w  < peek  ptr if  k  w

then  return  (Just n)

else  go (ptr ‘plusPtr‘ 1)  (n  + 1)

Функция: findIndices

Описание: обобщённый вариант функции elemIndices, в котором поиск позиции осуществляется при помощи заданного предиката.

Определение:

findIndices :: (Word8 ->  Bool)   ->  ByteString  ->  [Int] findIndices p ps = loop  0 ps

where

loop  a b   | a ‘seq‘ b ‘seq‘ False  =  undefined loop  n qs | null qs                     =  []

| p (unsafeHead  qs)  = n : loop  (n  + 1)  (unsafeTail qs)

| otherwise               =         loop  (n  + 1)  (unsafeTail qs)

Функция: count

Описание: возвращает количество вхождений заданного символа в восьмибитовую строку.

Определение:

count  :: Word8 ->  ByteString  ->  Int count  w  (PS x  s  m) =  inlinePerformIO $

withForeignPtr x  $

\p ->  fmap fromIntegral $

c_count  (p  ‘plusPtr‘  s) (fromIntegral m) w

Функция: zip

Описание: принимает на вход две восьмибитовые строки и возвращает список пар символов, находящихся на одинаковых позициях в каждой строке. Сложность — O(n), где n — длина меньшей строки.

Определение:

zip   :: ByteString ->  ByteString ->  [(Word8,Word8)] zip   ps qs | null ps || null  qs = []

| otherwise                 = (unsafeHead  ps,  unsafeHead qs)  :

zip   (unsafeTail ps)  (unsafeTail qs)

Функция: zipWith

Описание: обобщение функции zip,  которое  преобразует  пару  восьмибитовых строк в список при помощи заданной функции, получающей на вход по символу из каждой строки. Сложность — O(n), где n — длина меньшей строки.

Определение:

zipWith :: (Word8 ->  Word8 ->  a)  ->  ByteString ->  ByteString ->  [a] zipWith f ps qs | null ps || null qs =  []

| otherwise                 = f (unsafeHead  ps)  (unsafeHead  qs)  : zipWith f (unsafeTail  ps) (unsafeTail qs)

Функция: unzip

Описание: преобразует список пар символов в пару восьмибитовых строк. По эффекту обратна функции zip.  Сложность — O(n), где n — длина большей строки. Определение:

unzip  :: [(Word8,Word8)] ->  (ByteString,ByteString) unzip  ls = (pack  (P.map fst ls), pack (P.map snd ls))

Функция: sort

Описание: осуществляет сортировку символов в восьмибитовой  строке. Сложность — O(n), где n — длина строки.

Определение:

sort :: ByteString  ->  ByteString sort  (PS  input s  l)

=  unsafeCreate  l $

\p ->  allocaArray 256 $

\arr ->  do memset  (castPtr arr) 0 (256  * fromIntegral (sizeOf (undefined  :: CSize))) withForeignPtr input (\x  ->  countOccurrences   arr  (x  ‘plusPtr‘ s) l)

let go a b | a ‘seq‘ b ‘seq‘ False  =  undefined go 256 _     = return  ()

go i  ptr = do n < peekElemOff  arr i when  (n  /=  0)  $

memset  ptr (fromIntegral i) n  >> return () go (i + 1)  (ptr ‘plusPtr‘ (fromIntegral  n))

go 0 p

Функция: sortBy

Описание: обобщение функции sort,  которое  сортирует символы в  восьмибайтовой строке при помощи заданного предиката сравнения. В текущей поставке модулей не реализовано.

Определение:

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

Функция: packCString

Описание: создаёт восьмибитовую строку из строки типа CString. Сложность —

O(n), где n — длина строки.

Определение:

packCString   :: CString ->  ByteString packCString   cstr  =  unsafePerformIO   $

do fp < newForeignPtr_  (castPtr cstr) l < c_strlen  cstr

return $! PS  fp 0 (fromIntegral l)

Функция: packCStringLen

Описание: создаёт восьмибитовую строку из строки типа CString  без использования функции strlen, а потому сложность — O(1).

Определение:

packCStringLen  :: CStringLen  ->  ByteString packCStringLen  (ptr, len)  =  unsafePerformIO   $

do fp < newForeignPtr_  (castPtr  ptr) return $! PS  fp  0 (fromIntegral len)

Функция: packMallocCString

Описание: создаёт восьмибитовую строку из строки типа CString, которая была создана при помощи функции malloc  (в языке C). Сложность — O(n), где n — длина строки.

Определение:

packMallocCString :: CString ->  ByteString packMallocCString cstr  =  unsafePerformIO   $

do fp < newForeignFreePtr  (castPtr cstr) len  < c_strlen  cstr

return $! PS  fp 0 (fromIntegral len)

Функция: useAsCString

Описание: использование восьмибитовой  строки в тех функциях,  которые  используют строки в стиле языка C (заканчивающиеся  нулевым символом). Па-

мять от созданной строки после использования освобождается  автоматически.

Сложность — O(n), где n — длина строки.

Определение:

useAsCString  :: ByteString ->  (CString ->  IO  a)  ->  IO a useAsCString  (PS ps s  l) = bracket  alloc (c_free.castPtr)

where

alloc = withForeignPtr ps $

\p ->  do buf  < c_malloc  (fromIntegral l+1)

memcpy  (castPtr buf) (castPtr p ‘plusPtr‘ s)  (fromIntegral l) poke (buf ‘plusPtr‘  l) (0  ::  Word8)

return  (castPtr  buf)

Функция: useAsCStringLen

Описание: вариант функции useAsCString, которая имеет сложность O(1) и используется тогда, когда известна длина строки.

Определение:

useAsCStringLen  :: ByteString ->  (CStringLen ->  IO  a)  ->  IO a

Функция определена в виде примитива.

Функция: copy

Описание: копирует восьмибитовую строку. Эта функция может использоваться в тех случаях, когда старая копия строки может быть подвергнута уборке сборщиком мусора. Например, если для работы получена какая-либо большая строка, из которой используется только часть. Сложность — O(n), где n — длина  строки. Определение:

copy :: ByteString ->  ByteString copy (PS x  s  l) = unsafeCreate  l $

\p ->  withForeignPtr  x  $

\f ->  memcpy  p (f ‘plusPtr‘  s) (fromIntegral l)

Функция: copyCString

Описание: копирует строку типа CString  в виде восьмибитовой  строки. Функция используется тогда, когда известно, что исходная строка будет уничтожена во внешнем модуле. Сложность — O(n), где n — длина строки.

Определение:

copyCString   :: CString ->  IO  ByteString copyCString   cstr = do  len < c_strlen cstr

copyCStringLen  (cstr,  fromIntegral len)

Функция: copyCStringLen

Описание: вариант функции copyCString,  который  используется  тогда, когда известна длина строки.

Определение:

copyCStringLen  :: CStringLen  ->  IO  ByteString copyCStringLen  (cstr, len)  = create len  $

\p ->  memcpy  p (castPtr cstr)  (fromIntegral len)

Функция: getLine

Описание: считывает восьмибитовую строку из стандартного потока ввода.

Определение:

getLine :: IO  ByteString getLine =  hGetLine  stdin

Функция: getContents

Описание: считывает всё содержимое  стандартного потока ввода в восьмибитовую строку.

Определение:

getContents :: IO  ByteString getContents =  hGetContents  stdin

Функция: putStr

Описание: записывает заданную восьмибитовую строку в стандартный поток вывода.

Определение:

putStr :: ByteString  ->  IO () putStr =  hPut  stdout

Функция: putStrLn

Описание: вариант функции putStr, записывающий в стандартный поток вывода после строки символ перевода строки.

Определение:

putStrLn ::  ByteString ->  IO () putStrLn =  hPutStrLn  stdout

Функция: interact

Описание: принимает на вход функцию, которой подаётся на вход всё содержимое стандартного потока ввода и чей результат  записывается  непосредственно в стандартный поток вывода.

Определение:

interact :: (ByteString ->  ByteString) ->  IO ()

interact  transformer = putStr . transformer =<<  getContents

Функция: readFile

Описание: считывает всё содержимое заданного файла в восьмибитовую строку. Эта функция более эффективна,  нежели считывание символов файла в список символов String, а потом использование функции pack.

Определение:

readFile :: FilePath ->  IO  ByteString

readFile f = bracket (openBinaryFile  f ReadMode) hClose

(\h ->  hFileSize h >>= hGet h .  fromIntegral)

Функция: writeFile

Описание: записывает восьмибитовую строку в заданный файл, перезаписывая его содержимое.

Определение:

writeFile :: FilePath ->  ByteString ->  IO ()

writeFile f txt = bracket (openBinaryFile  f  WriteMode) hClose

(\h ->  hPut  h txt)

Функция: appendFile

Описание: дописывает восьмибитовую строку в конец заданного файла.

Определение:

appendFile  :: FilePath ->  ByteString ->  IO ()

appendFile  f txt = bracket (openBinaryFile f  AppendMode) hClose

(\h ->  hPut  h  txt)

Функция: hGetLine

Описание: считывает восьмибитовую строку из заданного источника.

Определение:

hGetLine  :: Handle ->  IO ByteString

hGetLine  h = System.IO.hGetLine h >>= return . pack . P.map c2w

Функция:  hGetContents

Описание: считывает всё содержимое заданного источника в  восьмибитовую строку.

Определение:

hGetContents  :: Handle ->  IO  ByteString hGetContents  h = do  let  start_size = 1024

p < mallocArray  start_size i < hGetBuf h p  start_size if i <  start_size

then  do p’ < reallocArray p i

fp < newForeignFreePtr  p’ return $! PS  fp  0 i

else  f p start_size

where

f p s  = do let s’ = 2 * s

p’ < reallocArray p s’

i < hGetBuf h (p’  ‘plusPtr‘ s) s if i < s

then  do let i’ = s  + i

p’’ < reallocArray p’ i’

fp   < newForeignFreePtr  p’’ return $! PS  fp  0  i’

else  f p’ s’

Функция: hGet

Описание: считывает восьмибитовую строку непосредственно из  заданного источника, не выделяя для этого буфер, как это делает функция hGetcontents.

Определение:

hGet :: Handle ->  Int ->  IO  ByteString hGet _ 0 =  return empty

hGet h i = createAndTrim  i $ \p ->  hGetBuf h p i

Функция: hGetNonBlocking

Описание: вариант функции  hGet, который  не ожидает  доступности данных, а возвращает только те данные, которые доступны на момент вызова функции. Определение:

hGetNonBlocking  :: Handle ->  Int ->  IO  ByteString hGetNonBlocking  = hGet

Функция: hPut

Описание: записывает восьмибитовую строку в заданный источник.

Определение:

hPut  :: Handle ->  ByteString ->  IO ()

hPut  _ (PS _

_ 0)  = return ()

hPut  h (PS ps s  l) = withForeignPtr ps $ \p-> hPutBuf  h (p  ‘plusPtr‘ s) l

Функция: hPutStr

Описание: синоним функции hPut для совместимости.

Определение:

hPutStr :: Handle ->  ByteString ->  IO () hPutStr =  hPut

Функция: hPutStrLn

Описание: вариант функции hPut, который добавляет после записанной в заданный источник восьмибитовой строки символ перевода строки.

Определение:

hPutStrLn   :: Handle ->  ByteString ->  IO ()

hPutStrLn   h ps | length ps < 1024 = hPut  h (ps  ‘snoc‘  0x0a)

| otherwise             = hPut  h ps >> hPut  h (singleton (0x0a))

Источник: Душкин Р. В., Справочник по языку Haskell. М.: ДМК Пресс, 2008. 544 с., ил.

По теме:

  • Комментарии