{-# LANGUAGE CPP #-}
{-# OPTIONS_GHC -Wno-incomplete-patterns #-}
-- because of https://gitlab.haskell.org/ghc/ghc/issues/10339


-- | Missing functionality for non-empty lists.
--
-- This module is meant to be imported qualified ala:
--
-- @
-- {-# LANGUAGE PatternSynonyms #-}
--
-- import Mikan.Utils.List1 (List1, pattern (:|))
-- import Mikan.Utils.List1 qualified as List1
-- @
module Mikan.Utils.List1
  ( List1
  -- * Basic functions
  , initLast
  , last2
  , snoc
  , snoc1
  -- * Traversals
  , map'
  , mapMaybe
  -- * Folds
  , foldr
  -- ** Special folds
  , concat
  , concat'
  , concatMap1
  , catMaybes
  -- * Sublists
  , breakAfter
  , wordsBy
  , lefts
  , rights
  , partitionEithers
  -- ** Grouping
  , groupOn
  , groupOn1
  , groupBy'
  , groupByFst
  , groupByFst1
  -- * Searching non-empty lists
  , find
  , filter'
  -- * Zipping and unzipping non-empty lists
  , zipWithM
  , zipWithM_
  , unzipWith
  -- * Special lists
  -- ** String operations
  , String1
  , unwords
  -- ** "Set" operations
  , union
  , allEqual
  , nubM
  -- * Recovering non-emptyness
  , ifNull
  , ifNotNull
  , unlessNull
  , unlessNullM
  -- * Conversions
  , toList'
  , fromListSafe
  -- * Optics
  , lensHead
  , lensLast
  -- * Re-exports
  , module List1
  , module IsList
  , module Unzip
  ) where

import Prelude hiding (filter, unzip, unwords, foldr, concat)

import Control.Arrow ((&&&))
import Control.Monad (filterM)
import Control.Monad qualified as List (zipWithM, zipWithM_)

import Data.Either qualified as Either
import Data.Function ( on )
import Data.List qualified as List
import Data.Maybe qualified as Maybe

import Data.List.NonEmpty as List1 hiding (fromList, toList, unzip)
import Data.List.NonEmpty qualified as List1 (toList)

-- Prevent warning -Wx-data-list-nonempty-unzip
#if MIN_VERSION_base(4,19,0)
import Data.Functor as Unzip (unzip)
#else
import Data.List.NonEmpty as Unzip (unzip)
#endif

import GHC.Exts as IsList ( IsList(..) )

import Mikan.Utils.Functor ((<.>), (<&>))
import Mikan.Utils.Null (Null(..))
import Mikan.Utils.List qualified as List

-- | A 'List1' is a non-empty list.
--
-- We prefer to use 'List1' over 'NonEmpty', as it is
-- more suggestive that the list is, well, a list.
type List1 = NonEmpty

--------------------------------------------------------------------------------
-- Basic functions

-- | Return the last element and the rest.
--
-- This function performs two traversals of the list, but
-- does not create intermediate pairs.
initLast :: List1 a -> ([a], a)
initLast :: forall a. List1 a -> ([a], a)
initLast = List1 a -> [a]
forall a. NonEmpty a -> [a]
List1.init (List1 a -> [a]) -> (List1 a -> a) -> List1 a -> ([a], a)
forall b c c'. (b -> c) -> (b -> c') -> b -> (c, c')
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& List1 a -> a
forall a. NonEmpty a -> a
List1.last

-- | \(\mathcal{O}(n)\). Last two elements (safe).
last2 :: List1 a -> Maybe (a, a)
last2 :: forall a. List1 a -> Maybe (a, a)
last2 (a
x :| a
y : [a]
xs) = (a, a) -> Maybe (a, a)
forall a. a -> Maybe a
Just ((a, a) -> Maybe (a, a)) -> (a, a) -> Maybe (a, a)
forall a b. (a -> b) -> a -> b
$ a -> a -> [a] -> (a, a)
forall a. a -> a -> [a] -> (a, a)
List.last2' a
x a
y [a]
xs
last2 NonEmpty a
_ = Maybe (a, a)
forall a. Maybe a
Nothing

-- | Add an element to the end of a list.
snoc :: [a] -> a -> List1 a
snoc :: forall a. [a] -> a -> List1 a
snoc [a]
as a
a = [a] -> NonEmpty a -> NonEmpty a
forall a. [a] -> NonEmpty a -> NonEmpty a
prependList [a]
as (NonEmpty a -> NonEmpty a) -> NonEmpty a -> NonEmpty a
forall a b. (a -> b) -> a -> b
$ a
a a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| []

-- | Append an element to a non-empty list.
snoc1 :: List1 a -> a -> List1 a
snoc1 :: forall a. List1 a -> a -> List1 a
snoc1 List1 a
as a
a = List1 a
as List1 a -> List1 a -> List1 a
forall a. Semigroup a => a -> a -> a
<> (a
a a -> [a] -> List1 a
forall a. a -> [a] -> NonEmpty a
:| [])

--------------------------------------------------------------------------------
-- Traversals

{-# INLINE map' #-}
-- | Strict map.
map' :: (a -> b) -> List1 a -> List1 b
map' :: forall a b. (a -> b) -> List1 a -> List1 b
map' a -> b
f (a
a :| [a]
as) = let !b :: b
b = a -> b
f a
a; !bs :: [b]
bs = (a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
List.map' a -> b
f [a]
as in b
b b -> [b] -> NonEmpty b
forall a. a -> [a] -> NonEmpty a
:| [b]
bs

-- Will be part of base with GHC 9.16 (base-4.23)
#if !MIN_VERSION_base(4,23,0)
-- | Like 'Maybe.mapMaybe'.
mapMaybe :: (a -> Maybe b) -> List1 a -> [b]
mapMaybe :: forall a b. (a -> Maybe b) -> List1 a -> [b]
mapMaybe a -> Maybe b
f = (a -> Maybe b) -> [a] -> [b]
forall a b. (a -> Maybe b) -> [a] -> [b]
Maybe.mapMaybe a -> Maybe b
f ([a] -> [b]) -> (List1 a -> [a]) -> List1 a -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List1 a -> [a]
forall a. NonEmpty a -> [a]
List1.toList
#endif

--------------------------------------------------------------------------------
-- Folds

-- [FIXME: Reed M, 20/05/2026] This is foldrMap1
-- | A variant of 'Data.List.foldr' but with a base case for the singleton list.
foldr :: (a -> b -> b) -> (a -> b) -> List1 a -> b
foldr :: forall a b. (a -> b -> b) -> (a -> b) -> List1 a -> b
foldr a -> b -> b
f a -> b
g (a
x :| [a]
xs) = a -> [a] -> b
loop a
x [a]
xs
  where
  loop :: a -> [a] -> b
loop a
x []       = a -> b
g a
x
  loop a
x (a
y : [a]
ys) = a -> b -> b
f a
x (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$ a -> [a] -> b
loop a
y [a]
ys

--------------------------------------------------------------------------------
-- Special folds

-- | Concatenate one or more non-empty lists.
concat :: [List1 a] -> [a]
concat :: forall a. [List1 a] -> [a]
concat = (List1 a -> [a]) -> [List1 a] -> [a]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap List1 a -> [a]
List1 a -> [Item (List1 a)]
forall l. IsList l => l -> [Item l]
toList

-- | A spine-strict variant of 'concat'.
concat' :: [List1 a] -> [a]
concat' :: forall a. [List1 a] -> [a]
concat' = (List1 a -> [a]) -> [List1 a] -> [a]
forall a b. (a -> [b]) -> [a] -> [b]
List.concatMap' List1 a -> [a]
List1 a -> [Item (List1 a)]
forall l. IsList l => l -> [Item l]
toList

-- | Map a function over a non-empty list and concatentate
-- the resulting non-empty lists.
concatMap1 :: (a -> List1 b) -> List1 a -> List1 b
concatMap1 :: forall a b. (a -> List1 b) -> List1 a -> List1 b
concatMap1 = (a -> NonEmpty b) -> NonEmpty a -> NonEmpty b
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
(=<<)

-- | Non-empty variant of 'Data.Maybe.catMaybes'.
catMaybes :: List1 (Maybe a) -> [a]
catMaybes :: forall a. List1 (Maybe a) -> [a]
catMaybes =  [Maybe a] -> [a]
forall a. [Maybe a] -> [a]
Maybe.catMaybes ([Maybe a] -> [a])
-> (List1 (Maybe a) -> [Maybe a]) -> List1 (Maybe a) -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List1 (Maybe a) -> [Maybe a]
forall a. NonEmpty a -> [a]
List1.toList

--------------------------------------------------------------------------------
-- Sublists

-- | Breaks a list just /after/ an element satisfying the predicate is
-- found.
--
-- ==== __Examples__
--
-- >>> breakAfter even [1,3,5,2,4,7,8]
-- (1 :| [3,5,2],[4,7,8])
breakAfter :: (a -> Bool) -> List1 a -> (List1 a, [a])
breakAfter :: forall a. (a -> Bool) -> List1 a -> (List1 a, [a])
breakAfter a -> Bool
p (a
x :| [a]
xs) = (a -> Bool) -> a -> [a] -> (NonEmpty a, [a])
forall a. (a -> Bool) -> a -> [a] -> (List1 a, [a])
List.breakAfter1 a -> Bool
p a
x [a]
xs

-- | \(\mathcal{O}(n)\). Split a list into sublists.
--
-- Generalisation of the prelude function @words@.
-- Same as 'Data.List.Split.wordsBy' and 'Data.List.Extra.wordsBy',
--  but with the non-emptyness guarantee on the chunks.
--
-- ==== __Laws__
--
-- > words xs == wordsBy isSpace xs
wordsBy :: (a -> Bool) -> [a] -> [List1 a]
wordsBy :: forall a. (a -> Bool) -> [a] -> [List1 a]
wordsBy a -> Bool
p = [a] -> [NonEmpty a]
loop
  where
  loop :: [a] -> [NonEmpty a]
loop [a]
as = case (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
List.dropWhile a -> Bool
p [a]
as of
    []   -> []
    a
x:[a]
xs -> (a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
ys) NonEmpty a -> [NonEmpty a] -> [NonEmpty a]
forall a. a -> [a] -> [a]
: [a] -> [NonEmpty a]
loop [a]
zs where ([a]
ys, [a]
zs) = (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.break a -> Bool
p [a]
xs

-- | Non-empty variant of 'Data.Either.partitionEithers'.
partitionEithers :: List1 (Either a b) -> ([a], [b])
partitionEithers :: forall a b. List1 (Either a b) -> ([a], [b])
partitionEithers = [Either a b] -> ([a], [b])
forall a b. [Either a b] -> ([a], [b])
Either.partitionEithers ([Either a b] -> ([a], [b]))
-> (List1 (Either a b) -> [Either a b])
-> List1 (Either a b)
-> ([a], [b])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List1 (Either a b) -> [Either a b]
forall a. NonEmpty a -> [a]
List1.toList

-- | Non-empty variant of 'Data.Either.lefts'.
lefts :: List1 (Either a b) -> [a]
lefts :: forall a b. List1 (Either a b) -> [a]
lefts = [Either a b] -> [a]
forall a b. [Either a b] -> [a]
Either.lefts  ([Either a b] -> [a])
-> (List1 (Either a b) -> [Either a b])
-> List1 (Either a b)
-> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List1 (Either a b) -> [Either a b]
forall a. NonEmpty a -> [a]
List1.toList

-- | Non-empty variant of 'Data.Either.rights'.
rights :: List1 (Either a b) -> [b]
rights :: forall a b. List1 (Either a b) -> [b]
rights = [Either a b] -> [b]
forall a b. [Either a b] -> [b]
Either.rights  ([Either a b] -> [b])
-> (List1 (Either a b) -> [Either a b])
-> List1 (Either a b)
-> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List1 (Either a b) -> [Either a b]
forall a. NonEmpty a -> [a]
List1.toList

--------------------------------------------------------------------------------
-- Grouping

-- | \(\mathcal{O}(n \log n)\).
--
-- ==== __Laws__
--
-- > groupOn f = groupBy ((==) \`on\` f) . List.sortBy (compare \`on\` f)
groupOn :: Ord b => (a -> b) -> [a] -> [List1 a]
groupOn :: forall b a. Ord b => (a -> b) -> [a] -> [List1 a]
groupOn a -> b
f = (a -> a -> Bool) -> [a] -> [NonEmpty a]
forall (f :: * -> *) a.
Foldable f =>
(a -> a -> Bool) -> f a -> [NonEmpty a]
List1.groupBy (b -> b -> Bool
forall a. Eq a => a -> a -> Bool
(==) (b -> b -> Bool) -> (a -> b) -> a -> a -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` a -> b
f) ([a] -> [NonEmpty a]) -> ([a] -> [a]) -> [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.sortBy (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)

groupOn1 :: Ord b => (a -> b) -> List1 a -> List1 (List1 a)
groupOn1 :: forall b a. Ord b => (a -> b) -> List1 a -> List1 (List1 a)
groupOn1 a -> b
f = (a -> a -> Bool) -> NonEmpty a -> NonEmpty (NonEmpty a)
forall a. (a -> a -> Bool) -> NonEmpty a -> NonEmpty (NonEmpty a)
List1.groupBy1 (b -> b -> Bool
forall a. Eq a => a -> a -> Bool
(==) (b -> b -> Bool) -> (a -> b) -> a -> a -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` a -> b
f) (NonEmpty a -> NonEmpty (NonEmpty a))
-> (NonEmpty a -> NonEmpty a)
-> NonEmpty a
-> NonEmpty (NonEmpty a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
forall a. (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a
List1.sortBy (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)

-- | \(\mathcal{O}(n)\). More precise type for 'Mikan.Utils.List.groupBy''.
--
-- A variant of 'List.groupBy' which applies the predicate to consecutive
-- pairs.
groupBy' :: forall a. (a -> a -> Bool) -> [a] -> [List1 a]
groupBy' :: forall a. (a -> a -> Bool) -> [a] -> [List1 a]
groupBy' a -> a -> Bool
_ []           = []
groupBy' a -> a -> Bool
p xxs :: [a]
xxs@(a
x : [a]
xs) = a -> [(Bool, a)] -> [List1 a]
grp a
x ([(Bool, a)] -> [List1 a]) -> [(Bool, a)] -> [List1 a]
forall a b. (a -> b) -> a -> b
$ (a -> a -> (Bool, a)) -> [a] -> [a] -> [(Bool, a)]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
List.zipWith (\ a
x a
y -> (a -> a -> Bool
p a
x a
y, a
y)) [a]
xxs [a]
xs
  where
  grp :: a -> [(Bool,a)] -> [List1 a]
  grp :: a -> [(Bool, a)] -> [List1 a]
grp a
x [(Bool, a)]
ys
    | let ([(Bool, a)]
xs, [(Bool, a)]
rest) = ((Bool, a) -> Bool) -> [(Bool, a)] -> ([(Bool, a)], [(Bool, a)])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.span (Bool, a) -> Bool
forall a b. (a, b) -> a
fst [(Bool, a)]
ys
    = (a
x a -> [a] -> List1 a
forall a. a -> [a] -> NonEmpty a
:| ((Bool, a) -> a) -> [(Bool, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
List.map (Bool, a) -> a
forall a b. (a, b) -> b
snd [(Bool, a)]
xs) List1 a -> [List1 a] -> [List1 a]
forall a. a -> [a] -> [a]
: case [(Bool, a)]
rest of
      []                 -> []
      ((Bool
_false, a
z) : [(Bool, a)]
zs) -> a -> [(Bool, a)] -> [List1 a]
grp a
z [(Bool, a)]
zs

-- | \(\mathcal{O}(n)\). Group consecutive items that share the same first component.
groupByFst :: forall a b. Eq a => [(a,b)] -> [(a, List1 b)]
groupByFst :: forall a b. Eq a => [(a, b)] -> [(a, List1 b)]
groupByFst =
    (NonEmpty (a, b) -> (a, List1 b))
-> [NonEmpty (a, b)] -> [(a, List1 b)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\ ((a
tag, b
b) :| [(a, b)]
xs) -> (a
tag, b
b b -> [b] -> List1 b
forall a. a -> [a] -> NonEmpty a
:| ((a, b) -> b) -> [(a, b)] -> [b]
forall a b. (a -> b) -> [a] -> [b]
List.map (a, b) -> b
forall a b. (a, b) -> b
snd [(a, b)]
xs))
      -- Float the grouping to the top level
  ([NonEmpty (a, b)] -> [(a, List1 b)])
-> ([(a, b)] -> [NonEmpty (a, b)]) -> [(a, b)] -> [(a, List1 b)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, b) -> (a, b) -> Bool) -> [(a, b)] -> [NonEmpty (a, b)]
forall (f :: * -> *) a.
Foldable f =>
(a -> a -> Bool) -> f a -> [NonEmpty a]
List1.groupBy (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==) (a -> a -> Bool) -> ((a, b) -> a) -> (a, b) -> (a, b) -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (a, b) -> a
forall a b. (a, b) -> a
fst)
      -- Group together characters in the same role.

-- | \(\mathcal{O}(n)\). Group consecutive items that share the same first component.
groupByFst1 :: forall a b. Eq a => List1 (a, b) -> List1 (a, List1 b)
groupByFst1 :: forall a b. Eq a => List1 (a, b) -> List1 (a, List1 b)
groupByFst1 =
    (NonEmpty (a, b) -> (a, List1 b))
-> NonEmpty (NonEmpty (a, b)) -> NonEmpty (a, List1 b)
forall a b. (a -> b) -> List1 a -> List1 b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\ ((a
tag, b
b) :| [(a, b)]
xs) -> (a
tag, b
b b -> [b] -> List1 b
forall a. a -> [a] -> NonEmpty a
:| ((a, b) -> b) -> [(a, b)] -> [b]
forall a b. (a -> b) -> [a] -> [b]
List.map (a, b) -> b
forall a b. (a, b) -> b
snd [(a, b)]
xs))
      -- Float the grouping to the top level
  (NonEmpty (NonEmpty (a, b)) -> NonEmpty (a, List1 b))
-> (NonEmpty (a, b) -> NonEmpty (NonEmpty (a, b)))
-> NonEmpty (a, b)
-> NonEmpty (a, List1 b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, b) -> (a, b) -> Bool)
-> NonEmpty (a, b) -> NonEmpty (NonEmpty (a, b))
forall a. (a -> a -> Bool) -> NonEmpty a -> NonEmpty (NonEmpty a)
List1.groupBy1 (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==) (a -> a -> Bool) -> ((a, b) -> a) -> (a, b) -> (a, b) -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (a, b) -> a
forall a b. (a, b) -> a
fst)
      -- Group together characters in the same role.

--------------------------------------------------------------------------------
-- Zipping and unzipping non-empty lists

-- | Like 'Control.Monad.zipWithM'.
zipWithM :: Applicative m => (a -> b -> m c) -> List1 a -> List1 b -> m (List1 c)
zipWithM :: forall (m :: * -> *) a b c.
Applicative m =>
(a -> b -> m c) -> List1 a -> List1 b -> m (List1 c)
zipWithM a -> b -> m c
f (a
a :| [a]
as) (b
b :| [b]
bs) = c -> [c] -> NonEmpty c
forall a. a -> [a] -> NonEmpty a
(:|) (c -> [c] -> NonEmpty c) -> m c -> m ([c] -> NonEmpty c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> b -> m c
f a
a b
b m ([c] -> NonEmpty c) -> m [c] -> m (NonEmpty c)
forall a b. m (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (a -> b -> m c) -> [a] -> [b] -> m [c]
forall (m :: * -> *) a b c.
Applicative m =>
(a -> b -> m c) -> [a] -> [b] -> m [c]
List.zipWithM a -> b -> m c
f [a]
as [b]
bs

-- | Like 'Control.Monad.zipWithM'.
zipWithM_ :: Applicative m => (a -> b -> m c) -> List1 a -> List1 b -> m ()
zipWithM_ :: forall (m :: * -> *) a b c.
Applicative m =>
(a -> b -> m c) -> List1 a -> List1 b -> m ()
zipWithM_ a -> b -> m c
f (a
a :| [a]
as) (b
b :| [b]
bs) = a -> b -> m c
f a
a b
b m c -> m () -> m ()
forall a b. m a -> m b -> m b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> (a -> b -> m c) -> [a] -> [b] -> m ()
forall (m :: * -> *) a b c.
Applicative m =>
(a -> b -> m c) -> [a] -> [b] -> m ()
List.zipWithM_ a -> b -> m c
f [a]
as [b]
bs

-- | Like 'Mikan.Utils.List.unzipWith'.
unzipWith :: (a -> (b, c)) -> List1 a -> (List1 b, List1 c)
unzipWith :: forall a b c. (a -> (b, c)) -> List1 a -> (List1 b, List1 c)
unzipWith a -> (b, c)
f = NonEmpty (b, c) -> (NonEmpty b, NonEmpty c)
forall (f :: * -> *) a b. Functor f => f (a, b) -> (f a, f b)
unzip (NonEmpty (b, c) -> (NonEmpty b, NonEmpty c))
-> (List1 a -> NonEmpty (b, c))
-> List1 a
-> (NonEmpty b, NonEmpty c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (b, c)) -> List1 a -> NonEmpty (b, c)
forall a b. (a -> b) -> List1 a -> List1 b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> (b, c)
f

--------------------------------------------------------------------------------
-- Searching non-empty lists

-- | Non-empty variant of 'Data.List.find'.
find :: (a -> Bool) -> List1 a -> Maybe a
find :: forall a. (a -> Bool) -> List1 a -> Maybe a
find a -> Bool
f = (a -> Bool) -> [a] -> Maybe a
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a
List.find a -> Bool
f ([a] -> Maybe a) -> (List1 a -> [a]) -> List1 a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List1 a -> [a]
forall a. NonEmpty a -> [a]
List1.toList

-- | A strict variant of 'Data.List.filter'.
filter' :: (a -> Bool) -> List1 a -> [a]
filter' :: forall a. (a -> Bool) -> List1 a -> [a]
filter' a -> Bool
f (a
a :| [a]
as) =
  let !as' :: [a]
as' = (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
List.filter' a -> Bool
f [a]
as
  in if a -> Bool
f a
a then a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
as' else [a]
as'

--------------------------------------------------------------------------------
-- String operations

-- | A 'String1' is a non-empty string.
type String1 = List1 Char

-- | Non-empty variant of 'Data.List.unwords'.
unwords :: List1 String -> String
unwords :: List1 String -> String
unwords = [String] -> String
List.unwords ([String] -> String)
-> (List1 String -> [String]) -> List1 String -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. List1 String -> [String]
forall a. NonEmpty a -> [a]
List1.toList

--------------------------------------------------------------------------------
-- "Set" operations

-- | \(\mathcal{O}(mn)\). Non-empty variant of 'Data.List.union'.
--
-- Duplicates in the first list are not removed.
union :: Eq a => List1 a -> List1 a -> List1 a
union :: forall a. Eq a => List1 a -> List1 a -> List1 a
union (a
a :| [a]
as) NonEmpty a
bs = a
a a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a] -> [a] -> [a]
forall a. Eq a => [a] -> [a] -> [a]
List.union [a]
as ((a -> Bool) -> NonEmpty a -> [a]
forall a. (a -> Bool) -> List1 a -> [a]
filter (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
a) NonEmpty a
bs)

-- | \(\mathcal{O}(n)\). Checks if all the elements in the list are equal.
--
-- Assumes that the 'Eq' instance stands for an equivalence relation.
allEqual :: Eq a => List1 a -> Bool
allEqual :: forall a. Eq a => List1 a -> Bool
allEqual (a
x :| [a]
xs) = (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x) [a]
xs

-- | \(\mathcal{O}(n^2)\). Non-efficient, monadic 'nub'.
nubM :: Monad m => (a -> a -> m Bool) -> List1 a -> m (List1 a)
nubM :: forall (m :: * -> *) a.
Monad m =>
(a -> a -> m Bool) -> List1 a -> m (List1 a)
nubM a -> a -> m Bool
eq (a
a :| [a]
as) = (a
a a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:|) ([a] -> NonEmpty a) -> m [a] -> m (NonEmpty a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> do (a -> a -> m Bool) -> [a] -> m [a]
forall (m :: * -> *) a.
Monad m =>
(a -> a -> m Bool) -> [a] -> m [a]
List.nubM a -> a -> m Bool
eq ([a] -> m [a]) -> m [a] -> m [a]
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< (a -> m Bool) -> [a] -> m [a]
forall (m :: * -> *) a.
Applicative m =>
(a -> m Bool) -> [a] -> m [a]
filterM (Bool -> Bool
not (Bool -> Bool) -> (a -> m Bool) -> a -> m Bool
forall (m :: * -> *) b c a.
Functor m =>
(b -> c) -> (a -> m b) -> a -> m c
<.> a -> a -> m Bool
eq a
a) [a]
as

--------------------------------------------------------------------------------
-- Recovering non-emptyness

ifNull :: [a] -> b -> (List1 a -> b) -> b
ifNull :: forall a b. [a] -> b -> (List1 a -> b) -> b
ifNull []       b
b List1 a -> b
_ = b
b
ifNull (a
a : [a]
as) b
_ List1 a -> b
f = List1 a -> b
f (List1 a -> b) -> List1 a -> b
forall a b. (a -> b) -> a -> b
$ a
a a -> [a] -> List1 a
forall a. a -> [a] -> NonEmpty a
:| [a]
as

ifNotNull :: [a] -> (List1 a -> b) -> b -> b
ifNotNull :: forall a b. [a] -> (List1 a -> b) -> b -> b
ifNotNull []       List1 a -> b
_ b
b = b
b
ifNotNull (a
a : [a]
as) List1 a -> b
f b
_ = List1 a -> b
f (List1 a -> b) -> List1 a -> b
forall a b. (a -> b) -> a -> b
$ a
a a -> [a] -> List1 a
forall a. a -> [a] -> NonEmpty a
:| [a]
as

-- | The more general type @Null m => [a] -> (List1 a -> m) -> m@
--   often causes type inference to fail, as we do not in general have
--   @instance Applicative m => Null (m ())@.
unlessNull :: Applicative m => [a] -> (List1 a -> m ()) -> m ()
unlessNull :: forall (m :: * -> *) a.
Applicative m =>
[a] -> (List1 a -> m ()) -> m ()
unlessNull []       List1 a -> m ()
_ = () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
unlessNull (a
x : [a]
xs) List1 a -> m ()
f = List1 a -> m ()
f (List1 a -> m ()) -> List1 a -> m ()
forall a b. (a -> b) -> a -> b
$ a
x a -> [a] -> List1 a
forall a. a -> [a] -> NonEmpty a
:| [a]
xs

unlessNullM :: Monad m => m [a] -> (List1 a -> m ()) -> m ()
unlessNullM :: forall (m :: * -> *) a.
Monad m =>
m [a] -> (List1 a -> m ()) -> m ()
unlessNullM m [a]
m List1 a -> m ()
k = m [a]
m m [a] -> ([a] -> m ()) -> m ()
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= ([a] -> (List1 a -> m ()) -> m ()
forall (m :: * -> *) a.
Applicative m =>
[a] -> (List1 a -> m ()) -> m ()
`unlessNull` List1 a -> m ()
k)

--------------------------------------------------------------------------------
-- Conversions

{-# INLINE toList' #-}
-- | Lossless 'toList', opposite of 'nonEmpty'.
toList' :: Maybe (List1 a) -> [a]
toList' :: forall a. Maybe (List1 a) -> [a]
toList' = [a] -> (List1 a -> [a]) -> Maybe (List1 a) -> [a]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe [] List1 a -> [a]
List1 a -> [Item (List1 a)]
forall l. IsList l => l -> [Item l]
toList

{-# INLINE fromListSafe #-}
-- | Safe version of 'Data.List.NonEmpty.fromList'.
fromListSafe
  :: List1 a  -- ^ Default value if convertee is empty.
  -> [a]      -- ^ List to convert, supposedly non-empty.
  -> List1 a  -- ^ Converted list.
fromListSafe :: forall a. List1 a -> [a] -> List1 a
fromListSafe List1 a
err   [] = List1 a
err
fromListSafe List1 a
_ (a
x:[a]
xs) = a
x a -> [a] -> List1 a
forall a. a -> [a] -> NonEmpty a
:| [a]
xs

-- | Lift a function on non-empty lists to a function on lists.
--
-- This is in essence 'fmap' for 'Maybe', if we take @[a] = Maybe (List1 a)@.
liftList1 :: (List1 a -> List1 b) -> [a] -> [b]
liftList1 :: forall a b. (List1 a -> List1 b) -> [a] -> [b]
liftList1 List1 a -> List1 b
f = Maybe (List1 b) -> [b]
forall a. Maybe (List1 a) -> [a]
toList' (Maybe (List1 b) -> [b]) -> ([a] -> Maybe (List1 b)) -> [a] -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (List1 a -> List1 b) -> Maybe (List1 a) -> Maybe (List1 b)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap List1 a -> List1 b
f (Maybe (List1 a) -> Maybe (List1 b))
-> ([a] -> Maybe (List1 a)) -> [a] -> Maybe (List1 b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Maybe (List1 a)
forall a. [a] -> Maybe (NonEmpty a)
nonEmpty

--------------------------------------------------------------------------------
-- Optics

-- | \(\mathcal{O}(1)\). Focus on the first element of a non-empty list.
lensHead :: Functor f => (a -> f a) -> List1 a -> f (List1 a)
lensHead :: forall (f :: * -> *) a.
Functor f =>
(a -> f a) -> List1 a -> f (List1 a)
lensHead a -> f a
f (a
a :| [a]
as) = a -> f a
f a
a f a -> (a -> NonEmpty a) -> f (NonEmpty a)
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> (a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
as)

-- | \(\mathcal{O}(n)\). Focus on the last element of a non-empty list.
lensLast :: Functor f => (a -> f a) -> List1 a -> f (List1 a)
lensLast :: forall (f :: * -> *) a.
Functor f =>
(a -> f a) -> List1 a -> f (List1 a)
lensLast a -> f a
f (a
a :| [a]
as) = a -> [a] -> f (NonEmpty a)
loop a
a [a]
as
  where
  loop :: a -> [a] -> f (NonEmpty a)
loop a
a []       = a -> NonEmpty a
forall a. a -> NonEmpty a
singleton (a -> NonEmpty a) -> f a -> f (NonEmpty a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f a
f a
a
  loop a
a (a
b : [a]
bs) = a -> NonEmpty a -> NonEmpty a
forall a. a -> NonEmpty a -> NonEmpty a
cons a
a (NonEmpty a -> NonEmpty a) -> f (NonEmpty a) -> f (NonEmpty a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> [a] -> f (NonEmpty a)
loop a
b [a]
bs