1{-# LANGUAGE BangPatterns #-}
2{-# OPTIONS_GHC -fno-warn-orphans #-}
6-- Copyright : (c) Tom Harper 2008-2009,
7-- (c) Bryan O'Sullivan 2009,
8-- (c) Duncan Coutts 2009
11-- Maintainer : bos@serpentine.com, rtharper@aftereternity.co.uk,
13-- Stability : experimental
16-- A time and space-efficient implementation of Unicode text using
17-- packed Word16 arrays. Suitable for performance critical use, both
18-- in terms of large data quantities and high speed.
20-- This module is intended to be imported @qualified@, to avoid name
21-- clashes with "Prelude" functions, e.g.
23-- > import qualified Data.Text as T
33 -- * Creation and elimination
94 -- ** Accumulating maps
98 -- ** Generation and unfolding
106 -- ** Breaking strings
124 -- ** Breaking into many substrings
132 -- ** Breaking into lines and words
159 -- * Zipping and unzipping
167import Prelude (Char, Bool(..), Functor(..), Int, Maybe(..), String,
168 Eq(..), Ord(..), (++),
170 (&&), (||), (+), (-), (.), ($),
171 fromIntegral, div, not, return, otherwise)
172import Control.Exception (assert)
173import Data.Char (isSpace)
174import Control.Monad.ST (ST)
175import qualified Data.Text.Array as A
176import qualified Data.List as L
177import Data.Monoid (Monoid(..))
178import Data.Word (Word16)
179import Data.String (IsString(..))
180import qualified Data.Text.Fusion as S
181import qualified Data.Text.Fusion.Common as S
182import Data.Text.Fusion (stream, reverseStream, unstream)
183import Data.Text.Internal (Text(..), empty, text, textP)
184import qualified Prelude as P
185import Data.Text.Unsafe (iter, iter_, reverseIter, unsafeHead, unsafeTail)
186import Data.Text.UnsafeChar (unsafeChr)
187import qualified Data.Text.Encoding.Utf16 as U16
188import Data.Text.Search (indices)
192-- Most of the functions in this module are subject to /fusion/,
193-- meaning that a pipeline of such functions will usually allocate at
194-- most one 'Text' value.
196instance Eq Text where
197 t1 == t2 = stream t1 == stream t2
200instance Ord Text where
201 compare t1 t2 = compare (stream t1) (stream t2)
202 {-# INLINE compare #-}
204instance Show Text where
205 showsPrec p ps r = showsPrec p (unpack ps) r
207instance Read Text where
208 readsPrec p str = [(pack x,y) | (x,y) <- readsPrec p str]
210instance Monoid Text where
215instance IsString Text where
218-- -----------------------------------------------------------------------------
219-- * Conversion to/from 'Text'
221-- | /O(n)/ Convert a 'String' into a 'Text'. Subject to fusion.
222pack :: String -> Text
223pack = unstream . S.streamList
224{-# INLINE [1] pack #-}
226-- | /O(n)/ Convert a Text into a String. Subject to fusion.
227unpack :: Text -> String
228unpack = S.unstreamList . stream
229{-# INLINE [1] unpack #-}
231-- | /O(1)/ Convert a character into a Text.
233singleton :: Char -> Text
234singleton = unstream . S.singleton
235{-# INLINE [1] singleton #-}
237-- -----------------------------------------------------------------------------
240-- | /O(n)/ Adds a character to the front of a 'Text'. This function
241-- is more costly than its 'List' counterpart because it requires
242-- copying a new array. Subject to fusion.
243cons :: Char -> Text -> Text
244cons c t = unstream (S.cons c (stream t))
247-- | /O(n)/ Adds a character to the end of a 'Text'. This copies the
248-- entire array in the process, unless fused. Subject to fusion.
249snoc :: Text -> Char -> Text
250snoc t c = unstream (S.snoc (stream t) c)
253-- | /O(n)/ Appends one 'Text' to the other by copying both of them
254-- into a new 'Text'. Subject to fusion.
255append :: Text -> Text -> Text
256append (Text arr1 off1 len1) (Text arr2 off2 len2) = Text (A.run x) 0 len
260 arr <- A.unsafeNew len :: ST s (A.MArray s Word16)
261 copy arr1 off1 (len1+off1) arr 0
262 copy arr2 off2 (len2+off2) arr len1
265 copy arr i top arr' j
266 | i >= top = return ()
267 | otherwise = do A.unsafeWrite arr' j (arr `A.unsafeIndex` i)
268 copy arr (i+1) top arr' (j+1)
272"TEXT append -> fused" [~1] forall t1 t2.
273 append t1 t2 = unstream (S.append (stream t1) (stream t2))
274"TEXT append -> unfused" [1] forall t1 t2.
275 unstream (S.append (stream t1) (stream t2)) = append t1 t2
278-- | /O(1)/ Returns the first character of a 'Text', which must be
279-- non-empty. Subject to fusion.
281head t = S.head (stream t)
284-- | /O(1)/ Returns the first character and rest of a 'Text', or
285-- 'Nothing' if empty. Subject to fusion.
286uncons :: Text -> Maybe (Char, Text)
287uncons t@(Text arr off len)
289 | otherwise = Just (c, textP arr (off+d) (len-d))
290 where (c,d) = iter t 0
291{-# INLINE [1] uncons #-}
293-- | Lifted from Control.Arrow and specialized.
294second :: (b -> c) -> (a,b) -> (a,c)
295second f (a, b) = (a, f b)
298"TEXT uncons -> fused" [~1] forall t.
299 uncons t = fmap (second unstream) (S.uncons (stream t))
300"TEXT uncons -> unfused" [1] forall t.
301 fmap (second unstream) (S.uncons (stream t)) = uncons t
304-- | /O(1)/ Returns the last character of a 'Text', which must be
305-- non-empty. Subject to fusion.
307last (Text arr off len)
308 | len <= 0 = emptyError "last"
309 | n < 0xDC00 || n > 0xDFFF = unsafeChr n
310 | otherwise = U16.chr2 n0 n
311 where n = A.unsafeIndex arr (off+len-1)
312 n0 = A.unsafeIndex arr (off+len-2)
313{-# INLINE [1] last #-}
316"TEXT last -> fused" [~1] forall t.
317 last t = S.last (stream t)
318"TEXT last -> unfused" [1] forall t.
319 S.last (stream t) = last t
322-- | /O(1)/ Returns all characters after the head of a 'Text', which
323-- must be non-empty. Subject to fusion.
325tail t@(Text arr off len)
326 | len <= 0 = emptyError "tail"
327 | otherwise = textP arr (off+d) (len-d)
329{-# INLINE [1] tail #-}
332"TEXT tail -> fused" [~1] forall t.
333 tail t = unstream (S.tail (stream t))
334"TEXT tail -> unfused" [1] forall t.
335 unstream (S.tail (stream t)) = tail t
338-- | /O(1)/ Returns all but the last character of a 'Text', which must
339-- be non-empty. Subject to fusion.
341init (Text arr off len) | len <= 0 = emptyError "init"
342 | n >= 0xDC00 && n <= 0xDFFF = textP arr off (len-2)
343 | otherwise = textP arr off (len-1)
345 n = A.unsafeIndex arr (off+len-1)
346{-# INLINE [1] init #-}
349"TEXT init -> fused" [~1] forall t.
350 init t = unstream (S.init (stream t))
351"TEXT init -> unfused" [1] forall t.
352 unstream (S.init (stream t)) = init t
355-- | /O(1)/ Tests whether a 'Text' is empty or not. Subject to
358null (Text _arr _off len) = assert (len >= 0) $ len <= 0
359{-# INLINE [1] null #-}
362"TEXT null -> fused" [~1] forall t.
363 null t = S.null (stream t)
364"TEXT null -> unfused" [1] forall t.
365 S.null (stream t) = null t
368-- | /O(1)/ Tests whether a 'Text' contains exactly one character.
370isSingleton :: Text -> Bool
371isSingleton = S.isSingleton . stream
372{-# INLINE isSingleton #-}
374-- | /O(n)/ Returns the number of characters in a 'Text'.
377length t = S.length (stream t)
380-- -----------------------------------------------------------------------------
382-- | /O(n)/ 'map' @f@ @t@ is the 'Text' obtained by applying @f@ to
383-- each element of @t@. Subject to fusion.
384map :: (Char -> Char) -> Text -> Text
385map f t = unstream (S.map f (stream t))
386{-# INLINE [1] map #-}
388-- | /O(n)/ The 'intercalate' function takes a 'Text' and a list of
389-- 'Text's and concatenates the list after interspersing the first
390-- argument between each element of the list.
391intercalate :: Text -> [Text] -> Text
392intercalate t ts = unstream (S.intercalate (stream t) (L.map stream ts))
393{-# INLINE intercalate #-}
395-- | /O(n)/ The 'intersperse' function takes a character and places it
396-- between the characters of a 'Text'. Subject to fusion.
397intersperse :: Char -> Text -> Text
398intersperse c t = unstream (S.intersperse c (stream t))
399{-# INLINE intersperse #-}
401-- | /O(n)/ Reverse the characters of a string. Subject to fusion.
402reverse :: Text -> Text
403reverse t = S.reverse (stream t)
404{-# INLINE reverse #-}
406-- | /O(m*n)/ Replace every occurrence of one substring with another.
407replace :: Text -- ^ Text to search for
408 -> Text -- ^ Replacement text
409 -> Text -- ^ Input text
411replace s d = intercalate d . split s
412{-# INLINE replace #-}
414-- ----------------------------------------------------------------------------
415-- ** Case conversions (folds)
419-- When case converting 'Text' values, do not use combinators like
420-- @map toUpper@ to case convert each character of a string
421-- individually, as this gives incorrect results according to the
422-- rules of some writing systems. The whole-string case conversion
423-- functions from this module, such as @toUpper@, obey the correct
424-- case conversion rules. As a result, these functions may map one
425-- input character to two or three output characters. For examples,
426-- see the documentation of each function.
428-- | /O(n)/ Convert a string to folded case. This function is mainly
429-- useful for performing caseless (also known as case insensitive)
430-- string comparisons.
432-- A string @x@ is a caseless match for a string @y@ if and only if:
434-- @toCaseFold x == toCaseFold y@
436-- The result string may be longer than the input string, and may
437-- differ from applying 'toLower' to the input string. For instance,
438-- the Armenian small ligature \"ﬓ\" (men now, U+FB13) is case
439-- folded to the sequence \"մ\" (men, U+0574) followed by
440-- \"ն\" (now, U+0576), while the Greek \"µ\" (micro sign,
441-- U+00B5) is case folded to \"μ\" (small letter mu, U+03BC)
443toCaseFold :: Text -> Text
444toCaseFold t = unstream (S.toCaseFold (stream t))
445{-# INLINE [0] toCaseFold #-}
447-- | /O(n)/ Convert a string to lower case, using simple case
448-- conversion. The result string may be longer than the input string.
449-- For instance, \"İ\" (Latin capital letter I with dot above,
450-- U+0130) maps to the sequence \"i\" (Latin small letter i, U+0069) followed
451-- by \" ̇\" (combining dot above, U+0307).
452toLower :: Text -> Text
453toLower t = unstream (S.toLower (stream t))
454{-# INLINE toLower #-}
456-- | /O(n)/ Convert a string to upper case, using simple case
457-- conversion. The result string may be longer than the input string.
458-- For instance, the German \"ß\" (eszett, U+00DF) maps to the
459-- two-letter sequence \"SS\".
460toUpper :: Text -> Text
461toUpper t = unstream (S.toUpper (stream t))
462{-# INLINE toUpper #-}
464-- | /O(n)/ Left-justify a string to the given length, using the
465-- specified fill character on the right. Subject to fusion. Examples:
467-- > justifyLeft 7 'x' "foo" == "fooxxxx"
468-- > justifyLeft 3 'x' "foobar" == "foobar"
469justifyLeft :: Int -> Char -> Text -> Text
472 | otherwise = t `append` replicateChar (k-len) c
474{-# INLINE [1] justifyLeft #-}
477"TEXT justifyLeft -> fused" [~1] forall k c t.
478 justifyLeft k c t = unstream (S.justifyLeftI k c (stream t))
479"TEXT justifyLeft -> unfused" [1] forall k c t.
480 unstream (S.justifyLeftI k c (stream t)) = justifyLeft k c t
483-- | /O(n)/ Right-justify a string to the given length, using the
484-- specified fill character on the left. Examples:
486-- > justifyRight 7 'x' "bar" == "xxxxbar"
487-- > justifyRight 3 'x' "foobar" == "foobar"
488justifyRight :: Int -> Char -> Text -> Text
491 | otherwise = replicateChar (k-len) c `append` t
493{-# INLINE justifyRight #-}
495-- | /O(n)/ Center a string to the given length, using the
496-- specified fill character on either side. Examples:
498-- > center 8 'x' "HS" = "xxxHSxxx"
499center :: Int -> Char -> Text -> Text
502 | otherwise = replicateChar l c `append` t `append` replicateChar r c
509-- | /O(n)/ The 'transpose' function transposes the rows and columns
510-- of its 'Text' argument. Note that this function uses 'pack',
511-- 'unpack', and the list version of transpose, and is thus not very
513transpose :: [Text] -> [Text]
514transpose ts = P.map pack (L.transpose (P.map unpack ts))
516-- -----------------------------------------------------------------------------
517-- * Reducing 'Text's (folds)
519-- | /O(n)/ 'foldl', applied to a binary operator, a starting value
520-- (typically the left-identity of the operator), and a 'Text',
521-- reduces the 'Text' using the binary operator, from left to right.
523foldl :: (b -> Char -> b) -> b -> Text -> b
524foldl f z t = S.foldl f z (stream t)
527-- | /O(n)/ A strict version of 'foldl'. Subject to fusion.
528foldl' :: (b -> Char -> b) -> b -> Text -> b
529foldl' f z t = S.foldl' f z (stream t)
532-- | /O(n)/ A variant of 'foldl' that has no starting value argument,
533-- and thus must be applied to a non-empty 'Text'. Subject to fusion.
534foldl1 :: (Char -> Char -> Char) -> Text -> Char
535foldl1 f t = S.foldl1 f (stream t)
538-- | /O(n)/ A strict version of 'foldl1'. Subject to fusion.
539foldl1' :: (Char -> Char -> Char) -> Text -> Char
540foldl1' f t = S.foldl1' f (stream t)
541{-# INLINE foldl1' #-}
543-- | /O(n)/ 'foldr', applied to a binary operator, a starting value
544-- (typically the right-identity of the operator), and a 'Text',
545-- reduces the 'Text' using the binary operator, from right to left.
547foldr :: (Char -> b -> b) -> b -> Text -> b
548foldr f z t = S.foldr f z (stream t)
551-- | /O(n)/ A variant of 'foldr' that has no starting value argument,
552-- and thust must be applied to a non-empty 'Text'. Subject to
554foldr1 :: (Char -> Char -> Char) -> Text -> Char
555foldr1 f t = S.foldr1 f (stream t)
558-- -----------------------------------------------------------------------------
561-- | /O(n)/ Concatenate a list of 'Text's. Subject to fusion.
562concat :: [Text] -> Text
563concat ts = unstream (S.concat (L.map stream ts))
566-- | /O(n)/ Map a function over a 'Text' that results in a 'Text', and
567-- concatenate the results. Subject to fusion.
569-- Note: if in 'concatMap' @f@ @t@, @f@ is defined in terms of fusible
570-- functions, it will also be fusible.
571concatMap :: (Char -> Text) -> Text -> Text
572concatMap f t = unstream (S.concatMap (stream . f) (stream t))
573{-# INLINE concatMap #-}
575-- | /O(n)/ 'any' @p@ @t@ determines whether any character in the
576-- 'Text' @t@ satisifes the predicate @p@. Subject to fusion.
577any :: (Char -> Bool) -> Text -> Bool
578any p t = S.any p (stream t)
581-- | /O(n)/ 'all' @p@ @t@ determines whether all characters in the
582-- 'Text' @t@ satisify the predicate @p@. Subject to fusion.
583all :: (Char -> Bool) -> Text -> Bool
584all p t = S.all p (stream t)
587-- | /O(n)/ 'maximum' returns the maximum value from a 'Text', which
588-- must be non-empty. Subject to fusion.
589maximum :: Text -> Char
590maximum t = S.maximum (stream t)
591{-# INLINE maximum #-}
593-- | /O(n)/ 'minimum' returns the minimum value from a 'Text', which
594-- must be non-empty. Subject to fusion.
595minimum :: Text -> Char
596minimum t = S.minimum (stream t)
597{-# INLINE minimum #-}
599-- -----------------------------------------------------------------------------
602-- | /O(n)/ 'scanl' is similar to 'foldl', but returns a list of
603-- successive reduced values from the left. Subject to fusion.
605-- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
609-- > last (scanl f z xs) == foldl f z xs.
610scanl :: (Char -> Char -> Char) -> Char -> Text -> Text
611scanl f z t = unstream (S.scanl f z (stream t))
614-- | /O(n)/ 'scanl1' is a variant of 'scanl' that has no starting
615-- value argument. Subject to fusion.
617-- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
618scanl1 :: (Char -> Char -> Char) -> Text -> Text
619scanl1 f t | null t = empty
620 | otherwise = scanl f (unsafeHead t) (unsafeTail t)
623-- | /O(n)/ 'scanr' is the right-to-left dual of 'scanl'.
625-- > scanr f v == reverse . scanl (flip f) v . reverse
626scanr :: (Char -> Char -> Char) -> Char -> Text -> Text
627scanr f z = S.reverse . S.reverseScanr f z . reverseStream
630-- | /O(n)/ 'scanr1' is a variant of 'scanr' that has no starting
631-- value argument. Subject to fusion.
632scanr1 :: (Char -> Char -> Char) -> Text -> Text
633scanr1 f t | null t = empty
634 | otherwise = scanr f (last t) (init t)
637-- | /O(n)/ Like a combination of 'map' and 'foldl'. Applies a
638-- function to each element of a 'Text', passing an accumulating
639-- parameter from left to right, and returns a final 'Text'.
640mapAccumL :: (a -> Char -> (a,Char)) -> a -> Text -> (a, Text)
641mapAccumL f s t = case uncons t of
642 Nothing -> (s, empty)
643 Just (x, xs) -> (s'', cons y ys)
644 where (s', y ) = f s x
645 (s'',ys) = mapAccumL f s' xs
647-- | The 'mapAccumR' function behaves like a combination of 'map' and
648-- 'foldr'; it applies a function to each element of a 'Text', passing
649-- an accumulating parameter from right to left, and returning a final
650-- value of this accumulator together with the new 'Text'.
651mapAccumR :: (a -> Char -> (a,Char)) -> a -> Text -> (a, Text)
652mapAccumR f s t = case uncons t of
653 Nothing -> (s, empty)
654 Just (x, xs) -> (s'', cons y ys)
655 where (s'',y ) = f s' x
656 (s', ys) = mapAccumR f s xs
658-- -----------------------------------------------------------------------------
659-- ** Generating and unfolding 'Text's
661-- | /O(n*m)/ 'replicate' @n@ @t@ is a 'Text' consisting of the input
662-- @t@ repeated @n@ times. Subject to fusion.
663replicate :: Int -> Text -> Text
664replicate n t = unstream (S.replicateI (fromIntegral n) (S.stream t))
665{-# INLINE [1] replicate #-}
668"TEXT replicate/singleton -> replicateChar" [~1] forall n c.
669 replicate n (singleton c) = replicateChar n c
672-- | /O(n)/ 'replicateChar' @n@ @c@ is a 'Text' of length @n@ with @c@ the
673-- value of every element. Subject to fusion.
674replicateChar :: Int -> Char -> Text
675replicateChar n c = unstream (S.replicateCharI n c)
677-- | /O(n)/, where @n@ is the length of the result. The 'unfoldr'
678-- function is analogous to the List 'L.unfoldr'. 'unfoldr' builds a
679-- 'Text' from a seed value. The function takes the element and
680-- returns 'Nothing' if it is done producing the 'Text', otherwise
681-- 'Just' @(a,b)@. In this case, @a@ is the next 'Char' in the
682-- string, and @b@ is the seed value for further production. Subject
684unfoldr :: (a -> Maybe (Char,a)) -> a -> Text
685unfoldr f s = unstream (S.unfoldr f s)
686{-# INLINE unfoldr #-}
688-- | /O(n)/ Like 'unfoldr', 'unfoldrN' builds a 'Text' from a seed
689-- value. However, the length of the result should be limited by the
690-- first argument to 'unfoldrN'. This function is more efficient than
691-- 'unfoldr' when the maximum length of the result is known and
692-- correct, otherwise its performance is similar to 'unfoldr'. Subject
694unfoldrN :: Int -> (a -> Maybe (Char,a)) -> a -> Text
695unfoldrN n f s = unstream (S.unfoldrN n f s)
696{-# INLINE unfoldrN #-}
698-- -----------------------------------------------------------------------------
701-- | /O(n)/ 'take' @n@, applied to a 'Text', returns the prefix of the
702-- 'Text' of length @n@, or the 'Text' itself if @n@ is greater than
703-- the length of the Text. Subject to fusion.
704take :: Int -> Text -> Text
705take n t@(Text arr off len)
708 | otherwise = Text arr off (loop 0 0)
711 | i >= len || cnt >= n = i
712 | otherwise = loop (i+d) (cnt+1)
714{-# INLINE [1] take #-}
717"TEXT take -> fused" [~1] forall n t.
718 take n t = unstream (S.take n (stream t))
719"TEXT take -> unfused" [1] forall n t.
720 unstream (S.take n (stream t)) = take n t
723-- | /O(n)/ 'drop' @n@, applied to a 'Text', returns the suffix of the
724-- 'Text' of length @n@, or the empty 'Text' if @n@ is greater than the
725-- length of the 'Text'. Subject to fusion.
726drop :: Int -> Text -> Text
727drop n t@(Text arr off len)
730 | otherwise = loop 0 0
732 | i >= len || cnt >= n = Text arr (off+i) (len-i)
733 | otherwise = loop (i+d) (cnt+1)
735{-# INLINE [1] drop #-}
738"TEXT drop -> fused" [~1] forall n t.
739 drop n t = unstream (S.drop n (stream t))
740"TEXT drop -> unfused" [1] forall n t.
741 unstream (S.drop n (stream t)) = drop n t
744-- | /O(n)/ 'takeWhile', applied to a predicate @p@ and a 'Text',
745-- returns the longest prefix (possibly empty) of elements that
746-- satisfy @p@. Subject to fusion.
747takeWhile :: (Char -> Bool) -> Text -> Text
748takeWhile p t@(Text arr off len) = loop 0
749 where loop !i | i >= len = t
751 | otherwise = textP arr off i
752 where (c,d) = iter t i
753{-# INLINE [1] takeWhile #-}
756"TEXT takeWhile -> fused" [~1] forall p t.
757 takeWhile p t = unstream (S.takeWhile p (stream t))
758"TEXT takeWhile -> unfused" [1] forall p t.
759 unstream (S.takeWhile p (stream t)) = takeWhile p t
762-- | /O(n)/ 'dropWhile' @p@ @t@ returns the suffix remaining after
763-- 'takeWhile' @p@ @t@. Subject to fusion.
764dropWhile :: (Char -> Bool) -> Text -> Text
765dropWhile p t@(Text arr off len) = loop 0 0
766 where loop !i !l | l >= len = empty
767 | p c = loop (i+d) (l+d)
768 | otherwise = Text arr (off+i) (len-l)
769 where (c,d) = iter t i
770{-# INLINE [1] dropWhile #-}
773"TEXT dropWhile -> fused" [~1] forall p t.
774 dropWhile p t = unstream (S.dropWhile p (stream t))
775"TEXT dropWhile -> unfused" [1] forall p t.
776 unstream (S.dropWhile p (stream t)) = dropWhile p t
779-- | /O(n)/ 'dropWhileEnd' @p@ @t@ returns the prefix remaining after
780-- dropping characters that fail the predicate @p@ from the end of
781-- @t@. Subject to fusion.
784-- > dropWhileEnd (=='.') "foo..." == "foo"
785dropWhileEnd :: (Char -> Bool) -> Text -> Text
786dropWhileEnd p t@(Text arr off len) = loop (len-1) len
787 where loop !i !l | l <= 0 = empty
788 | p c = loop (i+d) (l+d)
789 | otherwise = Text arr off l
790 where (c,d) = reverseIter t i
791{-# INLINE [1] dropWhileEnd #-}
794"TEXT dropWhileEnd -> fused" [~1] forall p t.
795 dropWhileEnd p t = S.reverse (S.dropWhile p (S.reverseStream t))
796"TEXT dropWhileEnd -> unfused" [1] forall p t.
797 S.reverse (S.dropWhile p (S.reverseStream t)) = dropWhileEnd p t
800-- | /O(n)/ 'dropAround' @p@ @t@ returns the substring remaining after
801-- dropping characters that fail the predicate @p@ from both the
802-- beginning and end of @t@. Subject to fusion.
803dropAround :: (Char -> Bool) -> Text -> Text
804dropAround p = dropWhile p . dropWhileEnd p
805{-# INLINE [1] dropAround #-}
807-- | /O(n)/ Remove leading white space from a string. Equivalent to:
809-- > dropWhile isSpace
810stripStart :: Text -> Text
811stripStart = dropWhile isSpace
812{-# INLINE [1] stripStart #-}
814-- | /O(n)/ Remove trailing white space from a string. Equivalent to:
816-- > dropWhileEnd isSpace
817stripEnd :: Text -> Text
818stripEnd = dropWhileEnd isSpace
819{-# INLINE [1] stripEnd #-}
821-- | /O(n)/ Remove leading and trailing white space from a string.
824-- > dropAround isSpace
826strip = dropAround isSpace
827{-# INLINE [1] strip #-}
829-- | /O(n)/ 'splitAt' @n t@ returns a pair whose first element is a
830-- prefix of @t@ of length @n@, and whose second is the remainder of
831-- the string. It is equivalent to @('take' n t, 'drop' n t)@.
832splitAt :: Int -> Text -> (Text, Text)
833splitAt n t@(Text arr off len)
834 | n <= 0 = (empty, t)
835 | n >= len = (t, empty)
836 | otherwise = (Text arr off k, Text arr (off+k) (len-k))
839 | i >= len || cnt >= n = i
840 | otherwise = loop (i+d) (cnt+1)
842{-# INLINE splitAt #-}
844-- | /O(n)/ 'span', applied to a predicate @p@ and text @t@, returns a
845-- pair whose first element is the longest prefix (possibly empty) of
846-- @t@ of elements that satisfy @p@, and whose second is the remainder
848span :: (Char -> Bool) -> Text -> (Text, Text)
849span p t@(Text arr off len) = (textP arr off k, textP arr (off+k) (len-k))
851 loop !i | i >= len || not (p c) = i
852 | otherwise = loop (i+d)
853 where (c,d) = iter t i
856-- | /O(n)/ 'break' is like 'span', but the prefix returned is over
857-- elements that fail the predicate @p@.
858break :: (Char -> Bool) -> Text -> (Text, Text)
859break p = span (not . p)
862-- | /O(n)/ Group characters in a string according to a predicate.
863groupBy :: (Char -> Char -> Bool) -> Text -> [Text]
866 loop t@(Text arr off len)
868 | otherwise = text arr off n : loop (text arr (off+n) (len-n))
869 where (c,d) = iter t 0
870 n = d + findAIndexOrEnd (not . p c) (Text arr (off+d) (len-d))
872-- | Returns the /array/ index (in units of 'Word16') at which a
873-- character may be found. This is /not/ the same as the logical
874-- index returned by e.g. 'findIndex'.
875findAIndexOrEnd :: (Char -> Bool) -> Text -> Int
876findAIndexOrEnd q t@(Text _arr _off len) = go 0
877 where go !i | i >= len || q c = i
878 | otherwise = go (i+d)
879 where (c,d) = iter t i
881-- | /O(n)/ Group characters in a string by equality.
882group :: Text -> [Text]
885-- | /O(n)/ Return all initial segments of the given 'Text', shortest
887inits :: Text -> [Text]
888inits t@(Text arr off len) = loop 0
889 where loop i | i >= len = [t]
890 | otherwise = Text arr off i : loop (i + iter_ t i)
892-- | /O(n)/ Return all final segments of the given 'Text', longest
894tails :: Text -> [Text]
895tails t | null t = [empty]
896 | otherwise = t : tails (unsafeTail t)
900-- Splitting functions in this library do not perform character-wise
901-- copies to create substrings; they just construct new 'Text's that
902-- are slices of the original.
904-- | /O(m+n)/ Break a 'Text' into pieces separated by the first
905-- 'Text' argument, consuming the delimiter. An empty delimiter is
906-- invalid, and will cause an error to be raised.
910-- > split "\r\n" "a\r\nb\r\nd\r\ne" == ["a","b","d","e"]
911-- > split "aaa" "aaaXaaaXaaaXaaa" == ["","X","X","X",""]
912-- > split "x" "x" == ["",""]
916-- > intercalate s . split s == id
917-- > split (singleton c) == splitBy (==c)
919-- In (unlikely) bad cases, this function's time complexity
920-- degenerates towards /O(n*m)/.
921split :: Text -> Text -> [Text]
922split pat@(Text _ _ l) src@(Text arr off len)
923 | l <= 0 = emptyError "split"
924 | isSingleton pat = splitBy (== unsafeHead pat) src
925 | otherwise = go 0 (indices pat src)
927 go !s (x:xs) = textP arr (s+off) (x-s) : go (x+l) xs
928 go s _ = [textP arr (s+off) (len-s)]
929{-# INLINE [1] split #-}
932"TEXT split/singleton -> splitBy/==" [~1] forall c t.
933 split (singleton c) t = splitBy (==c) t
936-- | /O(m+n)/ Break a 'Text' into pieces at most @k@ times,
937-- treating the first 'Text' argument as the delimiter to break on,
938-- and consuming the delimiter. The last element of the list contains
939-- the remaining text after the number of times to split has been
940-- reached. A value of zero or less for @k@ causes no splitting to
941-- occur. An empty delimiter is invalid, and will cause an error to be
946-- > splitTimes 0 "//" "a//b//c" == ["a//b//c"]
947-- > splitTimes 2 ":" "a:b:c:d:e" == ["a","b","c:d:e"]
948-- > splitTimes 100 "???" "a????b" == ["a","?b"]
952-- > intercalate s . splitTimes k s == id
954-- In (unlikely) bad cases, this function's time complexity
955-- degenerates towards /O(n*m)/.
956splitTimes :: Int -- ^ Maximum number of times to split
957 -> Text -- ^ Text to split on
958 -> Text -- ^ Input text
960splitTimes k pat@(Text _ _ l) src@(Text arr off len)
961 | l <= 0 = emptyError "splitTimes"
962 | otherwise = go 0 0 (indices pat src)
964 go !s !i _ | i >= k = [textP arr (s+off) (len-s)]
965 go !s _ [] = [textP arr (s+off) (len-s)]
966 go !s !i (x:xs) = textP arr (s+off) (x-s) : go (x+l) (i+1) xs
967{-# INLINE splitTimes #-}
969-- | /O(m+n)/ Break a 'Text' into pieces at most @k@ times, like
970-- 'splitTimes', but start from the end of the input and work towards
975-- > splitTimes 2 "::" "a::b::c::d::e" == ["a","b","c::d::e"]
976-- > splitTimesEnd 2 "::" "a::b::c::d::e" == ["a::b::c","d","e"]
978-- In (unlikely) bad cases, this function's time complexity
979-- degenerates towards /O(n*m)/.
980splitTimesEnd :: Int -- ^ Maximum number of times to split
981 -> Text -- ^ Text to split on
982 -> Text -- ^ Input text
984splitTimesEnd k pat src =
985 L.reverse . L.map reverse $ splitTimes k (reverse pat) (reverse src)
986{-# INLINE splitTimesEnd #-}
988-- | /O(n)/ Splits a 'Text' into components delimited by separators,
989-- where the predicate returns True for a separator element. The
990-- resulting components do not contain the separators. Two adjacent
991-- separators result in an empty component in the output. eg.
993-- > splitBy (=='a') "aabbaca" == ["","","bb","c",""]
994-- > splitBy (=='a') "" == [""]
995splitBy :: (Char -> Bool) -> Text -> [Text]
996splitBy _ t@(Text _off _arr 0) = [t]
998 where loop s | null s' = [l]
999 | otherwise = l : loop (unsafeTail s')
1000 where (l, s') = break p s
1001{-# INLINE splitBy #-}
1003-- | /O(n)/ Splits a 'Text' into components of length @k@. The last
1004-- element may be shorter than the other chunks, depending on the
1005-- length of the input. Examples:
1007-- > chunksOf 3 "foobarbaz" == ["foo","bar","baz"]
1008-- > chunksOf 4 "haskell.org" == ["hask","ell.","org"]
1009chunksOf :: Int -> Text -> [Text]
1012 go t = case splitAt k t of
1013 (a,b) | null a -> []
1014 | otherwise -> a : go b
1015{-# INLINE chunksOf #-}
1017-- ----------------------------------------------------------------------------
1020-------------------------------------------------------------------------------
1021-- ** Searching by equality
1023-- | /O(n)/ 'elem' is the 'Text' membership predicate.
1024elem :: Char -> Text -> Bool
1025elem c t = S.elem c (stream t)
1028-------------------------------------------------------------------------------
1029-- ** Searching with a predicate
1031-- | /O(n)/ The 'findBy' function takes a predicate and a 'Text', and
1032-- returns the first element in matching the predicate, or 'Nothing'
1033-- if there is no such element.
1034findBy :: (Char -> Bool) -> Text -> Maybe Char
1035findBy p t = S.findBy p (stream t)
1036{-# INLINE findBy #-}
1038-- | /O(n)/ The 'partition' function takes a predicate and a 'Text',
1039-- and returns the pair of 'Text's with elements which do and do not
1040-- satisfy the predicate, respectively; i.e.
1042-- > partition p t == (filter p t, filter (not . p) t)
1043partition :: (Char -> Bool) -> Text -> (Text, Text)
1044partition p t = (filter p t, filter (not . p) t)
1045{-# INLINE partition #-}
1047-- | /O(n)/ 'filter', applied to a predicate and a 'Text',
1048-- returns a 'Text' containing those characters that satisfy the
1050filter :: (Char -> Bool) -> Text -> Text
1051filter p t = unstream (S.filter p (stream t))
1052{-# INLINE filter #-}
1054-- /O(n+m)/ Find all non-overlapping instances of @needle@ in
1055-- @haystack@. The first element of the returned tuple is the prefix
1056-- of @haystack@ before any matches of @needle@. The second element
1057-- of the tuple is a list of non-overlapping substrings from
1058-- @haystack@. Each begins with @needle@ and ends just before the
1059-- following match. If @needle@ is not present in @haystack@, the
1060-- list will be empty and the prefix will contain @haystack@.
1064-- > find "::" "a::b::c" ==> ("a", ["::b", "::c"])
1065-- > find "/" "foobar" ==> ("foobar", [])
1069-- > concat (prefix : matches) == haystack
1070-- > where (prefix, matches) = find needle haystack
1072-- In (unlikely) bad cases, this function's time complexity
1073-- degenerates towards /O(n*m)/.
1074find :: Text -> Text -> (Text, [Text])
1075find pat src@(Text arr off len)
1076 | null pat = emptyError "find"
1077 | otherwise = case indices pat src of
1079 (x:xs) -> (textP arr off x, go x xs)
1081 go !s (x:xs) = textP arr (s+off) (x-s) : go x xs
1082 go s _ = [textP arr (s+off) (len-s)]
1085-------------------------------------------------------------------------------
1086-- ** Indexing 'Text's
1090-- If you think of a 'Text' value as an array of 'Char' values (which
1091-- it is not), you run the risk of writing inefficient code.
1093-- An idiom that is common in some languages is to find the numeric
1094-- offset of a character or substring, then use that number to split
1095-- or trim the searched string. With a 'Text' value, this approach
1096-- would require two /O(n)/ operations: one to perform the search, and
1097-- one to operate from wherever the search ended.
1099-- For example, suppose you have a string that you want to split on
1100-- the substring @\"::\"@, such as @\"foo::bar::quux\"@. Instead of
1101-- searching for the index of @\"::\"@ and taking the substrings
1102-- before and after that index, you would instead use @splitTimes 1
1105-- | /O(n)/ 'Text' index (subscript) operator, starting from 0.
1106index :: Text -> Int -> Char
1107index t n = S.index (stream t) n
1110-- | /O(n)/ The 'findIndex' function takes a predicate and a 'Text'
1111-- and returns the index of the first element in the 'Text' satisfying
1112-- the predicate. Subject to fusion.
1113findIndex :: (Char -> Bool) -> Text -> Maybe Int
1114findIndex p t = S.findIndex p (stream t)
1115{-# INLINE findIndex #-}
1117-- | /O(n+m)/ The 'count' function returns the number of times the
1118-- query string appears in the given 'Text'. An empty query string is
1119-- invalid, and will cause an error to be raised.
1121-- In (unlikely) bad cases, this function's time complexity
1122-- degenerates towards /O(n*m)/.
1123count :: Text -> Text -> Int
1125 | null pat = emptyError "count"
1126 | isSingleton pat = countChar (unsafeHead pat) src
1127 | otherwise = L.length (indices pat src)
1128{-# INLINE [1] count #-}
1131"TEXT count/singleton -> countChar" [~1] forall c t.
1132 count (singleton c) t = countChar c t
1135-- | /O(n)/ The 'countChar' function returns the number of times the
1136-- query element appears in the given 'Text'. Subject to fusion.
1137countChar :: Char -> Text -> Int
1138countChar c t = S.countChar c (stream t)
1139{-# INLINE countChar #-}
1141-------------------------------------------------------------------------------
1144-- | /O(n)/ 'zip' takes two 'Text's and returns a list of
1145-- corresponding pairs of bytes. If one input 'Text' is short,
1146-- excess elements of the longer 'Text' are discarded. This is
1147-- equivalent to a pair of 'unpack' operations.
1148zip :: Text -> Text -> [(Char,Char)]
1149zip a b = S.unstreamList $ S.zipWith (,) (stream a) (stream b)
1150{-# INLINE [0] zip #-}
1152-- | /O(n)/ 'zipWith' generalises 'zip' by zipping with the function
1153-- given as the first argument, instead of a tupling function.
1154zipWith :: (Char -> Char -> Char) -> Text -> Text -> Text
1155zipWith f t1 t2 = unstream (S.zipWith f (stream t1) (stream t2))
1156{-# INLINE [0] zipWith #-}
1158-- | /O(n)/ Breaks a 'Text' up into a list of words, delimited by 'Char's
1159-- representing white space.
1160words :: Text -> [Text]
1161words t@(Text arr off len) = loop 0 0
1164 | n >= len = if start == n
1166 else [Text arr (start+off) (n-start)]
1169 then loop (start+1) (start+1)
1170 else Text arr (start+off) (n-start) : loop (n+d) (n+d)
1171 | otherwise = loop start (n+d)
1172 where (c,d) = iter t n
1175-- | /O(n)/ Breaks a 'Text' up into a list of 'Text's at
1176-- newline 'Char's. The resulting strings do not contain newlines.
1177lines :: Text -> [Text]
1178lines ps | null ps = []
1179 | otherwise = h : if null t
1181 else lines (unsafeTail t)
1182 where (h,t) = span (/= '\n') ps
1185-- | /O(n)/ Portably breaks a 'Text' up into a list of 'Text's at line
1188-- A line boundary is considered to be either a line feed, a carriage
1189-- return immediately followed by a line feed, or a carriage return.
1190-- This accounts for both Unix and Windows line ending conventions,
1191-- and for the old convention used on Mac OS 9 and earlier.
1193lines' :: Text -> [Text]
1194lines' ps | null ps = []
1195 | otherwise = h : case uncons t of
1198 | c == '\n' -> lines t'
1199 | c == '\r' -> case uncons t' of
1200 Just ('\n',t'') -> lines t''
1202 where (h,t) = span notEOL ps
1203 notEOL c = c /= '\n' && c /= '\r'
1204{-# INLINE lines' #-}
1207-- | /O(n)/ Joins lines, after appending a terminating newline to
1209unlines :: [Text] -> Text
1210unlines = concat . L.map (`snoc` '\n')
1211{-# INLINE unlines #-}
1213-- | /O(n)/ Joins words using single space characters.
1214unwords :: [Text] -> Text
1215unwords = intercalate (singleton ' ')
1216{-# INLINE unwords #-}
1218-- | /O(n)/ The 'isPrefixOf' function takes two 'Text's and returns
1219-- 'True' iff the first is a prefix of the second. This function is
1220-- subject to fusion.
1221isPrefixOf :: Text -> Text -> Bool
1222isPrefixOf a@(Text _ _ alen) b@(Text _ _ blen) =
1223 alen <= blen && S.isPrefixOf (stream a) (stream b)
1224{-# INLINE [1] isPrefixOf #-}
1227"TEXT isPrefixOf -> fused" [~1] forall s t.
1228 isPrefixOf s t = S.isPrefixOf (stream s) (stream t)
1229"TEXT isPrefixOf -> unfused" [1] forall s t.
1230 S.isPrefixOf (stream s) (stream t) = isPrefixOf s t
1233-- | /O(n)/ The 'isSuffixOf' function takes two 'Text's and returns
1234-- 'True' iff the first is a suffix of the second.
1235isSuffixOf :: Text -> Text -> Bool
1236isSuffixOf a@(Text _aarr _aoff alen) b@(Text barr boff blen) =
1238 where d = blen - alen
1240 | otherwise = Text barr (boff+d) alen
1241{-# INLINE isSuffixOf #-}
1243-- | /O(n+m)/ The 'isInfixOf' function takes two 'Text's and returns
1244-- 'True' iff the first is contained, wholly and intact, anywhere
1245-- within the second.
1247-- In (unlikely) bad cases, this function's time complexity
1248-- degenerates towards /O(n*m)/.
1249isInfixOf :: Text -> Text -> Bool
1250isInfixOf pat src = null pat || (not . L.null $ indices pat src)
1251{-# INLINE isInfixOf #-}
1253emptyError :: String -> a
1254emptyError fun = P.error ("Data.Text." ++ fun ++ ": empty input")
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list