{- |
The functions in this module process the list from the end.
They do not access elements at the beginning if not necessary.
You can apply the function only to infinite lists.
Use these functions if the list is short and the test is expensive.
-}
module Data.List.Reverse.StrictSpine where

import Data.Tuple.HT (mapFst, mapSnd, forcePair, )

import Prelude hiding (dropWhile, takeWhile, span, )


{- |
Like @reverse . List.dropWhile p . reverse@.
-}
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile p :: a -> Bool
p =
   (a -> [a] -> [a]) -> [a] -> [a] -> [a]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\x :: a
x xs :: [a]
xs -> if [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
xs Bool -> Bool -> Bool
&& a -> Bool
p a
x then [] else a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) []

{- |
Like @reverse . List.takeWhile p . reverse@.
-}
takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile p :: a -> Bool
p =
   (Bool, [a]) -> [a]
forall a b. (a, b) -> b
snd ((Bool, [a]) -> [a]) -> ([a] -> (Bool, [a])) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   (a -> (Bool, [a]) -> (Bool, [a]))
-> (Bool, [a]) -> [a] -> (Bool, [a])
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr
      (\x :: a
x xys :: (Bool, [a])
xys ->
         (if (Bool, [a]) -> Bool
forall a b. (a, b) -> a
fst (Bool, [a])
xys Bool -> Bool -> Bool
&& a -> Bool
p a
x then ([a] -> [a]) -> (Bool, [a]) -> (Bool, [a])
forall b c a. (b -> c) -> (a, b) -> (a, c)
mapSnd (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) else (Bool -> Bool) -> (Bool, [a]) -> (Bool, [a])
forall a c b. (a -> c) -> (a, b) -> (c, b)
mapFst (Bool -> Bool -> Bool
forall a b. a -> b -> a
const Bool
False)) (Bool, [a])
xys)
      (Bool
True, [])

{- |
@span p xs == (dropWhile p xs, takeWhile p xs)@
-}
span :: (a -> Bool) -> [a] -> ([a], [a])
span :: (a -> Bool) -> [a] -> ([a], [a])
span p :: a -> Bool
p =
   ([a], [a]) -> ([a], [a])
forall a b. (a, b) -> (a, b)
forcePair (([a], [a]) -> ([a], [a]))
-> ([a] -> ([a], [a])) -> [a] -> ([a], [a])
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   (a -> ([a], [a]) -> ([a], [a])) -> ([a], [a]) -> [a] -> ([a], [a])
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr
      (\x :: a
x xys :: ([a], [a])
xys ->
         (if [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null (([a], [a]) -> [a]
forall a b. (a, b) -> a
fst ([a], [a])
xys) Bool -> Bool -> Bool
&& a -> Bool
p a
x then ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall b c a. (b -> c) -> (a, b) -> (a, c)
mapSnd else ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall a c b. (a -> c) -> (a, b) -> (c, b)
mapFst) (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a], [a])
xys)
      ([], [])