module Data.List.Reverse.Private where

import qualified Data.List.Key.Private as Key
import Data.List.HT (segmentAfter, viewR, groupBy)

import Prelude hiding (dropWhile, takeWhile)


-- $setup
-- >>> import Test.Utility (forAllPredicates)
-- >>> import qualified Data.List.Reverse.StrictElement as Rev
-- >>> import Prelude hiding (dropWhile, takeWhile)


{- |
prop> forAllPredicates $ \p xs -> dropWhile p xs == Rev.dropWhile p xs
-}
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: forall a. (a -> Bool) -> [a] -> [a]
dropWhile a -> Bool
p =
   [[a]] -> [a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([[a]] -> [a]) -> ([a] -> [[a]]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[a]] -> [[a]]
forall a. HasCallStack => [a] -> [a]
init ([[a]] -> [[a]]) -> ([a] -> [[a]]) -> [a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> [a] -> [[a]]
forall a. (a -> Bool) -> [a] -> [[a]]
segmentAfter (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)

{- |
prop> forAllPredicates $ \p xs -> takeWhile0 p xs == Rev.takeWhile p xs
-}
takeWhile0 :: (a -> Bool) -> [a] -> [a]
takeWhile0 :: forall a. (a -> Bool) -> [a] -> [a]
takeWhile0 a -> Bool
p =
   [[a]] -> [a]
forall a. HasCallStack => [a] -> a
last ([[a]] -> [a]) -> ([a] -> [[a]]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> [a] -> [[a]]
forall a. (a -> Bool) -> [a] -> [[a]]
segmentAfter (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)

{- |
Doesn't seem to be superior to the naive implementation.

prop> forAllPredicates $ \p xs -> takeWhile1 p xs == Rev.takeWhile p xs
-}
takeWhile1 :: (a -> Bool) -> [a] -> [a]
takeWhile1 :: forall a. (a -> Bool) -> [a] -> [a]
takeWhile1 a -> Bool
p =
   (\Maybe ([[(Bool, a)]], [(Bool, a)])
mx ->
      case Maybe ([[(Bool, a)]], [(Bool, a)])
mx of
         Just ([[(Bool, a)]]
_, xs :: [(Bool, a)]
xs@((Bool
True,a
_):[(Bool, a)]
_)) -> ((Bool, a) -> a) -> [(Bool, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (Bool, a) -> a
forall a b. (a, b) -> b
snd [(Bool, a)]
xs
         Maybe ([[(Bool, a)]], [(Bool, a)])
_ -> []) (Maybe ([[(Bool, a)]], [(Bool, a)]) -> [a])
-> ([a] -> Maybe ([[(Bool, a)]], [(Bool, a)])) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   [[(Bool, a)]] -> Maybe ([[(Bool, a)]], [(Bool, a)])
forall a. [a] -> Maybe ([a], a)
viewR ([[(Bool, a)]] -> Maybe ([[(Bool, a)]], [(Bool, a)]))
-> ([a] -> [[(Bool, a)]])
-> [a]
-> Maybe ([[(Bool, a)]], [(Bool, a)])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (((Bool, a) -> (Bool, a) -> Bool) -> [(Bool, a)] -> [[(Bool, a)]])
-> (Bool -> Bool -> Bool) -> (a -> Bool) -> [a] -> [[(Bool, a)]]
forall key a b c.
(((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
-> (key -> key -> b) -> (a -> key) -> [a] -> c
Key.aux ((Bool, a) -> (Bool, a) -> Bool) -> [(Bool, a)] -> [[(Bool, a)]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
groupBy Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
(==) a -> Bool
p

{- |
However it is more inefficient,
because of repeatedly appending single elements. :-(

prop> forAllPredicates $ \p xs -> takeWhile2 p xs == Rev.takeWhile p xs
-}
takeWhile2 :: (a -> Bool) -> [a] -> [a]
takeWhile2 :: forall a. (a -> Bool) -> [a] -> [a]
takeWhile2 a -> Bool
p =
   ([a] -> a -> [a]) -> [a] -> [a] -> [a]
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (\[a]
xs a
x -> if a -> Bool
p a
x then [a]
xs[a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++[a
x] else []) []