{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DefaultSignatures          #-}
{-# LANGUAGE DeriveDataTypeable         #-}
{-# LANGUAGE DeriveGeneric              #-}
{-# LANGUAGE FlexibleContexts           #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE PolyKinds                  #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE Trustworthy                #-}
{-# LANGUAGE TypeOperators              #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Semigroup
-- Copyright   :  (C) 2011-2015 Edward Kmett
-- License     :  BSD-style (see the file LICENSE)
--
-- Maintainer  :  libraries@haskell.org
-- Stability   :  provisional
-- Portability :  portable
--
-- A type @a@ is a 'Semigroup' if it provides an associative function ('<>')
-- that lets you combine any two values of type @a@ into one. Where being
-- associative means that the following must always hold:
--
-- >>> (a <> b) <> c == a <> (b <> c)
--
-- ==== __Examples__
--
-- The 'Min' 'Semigroup' instance for 'Int' is defined to always pick the smaller
-- number:
-- >>> Min 1 <> Min 2 <> Min 3 <> Min 4 :: Min Int
-- Min {getMin = 1}
--
-- If we need to combine multiple values we can use the 'sconcat' function
-- to do so. We need to ensure however that we have at least one value to
-- operate on, since otherwise our result would be undefined. It is for this
-- reason that 'sconcat' uses "Data.List.NonEmpty.NonEmpty" - a list that
-- can never be empty:
--
-- >>> (1 :| [])
-- 1 :| []               -- equivalent to [1] but guaranteed to be non-empty
-- >>> (1 :| [2, 3, 4])
-- 1 :| [2,3,4]          -- equivalent to [1,2,3,4] but guaranteed to be non-empty
--
-- Equipped with this guaranteed to be non-empty data structure, we can combine
-- values using 'sconcat' and a 'Semigroup' of our choosing. We can try the 'Min'
-- and 'Max' instances of 'Int' which pick the smallest, or largest number
-- respectively:
--
-- >>> sconcat (1 :| [2, 3, 4]) :: Min Int
-- Min {getMin = 1}
-- >>> sconcat (1 :| [2, 3, 4]) :: Max Int
-- Max {getMax = 4}
--
-- String concatenation is another example of a 'Semigroup' instance:
--
-- >>> "foo" <> "bar"
-- "foobar"
--
-- A 'Semigroup' is a generalization of a 'Monoid'. Yet unlike the 'Semigroup', the 'Monoid'
-- requires the presence of a neutral element ('mempty') in addition to the associative
-- operator. The requirement for a neutral element prevents many types from being a full Monoid,
-- like "Data.List.NonEmpty.NonEmpty".
--
-- Note that the use of @(\<\>)@ in this module conflicts with an operator with the same
-- name that is being exported by "Data.Monoid". However, this package
-- re-exports (most of) the contents of Data.Monoid, so to use semigroups
-- and monoids in the same package just
--
-- > import Data.Semigroup
--
-- @since 4.9.0.0
----------------------------------------------------------------------------
module Data.Semigroup (
    Semigroup(..)
  , stimesMonoid
  , stimesIdempotent
  , stimesIdempotentMonoid
  , mtimesDefault
  -- * Semigroups
  , Min(..)
  , Max(..)
  , First(..)
  , Last(..)
  , WrappedMonoid(..)
  -- * Re-exported monoids from Data.Monoid
  , Dual(..)
  , Endo(..)
  , All(..)
  , Any(..)
  , Sum(..)
  , Product(..)
  -- * A better monoid for Maybe
  , Option(..)
  , option
  -- * Difference lists of a semigroup
  , diff
  , cycle1
  -- * ArgMin, ArgMax
  , Arg(..)
  , ArgMin
  , ArgMax
  ) where

import           Prelude             hiding (foldr1)

import GHC.Base (Semigroup(..))

import           Data.Semigroup.Internal

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Fix
import           Data.Bifoldable
import           Data.Bifunctor
import           Data.Bitraversable
import           Data.Coerce
import           Data.Data
import           GHC.Generics

-- | A generalization of 'Data.List.cycle' to an arbitrary 'Semigroup'.
-- May fail to terminate for some values in some semigroups.
cycle1 :: Semigroup m => m -> m
cycle1 :: m -> m
cycle1 m
xs = m
xs' where xs' :: m
xs' = m
xs m -> m -> m
forall a. Semigroup a => a -> a -> a
<> m
xs'

-- | This lets you use a difference list of a 'Semigroup' as a 'Monoid'.
diff :: Semigroup m => m -> Endo m
diff :: m -> Endo m
diff = (m -> m) -> Endo m
forall a. (a -> a) -> Endo a
Endo ((m -> m) -> Endo m) -> (m -> m -> m) -> m -> Endo m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m -> m -> m
forall a. Semigroup a => a -> a -> a
(<>)

newtype Min a = Min { Min a -> a
getMin :: a }
  deriving ( Bounded  -- ^ @since 4.9.0.0
           , Eq       -- ^ @since 4.9.0.0
           , Ord      -- ^ @since 4.9.0.0
           , Show     -- ^ @since 4.9.0.0
           , Read     -- ^ @since 4.9.0.0
           , Data     -- ^ @since 4.9.0.0
           , Generic  -- ^ @since 4.9.0.0
           , Generic1 -- ^ @since 4.9.0.0
           )

-- | @since 4.9.0.0
instance Enum a => Enum (Min a) where
  succ :: Min a -> Min a
succ (Min a
a) = a -> Min a
forall a. a -> Min a
Min (a -> a
forall a. Enum a => a -> a
succ a
a)
  pred :: Min a -> Min a
pred (Min a
a) = a -> Min a
forall a. a -> Min a
Min (a -> a
forall a. Enum a => a -> a
pred a
a)
  toEnum :: Int -> Min a
toEnum = a -> Min a
forall a. a -> Min a
Min (a -> Min a) -> (Int -> a) -> Int -> Min a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> a
forall a. Enum a => Int -> a
toEnum
  fromEnum :: Min a -> Int
fromEnum = a -> Int
forall a. Enum a => a -> Int
fromEnum (a -> Int) -> (Min a -> a) -> Min a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Min a -> a
forall a. Min a -> a
getMin
  enumFrom :: Min a -> [Min a]
enumFrom (Min a
a) = a -> Min a
forall a. a -> Min a
Min (a -> Min a) -> [a] -> [Min a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> [a]
forall a. Enum a => a -> [a]
enumFrom a
a
  enumFromThen :: Min a -> Min a -> [Min a]
enumFromThen (Min a
a) (Min a
b) = a -> Min a
forall a. a -> Min a
Min (a -> Min a) -> [a] -> [Min a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromThen a
a a
b
  enumFromTo :: Min a -> Min a -> [Min a]
enumFromTo (Min a
a) (Min a
b) = a -> Min a
forall a. a -> Min a
Min (a -> Min a) -> [a] -> [Min a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromTo a
a a
b
  enumFromThenTo :: Min a -> Min a -> Min a -> [Min a]
enumFromThenTo (Min a
a) (Min a
b) (Min a
c) = a -> Min a
forall a. a -> Min a
Min (a -> Min a) -> [a] -> [Min a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> a -> [a]
forall a. Enum a => a -> a -> a -> [a]
enumFromThenTo a
a a
b a
c


-- | @since 4.9.0.0
instance Ord a => Semigroup (Min a) where
  <> :: Min a -> Min a -> Min a
(<>) = (a -> a -> a) -> Min a -> Min a -> Min a
coerce (a -> a -> a
forall a. Ord a => a -> a -> a
min :: a -> a -> a)
  stimes :: b -> Min a -> Min a
stimes = b -> Min a -> Min a
forall b a. Integral b => b -> a -> a
stimesIdempotent

-- | @since 4.9.0.0
instance (Ord a, Bounded a) => Monoid (Min a) where
  mempty :: Min a
mempty = Min a
forall a. Bounded a => a
maxBound

-- | @since 4.9.0.0
instance Functor Min where
  fmap :: (a -> b) -> Min a -> Min b
fmap a -> b
f (Min a
x) = b -> Min b
forall a. a -> Min a
Min (a -> b
f a
x)

-- | @since 4.9.0.0
instance Foldable Min where
  foldMap :: (a -> m) -> Min a -> m
foldMap a -> m
f (Min a
a) = a -> m
f a
a

-- | @since 4.9.0.0
instance Traversable Min where
  traverse :: (a -> f b) -> Min a -> f (Min b)
traverse a -> f b
f (Min a
a) = b -> Min b
forall a. a -> Min a
Min (b -> Min b) -> f b -> f (Min b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a

-- | @since 4.9.0.0
instance Applicative Min where
  pure :: a -> Min a
pure = a -> Min a
forall a. a -> Min a
Min
  Min a
a <* :: Min a -> Min b -> Min a
<* Min b
_ = Min a
a
  Min a
_ *> :: Min a -> Min b -> Min b
*> Min b
a = Min b
a
  <*> :: Min (a -> b) -> Min a -> Min b
(<*>) = Min (a -> b) -> Min a -> Min b
coerce
  liftA2 :: (a -> b -> c) -> Min a -> Min b -> Min c
liftA2 = (a -> b -> c) -> Min a -> Min b -> Min c
coerce

-- | @since 4.9.0.0
instance Monad Min where
  >> :: Min a -> Min b -> Min b
(>>) = Min a -> Min b -> Min b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
(*>)
  Min a
a >>= :: Min a -> (a -> Min b) -> Min b
>>= a -> Min b
f = a -> Min b
f a
a

-- | @since 4.9.0.0
instance MonadFix Min where
  mfix :: (a -> Min a) -> Min a
mfix a -> Min a
f = (Min a -> Min a) -> Min a
forall a. (a -> a) -> a
fix (a -> Min a
f (a -> Min a) -> (Min a -> a) -> Min a -> Min a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Min a -> a
forall a. Min a -> a
getMin)

-- | @since 4.9.0.0
instance Num a => Num (Min a) where
  (Min a
a) + :: Min a -> Min a -> Min a
+ (Min a
b) = a -> Min a
forall a. a -> Min a
Min (a
a a -> a -> a
forall a. Num a => a -> a -> a
+ a
b)
  (Min a
a) * :: Min a -> Min a -> Min a
* (Min a
b) = a -> Min a
forall a. a -> Min a
Min (a
a a -> a -> a
forall a. Num a => a -> a -> a
* a
b)
  (Min a
a) - :: Min a -> Min a -> Min a
- (Min a
b) = a -> Min a
forall a. a -> Min a
Min (a
a a -> a -> a
forall a. Num a => a -> a -> a
- a
b)
  negate :: Min a -> Min a
negate (Min a
a) = a -> Min a
forall a. a -> Min a
Min (a -> a
forall a. Num a => a -> a
negate a
a)
  abs :: Min a -> Min a
abs    (Min a
a) = a -> Min a
forall a. a -> Min a
Min (a -> a
forall a. Num a => a -> a
abs a
a)
  signum :: Min a -> Min a
signum (Min a
a) = a -> Min a
forall a. a -> Min a
Min (a -> a
forall a. Num a => a -> a
signum a
a)
  fromInteger :: Integer -> Min a
fromInteger    = a -> Min a
forall a. a -> Min a
Min (a -> Min a) -> (Integer -> a) -> Integer -> Min a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> a
forall a. Num a => Integer -> a
fromInteger

newtype Max a = Max { Max a -> a
getMax :: a }
  deriving ( Bounded  -- ^ @since 4.9.0.0
           , Eq       -- ^ @since 4.9.0.0
           , Ord      -- ^ @since 4.9.0.0
           , Show     -- ^ @since 4.9.0.0
           , Read     -- ^ @since 4.9.0.0
           , Data     -- ^ @since 4.9.0.0
           , Generic  -- ^ @since 4.9.0.0
           , Generic1 -- ^ @since 4.9.0.0
           )

-- | @since 4.9.0.0
instance Enum a => Enum (Max a) where
  succ :: Max a -> Max a
succ (Max a
a) = a -> Max a
forall a. a -> Max a
Max (a -> a
forall a. Enum a => a -> a
succ a
a)
  pred :: Max a -> Max a
pred (Max a
a) = a -> Max a
forall a. a -> Max a
Max (a -> a
forall a. Enum a => a -> a
pred a
a)
  toEnum :: Int -> Max a
toEnum = a -> Max a
forall a. a -> Max a
Max (a -> Max a) -> (Int -> a) -> Int -> Max a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> a
forall a. Enum a => Int -> a
toEnum
  fromEnum :: Max a -> Int
fromEnum = a -> Int
forall a. Enum a => a -> Int
fromEnum (a -> Int) -> (Max a -> a) -> Max a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Max a -> a
forall a. Max a -> a
getMax
  enumFrom :: Max a -> [Max a]
enumFrom (Max a
a) = a -> Max a
forall a. a -> Max a
Max (a -> Max a) -> [a] -> [Max a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> [a]
forall a. Enum a => a -> [a]
enumFrom a
a
  enumFromThen :: Max a -> Max a -> [Max a]
enumFromThen (Max a
a) (Max a
b) = a -> Max a
forall a. a -> Max a
Max (a -> Max a) -> [a] -> [Max a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromThen a
a a
b
  enumFromTo :: Max a -> Max a -> [Max a]
enumFromTo (Max a
a) (Max a
b) = a -> Max a
forall a. a -> Max a
Max (a -> Max a) -> [a] -> [Max a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromTo a
a a
b
  enumFromThenTo :: Max a -> Max a -> Max a -> [Max a]
enumFromThenTo (Max a
a) (Max a
b) (Max a
c) = a -> Max a
forall a. a -> Max a
Max (a -> Max a) -> [a] -> [Max a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> a -> [a]
forall a. Enum a => a -> a -> a -> [a]
enumFromThenTo a
a a
b a
c

-- | @since 4.9.0.0
instance Ord a => Semigroup (Max a) where
  <> :: Max a -> Max a -> Max a
(<>) = (a -> a -> a) -> Max a -> Max a -> Max a
coerce (a -> a -> a
forall a. Ord a => a -> a -> a
max :: a -> a -> a)
  stimes :: b -> Max a -> Max a
stimes = b -> Max a -> Max a
forall b a. Integral b => b -> a -> a
stimesIdempotent

-- | @since 4.9.0.0
instance (Ord a, Bounded a) => Monoid (Max a) where
  mempty :: Max a
mempty = Max a
forall a. Bounded a => a
minBound

-- | @since 4.9.0.0
instance Functor Max where
  fmap :: (a -> b) -> Max a -> Max b
fmap a -> b
f (Max a
x) = b -> Max b
forall a. a -> Max a
Max (a -> b
f a
x)

-- | @since 4.9.0.0
instance Foldable Max where
  foldMap :: (a -> m) -> Max a -> m
foldMap a -> m
f (Max a
a) = a -> m
f a
a

-- | @since 4.9.0.0
instance Traversable Max where
  traverse :: (a -> f b) -> Max a -> f (Max b)
traverse a -> f b
f (Max a
a) = b -> Max b
forall a. a -> Max a
Max (b -> Max b) -> f b -> f (Max b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a

-- | @since 4.9.0.0
instance Applicative Max where
  pure :: a -> Max a
pure = a -> Max a
forall a. a -> Max a
Max
  Max a
a <* :: Max a -> Max b -> Max a
<* Max b
_ = Max a
a
  Max a
_ *> :: Max a -> Max b -> Max b
*> Max b
a = Max b
a
  <*> :: Max (a -> b) -> Max a -> Max b
(<*>) = Max (a -> b) -> Max a -> Max b
coerce
  liftA2 :: (a -> b -> c) -> Max a -> Max b -> Max c
liftA2 = (a -> b -> c) -> Max a -> Max b -> Max c
coerce

-- | @since 4.9.0.0
instance Monad Max where
  >> :: Max a -> Max b -> Max b
(>>) = Max a -> Max b -> Max b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
(*>)
  Max a
a >>= :: Max a -> (a -> Max b) -> Max b
>>= a -> Max b
f = a -> Max b
f a
a

-- | @since 4.9.0.0
instance MonadFix Max where
  mfix :: (a -> Max a) -> Max a
mfix a -> Max a
f = (Max a -> Max a) -> Max a
forall a. (a -> a) -> a
fix (a -> Max a
f (a -> Max a) -> (Max a -> a) -> Max a -> Max a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Max a -> a
forall a. Max a -> a
getMax)

-- | @since 4.9.0.0
instance Num a => Num (Max a) where
  (Max a
a) + :: Max a -> Max a -> Max a
+ (Max a
b) = a -> Max a
forall a. a -> Max a
Max (a
a a -> a -> a
forall a. Num a => a -> a -> a
+ a
b)
  (Max a
a) * :: Max a -> Max a -> Max a
* (Max a
b) = a -> Max a
forall a. a -> Max a
Max (a
a a -> a -> a
forall a. Num a => a -> a -> a
* a
b)
  (Max a
a) - :: Max a -> Max a -> Max a
- (Max a
b) = a -> Max a
forall a. a -> Max a
Max (a
a a -> a -> a
forall a. Num a => a -> a -> a
- a
b)
  negate :: Max a -> Max a
negate (Max a
a) = a -> Max a
forall a. a -> Max a
Max (a -> a
forall a. Num a => a -> a
negate a
a)
  abs :: Max a -> Max a
abs    (Max a
a) = a -> Max a
forall a. a -> Max a
Max (a -> a
forall a. Num a => a -> a
abs a
a)
  signum :: Max a -> Max a
signum (Max a
a) = a -> Max a
forall a. a -> Max a
Max (a -> a
forall a. Num a => a -> a
signum a
a)
  fromInteger :: Integer -> Max a
fromInteger    = a -> Max a
forall a. a -> Max a
Max (a -> Max a) -> (Integer -> a) -> Integer -> Max a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> a
forall a. Num a => Integer -> a
fromInteger

-- | 'Arg' isn't itself a 'Semigroup' in its own right, but it can be
-- placed inside 'Min' and 'Max' to compute an arg min or arg max.
data Arg a b = Arg a b deriving
  ( Show     -- ^ @since 4.9.0.0
  , Read     -- ^ @since 4.9.0.0
  , Data     -- ^ @since 4.9.0.0
  , Generic  -- ^ @since 4.9.0.0
  , Generic1 -- ^ @since 4.9.0.0
  )

type ArgMin a b = Min (Arg a b)
type ArgMax a b = Max (Arg a b)

-- | @since 4.9.0.0
instance Functor (Arg a) where
  fmap :: (a -> b) -> Arg a a -> Arg a b
fmap a -> b
f (Arg a
x a
a) = a -> b -> Arg a b
forall a b. a -> b -> Arg a b
Arg a
x (a -> b
f a
a)

-- | @since 4.9.0.0
instance Foldable (Arg a) where
  foldMap :: (a -> m) -> Arg a a -> m
foldMap a -> m
f (Arg a
_ a
a) = a -> m
f a
a

-- | @since 4.9.0.0
instance Traversable (Arg a) where
  traverse :: (a -> f b) -> Arg a a -> f (Arg a b)
traverse a -> f b
f (Arg a
x a
a) = a -> b -> Arg a b
forall a b. a -> b -> Arg a b
Arg a
x (b -> Arg a b) -> f b -> f (Arg a b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a

-- | @since 4.9.0.0
instance Eq a => Eq (Arg a b) where
  Arg a
a b
_ == :: Arg a b -> Arg a b -> Bool
== Arg a
b b
_ = a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b

-- | @since 4.9.0.0
instance Ord a => Ord (Arg a b) where
  Arg a
a b
_ compare :: Arg a b -> Arg a b -> Ordering
`compare` Arg a
b b
_ = a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a a
b
  min :: Arg a b -> Arg a b -> Arg a b
min x :: Arg a b
x@(Arg a
a b
_) y :: Arg a b
y@(Arg a
b b
_)
    | a
a a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
b    = Arg a b
x
    | Bool
otherwise = Arg a b
y
  max :: Arg a b -> Arg a b -> Arg a b
max x :: Arg a b
x@(Arg a
a b
_) y :: Arg a b
y@(Arg a
b b
_)
    | a
a a -> a -> Bool
forall a. Ord a => a -> a -> Bool
>= a
b    = Arg a b
x
    | Bool
otherwise = Arg a b
y

-- | @since 4.9.0.0
instance Bifunctor Arg where
  bimap :: (a -> b) -> (c -> d) -> Arg a c -> Arg b d
bimap a -> b
f c -> d
g (Arg a
a c
b) = b -> d -> Arg b d
forall a b. a -> b -> Arg a b
Arg (a -> b
f a
a) (c -> d
g c
b)

-- | @since 4.10.0.0
instance Bifoldable Arg where
  bifoldMap :: (a -> m) -> (b -> m) -> Arg a b -> m
bifoldMap a -> m
f b -> m
g (Arg a
a b
b) = a -> m
f a
a m -> m -> m
forall a. Semigroup a => a -> a -> a
<> b -> m
g b
b

-- | @since 4.10.0.0
instance Bitraversable Arg where
  bitraverse :: (a -> f c) -> (b -> f d) -> Arg a b -> f (Arg c d)
bitraverse a -> f c
f b -> f d
g (Arg a
a b
b) = c -> d -> Arg c d
forall a b. a -> b -> Arg a b
Arg (c -> d -> Arg c d) -> f c -> f (d -> Arg c d)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f c
f a
a f (d -> Arg c d) -> f d -> f (Arg c d)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> b -> f d
g b
b

-- | Use @'Option' ('First' a)@ to get the behavior of
-- 'Data.Monoid.First' from "Data.Monoid".
newtype First a = First { First a -> a
getFirst :: a }
  deriving ( Bounded  -- ^ @since 4.9.0.0
           , Eq       -- ^ @since 4.9.0.0
           , Ord      -- ^ @since 4.9.0.0
           , Show     -- ^ @since 4.9.0.0
           , Read     -- ^ @since 4.9.0.0
           , Data     -- ^ @since 4.9.0.0
           , Generic  -- ^ @since 4.9.0.0
           , Generic1 -- ^ @since 4.9.0.0
           )

-- | @since 4.9.0.0
instance Enum a => Enum (First a) where
  succ :: First a -> First a
succ (First a
a) = a -> First a
forall a. a -> First a
First (a -> a
forall a. Enum a => a -> a
succ a
a)
  pred :: First a -> First a
pred (First a
a) = a -> First a
forall a. a -> First a
First (a -> a
forall a. Enum a => a -> a
pred a
a)
  toEnum :: Int -> First a
toEnum = a -> First a
forall a. a -> First a
First (a -> First a) -> (Int -> a) -> Int -> First a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> a
forall a. Enum a => Int -> a
toEnum
  fromEnum :: First a -> Int
fromEnum = a -> Int
forall a. Enum a => a -> Int
fromEnum (a -> Int) -> (First a -> a) -> First a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. First a -> a
forall a. First a -> a
getFirst
  enumFrom :: First a -> [First a]
enumFrom (First a
a) = a -> First a
forall a. a -> First a
First (a -> First a) -> [a] -> [First a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> [a]
forall a. Enum a => a -> [a]
enumFrom a
a
  enumFromThen :: First a -> First a -> [First a]
enumFromThen (First a
a) (First a
b) = a -> First a
forall a. a -> First a
First (a -> First a) -> [a] -> [First a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromThen a
a a
b
  enumFromTo :: First a -> First a -> [First a]
enumFromTo (First a
a) (First a
b) = a -> First a
forall a. a -> First a
First (a -> First a) -> [a] -> [First a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromTo a
a a
b
  enumFromThenTo :: First a -> First a -> First a -> [First a]
enumFromThenTo (First a
a) (First a
b) (First a
c) = a -> First a
forall a. a -> First a
First (a -> First a) -> [a] -> [First a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> a -> [a]
forall a. Enum a => a -> a -> a -> [a]
enumFromThenTo a
a a
b a
c

-- | @since 4.9.0.0
instance Semigroup (First a) where
  First a
a <> :: First a -> First a -> First a
<> First a
_ = First a
a
  stimes :: b -> First a -> First a
stimes = b -> First a -> First a
forall b a. Integral b => b -> a -> a
stimesIdempotent

-- | @since 4.9.0.0
instance Functor First where
  fmap :: (a -> b) -> First a -> First b
fmap a -> b
f (First a
x) = b -> First b
forall a. a -> First a
First (a -> b
f a
x)

-- | @since 4.9.0.0
instance Foldable First where
  foldMap :: (a -> m) -> First a -> m
foldMap a -> m
f (First a
a) = a -> m
f a
a

-- | @since 4.9.0.0
instance Traversable First where
  traverse :: (a -> f b) -> First a -> f (First b)
traverse a -> f b
f (First a
a) = b -> First b
forall a. a -> First a
First (b -> First b) -> f b -> f (First b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a

-- | @since 4.9.0.0
instance Applicative First where
  pure :: a -> First a
pure a
x = a -> First a
forall a. a -> First a
First a
x
  First a
a <* :: First a -> First b -> First a
<* First b
_ = First a
a
  First a
_ *> :: First a -> First b -> First b
*> First b
a = First b
a
  <*> :: First (a -> b) -> First a -> First b
(<*>) = First (a -> b) -> First a -> First b
coerce
  liftA2 :: (a -> b -> c) -> First a -> First b -> First c
liftA2 = (a -> b -> c) -> First a -> First b -> First c
coerce

-- | @since 4.9.0.0
instance Monad First where
  >> :: First a -> First b -> First b
(>>) = First a -> First b -> First b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
(*>)
  First a
a >>= :: First a -> (a -> First b) -> First b
>>= a -> First b
f = a -> First b
f a
a

-- | @since 4.9.0.0
instance MonadFix First where
  mfix :: (a -> First a) -> First a
mfix a -> First a
f = (First a -> First a) -> First a
forall a. (a -> a) -> a
fix (a -> First a
f (a -> First a) -> (First a -> a) -> First a -> First a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. First a -> a
forall a. First a -> a
getFirst)

-- | Use @'Option' ('Last' a)@ to get the behavior of
-- 'Data.Monoid.Last' from "Data.Monoid"
newtype Last a = Last { Last a -> a
getLast :: a }
  deriving ( Bounded  -- ^ @since 4.9.0.0
           , Eq       -- ^ @since 4.9.0.0
           , Ord      -- ^ @since 4.9.0.0
           , Show     -- ^ @since 4.9.0.0
           , Read     -- ^ @since 4.9.0.0
           , Data     -- ^ @since 4.9.0.0
           , Generic  -- ^ @since 4.9.0.0
           , Generic1 -- ^ @since 4.9.0.0
           )

-- | @since 4.9.0.0
instance Enum a => Enum (Last a) where
  succ :: Last a -> Last a
succ (Last a
a) = a -> Last a
forall a. a -> Last a
Last (a -> a
forall a. Enum a => a -> a
succ a
a)
  pred :: Last a -> Last a
pred (Last a
a) = a -> Last a
forall a. a -> Last a
Last (a -> a
forall a. Enum a => a -> a
pred a
a)
  toEnum :: Int -> Last a
toEnum = a -> Last a
forall a. a -> Last a
Last (a -> Last a) -> (Int -> a) -> Int -> Last a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> a
forall a. Enum a => Int -> a
toEnum
  fromEnum :: Last a -> Int
fromEnum = a -> Int
forall a. Enum a => a -> Int
fromEnum (a -> Int) -> (Last a -> a) -> Last a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Last a -> a
forall a. Last a -> a
getLast
  enumFrom :: Last a -> [Last a]
enumFrom (Last a
a) = a -> Last a
forall a. a -> Last a
Last (a -> Last a) -> [a] -> [Last a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> [a]
forall a. Enum a => a -> [a]
enumFrom a
a
  enumFromThen :: Last a -> Last a -> [Last a]
enumFromThen (Last a
a) (Last a
b) = a -> Last a
forall a. a -> Last a
Last (a -> Last a) -> [a] -> [Last a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromThen a
a a
b
  enumFromTo :: Last a -> Last a -> [Last a]
enumFromTo (Last a
a) (Last a
b) = a -> Last a
forall a. a -> Last a
Last (a -> Last a) -> [a] -> [Last a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromTo a
a a
b
  enumFromThenTo :: Last a -> Last a -> Last a -> [Last a]
enumFromThenTo (Last a
a) (Last a
b) (Last a
c) = a -> Last a
forall a. a -> Last a
Last (a -> Last a) -> [a] -> [Last a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> a -> [a]
forall a. Enum a => a -> a -> a -> [a]
enumFromThenTo a
a a
b a
c

-- | @since 4.9.0.0
instance Semigroup (Last a) where
  Last a
_ <> :: Last a -> Last a -> Last a
<> Last a
b = Last a
b
  stimes :: b -> Last a -> Last a
stimes = b -> Last a -> Last a
forall b a. Integral b => b -> a -> a
stimesIdempotent

-- | @since 4.9.0.0
instance Functor Last where
  fmap :: (a -> b) -> Last a -> Last b
fmap a -> b
f (Last a
x) = b -> Last b
forall a. a -> Last a
Last (a -> b
f a
x)
  a
a <$ :: a -> Last b -> Last a
<$ Last b
_ = a -> Last a
forall a. a -> Last a
Last a
a

-- | @since 4.9.0.0
instance Foldable Last where
  foldMap :: (a -> m) -> Last a -> m
foldMap a -> m
f (Last a
a) = a -> m
f a
a

-- | @since 4.9.0.0
instance Traversable Last where
  traverse :: (a -> f b) -> Last a -> f (Last b)
traverse a -> f b
f (Last a
a) = b -> Last b
forall a. a -> Last a
Last (b -> Last b) -> f b -> f (Last b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a

-- | @since 4.9.0.0
instance Applicative Last where
  pure :: a -> Last a
pure = a -> Last a
forall a. a -> Last a
Last
  Last a
a <* :: Last a -> Last b -> Last a
<* Last b
_ = Last a
a
  Last a
_ *> :: Last a -> Last b -> Last b
*> Last b
a = Last b
a
  <*> :: Last (a -> b) -> Last a -> Last b
(<*>) = Last (a -> b) -> Last a -> Last b
coerce
  liftA2 :: (a -> b -> c) -> Last a -> Last b -> Last c
liftA2 = (a -> b -> c) -> Last a -> Last b -> Last c
coerce

-- | @since 4.9.0.0
instance Monad Last where
  >> :: Last a -> Last b -> Last b
(>>) = Last a -> Last b -> Last b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
(*>)
  Last a
a >>= :: Last a -> (a -> Last b) -> Last b
>>= a -> Last b
f = a -> Last b
f a
a

-- | @since 4.9.0.0
instance MonadFix Last where
  mfix :: (a -> Last a) -> Last a
mfix a -> Last a
f = (Last a -> Last a) -> Last a
forall a. (a -> a) -> a
fix (a -> Last a
f (a -> Last a) -> (Last a -> a) -> Last a -> Last a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Last a -> a
forall a. Last a -> a
getLast)

-- | Provide a Semigroup for an arbitrary Monoid.
--
-- __NOTE__: This is not needed anymore since 'Semigroup' became a superclass of
-- 'Monoid' in /base-4.11/ and this newtype be deprecated at some point in the future.
newtype WrappedMonoid m = WrapMonoid { WrappedMonoid m -> m
unwrapMonoid :: m }
  deriving ( Bounded  -- ^ @since 4.9.0.0
           , Eq       -- ^ @since 4.9.0.0
           , Ord      -- ^ @since 4.9.0.0
           , Show     -- ^ @since 4.9.0.0
           , Read     -- ^ @since 4.9.0.0
           , Data     -- ^ @since 4.9.0.0
           , Generic  -- ^ @since 4.9.0.0
           , Generic1 -- ^ @since 4.9.0.0
           )

-- | @since 4.9.0.0
instance Monoid m => Semigroup (WrappedMonoid m) where
  <> :: WrappedMonoid m -> WrappedMonoid m -> WrappedMonoid m
(<>) = (m -> m -> m)
-> WrappedMonoid m -> WrappedMonoid m -> WrappedMonoid m
coerce (m -> m -> m
forall a. Monoid a => a -> a -> a
mappend :: m -> m -> m)

-- | @since 4.9.0.0
instance Monoid m => Monoid (WrappedMonoid m) where
  mempty :: WrappedMonoid m
mempty = m -> WrappedMonoid m
forall m. m -> WrappedMonoid m
WrapMonoid m
forall a. Monoid a => a
mempty

-- | @since 4.9.0.0
instance Enum a => Enum (WrappedMonoid a) where
  succ :: WrappedMonoid a -> WrappedMonoid a
succ (WrapMonoid a
a) = a -> WrappedMonoid a
forall m. m -> WrappedMonoid m
WrapMonoid (a -> a
forall a. Enum a => a -> a
succ a
a)
  pred :: WrappedMonoid a -> WrappedMonoid a
pred (WrapMonoid a
a) = a -> WrappedMonoid a
forall m. m -> WrappedMonoid m
WrapMonoid (a -> a
forall a. Enum a => a -> a
pred a
a)
  toEnum :: Int -> WrappedMonoid a
toEnum = a -> WrappedMonoid a
forall m. m -> WrappedMonoid m
WrapMonoid (a -> WrappedMonoid a) -> (Int -> a) -> Int -> WrappedMonoid a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> a
forall a. Enum a => Int -> a
toEnum
  fromEnum :: WrappedMonoid a -> Int
fromEnum = a -> Int
forall a. Enum a => a -> Int
fromEnum (a -> Int) -> (WrappedMonoid a -> a) -> WrappedMonoid a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. WrappedMonoid a -> a
forall m. WrappedMonoid m -> m
unwrapMonoid
  enumFrom :: WrappedMonoid a -> [WrappedMonoid a]
enumFrom (WrapMonoid a
a) = a -> WrappedMonoid a
forall m. m -> WrappedMonoid m
WrapMonoid (a -> WrappedMonoid a) -> [a] -> [WrappedMonoid a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> [a]
forall a. Enum a => a -> [a]
enumFrom a
a
  enumFromThen :: WrappedMonoid a -> WrappedMonoid a -> [WrappedMonoid a]
enumFromThen (WrapMonoid a
a) (WrapMonoid a
b) = a -> WrappedMonoid a
forall m. m -> WrappedMonoid m
WrapMonoid (a -> WrappedMonoid a) -> [a] -> [WrappedMonoid a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromThen a
a a
b
  enumFromTo :: WrappedMonoid a -> WrappedMonoid a -> [WrappedMonoid a]
enumFromTo (WrapMonoid a
a) (WrapMonoid a
b) = a -> WrappedMonoid a
forall m. m -> WrappedMonoid m
WrapMonoid (a -> WrappedMonoid a) -> [a] -> [WrappedMonoid a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> [a]
forall a. Enum a => a -> a -> [a]
enumFromTo a
a a
b
  enumFromThenTo :: WrappedMonoid a
-> WrappedMonoid a -> WrappedMonoid a -> [WrappedMonoid a]
enumFromThenTo (WrapMonoid a
a) (WrapMonoid a
b) (WrapMonoid a
c) =
      a -> WrappedMonoid a
forall m. m -> WrappedMonoid m
WrapMonoid (a -> WrappedMonoid a) -> [a] -> [WrappedMonoid a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> a -> a -> [a]
forall a. Enum a => a -> a -> a -> [a]
enumFromThenTo a
a a
b a
c

-- | Repeat a value @n@ times.
--
-- > mtimesDefault n a = a <> a <> ... <> a  -- using <> (n-1) times
--
-- Implemented using 'stimes' and 'mempty'.
--
-- This is a suitable definition for an 'mtimes' member of 'Monoid'.
mtimesDefault :: (Integral b, Monoid a) => b -> a -> a
mtimesDefault :: b -> a -> a
mtimesDefault b
n a
x
  | b
n b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0    = a
forall a. Monoid a => a
mempty
  | Bool
otherwise = WrappedMonoid a -> a
forall m. WrappedMonoid m -> m
unwrapMonoid (b -> WrappedMonoid a -> WrappedMonoid a
forall a b. (Semigroup a, Integral b) => b -> a -> a
stimes b
n (a -> WrappedMonoid a
forall m. m -> WrappedMonoid m
WrapMonoid a
x))

-- | 'Option' is effectively 'Maybe' with a better instance of
-- 'Monoid', built off of an underlying 'Semigroup' instead of an
-- underlying 'Monoid'.
--
-- Ideally, this type would not exist at all and we would just fix the
-- 'Monoid' instance of 'Maybe'.
--
-- In GHC 8.4 and higher, the 'Monoid' instance for 'Maybe' has been
-- corrected to lift a 'Semigroup' instance instead of a 'Monoid'
-- instance. Consequently, this type is no longer useful. It will be
-- marked deprecated in GHC 8.8 and removed in GHC 8.10.
newtype Option a = Option { Option a -> Maybe a
getOption :: Maybe a }
  deriving ( Eq       -- ^ @since 4.9.0.0
           , Ord      -- ^ @since 4.9.0.0
           , Show     -- ^ @since 4.9.0.0
           , Read     -- ^ @since 4.9.0.0
           , Data     -- ^ @since 4.9.0.0
           , Generic  -- ^ @since 4.9.0.0
           , Generic1 -- ^ @since 4.9.0.0
           )

-- | @since 4.9.0.0
instance Functor Option where
  fmap :: (a -> b) -> Option a -> Option b
fmap a -> b
f (Option Maybe a
a) = Maybe b -> Option b
forall a. Maybe a -> Option a
Option ((a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Maybe a
a)

-- | @since 4.9.0.0
instance Applicative Option where
  pure :: a -> Option a
pure a
a = Maybe a -> Option a
forall a. Maybe a -> Option a
Option (a -> Maybe a
forall a. a -> Maybe a
Just a
a)
  Option Maybe (a -> b)
a <*> :: Option (a -> b) -> Option a -> Option b
<*> Option Maybe a
b = Maybe b -> Option b
forall a. Maybe a -> Option a
Option (Maybe (a -> b)
a Maybe (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Maybe a
b)
  liftA2 :: (a -> b -> c) -> Option a -> Option b -> Option c
liftA2 a -> b -> c
f (Option Maybe a
x) (Option Maybe b
y) = Maybe c -> Option c
forall a. Maybe a -> Option a
Option ((a -> b -> c) -> Maybe a -> Maybe b -> Maybe c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 a -> b -> c
f Maybe a
x Maybe b
y)

  Option Maybe a
Nothing  *> :: Option a -> Option b -> Option b
*>  Option b
_ = Maybe b -> Option b
forall a. Maybe a -> Option a
Option Maybe b
forall a. Maybe a
Nothing
  Option a
_               *>  Option b
b = Option b
b

-- | @since 4.9.0.0
instance Monad Option where
  Option (Just a
a) >>= :: Option a -> (a -> Option b) -> Option b
>>= a -> Option b
k = a -> Option b
k a
a
  Option a
_               >>= a -> Option b
_ = Maybe b -> Option b
forall a. Maybe a -> Option a
Option Maybe b
forall a. Maybe a
Nothing
  >> :: Option a -> Option b -> Option b
(>>) = Option a -> Option b -> Option b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
(*>)

-- | @since 4.9.0.0
instance Alternative Option where
  empty :: Option a
empty = Maybe a -> Option a
forall a. Maybe a -> Option a
Option Maybe a
forall a. Maybe a
Nothing
  Option Maybe a
Nothing <|> :: Option a -> Option a -> Option a
<|> Option a
b = Option a
b
  Option a
a <|> Option a
_ = Option a
a

-- | @since 4.9.0.0
instance MonadPlus Option

-- | @since 4.9.0.0
instance MonadFix Option where
  mfix :: (a -> Option a) -> Option a
mfix a -> Option a
f = Maybe a -> Option a
forall a. Maybe a -> Option a
Option ((a -> Maybe a) -> Maybe a
forall (m :: * -> *) a. MonadFix m => (a -> m a) -> m a
mfix (Option a -> Maybe a
forall a. Option a -> Maybe a
getOption (Option a -> Maybe a) -> (a -> Option a) -> a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Option a
f))

-- | @since 4.9.0.0
instance Foldable Option where
  foldMap :: (a -> m) -> Option a -> m
foldMap a -> m
f (Option (Just a
m)) = a -> m
f a
m
  foldMap a -> m
_ (Option Maybe a
Nothing)  = m
forall a. Monoid a => a
mempty

-- | @since 4.9.0.0
instance Traversable Option where
  traverse :: (a -> f b) -> Option a -> f (Option b)
traverse a -> f b
f (Option (Just a
a)) = Maybe b -> Option b
forall a. Maybe a -> Option a
Option (Maybe b -> Option b) -> (b -> Maybe b) -> b -> Option b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> Maybe b
forall a. a -> Maybe a
Just (b -> Option b) -> f b -> f (Option b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a
  traverse a -> f b
_ (Option Maybe a
Nothing)  = Option b -> f (Option b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe b -> Option b
forall a. Maybe a -> Option a
Option Maybe b
forall a. Maybe a
Nothing)

-- | Fold an 'Option' case-wise, just like 'maybe'.
option :: b -> (a -> b) -> Option a -> b
option :: b -> (a -> b) -> Option a -> b
option b
n a -> b
j (Option Maybe a
m) = b -> (a -> b) -> Maybe a -> b
forall b a. b -> (a -> b) -> Maybe a -> b
maybe b
n a -> b
j Maybe a
m

-- | @since 4.9.0.0
instance Semigroup a => Semigroup (Option a) where
  <> :: Option a -> Option a -> Option a
(<>) = (Maybe a -> Maybe a -> Maybe a) -> Option a -> Option a -> Option a
coerce (Maybe a -> Maybe a -> Maybe a
forall a. Semigroup a => a -> a -> a
(<>) :: Maybe a -> Maybe a -> Maybe a)
#if !defined(__HADDOCK_VERSION__)
    -- workaround https://github.com/haskell/haddock/issues/680
  stimes _ (Option Nothing) = Option Nothing
  stimes n (Option (Just a)) = case compare n 0 of
    LT -> errorWithoutStackTrace "stimes: Option, negative multiplier"
    EQ -> Option Nothing
    GT -> Option (Just (stimes n a))
#endif

-- | @since 4.9.0.0
instance Semigroup a => Monoid (Option a) where
  mempty :: Option a
mempty = Maybe a -> Option a
forall a. Maybe a -> Option a
Option Maybe a
forall a. Maybe a
Nothing