{-# LANGUAGE CPP #-}
{-# OPTIONS_GHC -fno-warn-duplicate-exports #-}

-- | 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 NonEmpty a -> NonEmpty a -> NonEmpty a
forall a. Semigroup a => a -> a -> a
<> a -> NonEmpty a
forall a. a -> NonEmpty 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 = NonEmpty a -> a -> NonEmpty a
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 = (a -> NonEmpty a -> NonEmpty a) -> NonEmpty a -> [a] -> NonEmpty a
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> NonEmpty a -> NonEmpty a
forall a. a -> NonEmpty a -> NonEmpty a
cons (a -> NonEmpty a
forall a. a -> NonEmpty a
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 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = a -> Maybe a
forall a. a -> Maybe a
Just a
x
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0  = [a]
xs [a] -> Int -> Maybe a
forall a. [a] -> Int -> Maybe a
List.!? (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
  | Bool
otherwise = Maybe a
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 a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| ([a]
xs [a] -> [a] -> [a]
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 = (a -> NonEmpty a -> NonEmpty a) -> NonEmpty a -> [a] -> NonEmpty a
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> NonEmpty a -> NonEmpty a
forall a. a -> NonEmpty a -> NonEmpty a
cons NonEmpty a
nel [a]
l

#if __GLASGOW_HASKELL__ <= 908
-- | 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 = [a] -> NonEmpty a
forall a. HasCallStack => [a] -> NonEmpty a
fromList ([a] -> NonEmpty a)
-> (NonEmpty a -> [a]) -> NonEmpty a -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> [a] -> [a]
forall b a. Ord b => (a -> b) -> [a] -> [a]
List.sortOn a -> b
f ([a] -> [a]) -> (NonEmpty a -> [a]) -> NonEmpty a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
toList
#endif

-- | 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 = (a -> a -> Bool) -> NonEmpty a -> NonEmpty a -> NonEmpty a
forall a.
(a -> a -> Bool) -> NonEmpty a -> NonEmpty a -> NonEmpty a
unionBy a -> a -> Bool
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 = (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
forall a. (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
nubOrdBy a -> a -> Ordering
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 = [a] -> NonEmpty a
forall a. HasCallStack => [a] -> NonEmpty a
fromList ([a] -> NonEmpty a)
-> (NonEmpty a -> [a]) -> NonEmpty a -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
List.nubOrdBy a -> a -> Ordering
cmp ([a] -> [a]) -> (NonEmpty a -> [a]) -> NonEmpty a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> [a]
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 = [a] -> NonEmpty a
forall a. HasCallStack => [a] -> NonEmpty a
fromList ([a] -> NonEmpty a)
-> (NonEmpty a -> [a]) -> NonEmpty a -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> [a] -> [a]
forall b a. Ord b => (a -> b) -> [a] -> [a]
List.nubOrdOn a -> b
f ([a] -> [a]) -> (NonEmpty a -> [a]) -> NonEmpty a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty a -> [a]
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 = [a] -> NonEmpty a
forall a. HasCallStack => [a] -> NonEmpty a
fromList ([a] -> NonEmpty a) -> [a] -> NonEmpty a
forall a b. (a -> b) -> a -> b
$ (a -> a -> Bool) -> [a] -> [a] -> [a]
forall a. (a -> a -> Bool) -> [a] -> [a] -> [a]
List.unionBy a -> a -> Bool
eq (NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
toList NonEmpty a
xs) (NonEmpty a -> [a]
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 = NonEmpty a -> a
forall a. Ord a => NonEmpty a -> a
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 = NonEmpty a -> a
forall a. Ord a => NonEmpty a -> a
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 = (a -> a -> Ordering) -> NonEmpty a -> a
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 = (a -> a -> Ordering) -> NonEmpty a -> a
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 = (a -> a -> Ordering) -> NonEmpty a -> a
forall a. (a -> a -> Ordering) -> NonEmpty a -> a
maximumBy1 (b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (b -> b -> Ordering) -> (a -> b) -> a -> a -> Ordering
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 = (a -> a -> Ordering) -> NonEmpty a -> a
forall a. (a -> a -> Ordering) -> NonEmpty a -> a
minimumBy1 (b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (b -> b -> Ordering) -> (a -> b) -> a -> a -> Ordering
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) =  (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
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 b -> [b] -> NonEmpty b
forall a. a -> [a] -> NonEmpty a
:| (NonEmpty a -> (b, [a])) -> [a] -> [b]
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 a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
as)