{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DeriveDataTypeable         #-}
{-# LANGUAGE DeriveGeneric              #-}
{-# LANGUAGE FlexibleContexts           #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE LambdaCase                 #-}
{-# LANGUAGE NoImplicitPrelude          #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE TypeFamilies               #-}
{-# LANGUAGE TypeApplications           #-}
{-# LANGUAGE Trustworthy                #-}
{-# LANGUAGE RankNTypes                 #-}
{-# LANGUAGE PatternSynonyms            #-}

{-|
NonEmpty - Like base's NonEmpty but with:

  * 'Show' and 'Read' instance similar to `[]`
  * A completely safe API
  * added\/removed\/updated functions


Added functions:

  * 'aNonEmpty'
  * `scanl'`
  * 'sortOn'
  * 'fromCons'

  * 'groupAll'
  * 'groupAllBy'
  * 'groupAll1'
  * 'groupAllBy1'

  * 'snoc'
  * 'unsnoc'

  * 'foldl1'   -- this family is present in base's 'Foldable1' from >= 4.18.0.0
  * `foldl1'`
  * 'foldr1'

Removed functions:

  * 'NE.unzip'  (not nonempty-specific)
  * 'NE.unfold' (deprecated, use unfoldr)
  * 'NE.xor'    (seemed out of place)


Changed functions:

  * 'uncons'


Replaced functions:

  * s/(!!)/(!?)/
-}

module Data.List.NeoNonEmpty
  (
  -- * Construction
    NonEmpty
  , pattern (:|)
  , singleton
  , fromCons

  -- * Type annotations
  , aNonEmpty

  -- * Converting to and from base's 'NE.NonEmpty'
  , fromNonEmpty
  , toNonEmpty

  -- * Converting to and from lists
  , fromList
  , toList

  -- * Basic functions
  , length
  , head
  , tail
  , last
  , init
  , cons
  , uncons
  , snoc
  , unsnoc
  , unfoldr
  , sort
  , reverse
  , inits
  , inits1
  , tails
  , tails1
  , append
  , appendList
  , prependList

  -- * Stream transformations
  , map
  , intersperse
  , foldl1
  , foldl1'
  , foldr1
  , scanl
  , scanl'
  , scanl1
  , scanr
  , scanr1
  , transpose
  , sortBy
  , sortOn
  , sortWith

  -- * Building streams
  , iterate
  , repeat
  , cycle
  , insert
  , some1

  -- * Extracting sublists
  , take
  , drop
  , splitAt
  , takeWhile
  , dropWhile
  , span
  , break
  , filter
  , partition
  , group
  , groupAll
  , groupBy
  , groupAllBy
  , groupWith
  , groupAllWith
  , group1
  , groupAll1
  , groupBy1
  , groupAllBy1
  , groupWith1
  , groupAllWith1

  -- * Sublist predicates
  , isPrefixOf

  -- * "Set" operations
  , nub
  , nubBy

  -- * Indexing streams
  , (!?)

  -- * Zipping streams
  , zip
  , zipWith
  ) where

import Prelude
  ( Bool
  , Applicative(..)
  , Eq(..)
  , Int
  , Maybe(..)
  , Monad(..)
  , Ord(..)
  , Ordering(..)
  , Show(..)
  , ($)
  , (.)
  , (++)
  , error
  , fail
  , otherwise
  )

import Data.Bool                       (not, (&&))
import Control.Applicative             (Alternative)
import Control.Monad.Fix               (MonadFix)
import Control.Monad.Zip               (MonadZip)
import Data.Bifunctor                  (first)
import Data.Data                       (Data)
import Data.Foldable                   (Foldable)
#if MIN_VERSION_base(4,18,0)
import Data.Foldable1                  (Foldable1)
#endif
import Data.Functor                    (Functor(..))
import Data.Functor.Classes            (Eq1(..), Ord1(..), Read1(..), Show1(..))
import Data.Function                   ((&))
import Data.Maybe                      (listToMaybe)
import Data.Tuple                      (swap, fst)
import Data.Semigroup                  (Semigroup(..))
import GHC.Generics                    (Generic, Generic1)
import Text.Read                       (Read(..))

import qualified Data.Foldable             as Foldable
import qualified Data.List                 as List
#if (MIN_VERSION_base_compat(0,10,1))
import qualified Data.List.NonEmpty.Compat as NE
#else
import qualified Data.List.NonEmpty        as NE
#endif
import qualified GHC.Exts                  as Exts


-- * Instances

instance Exts.IsList (NonEmpty a) where
  type Item (NonEmpty a) = a
  fromList = NonEmpty . Exts.fromList
  toList (NonEmpty l) = NE.toList l

instance Show a => Show (NonEmpty a) where
  show (NonEmpty l) = show (NE.toList l)

instance Read a => Read (NonEmpty a) where
  readPrec = readPrec >>= \case
    (x : xs) -> pure $ NonEmpty $ x NE.:| xs
    [] -> fail "Can't read NonEmpty list with zero elements"


-- * Construction

-- | A list with one or more elements.
newtype NonEmpty a = NonEmpty (NE.NonEmpty a)
  -- `stock` deriving strategy is used where possible,
  -- `newtype` is fallen back on
  deriving
    ( Applicative
    , Eq
    , Functor
    , Generic
    , Generic1
    , Data
    , MonadFix
    , MonadZip
    , Foldable
#if MIN_VERSION_base(4,18,0)
    , Foldable1
#endif
    , Ord
#if MIN_VERSION_base(4,10,0)
    , Eq1
    , Ord1
    , Read1
    , Show1
#endif
    , Monad
    , Semigroup
    )

#if !MIN_VERSION_base(4,10,0)
instance Eq1 NonEmpty where
  liftEq f (x :| xs) (y :| ys) = f x y && liftEq f xs ys

instance Ord1 NonEmpty where
  liftCompare f (x :| xs) (y :| ys) = case f x y of
    LT -> LT
    GT -> GT
    EQ -> liftCompare f xs ys

instance Read1 NonEmpty where
  liftReadsPrec a b c s = liftReadsPrec a b c s
    & List.filter (not . List.null . fst)
    & fmap (first unsafeFromList)

instance Show1 NonEmpty where
  liftShowsPrec a b c = liftShowsPrec a b c . toList
#endif

{-# COMPLETE (:|) #-}
-- | Construct a NonEmpty from an element and a list.
pattern (:|) :: a -> [a] -> NonEmpty a
pattern x :| xs <- NonEmpty (x NE.:| xs) where
  x :| xs = NonEmpty (x NE.:| xs)

-- | Construct a NonEmpty list from a single element.
singleton :: a -> NonEmpty a
singleton a = NonEmpty (a NE.:| [])

-- | Construct a 'NonEmpty' from an element and a list.
fromCons :: a -> [a] -> NonEmpty a
fromCons x xs = NonEmpty (x NE.:| xs)


-- * Unsafe utilities, not exported

onUnderlying
  :: forall a b c d. (Exts.Coercible (NonEmpty c) a, Exts.Coercible b (NonEmpty d))
  => (a -> b)
  -> NonEmpty c -> NonEmpty d
onUnderlying f = Exts.coerce . f . Exts.coerce

onNonEmpty :: (NE.NonEmpty a -> NE.NonEmpty b) -> NonEmpty a -> NonEmpty b
onNonEmpty = onUnderlying

-- Unsafe. Not exported.
unsafeFromList :: [a] -> NonEmpty a
unsafeFromList [] = error "Tried to create a (Neo)NonEmpty list from an empty list"
unsafeFromList (x : xs) = x :| xs

-- Unsafe. Not exported.
onList :: ([a] -> [b]) -> NonEmpty a -> NonEmpty b
onList f = unsafeFromList . f . toList


-- * Type annotations

-- | A non empty thing. Useful as a syntactically lightweight type annotation,
-- especially when using OverloadedLists:
--
-- >>> :set -XOverloadedLists
-- >>> [(), ()]
--     • Ambiguous type variable ‘a0’ arising from a use of ‘print’
--       prevents the constraint ‘(Show a0)’ from being solved.
-- >>> aNonEmpty [(), ()]
-- [(),()]
aNonEmpty :: NonEmpty a -> NonEmpty a
aNonEmpty a = a


-- * Converting to and from nonempties

-- | Converts base's 'NE.NonEmpty' to a 'NonEmpty'
fromNonEmpty :: NE.NonEmpty a -> NonEmpty a
fromNonEmpty = NonEmpty

-- | Converts a 'NonEmpty' to base's 'NonEmpty'
toNonEmpty :: NonEmpty a -> NE.NonEmpty a
toNonEmpty (NonEmpty ne) = ne


-- * Converting to and from lists

-- | Converts a normal list to a NonEmpty list, given the list has at least one element
fromList :: [a] -> Maybe (NonEmpty a)
fromList (x : xs) = Just (fromCons x xs)
fromList [] = Nothing

-- | Converts a 'NonEmpty' list to a normal list
toList :: NonEmpty a -> [a]
toList (NonEmpty ne) = NE.toList ne


-- * Basic functions

-- | Number of elements in NonEmpty list.
length :: NonEmpty a -> Int
length = NE.length . toNonEmpty

-- | Extract the first element of the nonempty stream.
head :: NonEmpty a -> a
head = NE.head . toNonEmpty

-- | Extract the possibly-empty tail of the nonempty stream.
tail :: NonEmpty a -> [a]
tail = NE.tail . toNonEmpty

-- | Extract the last element of the nonempty stream.
last :: NonEmpty a -> a
last = NE.last . toNonEmpty

-- | Extract everything except the last element of the nonempty stream.
init :: NonEmpty a -> [a]
init = NE.init . toNonEmpty

-- | Prepend an element to the nonempty stream.
cons :: a -> NonEmpty a -> NonEmpty a
cons el = onUnderlying (NE.cons el)

-- | Produces the first element of the nonempty stream,
-- and a stream of the remaining elements.
uncons :: NonEmpty a -> (a, [a])
uncons (NonEmpty (x NE.:| xs)) = (x, xs)

-- | Append an element to the back of a nonempty stream.
snoc :: NonEmpty a -> a -> NonEmpty a
snoc l el = l `append` singleton el

-- | Produces all elements up to the last element, and the last element
unsnoc :: forall a. NonEmpty a -> ([a], a)
unsnoc = first List.reverse . swap . uncons . reverse

-- | Dual of 'foldr', see 'List.unfoldr'.
unfoldr :: (a -> (b, Maybe a)) -> a -> NonEmpty b
unfoldr f initial = fromNonEmpty $ NE.unfoldr f initial

-- | Sort a nonempty stream.
sort :: forall a. Ord a => NonEmpty a -> NonEmpty a
sort = onNonEmpty NE.sort

-- | Reverse a nonempty stream.
reverse :: NonEmpty a -> NonEmpty a
reverse = onNonEmpty NE.reverse

-- | Produces all the prefixes of a stream, starting with the shortest.
-- The result is 'NonEmpty' because the result always contains the empty list as
-- the first element.
--
-- >>> inits [1,2,3] 
-- [[], [1], [1,2], [1,2,3]]
--
-- >>> inits [1]
-- [[], [1]]
--
-- >>> inits []
-- [[]]
inits :: Foldable f => f a -> NonEmpty [a] 
inits = unsafeFromList . List.inits . Foldable.toList


-- | Produces all the nonempty prefixes of a nonempty stream, starting with the shortest.
--
-- >>> inits1 [1,2,3]
-- [[1], [1,2], [1,2,3]]
--
-- >>> inits1 [1]
-- [[1]]
inits1 :: forall a. NonEmpty a -> NonEmpty (NonEmpty a) 
# if (MIN_VERSION_base(4,18,0)) || (MIN_VERSION_base_compat(0,13,1))
inits1 = onUnderlying @_ @(NE.NonEmpty (NE.NonEmpty a)) NE.inits1
#else
inits1 = unsafeFromList . List.map unsafeFromList . List.tail . List.inits . toList
# endif

-- | Produces all the suffixes of a stream, starting with the longest.
-- The result is 'NonEmpty' because the result always contains the empty list as
-- the first element.
--
-- >>> tails [1,2,3]
-- [[1, 2, 3], [2, 3], [3], []]
--
-- >>> tails [1]
-- [[1], []]
--
-- >>> tails []
-- [[]]
tails :: Foldable f => f a -> NonEmpty [a]
tails = fromNonEmpty . NE.tails

-- | Produces all the nonempty suffixes of a nonempty stream, starting with the longest.
--
-- >>> tails1 [1,2,3]
-- [[1, 2, 3], [2, 3], [3]]
--
-- >>> tails1 [1]
-- [[1]]
tails1 :: forall a. NonEmpty a -> NonEmpty (NonEmpty a) 
# if (MIN_VERSION_base(4,18,0)) || (MIN_VERSION_base_compat(0,13,1))
tails1 = onUnderlying @_ @(NE.NonEmpty (NE.NonEmpty a)) NE.tails1
#else
tails1 = unsafeFromList . List.map unsafeFromList . List.init . List.tails . toList
#endif

-- | A monomorphic version of <> for 'NonEmpty'.
--
-- >>> append [1] [2, 3]
-- [1, 2, 3]
append :: NonEmpty a -> NonEmpty a -> NonEmpty a 
append (NonEmpty (x NE.:| xs)) (NonEmpty (y NE.:| ys))
  = NonEmpty $ x NE.:| (xs ++ y : ys)

-- | Append a list at the end of a 'NonEmpty'.
--
-- >>> appendList [1, 2, 3] []
-- [1, 2, 3]
--
-- >>> appendList [1, 2, 3] [4, 5]
-- [1, 2, 3, 4, 5]
appendList :: NonEmpty a -> [a] -> NonEmpty a
appendList (NonEmpty (x NE.:| xs)) ys
  = NonEmpty $ x NE.:| (xs ++ ys)

-- | Prepend a list to the front of a 'NonEmpty'.
--
-- >>> prependList [] [1, 2, 3]
-- [1, 2, 3]
--
-- >>> prependList [negate 1, 0] [1, 2, 3]
-- [-1, 0, 1, 2, 3]
prependList :: [a] -> NonEmpty a -> NonEmpty a
prependList [] xs = xs
prependList (x : xs) (NonEmpty (y NE.:| ys))
  = NonEmpty $ x NE.:| (xs ++ y : ys)


-- * Stream transformations

-- | Map a function over a NonEmpty stream.
map :: (a -> b) -> NonEmpty a -> NonEmpty b
map f = onUnderlying (NE.map f)

-- | Produces a 'NonEmpty' which alternates between elementes of
-- the input list, and the supplied element.
--
-- >>> intersperse 0 [1, 2, 3])
-- [1, 0, 2, 0, 3]
--
-- >>> intersperse 0 [1]
-- [1]
intersperse :: a -> NonEmpty a -> NonEmpty a 
intersperse el = onUnderlying (NE.intersperse el)

-- | Left-associative fold, lazy in the accumulator. See 'List.foldl'.
foldl1 :: (a -> a -> a) -> NonEmpty a -> a
foldl1 f l = let (x, xs) = uncons l in
  List.foldl f x xs

-- | Left-associative fold, strict in the accumulator. See `List.foldl'`.
foldl1' :: (a -> a -> a) -> NonEmpty a -> a
foldl1' f l = let (x, xs) = uncons l in
  List.foldl' f x xs

-- | Left-associative fold, strict in the accumulator. See `List.foldl'`.
foldr1 :: (a -> a -> a) -> NonEmpty a -> a
foldr1 f l = let (xs, x) = unsnoc l in
  List.foldr f x xs

-- | scanl is similar to foldl, but returns a stream of successive
-- reduced values from the left:
--
-- >>> scanl (+) 1 [20, 300, 4000]
-- [1,21,321,4321]
scanl :: Foldable f => (b -> a -> b) -> b -> f a -> NonEmpty b 
scanl f initial els = fromNonEmpty $ NE.scanl f initial (Foldable.toList els)

-- | A strict version of 'scanl'.
scanl' :: Foldable f => (b -> a -> b) -> b -> f a -> NonEmpty b 
scanl' f initial els = unsafeFromList $ List.scanl' f initial (Foldable.toList els)

-- | scanl1 is a variant of scanl that has no starting value argument:
--
-- @
-- scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, x1 `f` (x2 `f` x3), ...]
-- @
scanl1 :: (a -> a -> a) -> NonEmpty a -> NonEmpty a
scanl1 f = onUnderlying (NE.scanl1 f)

-- | Right-to-left dual of scanl. Note that the order of parameters
-- on the accumulating function are reversed compared to scanl.
-- Also note that
--
-- @
-- head (scanr f z xs) == foldr f z xs
-- @
--
-- >>> scanr (+) 0 [1..4]
-- [10,9,7,4,0]
--
-- >>> scanr (+) 42 []
-- [42]
--
-- >>> scanr (-) 100 [1..4]
-- [98,-97,99,-96,100]
scanr :: Foldable f => (a -> b -> b) -> b -> f a -> NonEmpty b 
scanr f initial els = fromNonEmpty $ NE.scanr f initial els

-- | scanr1 is a variant of scanr that has no starting value argument.
--
-- >>> scanr1 (+) [1..4]
-- [10,9,7,4]
--
-- >>> scanr1 (+) []
-- []
--
-- >>> scanr1 (-) [1..4]
-- [-2,3,-1,4]
scanr1 :: (a -> a -> a) -> NonEmpty a -> NonEmpty a 
scanr1 f = onUnderlying (NE.scanr1 f)

-- | transpose for NonEmpty, behaves the same as 'List.transpose'.
-- The rows/columns need not be the same length, in which case
--
-- @
-- transpose . transpose /= id
-- @
transpose :: forall a. NonEmpty (NonEmpty a) -> NonEmpty (NonEmpty a)
transpose = onUnderlying @_ @(NE.NonEmpty (NE.NonEmpty a)) NE.transpose

-- | Behaves the same as 'List.sortBy'
sortBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
sortBy f = onUnderlying (NE.sortBy f)

-- | Sort a list on a projection of its elements.
-- Projects once, then sorts, then un-projects.
-- This is useful when the projection function is expensive.
-- If it's not, you should probably use 'sortWith'.
sortOn :: Ord o => (a -> o) -> NonEmpty a -> NonEmpty a 
sortOn f = onList (List.sortOn f)

-- | Sort a list on a projection of its elements.
-- Projects during comparison.
-- This is useful when the projection function is cheap.
-- If it's not, you should probably use 'sortOn'.
sortWith :: Ord o => (a -> o) -> NonEmpty a -> NonEmpty a 
sortWith f = onUnderlying (NE.sortWith f)


-- * Building streams

-- | iterate f x produces the infinite sequence of repeated applications of f to x.
--
-- @
-- iterate f x = [x, f x, f (f x), ..]
-- @
iterate :: (a -> a) -> a -> NonEmpty a
iterate f initial = fromNonEmpty $ NE.iterate f initial

-- | repeat x returns a constant stream, where all elements are equal to x.
repeat :: a -> NonEmpty a
repeat = fromNonEmpty . NE.repeat

-- | cycle xs returns the infinite repetition of xs:
--
-- @
-- cycle [1, 2, 3] == [1, 2, 3, 1, 2, 3, ...]
-- @
cycle :: NonEmpty a -> NonEmpty a
cycle = onNonEmpty NE.cycle

-- | insert x xs inserts x into the last position in xs where it is still
-- less than or equal to the next element. If the list is sorted beforehand,
-- the result will also be sorted.
insert :: (Foldable f, Ord a) => a -> f a -> NonEmpty a
insert el = unsafeFromList . List.insert el . Foldable.toList

-- | some1 x sequences x one or more times.
some1 :: Alternative f => f a -> f (NonEmpty a)
some1 = fmap fromNonEmpty . NE.some1


-- * Extracting sublists

-- | take n xs returns the first n elements of xs.
take :: Int -> NonEmpty a -> [a]
take n = NE.take n . toNonEmpty

-- | drop n xs drops the first n elements from the front of the sequence xs.
drop :: Int -> NonEmpty a -> [a]
drop n = NE.drop n . toNonEmpty

-- | splitAt n xs returns a pair consisting of the prefix of xs of length n and the remaining stream immediately following this prefix.
--
-- 'splitAt' n xs == ('take' n xs, 'drop' n xs)
splitAt :: Int -> NonEmpty a -> ([a], [a])
splitAt n = NE.splitAt n . toNonEmpty

-- | Produces the longest prefix of the stream for which the predicate holds.
takeWhile :: (a -> Bool) -> NonEmpty a -> [a]
takeWhile f = NE.takeWhile f . toNonEmpty

-- | dropWhile p xs produces the suffix remaining after takeWhile p xs.
dropWhile :: (a -> Bool) -> NonEmpty a -> [a]
dropWhile f = NE.dropWhile f . toNonEmpty

-- | span p xs returns the longest prefix of xs that satisfies p, together with the remainder of the stream.
--
-- 'span' p xs == ('takeWhile' p xs, 'dropWhile' p xs)
span :: (a -> Bool) -> NonEmpty a -> ([a], [a])
span f = NE.span f . toNonEmpty

-- | break p is equivalent to span (not . p).
break :: (a -> Bool) -> NonEmpty a -> ([a], [a])
break f = NE.break f . toNonEmpty

-- | Removes any elements of a nonempty stream that do not satisfy a predicate.
filter :: (a -> Bool) -> NonEmpty a -> [a]
filter f = NE.filter f . toNonEmpty

-- | Produces a pair of lists, the first of elements that satisfy the given
-- predicate, the second of elements that did not.
--
-- @
-- 'partition' p xs == ('filter' p xs, 'filter' (not . p) xs)
-- @
partition :: (a -> Bool) -> NonEmpty a -> ([a], [a])
partition f = NE.partition f . toNonEmpty

-- | Takes a stream and returns a list of streams such that flattening
-- the resulting list is equal to the argument.
-- Moreover, each stream in the resulting list contains only equal elements.
--
-- >>> group "Mississippi"
-- ["M", "i", "ss", "i", "ss", "i", "pp", "i"]
group :: (Foldable f, Eq a) => f a -> [NonEmpty a]
group = groupBy (==)

-- | Similar to 'group', but sorts the input first so that each
-- equivalence class has, at most, one list in the output.
groupAll :: Ord a => [a] -> [NonEmpty a]
groupAll = groupAllBy compare

-- | Similar to 'group', but uses the provided equality predicate instead of '=='.
groupBy :: Foldable f => (a -> a -> Bool) -> f a -> [NonEmpty a]
groupBy f = Exts.coerce . NE.groupBy f

ordToEq :: (a -> b -> Ordering) -> a -> b -> Bool
ordToEq f a b = f a b == EQ

-- | Similar to 'groupBy', but sorts the input first so that each
-- equivalence class has, at most, one list in the output.
groupAllBy :: (a -> a -> Ordering) -> [a] -> [NonEmpty a]
groupAllBy f = groupBy (ordToEq f) . List.sortBy f

-- | Similar to 'group', but uses the provided projection when comparing for equality.
groupWith :: (Foldable f, Eq b) => (a -> b) -> f a -> [NonEmpty a]
groupWith f = Exts.coerce . NE.groupWith f

-- | Similar to 'groupWith', but sorts the input first so that each
-- equivalence class has, at most, one list in the output.
groupAllWith :: Ord b => (a -> b) -> [a] -> [NonEmpty a]
groupAllWith f = Exts.coerce . NE.groupAllWith f

-- | Similar to 'List.group', but uses the knowledge that its input is non-empty to
-- produce guaranteed non-empty output.
group1 :: forall a. Eq a => NonEmpty a -> NonEmpty (NonEmpty a)
group1 = onUnderlying @_ @(NE.NonEmpty (NE.NonEmpty a)) NE.group1

-- | Similar to 'group1', but sorts the input first so that each
-- equivalence class has, at most, one list in the output.
groupAll1 :: Ord a => NonEmpty a -> [NonEmpty a]
groupAll1 = group . sort

-- | Similar to 'group1', but uses the provided equality predicate instead of '=='.
groupBy1 :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty (NonEmpty a)
groupBy1 f = onUnderlying (NE.groupBy1 f)

-- | Similar to 'group', but sorts the input first so that each
-- equivalence class has, at most, one list in the output.
groupAllBy1 :: (a -> a -> Ordering) -> [a] -> [NonEmpty a]
groupAllBy1 f = groupBy (ordToEq f) . List.sortBy f

-- | Similar to 'group1', but uses the provided projection when comparing for equality.
groupWith1 :: Eq b => (a -> b) -> NonEmpty a -> NonEmpty (NonEmpty a)
groupWith1 f = onUnderlying (NE.groupWith1 f)

-- | Similar to 'groupWith1', but sorts the list first so that each
-- equivalence class has, at most, one list in the output.
groupAllWith1 :: Ord b => (a -> b) -> NonEmpty a -> NonEmpty (NonEmpty a)
groupAllWith1 f = onUnderlying (NE.groupAllWith1 f)


-- * Sublist predicates

-- | Returns True if the first argument is a prefix of the second.
--
-- >>> isPrefixOf [1, 2, 3] [1, 2, 3, 4, 5]
-- True
-- >>> isPrefixOf "abc" "defghi"
-- False
-- >>> isPrefixOf "abc" ""
-- False
isPrefixOf :: Eq a => [a] -> NonEmpty a -> Bool
isPrefixOf els = NE.isPrefixOf els . toNonEmpty


-- * "Set" operations

-- | Removes duplicate elements from a list. In particular, it keeps only
-- the first occurrence of each element. (The name nub means 'essence'.)
-- It is a special case of nubBy, which allows the programmer to supply
-- their own inequality test.
nub :: Eq a => NonEmpty a -> NonEmpty a 
nub = onNonEmpty NE.nub

-- | Behaves just like nub, except it uses a user-supplied equality
-- predicate instead of the overloaded '==' function.
nubBy :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty a 
nubBy f = onNonEmpty (NE.nubBy f)


-- * Indexing streams

infixl 9 !?

-- | xs !! n returns the element of the stream xs at index n, if present.
-- Note that the head of the stream has index 0.
(!?) :: NonEmpty a -> Int -> Maybe a
(!?) l n
  | n < 0 = Nothing
  | otherwise = listToMaybe $ List.drop n $ toList l

-- * Zipping streams

-- | \(\mathcal{O}(\min(m,n))\).
-- Takes two streams and produces a stream of corresponding pairs.
--
-- >>> zip [1, 2] ['a', 'b']
-- [(1, 'a'),(2, 'b')]
zip :: forall a b. NonEmpty a -> NonEmpty b -> NonEmpty (a, b) 
zip l1 l2 = Exts.coerce @(NE.NonEmpty (a, b)) $ NE.zip (Exts.coerce l1) (Exts.coerce l2)

-- | \(\mathcal{O}(\min(m,n))\).
-- Generalises zip by zipping with the provided function, instead of
-- a tupling function.
zipWith :: forall a b c. (a -> b -> c) -> NonEmpty a -> NonEmpty b -> NonEmpty c 
zipWith f l1 l2 = Exts.coerce @(NE.NonEmpty c) $ NE.zipWith f (Exts.coerce l1) (Exts.coerce l2)