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
161 -- * Zipping and unzipping
169import Prelude (Char, Bool(..), Functor(..), Int, Maybe(..), String,
170 Eq(..), Ord(..), (++),
172 (&&), (||), (+), (-), (.), ($),
173 fromIntegral, div, not, return, otherwise)
174import Control.Exception (assert)
175import Data.Char (isSpace)
176import Control.Monad.ST (ST)
177import qualified Data.Text.Array as A
178import qualified Data.List as L
179import Data.Monoid (Monoid(..))
180import Data.Word (Word16)
181import Data.String (IsString(..))
183import qualified Data.Text.Fusion as S
184import qualified Data.Text.Fusion.Common as S
185import Data.Text.Fusion (stream, reverseStream, unstream)
187import Data.Text.Internal (Text(..), empty, text, textP)
188import qualified Prelude as P
189import Data.Text.Unsafe (iter, iter_, reverseIter, unsafeHead, unsafeTail)
190import Data.Text.UnsafeChar (unsafeChr)
191import qualified Data.Text.Encoding.Utf16 as U16
195-- Most of the functions in this module are subject to /fusion/,
196-- meaning that a pipeline of such functions will usually allocate at
197-- most one 'Text' value.
199instance Eq Text where
200 t1 == t2 = stream t1 == stream t2
203instance Ord Text where
204 compare t1 t2 = compare (stream t1) (stream t2)
205 {-# INLINE compare #-}
207instance Show Text where
208 showsPrec p ps r = showsPrec p (unpack ps) r
210instance Read Text where
211 readsPrec p str = [(pack x,y) | (x,y) <- readsPrec p str]
213instance Monoid Text where
218instance IsString Text where
221-- -----------------------------------------------------------------------------
222-- * Conversion to/from 'Text'
224-- | /O(n)/ Convert a 'String' into a 'Text'. Subject to fusion.
225pack :: String -> Text
226pack = unstream . S.streamList
227{-# INLINE [1] pack #-}
229-- | /O(n)/ Convert a Text into a String. Subject to fusion.
230unpack :: Text -> String
231unpack = S.unstreamList . stream
232{-# INLINE [1] unpack #-}
234-- | /O(1)/ Convert a character into a Text.
236singleton :: Char -> Text
237singleton = unstream . S.singleton
238{-# INLINE [1] singleton #-}
240-- -----------------------------------------------------------------------------
243-- | /O(n)/ Adds a character to the front of a 'Text'. This function
244-- is more costly than its 'List' counterpart because it requires
245-- copying a new array. Subject to fusion.
246cons :: Char -> Text -> Text
247cons c t = unstream (S.cons c (stream t))
250-- | /O(n)/ Adds a character to the end of a 'Text'. This copies the
251-- entire array in the process, unless fused. Subject to fusion.
252snoc :: Text -> Char -> Text
253snoc t c = unstream (S.snoc (stream t) c)
256-- | /O(n)/ Appends one 'Text' to the other by copying both of them
257-- into a new 'Text'. Subject to fusion.
258append :: Text -> Text -> Text
259append (Text arr1 off1 len1) (Text arr2 off2 len2) = Text (A.run x) 0 len
263 arr <- A.unsafeNew len :: ST s (A.MArray s Word16)
264 copy arr1 off1 (len1+off1) arr 0
265 copy arr2 off2 (len2+off2) arr len1
268 copy arr i top arr' j
269 | i >= top = return ()
270 | otherwise = do A.unsafeWrite arr' j (arr `A.unsafeIndex` i)
271 copy arr (i+1) top arr' (j+1)
275"TEXT append -> fused" [~1] forall t1 t2.
276 append t1 t2 = unstream (S.append (stream t1) (stream t2))
277"TEXT append -> unfused" [1] forall t1 t2.
278 unstream (S.append (stream t1) (stream t2)) = append t1 t2
281-- | /O(1)/ Returns the first character of a 'Text', which must be
282-- non-empty. Subject to fusion.
284head t = S.head (stream t)
287-- | /O(1)/ Returns the first character and rest of a 'Text', or
288-- 'Nothing' if empty. Subject to fusion.
289uncons :: Text -> Maybe (Char, Text)
290uncons t@(Text arr off len)
292 | otherwise = Just (c, textP arr (off+d) (len-d))
293 where (c,d) = iter t 0
294{-# INLINE [1] uncons #-}
296-- | Lifted from Control.Arrow and specialized.
297second :: (b -> c) -> (a,b) -> (a,c)
298second f (a, b) = (a, f b)
301"TEXT uncons -> fused" [~1] forall t.
302 uncons t = fmap (second unstream) (S.uncons (stream t))
303"TEXT uncons -> unfused" [1] forall t.
304 fmap (second unstream) (S.uncons (stream t)) = uncons t
307-- | /O(1)/ Returns the last character of a 'Text', which must be
308-- non-empty. Subject to fusion.
310last (Text arr off len)
311 | len <= 0 = emptyError "last"
312 | n < 0xDC00 || n > 0xDFFF = unsafeChr n
313 | otherwise = U16.chr2 n0 n
314 where n = A.unsafeIndex arr (off+len-1)
315 n0 = A.unsafeIndex arr (off+len-2)
316{-# INLINE [1] last #-}
319"TEXT last -> fused" [~1] forall t.
320 last t = S.last (stream t)
321"TEXT last -> unfused" [1] forall t.
322 S.last (stream t) = last t
325-- | /O(1)/ Returns all characters after the head of a 'Text', which
326-- must be non-empty. Subject to fusion.
328tail t@(Text arr off len)
329 | len <= 0 = emptyError "tail"
330 | otherwise = textP arr (off+d) (len-d)
332{-# INLINE [1] tail #-}
335"TEXT tail -> fused" [~1] forall t.
336 tail t = unstream (S.tail (stream t))
337"TEXT tail -> unfused" [1] forall t.
338 unstream (S.tail (stream t)) = tail t
341-- | /O(1)/ Returns all but the last character of a 'Text', which must
342-- be non-empty. Subject to fusion.
344init (Text arr off len) | len <= 0 = emptyError "init"
345 | n >= 0xDC00 && n <= 0xDFFF = textP arr off (len-2)
346 | otherwise = textP arr off (len-1)
348 n = A.unsafeIndex arr (off+len-1)
349{-# INLINE [1] init #-}
352"TEXT init -> fused" [~1] forall t.
353 init t = unstream (S.init (stream t))
354"TEXT init -> unfused" [1] forall t.
355 unstream (S.init (stream t)) = init t
358-- | /O(1)/ Tests whether a 'Text' is empty or not. Subject to
361null (Text _arr _off len) = assert (len >= 0) $ len <= 0
362{-# INLINE [1] null #-}
365"TEXT null -> fused" [~1] forall t.
366 null t = S.null (stream t)
367"TEXT null -> unfused" [1] forall t.
368 S.null (stream t) = null t
371-- | /O(n)/ Returns the number of characters in a 'Text'.
374length t = S.length (stream t)
377-- -----------------------------------------------------------------------------
379-- | /O(n)/ 'map' @f@ @t@ is the 'Text' obtained by applying @f@ to
380-- each element of @t@. Subject to fusion.
381map :: (Char -> Char) -> Text -> Text
382map f t = unstream (S.map f (stream t))
383{-# INLINE [1] map #-}
385-- | /O(n)/ The 'intercalate' function takes a 'Text' and a list of
386-- 'Text's and concatenates the list after interspersing the first
387-- argument between each element of the list.
388intercalate :: Text -> [Text] -> Text
389intercalate t ts = unstream (S.intercalate (stream t) (L.map stream ts))
390{-# INLINE intercalate #-}
392-- | /O(n)/ The 'intersperse' function takes a character and places it
393-- between the characters of a 'Text'. Subject to fusion.
394intersperse :: Char -> Text -> Text
395intersperse c t = unstream (S.intersperse c (stream t))
396{-# INLINE intersperse #-}
398-- | /O(n)/ Reverse the characters of a string. Subject to fusion.
399reverse :: Text -> Text
400reverse t = S.reverse (stream t)
401{-# INLINE reverse #-}
403-- | /O(m)*O(n)/ Replace every occurrence of one substring with another.
404replace :: Text -- ^ Text to search for
405 -> Text -- ^ Replacement text
406 -> Text -- ^ Input text
408replace s d = intercalate d . split s
409{-# INLINE replace #-}
411-- ----------------------------------------------------------------------------
412-- ** Case conversions (folds)
416-- When case converting 'Text' values, do not use combinators like
417-- @map toUpper@ to case convert each character of a string
418-- individually, as this gives incorrect results according to the
419-- rules of some writing systems. The whole-string case conversion
420-- functions from this module, such as @toUpper@, obey the correct
421-- case conversion rules. As a result, these functions may map one
422-- input character to two or three output characters. For examples,
423-- see the documentation of each function.
425-- | /O(n)/ Convert a string to folded case. This function is mainly
426-- useful for performing caseless (also known as case insensitive)
427-- string comparisons.
429-- A string @x@ is a caseless match for a string @y@ if and only if:
431-- @toCaseFold x == toCaseFold y@
433-- The result string may be longer than the input string, and may
434-- differ from applying 'toLower' to the input string. For instance,
435-- the Armenian small ligature \"ﬓ\" (men now, U+FB13) is case
436-- folded to the sequence \"մ\" (men, U+0574) followed by
437-- \"ն\" (now, U+0576), while the Greek \"µ\" (micro sign,
438-- U+00B5) is case folded to \"μ\" (small letter mu, U+03BC)
440toCaseFold :: Text -> Text
441toCaseFold t = unstream (S.toCaseFold (stream t))
442{-# INLINE [0] toCaseFold #-}
444-- | /O(n)/ Convert a string to lower case, using simple case
445-- conversion. The result string may be longer than the input string.
446-- For instance, \"İ\" (Latin capital letter I with dot above,
447-- U+0130) maps to the sequence \"i\" (Latin small letter i, U+0069) followed
448-- by \" ̇\" (combining dot above, U+0307).
449toLower :: Text -> Text
450toLower t = unstream (S.toLower (stream t))
451{-# INLINE toLower #-}
453-- | /O(n)/ Convert a string to upper case, using simple case
454-- conversion. The result string may be longer than the input string.
455-- For instance, the German \"ß\" (eszett, U+00DF) maps to the
456-- two-letter sequence \"SS\".
457toUpper :: Text -> Text
458toUpper t = unstream (S.toUpper (stream t))
459{-# INLINE toUpper #-}
461-- | /O(n)/ Left-justify a string to the given length, using the
462-- specified fill character on the right. Subject to fusion. Examples:
464-- > justifyLeft 7 'x' "foo" == "fooxxxx"
465-- > justifyLeft 3 'x' "foobar" == "foobar"
466justifyLeft :: Int -> Char -> Text -> Text
469 | otherwise = t `append` replicateChar (k-len) c
471{-# INLINE [1] justifyLeft #-}
474"TEXT justifyLeft -> fused" [~1] forall k c t.
475 justifyLeft k c t = unstream (S.justifyLeftI k c (stream t))
476"TEXT justifyLeft -> unfused" [1] forall k c t.
477 unstream (S.justifyLeftI k c (stream t)) = justifyLeft k c t
480-- | /O(n)/ Right-justify a string to the given length, using the
481-- specified fill character on the left. Examples:
483-- > justifyRight 7 'x' "bar" == "xxxxbar"
484-- > justifyRight 3 'x' "foobar" == "foobar"
485justifyRight :: Int -> Char -> Text -> Text
488 | otherwise = replicateChar (k-len) c `append` t
490{-# INLINE justifyRight #-}
492-- | /O(n)/ Center a string to the given length, using the
493-- specified fill character on either side. Examples:
495-- > center 8 'x' "HS" = "xxxHSxxx"
496center :: Int -> Char -> Text -> Text
499 | otherwise = replicateChar l c `append` t `append` replicateChar r c
506-- | /O(n)/ The 'transpose' function transposes the rows and columns
507-- of its 'Text' argument. Note that this function uses 'pack',
508-- 'unpack', and the list version of transpose, and is thus not very
510transpose :: [Text] -> [Text]
511transpose ts = P.map pack (L.transpose (P.map unpack ts))
513-- -----------------------------------------------------------------------------
514-- * Reducing 'Text's (folds)
516-- | /O(n)/ 'foldl', applied to a binary operator, a starting value
517-- (typically the left-identity of the operator), and a 'Text',
518-- reduces the 'Text' using the binary operator, from left to right.
520foldl :: (b -> Char -> b) -> b -> Text -> b
521foldl f z t = S.foldl f z (stream t)
524-- | /O(n)/ A strict version of 'foldl'. Subject to fusion.
525foldl' :: (b -> Char -> b) -> b -> Text -> b
526foldl' f z t = S.foldl' f z (stream t)
529-- | /O(n)/ A variant of 'foldl' that has no starting value argument,
530-- and thus must be applied to a non-empty 'Text'. Subject to fusion.
531foldl1 :: (Char -> Char -> Char) -> Text -> Char
532foldl1 f t = S.foldl1 f (stream t)
535-- | /O(n)/ A strict version of 'foldl1'. Subject to fusion.
536foldl1' :: (Char -> Char -> Char) -> Text -> Char
537foldl1' f t = S.foldl1' f (stream t)
538{-# INLINE foldl1' #-}
540-- | /O(n)/ 'foldr', applied to a binary operator, a starting value
541-- (typically the right-identity of the operator), and a 'Text',
542-- reduces the 'Text' using the binary operator, from right to left.
544foldr :: (Char -> b -> b) -> b -> Text -> b
545foldr f z t = S.foldr f z (stream t)
548-- | /O(n)/ A variant of 'foldr' that has no starting value argument,
549-- and thust must be applied to a non-empty 'Text'. Subject to
551foldr1 :: (Char -> Char -> Char) -> Text -> Char
552foldr1 f t = S.foldr1 f (stream t)
555-- -----------------------------------------------------------------------------
558-- | /O(n)/ Concatenate a list of 'Text's. Subject to fusion.
559concat :: [Text] -> Text
560concat ts = unstream (S.concat (L.map stream ts))
563-- | /O(n)/ Map a function over a 'Text' that results in a 'Text', and
564-- concatenate the results. Subject to fusion.
566-- Note: if in 'concatMap' @f@ @t@, @f@ is defined in terms of fusible
567-- functions, it will also be fusible.
568concatMap :: (Char -> Text) -> Text -> Text
569concatMap f t = unstream (S.concatMap (stream . f) (stream t))
570{-# INLINE concatMap #-}
572-- | /O(n)/ 'any' @p@ @t@ determines whether any character in the
573-- 'Text' @t@ satisifes the predicate @p@. Subject to fusion.
574any :: (Char -> Bool) -> Text -> Bool
575any p t = S.any p (stream t)
578-- | /O(n)/ 'all' @p@ @t@ determines whether all characters in the
579-- 'Text' @t@ satisify the predicate @p@. Subject to fusion.
580all :: (Char -> Bool) -> Text -> Bool
581all p t = S.all p (stream t)
584-- | /O(n)/ 'maximum' returns the maximum value from a 'Text', which
585-- must be non-empty. Subject to fusion.
586maximum :: Text -> Char
587maximum t = S.maximum (stream t)
588{-# INLINE maximum #-}
590-- | /O(n)/ 'minimum' returns the minimum value from a 'Text', which
591-- must be non-empty. Subject to fusion.
592minimum :: Text -> Char
593minimum t = S.minimum (stream t)
594{-# INLINE minimum #-}
596-- -----------------------------------------------------------------------------
599-- | /O(n)/ 'scanl' is similar to 'foldl', but returns a list of
600-- successive reduced values from the left. Subject to fusion.
602-- > scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
606-- > last (scanl f z xs) == foldl f z xs.
607scanl :: (Char -> Char -> Char) -> Char -> Text -> Text
608scanl f z t = unstream (S.scanl f z (stream t))
611-- | /O(n)/ 'scanl1' is a variant of 'scanl' that has no starting
612-- value argument. Subject to fusion.
614-- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
615scanl1 :: (Char -> Char -> Char) -> Text -> Text
616scanl1 f t | null t = empty
617 | otherwise = scanl f (unsafeHead t) (unsafeTail t)
620-- | /O(n)/ 'scanr' is the right-to-left dual of 'scanl'.
622-- > scanr f v == reverse . scanl (flip f) v . reverse
623scanr :: (Char -> Char -> Char) -> Char -> Text -> Text
624scanr f z = S.reverse . S.reverseScanr f z . reverseStream
627-- | /O(n)/ 'scanr1' is a variant of 'scanr' that has no starting
628-- value argument. Subject to fusion.
629scanr1 :: (Char -> Char -> Char) -> Text -> Text
630scanr1 f t | null t = empty
631 | otherwise = scanr f (last t) (init t)
634-- | /O(n)/ Like a combination of 'map' and 'foldl'. Applies a
635-- function to each element of a 'Text', passing an accumulating
636-- parameter from left to right, and returns a final 'Text'.
637mapAccumL :: (a -> Char -> (a,Char)) -> a -> Text -> (a, Text)
638mapAccumL f s t = case uncons t of
639 Nothing -> (s, empty)
640 Just (x, xs) -> (s'', cons y ys)
641 where (s', y ) = f s x
642 (s'',ys) = mapAccumL f s' xs
644-- | The 'mapAccumR' function behaves like a combination of 'map' and
645-- 'foldr'; it applies a function to each element of a 'Text', passing
646-- an accumulating parameter from right to left, and returning a final
647-- value of this accumulator together with the new 'Text'.
648mapAccumR :: (a -> Char -> (a,Char)) -> a -> Text -> (a, Text)
649mapAccumR f s t = case uncons t of
650 Nothing -> (s, empty)
651 Just (x, xs) -> (s'', cons y ys)
652 where (s'',y ) = f s' x
653 (s', ys) = mapAccumR f s xs
655-- -----------------------------------------------------------------------------
656-- ** Generating and unfolding 'Text's
658-- | /O(n*m)/ 'replicate' @n@ @t@ is a 'Text' consisting of the input
659-- @t@ repeated @n@ times. Subject to fusion.
660replicate :: Int -> Text -> Text
661replicate n t = unstream (S.replicateI (fromIntegral n) (S.stream t))
662{-# INLINE [1] replicate #-}
665"TEXT replicate/singleton -> replicateChar" [~1] forall n c.
666 replicate n (singleton c) = replicateChar n c
669-- | /O(n)/ 'replicateChar' @n@ @c@ is a 'Text' of length @n@ with @c@ the
670-- value of every element. Subject to fusion.
671replicateChar :: Int -> Char -> Text
672replicateChar n c = unstream (S.replicateCharI n c)
674-- | /O(n)/, where @n@ is the length of the result. The 'unfoldr'
675-- function is analogous to the List 'L.unfoldr'. 'unfoldr' builds a
676-- 'Text' from a seed value. The function takes the element and
677-- returns 'Nothing' if it is done producing the 'Text', otherwise
678-- 'Just' @(a,b)@. In this case, @a@ is the next 'Char' in the
679-- string, and @b@ is the seed value for further production. Subject
681unfoldr :: (a -> Maybe (Char,a)) -> a -> Text
682unfoldr f s = unstream (S.unfoldr f s)
683{-# INLINE unfoldr #-}
685-- | /O(n)/ Like 'unfoldr', 'unfoldrN' builds a 'Text' from a seed
686-- value. However, the length of the result should be limited by the
687-- first argument to 'unfoldrN'. This function is more efficient than
688-- 'unfoldr' when the maximum length of the result is known and
689-- correct, otherwise its performance is similar to 'unfoldr'. Subject
691unfoldrN :: Int -> (a -> Maybe (Char,a)) -> a -> Text
692unfoldrN n f s = unstream (S.unfoldrN n f s)
693{-# INLINE unfoldrN #-}
695-- -----------------------------------------------------------------------------
698-- | /O(n)/ 'take' @n@, applied to a 'Text', returns the prefix of the
699-- 'Text' of length @n@, or the 'Text' itself if @n@ is greater than
700-- the length of the Text. Subject to fusion.
701take :: Int -> Text -> Text
702take n t@(Text arr off len)
705 | otherwise = Text arr off (loop 0 0)
708 | i >= len || cnt >= n = i
709 | otherwise = loop (i+d) (cnt+1)
711{-# INLINE [1] take #-}
714"TEXT take -> fused" [~1] forall n t.
715 take n t = unstream (S.take n (stream t))
716"TEXT take -> unfused" [1] forall n t.
717 unstream (S.take n (stream t)) = take n t
720-- | /O(n)/ 'drop' @n@, applied to a 'Text', returns the suffix of the
721-- 'Text' of length @n@, or the empty 'Text' if @n@ is greater than the
722-- length of the 'Text'. Subject to fusion.
723drop :: Int -> Text -> Text
724drop n t@(Text arr off len)
727 | otherwise = loop 0 0
729 | i >= len || cnt >= n = Text arr (off+i) (len-i)
730 | otherwise = loop (i+d) (cnt+1)
732{-# INLINE [1] drop #-}
735"TEXT drop -> fused" [~1] forall n t.
736 drop n t = unstream (S.drop n (stream t))
737"TEXT drop -> unfused" [1] forall n t.
738 unstream (S.drop n (stream t)) = drop n t
741-- | /O(n)/ 'takeWhile', applied to a predicate @p@ and a 'Text',
742-- returns the longest prefix (possibly empty) of elements that
743-- satisfy @p@. Subject to fusion.
744takeWhile :: (Char -> Bool) -> Text -> Text
745takeWhile p t@(Text arr off len) = loop 0
746 where loop !i | i >= len = t
748 | otherwise = textP arr off i
749 where (c,d) = iter t i
750{-# INLINE [1] takeWhile #-}
753"TEXT takeWhile -> fused" [~1] forall p t.
754 takeWhile p t = unstream (S.takeWhile p (stream t))
755"TEXT takeWhile -> unfused" [1] forall p t.
756 unstream (S.takeWhile p (stream t)) = takeWhile p t
759-- | /O(n)/ 'dropWhile' @p@ @t@ returns the suffix remaining after
760-- 'takeWhile' @p@ @t@. Subject to fusion.
761dropWhile :: (Char -> Bool) -> Text -> Text
762dropWhile p t@(Text arr off len) = loop 0 0
763 where loop !i !l | l >= len = empty
764 | p c = loop (i+d) (l+d)
765 | otherwise = Text arr (off+i) (len-l)
766 where (c,d) = iter t i
767{-# INLINE [1] dropWhile #-}
770"TEXT dropWhile -> fused" [~1] forall p t.
771 dropWhile p t = unstream (S.dropWhile p (stream t))
772"TEXT dropWhile -> unfused" [1] forall p t.
773 unstream (S.dropWhile p (stream t)) = dropWhile p t
776-- | /O(n)/ 'dropWhileEnd' @p@ @t@ returns the prefix remaining after
777-- dropping characters that fail the predicate @p@ from the end of
778-- @t@. Subject to fusion.
781-- > dropWhileEnd (=='.') "foo..." == "foo"
782dropWhileEnd :: (Char -> Bool) -> Text -> Text
783dropWhileEnd p t@(Text arr off len) = loop (len-1) len
784 where loop !i !l | l <= 0 = empty
785 | p c = loop (i+d) (l+d)
786 | otherwise = Text arr off l
787 where (c,d) = reverseIter t i
788{-# INLINE [1] dropWhileEnd #-}
791"TEXT dropWhileEnd -> fused" [~1] forall p t.
792 dropWhileEnd p t = S.reverse (S.dropWhile p (S.reverseStream t))
793"TEXT dropWhileEnd -> unfused" [1] forall p t.
794 S.reverse (S.dropWhile p (S.reverseStream t)) = dropWhileEnd p t
797-- | /O(n)/ 'dropAround' @p@ @t@ returns the substring remaining after
798-- dropping characters that fail the predicate @p@ from both the
799-- beginning and end of @t@. Subject to fusion.
800dropAround :: (Char -> Bool) -> Text -> Text
801dropAround p = dropWhile p . dropWhileEnd p
802{-# INLINE [1] dropAround #-}
804-- | /O(n)/ Remove leading white space from a string. Equivalent to:
806-- > dropWhile isSpace
807stripStart :: Text -> Text
808stripStart = dropWhile isSpace
809{-# INLINE [1] stripStart #-}
811-- | /O(n)/ Remove trailing white space from a string. Equivalent to:
813-- > dropWhileEnd isSpace
814stripEnd :: Text -> Text
815stripEnd = dropWhileEnd isSpace
816{-# INLINE [1] stripEnd #-}
818-- | /O(n)/ Remove leading and trailing white space from a string.
821-- > dropAround isSpace
823strip = dropAround isSpace
824{-# INLINE [1] strip #-}
826-- | /O(n)/ 'splitAt' @n t@ returns a pair whose first element is a
827-- prefix of @t@ of length @n@, and whose second is the remainder of
828-- the string. It is equivalent to @('take' n t, 'drop' n t)@.
829splitAt :: Int -> Text -> (Text, Text)
830splitAt n t@(Text arr off len)
831 | n <= 0 = (empty, t)
832 | n >= len = (t, empty)
833 | otherwise = (Text arr off k, Text arr (off+k) (len-k))
836 | i >= len || cnt >= n = i
837 | otherwise = loop (i+d) (cnt+1)
839{-# INLINE splitAt #-}
841-- | /O(n)/ 'span', applied to a predicate @p@ and text @t@, returns a
842-- pair whose first element is the longest prefix (possibly empty) of
843-- @t@ of elements that satisfy @p@, and whose second is the remainder
845span :: (Char -> Bool) -> Text -> (Text, Text)
846span p t@(Text arr off len) = (textP arr off k, textP arr (off+k) (len-k))
848 loop !i | i >= len || not (p c) = i
849 | otherwise = loop (i+d)
850 where (c,d) = iter t i
853-- | /O(n)/ 'break' is like 'span', but the prefix returned is over
854-- elements that fail the predicate @p@.
855break :: (Char -> Bool) -> Text -> (Text, Text)
856break p = span (not . p)
859-- | /O(n)/ Group characters in a string according to a predicate.
860groupBy :: (Char -> Char -> Bool) -> Text -> [Text]
863 loop t@(Text arr off len)
865 | otherwise = text arr off n : loop (text arr (off+n) (len-n))
866 where (c,d) = iter t 0
867 n = d + findAIndexOrEnd (not . p c) (Text arr (off+d) (len-d))
869-- | Returns the /array/ index (in units of 'Word16') at which a
870-- character may be found. This is /not/ the same as the logical
871-- index returned by e.g. 'findIndex'.
872findAIndexOrEnd :: (Char -> Bool) -> Text -> Int
873findAIndexOrEnd q t@(Text _arr _off len) = go 0
874 where go !i | i >= len || q c = i
875 | otherwise = go (i+d)
876 where (c,d) = iter t i
878-- | /O(n)/ Group characters in a string by equality.
879group :: Text -> [Text]
882-- | /O(n)/ Return all initial segments of the given 'Text', shortest
884inits :: Text -> [Text]
885inits t@(Text arr off len) = loop 0
886 where loop i | i >= len = [t]
887 | otherwise = Text arr off i : loop (i + iter_ t i)
889-- | /O(n)/ Return all final segments of the given 'Text', longest
891tails :: Text -> [Text]
892tails t | null t = [empty]
893 | otherwise = t : tails (unsafeTail t)
897-- Splitting functions in this library do not perform character-wise
898-- copies to create substrings; they just construct new 'Text's that
899-- are slices of the original.
901-- | /O(m)*O(n)/ Break a 'Text' into pieces separated by the first
902-- 'Text' argument, consuming the delimiter. An empty delimiter is
903-- invalid, and will cause an error to be raised.
907-- > split "\r\n" "a\r\nb\r\nd\r\ne" == ["a","b","d","e"]
908-- > split "aaa" "aaaXaaaXaaaXaaa" == ["","X","X","X",""]
909-- > split "x" "x" == ["",""]
913-- > intercalate s . split s == id
914-- > split (singleton c) == splitWith (==c)
915split :: Text -- ^ Text to split on
916 -> Text -- ^ Input text
919 | l == 0 = emptyError "split"
920 | l == 1 = splitWith (== (unsafeHead pat)) src0
921 | otherwise = go src0
924 go src = search 0 src
927 | null s = [src] -- not found
928 | pat `isPrefixOf` s = take n src : go (drop l s)
929 | otherwise = search (n+1) (unsafeTail s)
930{-# INLINE [1] split #-}
933"TEXT split/singleton -> splitWith/==" [~1] forall c t.
934 split (singleton c) t = splitWith (==c) t
937-- | /O(m)*O(n)/ Break a 'Text' into pieces at most @k@ times,
938-- treating the first 'Text' argument as the delimiter to break on,
939-- and consuming the delimiter. The last element of the list contains
940-- the remaining text after the number of times to split has been
941-- reached. A value of zero or less for @k@ causes no splitting to
942-- occur. An empty delimiter is invalid, and will cause an error to be
947-- > splitTimes 0 "//" "a//b//c" == ["a//b//c"]
948-- > splitTimes 2 ":" "a:b:c:d:e" == ["a","b","c:d:e"]
949-- > splitTimes 100 "???" "a????b" == ["a","?b"]
953-- > intercalate s . splitTimes k s == id
954splitTimes :: Int -- ^ Maximum number of times to split
955 -> Text -- ^ Text to split on
956 -> Text -- ^ Input text
960 | l == 0 = emptyError "splitTimes"
961 | otherwise = go k src0
964 go !i src = search 0 src
967 | i == 0 || null s = [src] -- not found or limit reached
968 | pat `isPrefixOf` s = take n src : go (i-1) (drop l s)
969 | otherwise = search (n+1) (unsafeTail s)
970{-# INLINE splitTimes #-}
972-- | /O(m)*O(n)/ Break a 'Text' into pieces at most @k@ times, like
973-- 'splitTimes', but start from the end of the input and work towards
978-- > splitTimes 2 "::" "a::b::c::d::e" == ["a","b","c::d::e"]
979-- > splitTimesEnd 2 "::" "a::b::c::d::e" == ["a::b::c","d","e"]
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-- > splitWith (=='a') "aabbaca" == ["","","bb","c",""]
994-- > splitWith (=='a') "" == [""]
995splitWith :: (Char -> Bool) -> Text -> [Text]
996splitWith _ t@(Text _off _arr 0) = [t]
997splitWith p t = loop t
998 where loop s | null s' = [l]
999 | otherwise = l : loop (unsafeTail s')
1000 where (l, s') = break p s
1001{-# INLINE splitWith #-}
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 'find' function takes a predicate and a 'Text',
1032-- and returns the first element in matching the predicate, or 'Nothing'
1033-- if there is no such element.
1034find :: (Char -> Bool) -> Text -> Maybe Char
1035find p t = S.find p (stream t)
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 #-}
1055-------------------------------------------------------------------------------
1056-- ** Indexing 'Text's
1060-- If you think of a 'Text' value as an array of 'Char' values (which
1061-- it is not), you run the risk of writing inefficient code.
1063-- An idiom that is common in some languages is to find the numeric
1064-- offset of a character or substring, then use that number to split
1065-- or trim the searched string. With a 'Text' value, this approach
1066-- would require two /O(n)/ operations: one to perform the search, and
1067-- one to operate from wherever the search ended.
1069-- For example, suppose you have a string that you want to split on
1070-- the substring @\"::\"@, such as @\"foo::bar::quux\"@. Instead of
1071-- searching for the index of @\"::\"@ and taking the substrings
1072-- before and after that index, you would instead use @splitTimes 1
1075-- | /O(n)/ 'Text' index (subscript) operator, starting from 0.
1076index :: Text -> Int -> Char
1077index t n = S.index (stream t) n
1080-- | /O(n)/ The 'findIndex' function takes a predicate and a 'Text'
1081-- and returns the index of the first element in the 'Text' satisfying
1082-- the predicate. Subject to fusion.
1083findIndex :: (Char -> Bool) -> Text -> Maybe Int
1084findIndex p t = S.findIndex p (stream t)
1085{-# INLINE findIndex #-}
1087-- | The 'findIndices' function extends 'findIndex', by returning the
1088-- indices of all elements satisfying the predicate, in ascending
1089-- order. Subject to fusion.
1090findIndices :: (Char -> Bool) -> Text -> [Int]
1091findIndices p t = S.findIndices p (stream t)
1092{-# INLINE findIndices #-}
1094-- | /O(n)/ The 'elemIndex' function returns the index of the first
1095-- element in the given 'Text' which is equal to the query element, or
1096-- 'Nothing' if there is no such element. Subject to fusion.
1097elemIndex :: Char -> Text -> Maybe Int
1098elemIndex c t = S.elemIndex c (stream t)
1099{-# INLINE elemIndex #-}
1101-- | /O(n)/ The 'elemIndices' function returns the index of every
1102-- element in the given 'Text' which is equal to the query
1103-- element. Subject to fusion.
1104elemIndices :: Char -> Text -> [Int]
1105elemIndices c t = S.elemIndices c (stream t)
1106{-# INLINE elemIndices #-}
1108-- | /O(n*m)/ The 'count' function returns the number of times the
1109-- query string appears in the given 'Text'. An empty query string is
1110-- invalid, and will cause an error to be raised.
1111count :: Text -> Text -> Int
1113 | l == 0 = emptyError "count"
1114 | l == 1 = countChar (unsafeHead pat) src0
1115 | otherwise = go 0 src0
1118 go !n src = search src
1120 search s | null s = n
1121 | pat `isPrefixOf` s = go (n+1) (drop l s)
1122 | otherwise = search (unsafeTail s)
1123{-# INLINE [1] count #-}
1126"TEXT count/singleton -> countChar" [~1] forall c t.
1127 count (singleton c) t = countChar c t
1130-- | /O(n)/ The 'countChar' function returns the number of times the
1131-- query element appears in the given 'Text'. Subject to fusion.
1132countChar :: Char -> Text -> Int
1133countChar c t = S.countChar c (stream t)
1134{-# INLINE countChar #-}
1136-------------------------------------------------------------------------------
1139-- | /O(n)/ 'zip' takes two 'Text's and returns a list of
1140-- corresponding pairs of bytes. If one input 'Text' is short,
1141-- excess elements of the longer 'Text' are discarded. This is
1142-- equivalent to a pair of 'unpack' operations.
1143zip :: Text -> Text -> [(Char,Char)]
1144zip a b = S.unstreamList $ S.zipWith (,) (stream a) (stream b)
1145{-# INLINE [0] zip #-}
1147-- | /O(n)/ 'zipWith' generalises 'zip' by zipping with the function
1148-- given as the first argument, instead of a tupling function.
1149zipWith :: (Char -> Char -> Char) -> Text -> Text -> Text
1150zipWith f t1 t2 = unstream (S.zipWith f (stream t1) (stream t2))
1151{-# INLINE [0] zipWith #-}
1153-- | /O(n)/ Breaks a 'Text' up into a list of words, delimited by 'Char's
1154-- representing white space.
1155words :: Text -> [Text]
1156words t@(Text arr off len) = loop 0 0
1159 | n >= len = if start == n
1161 else [Text arr (start+off) (n-start)]
1164 then loop (start+1) (start+1)
1165 else Text arr (start+off) (n-start) : loop (n+d) (n+d)
1166 | otherwise = loop start (n+d)
1167 where (c,d) = iter t n
1170-- | /O(n)/ Breaks a 'Text' up into a list of 'Text's at
1171-- newline 'Char's. The resulting strings do not contain newlines.
1172lines :: Text -> [Text]
1173lines ps | null ps = []
1174 | otherwise = h : if null t
1176 else lines (unsafeTail t)
1177 where (h,t) = span (/= '\n') ps
1180-- | /O(n)/ Portably breaks a 'Text' up into a list of 'Text's at line
1183-- A line boundary is considered to be either a line feed, a carriage
1184-- return immediately followed by a line feed, or a carriage return.
1185-- This accounts for both Unix and Windows line ending conventions,
1186-- and for the old convention used on Mac OS 9 and earlier.
1188lines' :: Text -> [Text]
1189lines' ps | null ps = []
1190 | otherwise = h : case uncons t of
1193 | c == '\n' -> lines t'
1194 | c == '\r' -> case uncons t' of
1195 Just ('\n',t'') -> lines t''
1197 where (h,t) = span notEOL ps
1198 notEOL c = c /= '\n' && c /= '\r'
1199{-# INLINE lines' #-}
1202-- | /O(n)/ Joins lines, after appending a terminating newline to
1204unlines :: [Text] -> Text
1205unlines = concat . L.map (`snoc` '\n')
1206{-# INLINE unlines #-}
1208-- | /O(n)/ Joins words using single space characters.
1209unwords :: [Text] -> Text
1210unwords = intercalate (singleton ' ')
1211{-# INLINE unwords #-}
1213-- | /O(n)/ The 'isPrefixOf' function takes two 'Text's and returns
1214-- 'True' iff the first is a prefix of the second. This function is
1215-- subject to fusion.
1216isPrefixOf :: Text -> Text -> Bool
1217isPrefixOf a@(Text _ _ alen) b@(Text _ _ blen) =
1218 alen <= blen && S.isPrefixOf (stream a) (stream b)
1219{-# INLINE [1] isPrefixOf #-}
1222"TEXT isPrefixOf -> fused" [~1] forall s t.
1223 isPrefixOf s t = S.isPrefixOf (stream s) (stream t)
1224"TEXT isPrefixOf -> unfused" [1] forall s t.
1225 S.isPrefixOf (stream s) (stream t) = isPrefixOf s t
1228-- | /O(n)/ The 'isSuffixOf' function takes two 'Text's and returns
1229-- 'True' iff the first is a suffix of the second.
1230isSuffixOf :: Text -> Text -> Bool
1231isSuffixOf a@(Text _aarr _aoff alen) b@(Text barr boff blen) =
1233 where d = blen - alen
1235 | otherwise = Text barr (boff+d) alen
1236{-# INLINE isSuffixOf #-}
1238-- | /O(n)/ The 'isInfixOf' function takes two 'Text's and returns
1239-- 'True' iff the first is contained, wholly and intact, anywhere
1240-- within the second.
1241isInfixOf :: Text -> Text -> Bool
1242isInfixOf needle haystack = L.any (isPrefixOf needle) (tails haystack)
1243{-# INLINE isInfixOf #-}
1244-- TODO: a better implementation
1246emptyError :: String -> a
1247emptyError 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