{-# LANGUAGE CPP #-}

-- | Extra functions for working with 'NonEmpty' lists. The package
--   also exports the existing "Data.List.NonEmpty" functions.
module Data.List.NonEmpty.Extra(
    module Data.List.NonEmpty,
    (|:), (|>), snoc, (!?),
    appendl, appendr,
    sortOn, union, unionBy,
    nubOrd, nubOrdBy, nubOrdOn,
    maximum1, minimum1, maximumBy1, minimumBy1, maximumOn1, minimumOn1,
    foldl1', repeatedly
    ) where

import           Data.Function
import qualified Data.List.Extra as List
import           Data.List.NonEmpty

#if __GLASGOW_HASKELL__ <= 802
import Data.Semigroup ((<>))
#endif

infixl 5 |>, |:

-- | /O(n)/. Append an element to a non-empty list.
--
-- > (1 :| [2,3]) |> 4 |> 5 == 1 :| [2,3,4,5]
(|>) :: NonEmpty a -> a -> NonEmpty a
|> :: forall a. NonEmpty a -> a -> NonEmpty a
(|>) NonEmpty a
xs a
x = NonEmpty a
xs forall a. Semigroup a => a -> a -> a
<> forall (f :: * -> *) a. Applicative f => a -> f a
pure a
x

-- | Synonym for '|>'.
snoc :: NonEmpty a -> a -> NonEmpty a
snoc :: forall a. NonEmpty a -> a -> NonEmpty a
snoc = forall a. NonEmpty a -> a -> NonEmpty a
(|>)

-- | /O(n)/. Append an element to a list.
--
-- > [1,2,3] |: 4 |> 5 == 1 :| [2,3,4,5]
(|:) :: [a] -> a -> NonEmpty a
|: :: forall a. [a] -> a -> NonEmpty a
(|:) [a]
xs a
x = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> NonEmpty a -> NonEmpty a
cons (forall (f :: * -> *) a. Applicative f => a -> f a
pure a
x) [a]
xs

-- | A total variant of the list index function `(!?)`.
--
-- > (2 :| [3,4]) !? 1    == Just 3
-- > (2 :| [3,4]) !? (-1) == Nothing
-- > (1 :| [])    !? 1    == Nothing
(!?) :: NonEmpty a -> Int -> Maybe a
!? :: forall a. NonEmpty a -> Int -> Maybe a
(!?) ~(a
x :| [a]
xs) Int
n
  | Int
n forall a. Eq a => a -> a -> Bool
== Int
0 = forall a. a -> Maybe a
Just a
x
  | Int
n forall a. Ord a => a -> a -> Bool
> Int
0  = [a]
xs forall a. [a] -> Int -> Maybe a
List.!? (Int
n forall a. Num a => a -> a -> a
- Int
1)
  | Bool
otherwise = forall a. Maybe a
Nothing
infixl 9 !?

-- | Append a list to a non-empty list.
--
-- > appendl (1 :| [2,3]) [4,5] == 1 :| [2,3,4,5]
appendl :: NonEmpty a -> [a] -> NonEmpty a
appendl :: forall a. NonEmpty a -> [a] -> NonEmpty a
appendl (a
x :| [a]
xs) [a]
l = a
x forall a. a -> [a] -> NonEmpty a
:| ([a]
xs forall a. [a] -> [a] -> [a]
++ [a]
l)

-- | Append a non-empty list to a list.
--
-- > appendr [1,2,3] (4 :| [5]) == 1 :| [2,3,4,5]
appendr :: [a] -> NonEmpty a -> NonEmpty a
appendr :: forall a. [a] -> NonEmpty a -> NonEmpty a
appendr [a]
l NonEmpty a
nel = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. a -> NonEmpty a -> NonEmpty a
cons NonEmpty a
nel [a]
l

-- | Sort by comparing the results of a function applied to each element.
--   The sort is stable, and the function is evaluated only once for
--   each element.
sortOn :: Ord b => (a -> b) -> NonEmpty a -> NonEmpty a
sortOn :: forall b a. Ord b => (a -> b) -> NonEmpty a -> NonEmpty a
sortOn a -> b
f = forall a. [a] -> NonEmpty a
fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. Ord b => (a -> b) -> [a] -> [a]
List.sortOn a -> b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. NonEmpty a -> [a]
toList

-- | Return the union of two non-empty lists. Duplicates, and elements of the
--   first list, are removed from the the second list, but if the first list
--   contains duplicates, so will the result.
--
-- > (1 :| [3, 5, 3]) `union` (4 :| [5, 3, 5, 2]) == 1 :| [3, 5, 3, 4, 2]
union :: Eq a => NonEmpty a -> NonEmpty a -> NonEmpty a
union :: forall a. Eq a => NonEmpty a -> NonEmpty a -> NonEmpty a
union = forall a.
(a -> a -> Bool) -> NonEmpty a -> NonEmpty a -> NonEmpty a
unionBy forall a. Eq a => a -> a -> Bool
(==)

-- | @nubOrd@ for 'NonEmpty'. Behaves the same as 'Data.List.Extra.nubOrd'.
--
-- > Data.List.NonEmpty.Extra.nubOrd (1 :| [2, 3, 3, 4, 1, 2]) == 1 :| [2, 3, 4]
-- > \xs -> Data.List.NonEmpty.Extra.nubOrd xs == Data.List.NonEmpty.Extra.nub xs
nubOrd :: Ord a => NonEmpty a -> NonEmpty a
nubOrd :: forall a. Ord a => NonEmpty a -> NonEmpty a
nubOrd = forall a. (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
nubOrdBy forall a. Ord a => a -> a -> Ordering
compare

-- | @nubOrdBy@ for 'NonEmpty'. Behaves the same as 'Data.List.Extra.nubOrdBy'.
--
-- > Data.List.NonEmpty.Extra.nubOrdBy (compare `on` Data.List.length) ("a" :| ["test","of","this"]) == "a" :| ["test","of"]
nubOrdBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
nubOrdBy :: forall a. (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
nubOrdBy a -> a -> Ordering
cmp = forall a. [a] -> NonEmpty a
fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (a -> a -> Ordering) -> [a] -> [a]
List.nubOrdBy a -> a -> Ordering
cmp forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. NonEmpty a -> [a]
toList

-- | @nubOrdOn@ for 'NonEmpty'. Behaves the same as 'Data.List.Extra.nubOrdOn'.
--
-- > Data.List.NonEmpty.Extra.nubOrdOn Data.List.length ("a" :| ["test","of","this"]) == "a" :| ["test","of"]
nubOrdOn :: Ord b => (a -> b) -> NonEmpty a -> NonEmpty a
nubOrdOn :: forall b a. Ord b => (a -> b) -> NonEmpty a -> NonEmpty a
nubOrdOn a -> b
f = forall a. [a] -> NonEmpty a
fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. Ord b => (a -> b) -> [a] -> [a]
List.nubOrdOn a -> b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. NonEmpty a -> [a]
toList

-- | The non-overloaded version of 'union'.
unionBy :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty a -> NonEmpty a
unionBy :: forall a.
(a -> a -> Bool) -> NonEmpty a -> NonEmpty a -> NonEmpty a
unionBy a -> a -> Bool
eq NonEmpty a
xs NonEmpty a
ys = forall a. [a] -> NonEmpty a
fromList forall a b. (a -> b) -> a -> b
$ forall a. (a -> a -> Bool) -> [a] -> [a] -> [a]
List.unionBy a -> a -> Bool
eq (forall a. NonEmpty a -> [a]
toList NonEmpty a
xs) (forall a. NonEmpty a -> [a]
toList NonEmpty a
ys)

-- | The largest element of a non-empty list.
maximum1 :: Ord a => NonEmpty a -> a
maximum1 :: forall a. Ord a => NonEmpty a -> a
maximum1 = forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
List.maximum

-- | The least element of a non-empty list.
minimum1 :: Ord a => NonEmpty a -> a
minimum1 :: forall a. Ord a => NonEmpty a -> a
minimum1 = forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
List.minimum

-- | The largest element of a non-empty list with respect to the given
--   comparison function.
maximumBy1 :: (a -> a -> Ordering) -> NonEmpty a -> a
maximumBy1 :: forall a. (a -> a -> Ordering) -> NonEmpty a -> a
maximumBy1 = forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
List.maximumBy

-- | The least element of a non-empty list with respect to the given
--   comparison function.
minimumBy1 :: (a -> a -> Ordering) -> NonEmpty a -> a
minimumBy1 :: forall a. (a -> a -> Ordering) -> NonEmpty a -> a
minimumBy1 = forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
List.minimumBy

-- | A version of 'maximum1' where the comparison is done on some extracted value.
maximumOn1 :: Ord b => (a -> b) -> NonEmpty a -> a
maximumOn1 :: forall b a. Ord b => (a -> b) -> NonEmpty a -> a
maximumOn1 a -> b
f = forall a. (a -> a -> Ordering) -> NonEmpty a -> a
maximumBy1 (forall a. Ord a => a -> a -> Ordering
compare forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` a -> b
f)

-- | A version of 'minimum1' where the comparison is done on some extracted value.
minimumOn1 :: Ord b => (a -> b) -> NonEmpty a -> a
minimumOn1 :: forall b a. Ord b => (a -> b) -> NonEmpty a -> a
minimumOn1 a -> b
f = forall a. (a -> a -> Ordering) -> NonEmpty a -> a
minimumBy1 (forall a. Ord a => a -> a -> Ordering
compare forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` a -> b
f)

-- | A strict variant of variant `foldl1`
foldl1' :: (a -> a -> a) -> NonEmpty a -> a
foldl1' :: forall a. (a -> a -> a) -> NonEmpty a -> a
foldl1' a -> a -> a
f (a
x:|[a]
xs) =  forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' a -> a -> a
f a
x [a]
xs

-- | Apply some operation repeatedly, producing an element of output
--   and the remainder of the list.
repeatedly :: (NonEmpty a -> (b, [a])) -> NonEmpty a -> NonEmpty b
repeatedly :: forall a b. (NonEmpty a -> (b, [a])) -> NonEmpty a -> NonEmpty b
repeatedly NonEmpty a -> (b, [a])
f (a
a :| [a]
as) = b
b forall a. a -> [a] -> NonEmpty a
:| forall a b. (NonEmpty a -> (b, [a])) -> [a] -> [b]
List.repeatedlyNE NonEmpty a -> (b, [a])
f [a]
as'
    where (b
b, [a]
as') = NonEmpty a -> (b, [a])
f (a
a forall a. a -> [a] -> NonEmpty a
:| [a]
as)