{-# OPTIONS_GHC -Wno-redundant-constraints #-}

{-# LANGUAGE DataKinds            #-}
{-# LANGUAGE Safe                 #-}
{-# LANGUAGE TypeFamilies         #-}
{-# LANGUAGE TypeOperators        #-}
{-# LANGUAGE UndecidableInstances #-}

{- |
Copyright:  (c) 2011-2015 Edward Kmett
            (c) 2018-2020 Kowainik
SPDX-License-Identifier: MIT
Maintainer:  Kowainik <xrom.xkov@gmail.com>
Stability:   Experimental
Portability: Portable

'Foldable1' is a typeclass like 'Data.Foldable.Foldable' but for non-empty
structures. For example, 'Relude.NonEmpty', 'Relude.Identity'.

'Foldable1' has all type-safe and total methods like `head1`, `maximum1` in
contradiction with 'Data.Foldable.Foldable'.

@since 0.3.0
-}

module Relude.Extra.Foldable1
    ( Foldable1 (..)
    , foldl1'
    ) where

import Relude hiding (Product (..), Sum (..))
import Relude.Extra.Newtype (( #. ))

import Data.Functor.Product (Product (..))
import Data.Functor.Sum (Sum (..))
import GHC.TypeLits (ErrorMessage (..), TypeError)

import qualified Data.Semigroup as SG


-- $setup
-- >>> import Relude

{- | The class of foldable data structures that cannot be empty.

@since 0.3.0
-}
class Foldable f => Foldable1 f where
    {-# MINIMAL foldMap1 #-}

    {- | Map each element of the non-empty structure to a semigroup, and combine the results.

    >>> foldMap1 SG.Sum (1 :| [2, 3, 4])
    Sum {getSum = 10}
    >>> foldMap1 show (123 :| [456, 789, 0])
    "1234567890"
    -}
    foldMap1 :: Semigroup m => (a -> m) -> f a -> m

    {- | Combine the elements of a non-empty structure using a semigroup.

    >>> fold1 (1 :| [2, 3, 4 :: SG.Sum Int])
    Sum {getSum = 10}
    >>> fold1 (4 :| [5, 10 :: SG.Product Int])
    Product {getProduct = 200}
    -}
    fold1 :: Semigroup m => f m -> m
    fold1 = (m -> m) -> f m -> m
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 m -> m
forall a. a -> a
id

    {- | Convert a non-empty data structure to a NonEmpty list.

    >>> toNonEmpty (Identity 2)
    2 :| []
    -}
    toNonEmpty :: f a -> NonEmpty a
    toNonEmpty = (a -> NonEmpty a) -> f a -> NonEmpty a
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 (a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:|[])

    {- | The first element of a non-empty data structure.

    >>> head1 (1 :| [2, 3, 4])
    1
    -}
    head1 :: f a -> a
    head1 = First a -> a
forall a. First a -> a
SG.getFirst (First a -> a) -> (f a -> First a) -> f a -> a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> First a) -> f a -> First a
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 a -> First a
forall a. a -> First a
SG.First

    {- | The last element of a non-empty data structure.

    >>> last1 (1 :| [2, 3, 4])
    4
    -}
    last1 :: f a -> a
    last1 = Last a -> a
forall a. Last a -> a
SG.getLast (Last a -> a) -> (f a -> Last a) -> f a -> a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Last a) -> f a -> Last a
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 a -> Last a
forall a. a -> Last a
SG.Last

    {- | The largest element of a non-empty data structure.

    >>> maximum1 (32 :| [64, 8, 128, 16])
    128
    -}
    maximum1 :: Ord a => f a -> a
    maximum1 = Max a -> a
forall a. Max a -> a
SG.getMax (Max a -> a) -> (f a -> Max a) -> f a -> a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Max a) -> f a -> Max a
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 a -> Max a
forall a. a -> Max a
SG.Max

    {- | The smallest element of a non-empty data structure.

    >>> minimum1 (32 :| [64, 8, 128, 16])
    8
    -}
    minimum1 :: Ord a => f a -> a
    minimum1 = Min a -> a
forall a. Min a -> a
SG.getMin (Min a -> a) -> (f a -> Min a) -> f a -> a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Min a) -> f a -> Min a
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 a -> Min a
forall a. a -> Min a
SG.Min

{- |

@since 0.3.0
-}
instance Foldable1 NonEmpty where
    fold1 :: Semigroup m => NonEmpty m -> m
    fold1 :: NonEmpty m -> m
fold1 = NonEmpty m -> m
forall m. Semigroup m => NonEmpty m -> m
sconcat
    {-# INLINE fold1 #-}

    foldMap1 :: forall m a . Semigroup m => (a -> m) -> NonEmpty a -> m
    foldMap1 :: (a -> m) -> NonEmpty a -> m
foldMap1 f :: a -> m
f (a :: a
a :| as :: [a]
as) = (a -> (a -> m) -> a -> m) -> (a -> m) -> [a] -> a -> m
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> (a -> m) -> a -> m
go a -> m
f [a]
as a
a
      where
        go :: a -> (a -> m) -> a -> m
        go :: a -> (a -> m) -> a -> m
go b :: a
b g :: a -> m
g x :: a
x = a -> m
f a
x m -> m -> m
forall a. Semigroup a => a -> a -> a
<> a -> m
g a
b
    {-# INLINE foldMap1 #-}

    toNonEmpty :: NonEmpty a -> NonEmpty a
    toNonEmpty :: NonEmpty a -> NonEmpty a
toNonEmpty = NonEmpty a -> NonEmpty a
forall a. a -> a
id
    {-# INLINE toNonEmpty #-}

    head1, last1 :: NonEmpty a -> a
    head1 :: NonEmpty a -> a
head1 = NonEmpty a -> a
forall (f :: * -> *) a. IsNonEmpty f a a "head" => f a -> a
head
    last1 :: NonEmpty a -> a
last1 = NonEmpty a -> a
forall (f :: * -> *) a. IsNonEmpty f a a "last" => f a -> a
last
    {-# INLINE head1 #-}
    {-# INLINE last1 #-}

    maximum1, minimum1 :: Ord a => NonEmpty a -> a
    maximum1 :: NonEmpty a -> a
maximum1 = (a -> a -> a) -> NonEmpty a -> a
forall a. (a -> a -> a) -> NonEmpty a -> a
foldl1' a -> a -> a
forall a. Ord a => a -> a -> a
max
    minimum1 :: NonEmpty a -> a
minimum1 = (a -> a -> a) -> NonEmpty a -> a
forall a. (a -> a -> a) -> NonEmpty a -> a
foldl1' a -> a -> a
forall a. Ord a => a -> a -> a
min
    {-# INLINE maximum1 #-}
    {-# INLINE minimum1 #-}

{- |

@since 0.3.0
-}
instance Foldable1 Identity where
    foldMap1 :: Semigroup m => (a -> m) -> Identity a -> m
    foldMap1 :: (a -> m) -> Identity a -> m
foldMap1 = (a -> m) -> Identity a -> m
forall a b. Coercible a b => a -> b
coerce
    {-# INLINE foldMap1 #-}

    fold1 :: Semigroup m => Identity m -> m
    fold1 :: Identity m -> m
fold1 = Identity m -> m
forall a b. Coercible a b => a -> b
coerce
    {-# INLINE fold1 #-}

    toNonEmpty :: Identity a -> NonEmpty a
    toNonEmpty :: Identity a -> NonEmpty a
toNonEmpty = (a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:|[]) (a -> NonEmpty a) -> (Identity a -> a) -> Identity a -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Identity a -> a
forall a b. Coercible a b => a -> b
coerce
    {-# INLINE toNonEmpty #-}

    head1 :: Identity a -> a
    head1 :: Identity a -> a
head1 = Identity a -> a
forall a b. Coercible a b => a -> b
coerce
    {-# INLINE head1 #-}

    last1 :: Identity a -> a
    last1 :: Identity a -> a
last1 = Identity a -> a
forall a b. Coercible a b => a -> b
coerce
    {-# INLINE last1 #-}

    maximum1 :: Ord a => Identity a -> a
    maximum1 :: Identity a -> a
maximum1 = Identity a -> a
forall a b. Coercible a b => a -> b
coerce
    {-# INLINE maximum1 #-}

    minimum1 :: Ord a => Identity a -> a
    minimum1 :: Identity a -> a
minimum1 = Identity a -> a
forall a b. Coercible a b => a -> b
coerce
    {-# INLINE minimum1 #-}

{- |

@since 0.3.0
-}
instance Foldable1 ((,) c) where
    foldMap1 :: Semigroup m => (a -> m) -> (c, a) -> m
    foldMap1 :: (a -> m) -> (c, a) -> m
foldMap1 f :: a -> m
f = a -> m
f (a -> m) -> ((c, a) -> a) -> (c, a) -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c, a) -> a
forall c a. (c, a) -> a
snd
    {-# INLINE foldMap1 #-}

    fold1 :: Semigroup m => (c, m) -> m
    fold1 :: (c, m) -> m
fold1 = (c, m) -> m
forall c a. (c, a) -> a
snd
    {-# INLINE fold1 #-}

    toNonEmpty :: (c, a) -> NonEmpty a
    toNonEmpty :: (c, a) -> NonEmpty a
toNonEmpty (_, y :: a
y) = (a
y a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [])
    {-# INLINE toNonEmpty #-}

    head1, last1 :: (c, a) -> a
    head1 :: (c, a) -> a
head1 = (c, a) -> a
forall c a. (c, a) -> a
snd
    last1 :: (c, a) -> a
last1 = (c, a) -> a
forall c a. (c, a) -> a
snd
    {-# INLINE head1 #-}
    {-# INLINE last1 #-}

    maximum1, minimum1 :: Ord a => (c, a) -> a
    maximum1 :: (c, a) -> a
maximum1 = (c, a) -> a
forall c a. (c, a) -> a
snd
    minimum1 :: (c, a) -> a
minimum1 = (c, a) -> a
forall c a. (c, a) -> a
snd
    {-# INLINE maximum1 #-}
    {-# INLINE minimum1 #-}

{- |

@since 0.3.0
-}
instance (Foldable1 f, Foldable1 g) => Foldable1 (Compose f g) where
    foldMap1 :: Semigroup m => (a -> m) -> Compose f g a -> m
    foldMap1 :: (a -> m) -> Compose f g a -> m
foldMap1 f :: a -> m
f = (g a -> m) -> f (g a) -> m
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 ((a -> m) -> g a -> m
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 a -> m
f) (f (g a) -> m) -> (Compose f g a -> f (g a)) -> Compose f g a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Compose f g a -> f (g a)
forall k1 (f :: k1 -> *) k2 (g :: k2 -> k1) (a :: k2).
Compose f g a -> f (g a)
getCompose
    {-# INLINE foldMap1 #-}

    head1 :: Compose f g a -> a
    head1 :: Compose f g a -> a
head1 = g a -> a
forall (f :: * -> *) a. Foldable1 f => f a -> a
head1 (g a -> a) -> (Compose f g a -> g a) -> Compose f g a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f (g a) -> g a
forall (f :: * -> *) a. Foldable1 f => f a -> a
head1 (f (g a) -> g a)
-> (Compose f g a -> f (g a)) -> Compose f g a -> g a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Compose f g a -> f (g a)
forall k1 (f :: k1 -> *) k2 (g :: k2 -> k1) (a :: k2).
Compose f g a -> f (g a)
getCompose
    {-# INLINE head1 #-}

    last1 :: Compose f g a -> a
    last1 :: Compose f g a -> a
last1 = g a -> a
forall (f :: * -> *) a. Foldable1 f => f a -> a
last1 (g a -> a) -> (Compose f g a -> g a) -> Compose f g a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f (g a) -> g a
forall (f :: * -> *) a. Foldable1 f => f a -> a
last1 (f (g a) -> g a)
-> (Compose f g a -> f (g a)) -> Compose f g a -> g a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Compose f g a -> f (g a)
forall k1 (f :: k1 -> *) k2 (g :: k2 -> k1) (a :: k2).
Compose f g a -> f (g a)
getCompose
    {-# INLINE last1 #-}

{- |

@since 0.3.0
-}
instance (Foldable1 f, Foldable1 g) => Foldable1 (Product f g) where
    foldMap1 :: Semigroup m => (a -> m) -> Product f g a -> m
    foldMap1 :: (a -> m) -> Product f g a -> m
foldMap1 f :: a -> m
f (Pair a :: f a
a b :: g a
b) = (a -> m) -> f a -> m
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 a -> m
f f a
a m -> m -> m
forall a. Semigroup a => a -> a -> a
<> (a -> m) -> g a -> m
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 a -> m
f g a
b
    {-# INLINE foldMap1 #-}

{- |

@since 0.3.0
-}
instance (Foldable1 f, Foldable1 g) => Foldable1 (Sum f g) where
    foldMap1 :: Semigroup m => (a -> m) -> Sum f g a -> m
    foldMap1 :: (a -> m) -> Sum f g a -> m
foldMap1 f :: a -> m
f (InL x :: f a
x) = (a -> m) -> f a -> m
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 a -> m
f f a
x
    foldMap1 f :: a -> m
f (InR y :: g a
y) = (a -> m) -> g a -> m
forall (f :: * -> *) m a.
(Foldable1 f, Semigroup m) =>
(a -> m) -> f a -> m
foldMap1 a -> m
f g a
y
    {-# INLINE foldMap1 #-}


----------------------------------------------------------------------------
-- List custom error
----------------------------------------------------------------------------

-- | For tracking usage of ordinary list with 'Foldable1' functions.
type family IsListError :: Constraint
  where
    IsListError = TypeError
        ( 'Text "The methods of the 'Foldable1' type class work with non-empty containers."
        ':$$: 'Text "However, one of the 'Foldable1' functions is applied to the List."
        ':$$: 'Text ""
        ':$$: 'Text "Possible fixes:"
        ':$$: 'Text "  * Replace []"
        ':$$: 'Text "    with one of the: 'NonEmpty', 'Identity', '(c,)', 'Compose f g', 'Product f g', 'Sum f g'"
        ':$$: 'Text "  * Or use 'Foldable' class for your own risk."
        )


{- | ⚠️__CAUTION__⚠️ This instance is for custom error display only.

'Foldable1' is not supposed to be used with the lists.

In case it is used by mistake, the user will see the following:

>>> head1 [1, 2, 3]
...
... The methods of the 'Foldable1' type class work with non-empty containers.
      However, one of the 'Foldable1' functions is applied to the List.
...
      Possible fixes:
        * Replace []
          with one of the: 'NonEmpty', 'Identity', '(c,)', 'Compose f g', 'Product f g', 'Sum f g'
        * Or use 'Foldable' class for your own risk.
...

@since 0.6.0.0
-}
instance IsListError => Foldable1 [] where
    foldMap1 :: Semigroup m => (a -> m) -> [a] -> m
    foldMap1 :: (a -> m) -> [a] -> m
foldMap1 _ _ = Text -> m
forall a t. (HasCallStack, IsText t) => t -> a
error "Unreachable list instance of Foldable1"

    fold1 :: Semigroup m => [m] -> m
    fold1 :: [m] -> m
fold1 _ = Text -> m
forall a t. (HasCallStack, IsText t) => t -> a
error "Unreachable list instance of Foldable1"

    toNonEmpty :: [a] -> NonEmpty a
    toNonEmpty :: [a] -> NonEmpty a
toNonEmpty _ = Text -> NonEmpty a
forall a t. (HasCallStack, IsText t) => t -> a
error "Unreachable list instance of Foldable1"

    head1 :: [a] -> a
    head1 :: [a] -> a
head1 _ = Text -> a
forall a t. (HasCallStack, IsText t) => t -> a
error "Unreachable list instance of Foldable1"

    last1 :: [a] -> a
    last1 :: [a] -> a
last1 _ = Text -> a
forall a t. (HasCallStack, IsText t) => t -> a
error "Unreachable list instance of Foldable1"

    maximum1 :: Ord a => [a] -> a
    maximum1 :: [a] -> a
maximum1 _ = Text -> a
forall a t. (HasCallStack, IsText t) => t -> a
error "Unreachable list instance of Foldable1"

    minimum1 :: Ord a => [a] -> a
    minimum1 :: [a] -> a
minimum1 _ = Text -> a
forall a t. (HasCallStack, IsText t) => t -> a
error "Unreachable list instance of Foldable1"

{- | Strictly folds non-empty structure with given function @f@:

@
foldl1' f [x0, x1, x2 ...] = f (f x0 x1) x2 ...
@

>>> foldl1' (++) ([1,2] :| [[3,4], [5,6]])
[1,2,3,4,5,6]

@since 0.3.0
-}
foldl1' :: (a -> a -> a) -> NonEmpty a -> a
foldl1' :: (a -> a -> a) -> NonEmpty a -> a
foldl1' _ (x :: a
x :| [])     = a
x
foldl1' f :: a -> a -> a
f (x :: a
x :| (y :: a
y:ys :: [a]
ys)) = (a -> a -> a) -> a -> [a] -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' a -> a -> a
f (a -> a -> a
f a
x a
y) [a]
ys
{-# INLINE foldl1' #-}