{-# LANGUAGE CPP, NoImplicitPrelude #-} {-# LANGUAGE BangPatterns #-} {-# LANGUAGE Trustworthy #-} module Data.List.Compat ( module Base #if !(MIN_VERSION_base(4,21,0)) , compareLength , inits1 , tails1 #endif #if MIN_VERSION_base(4,18,0) && !(MIN_VERSION_base(4,20,0)) , List #endif #if !(MIN_VERSION_base(4,19,0)) , (!?) , unsnoc #endif #if !(MIN_VERSION_base(4,15,0)) , singleton #endif #if !(MIN_VERSION_base(4,11,0)) , iterate' #endif ) where import Data.List as Base #if MIN_VERSION_base(4,18,0) && !(MIN_VERSION_base(4,20,0)) import GHC.List (List) #endif #if !(MIN_VERSION_base(4,21,0)) import Data.List.NonEmpty (NonEmpty(..)) import GHC.Exts (build) import Prelude.Compat hiding (foldr, null) #endif #if !(MIN_VERSION_base(4,11,0)) -- | 'iterate\'' is the strict version of 'iterate'. -- -- It ensures that the result of each application of force to weak head normal -- form before proceeding. {-# NOINLINE [1] iterate' #-} iterate' :: (a -> a) -> a -> [a] iterate' f x = let x' = f x in x' `seq` (x : iterate' f x') {-# INLINE [0] iterate'FB #-} -- See Note [Inline FB functions] iterate'FB :: (a -> b -> b) -> (a -> a) -> a -> b iterate'FB c f x0 = go x0 where go x = let x' = f x in x' `seq` (x `c` go x') {-# RULES "iterate'" [~1] forall f x. iterate' f x = build (\c _n -> iterate'FB c f x) "iterate'FB" [1] iterate'FB (:) = iterate' #-} #endif #if !(MIN_VERSION_base(4,15,0)) -- | Produce singleton list. -- -- >>> singleton True -- [True] -- -- /Since: 4.14.0.0/ -- singleton :: a -> [a] singleton x = [x] #endif #if !(MIN_VERSION_base(4,19,0)) infixl 9 !? -- | List index (subscript) operator, starting from 0. Returns 'Nothing' -- if the index is out of bounds -- -- >>> ['a', 'b', 'c'] !? 0 -- Just 'a' -- >>> ['a', 'b', 'c'] !? 2 -- Just 'c' -- >>> ['a', 'b', 'c'] !? 3 -- Nothing -- >>> ['a', 'b', 'c'] !? (-1) -- Nothing -- -- This is the total variant of the partial '!!' operator. -- -- WARNING: This function takes linear time in the index. (!?) :: [a] -> Int -> Maybe a {-# INLINABLE (!?) #-} xs !? n | n < 0 = Nothing | otherwise = foldr (\x r k -> case k of 0 -> Just x _ -> r (k-1)) (const Nothing) xs n -- | \(\mathcal{O}(n)\). Decompose a list into 'init' and 'last'. -- -- * If the list is empty, returns 'Nothing'. -- * If the list is non-empty, returns @'Just' (xs, x)@, -- where @xs@ is the 'init'ial part of the list and @x@ is its 'last' element. -- -- /Since: 4.19.0.0/ -- -- >>> unsnoc [] -- Nothing -- >>> unsnoc [1] -- Just ([],1) -- >>> unsnoc [1, 2, 3] -- Just ([1,2],3) -- -- Laziness: -- -- >>> fst <$> unsnoc [undefined] -- Just [] -- >>> head . fst <$> unsnoc (1 : undefined) -- Just *** Exception: Prelude.undefined -- >>> head . fst <$> unsnoc (1 : 2 : undefined) -- Just 1 -- -- 'unsnoc' is dual to 'uncons': for a finite list @xs@ -- -- > unsnoc xs = (\(hd, tl) -> (reverse tl, hd)) <$> uncons (reverse xs) -- unsnoc :: [a] -> Maybe ([a], a) -- The lazy pattern ~(a, b) is important to be productive on infinite lists -- and not to be prone to stack overflows. -- Expressing the recursion via 'foldr' provides for list fusion. unsnoc = foldr (\x -> Just . maybe ([], x) (\(~(a, b)) -> (x : a, b))) Nothing {-# INLINABLE unsnoc #-} #endif #if !(MIN_VERSION_base(4,21,0)) -- | Use 'compareLength' @xs@ @n@ as a safer and faster alternative -- to 'compare' ('length' @xs@) @n@. Similarly, it's better -- to write @compareLength xs 10 == LT@ instead of @length xs < 10@. -- -- While 'length' would force and traverse -- the entire spine of @xs@ (which could even diverge if @xs@ is infinite), -- 'compareLength' traverses at most @n@ elements to determine its result. -- -- >>> compareLength [] 0 -- EQ -- >>> compareLength [] 1 -- LT -- >>> compareLength ['a'] 1 -- EQ -- >>> compareLength ['a', 'b'] 1 -- GT -- >>> compareLength [0..] 100 -- GT -- >>> compareLength undefined (-1) -- GT -- >>> compareLength ('a' : undefined) 0 -- GT -- -- @since 4.21.0.0 -- compareLength :: [a] -> Int -> Ordering compareLength :: forall a. [a] -> Int -> Ordering compareLength [a] xs Int n | Int n Int -> Int -> Bool forall a. Ord a => a -> a -> Bool < Int 0 = Ordering GT | Bool otherwise = (a -> (Int -> Ordering) -> Int -> Ordering) -> (Int -> Ordering) -> [a] -> Int -> Ordering forall a b. (a -> b -> b) -> b -> [a] -> b forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b foldr (\a _ Int -> Ordering f Int m -> if Int m Int -> Int -> Bool forall a. Ord a => a -> a -> Bool > Int 0 then Int -> Ordering f (Int m Int -> Int -> Int forall a. Num a => a -> a -> a - Int 1) else Ordering GT) (\Int m -> if Int m Int -> Int -> Bool forall a. Ord a => a -> a -> Bool > Int 0 then Ordering LT else Ordering EQ) [a] xs Int n inits1, tails1 :: [a] -> [NonEmpty a] -- | The 'inits1' function returns all non-empty initial segments of the -- argument, shortest first. -- -- @since 4.21.0.0 -- -- ==== __Laziness__ -- -- Note that 'inits1' has the following strictness property: -- @inits1 (xs ++ _|_) = inits1 xs ++ _|_@ -- -- In particular, -- @inits1 _|_ = _|_@ -- -- ==== __Examples__ -- -- >>> inits1 "abc" -- ['a' :| "",'a' :| "b",'a' :| "bc"] -- -- >>> inits1 [] -- [] -- -- inits1 is productive on infinite lists: -- -- >>> take 3 $ inits1 [1..] -- [1 :| [],1 :| [2],1 :| [2,3]] inits1 :: forall a. [a] -> [NonEmpty a] inits1 [] = [] inits1 (a x : [a] xs) = ([a] -> NonEmpty a) -> [[a]] -> [NonEmpty a] forall a b. (a -> b) -> [a] -> [b] map (a x a -> [a] -> NonEmpty a forall a. a -> [a] -> NonEmpty a :|) ([a] -> [[a]] forall a. [a] -> [[a]] inits [a] xs) -- | \(\mathcal{O}(n)\). The 'tails1' function returns all non-empty final -- segments of the argument, longest first. -- -- @since 4.21.0.0 -- -- ==== __Laziness__ -- -- Note that 'tails1' has the following strictness property: -- @tails1 _|_ = _|_@ -- -- >>> tails1 undefined -- *** Exception: Prelude.undefined -- -- >>> drop 1 (tails1 [undefined, 1, 2]) -- [1 :| [2],2 :| []] -- -- ==== __Examples__ -- -- >>> tails1 "abc" -- ['a' :| "bc",'b' :| "c",'c' :| ""] -- -- >>> tails1 [1, 2, 3] -- [1 :| [2,3],2 :| [3],3 :| []] -- -- >>> tails1 [] -- [] {-# INLINABLE tails1 #-} tails1 :: forall a. [a] -> [NonEmpty a] tails1 [a] lst = (forall b. (NonEmpty a -> b -> b) -> b -> b) -> [NonEmpty a] forall a. (forall b. (a -> b -> b) -> b -> b) -> [a] build (\NonEmpty a -> b -> b c b n -> let tails1Go :: [a] -> b tails1Go [] = b n tails1Go (a x : [a] xs) = (a x a -> [a] -> NonEmpty a forall a. a -> [a] -> NonEmpty a :| [a] xs) NonEmpty a -> b -> b `c` [a] -> b tails1Go [a] xs in [a] -> b tails1Go [a] lst) #endif