{-# LANGUAGE DeriveDataTypeable    #-}
{-# LANGUAGE DeriveFoldable        #-}
{-# LANGUAGE DeriveFunctor         #-}
{-# LANGUAGE DeriveTraversable     #-}
{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# OPTIONS_GHC -fno-warn-unused-imports       #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Monoid.Split
-- Copyright   :  (c) 2011-2015 diagrams-core team (see LICENSE)
-- License     :  BSD-style (see LICENSE)
-- Maintainer  :  diagrams-discuss@googlegroups.com
--
-- Sometimes we want to accumulate values from some monoid, but have
-- the ability to introduce a \"split\" which separates values on
-- either side.  Only the rightmost split is kept.  For example,
--
-- > a b c | d e | f g h == a b c d e | f g h
--
-- In the diagrams graphics framework this is used when accumulating
-- transformations to be applied to primitive diagrams: the 'freeze'
-- operation introduces a split, since only transformations occurring
-- outside the freeze should be applied to attributes.
--
-----------------------------------------------------------------------------

module Data.Monoid.Split
       ( Split(..)
       , split
       , unsplit

       ) where

import Data.Data
import Data.Foldable
import Data.Semigroup
import Data.Traversable

import Data.Monoid.Action

infix 5 :|

-- | A value of type @Split m@ is either a single @m@, or a pair of
--   @m@'s separated by a divider.  Single @m@'s combine as usual;
--   single @m@'s combine with split values by combining with the
--   value on the appropriate side; when two split values meet only
--   the rightmost split is kept, with both the values from the left
--   split combining with the left-hand value of the right split.
--
--   "Data.Monoid.Cut" is similar, but uses a different scheme for
--   composition.  @Split@ uses the asymmetric constructor @:|@, and
--   @Cut@ the symmetric constructor @:||:@, to emphasize the inherent
--   asymmetry of @Split@ and symmetry of @Cut@.  @Split@ keeps only
--   the rightmost split and combines everything on the left; @Cut@
--   keeps the outermost splits and throws away everything in between.
data Split m = M m
             | m :| m
  deriving (Split m -> DataType
Split m -> Constr
forall {m}. Data m => Typeable (Split m)
forall m. Data m => Split m -> DataType
forall m. Data m => Split m -> Constr
forall m.
Data m =>
(forall b. Data b => b -> b) -> Split m -> Split m
forall m u.
Data m =>
Int -> (forall d. Data d => d -> u) -> Split m -> u
forall m u.
Data m =>
(forall d. Data d => d -> u) -> Split m -> [u]
forall m r r'.
Data m =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Split m -> r
forall m r r'.
Data m =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Split m -> r
forall m (m :: * -> *).
(Data m, Monad m) =>
(forall d. Data d => d -> m d) -> Split m -> m (Split m)
forall m (m :: * -> *).
(Data m, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Split m -> m (Split m)
forall m (c :: * -> *).
Data m =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Split m)
forall m (c :: * -> *).
Data m =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Split m -> c (Split m)
forall m (t :: * -> *) (c :: * -> *).
(Data m, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Split m))
forall m (t :: * -> * -> *) (c :: * -> *).
(Data m, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Split m))
forall a.
Typeable a
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Split m)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Split m -> c (Split m)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Split m))
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Split m -> m (Split m)
$cgmapMo :: forall m (m :: * -> *).
(Data m, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Split m -> m (Split m)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Split m -> m (Split m)
$cgmapMp :: forall m (m :: * -> *).
(Data m, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Split m -> m (Split m)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Split m -> m (Split m)
$cgmapM :: forall m (m :: * -> *).
(Data m, Monad m) =>
(forall d. Data d => d -> m d) -> Split m -> m (Split m)
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Split m -> u
$cgmapQi :: forall m u.
Data m =>
Int -> (forall d. Data d => d -> u) -> Split m -> u
gmapQ :: forall u. (forall d. Data d => d -> u) -> Split m -> [u]
$cgmapQ :: forall m u.
Data m =>
(forall d. Data d => d -> u) -> Split m -> [u]
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Split m -> r
$cgmapQr :: forall m r r'.
Data m =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Split m -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Split m -> r
$cgmapQl :: forall m r r'.
Data m =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Split m -> r
gmapT :: (forall b. Data b => b -> b) -> Split m -> Split m
$cgmapT :: forall m.
Data m =>
(forall b. Data b => b -> b) -> Split m -> Split m
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Split m))
$cdataCast2 :: forall m (t :: * -> * -> *) (c :: * -> *).
(Data m, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Split m))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Split m))
$cdataCast1 :: forall m (t :: * -> *) (c :: * -> *).
(Data m, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Split m))
dataTypeOf :: Split m -> DataType
$cdataTypeOf :: forall m. Data m => Split m -> DataType
toConstr :: Split m -> Constr
$ctoConstr :: forall m. Data m => Split m -> Constr
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Split m)
$cgunfold :: forall m (c :: * -> *).
Data m =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Split m)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Split m -> c (Split m)
$cgfoldl :: forall m (c :: * -> *).
Data m =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Split m -> c (Split m)
Data, Typeable, Int -> Split m -> ShowS
forall m. Show m => Int -> Split m -> ShowS
forall m. Show m => [Split m] -> ShowS
forall m. Show m => Split m -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Split m] -> ShowS
$cshowList :: forall m. Show m => [Split m] -> ShowS
show :: Split m -> String
$cshow :: forall m. Show m => Split m -> String
showsPrec :: Int -> Split m -> ShowS
$cshowsPrec :: forall m. Show m => Int -> Split m -> ShowS
Show, ReadPrec [Split m]
ReadPrec (Split m)
ReadS [Split m]
forall m. Read m => ReadPrec [Split m]
forall m. Read m => ReadPrec (Split m)
forall m. Read m => Int -> ReadS (Split m)
forall m. Read m => ReadS [Split m]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [Split m]
$creadListPrec :: forall m. Read m => ReadPrec [Split m]
readPrec :: ReadPrec (Split m)
$creadPrec :: forall m. Read m => ReadPrec (Split m)
readList :: ReadS [Split m]
$creadList :: forall m. Read m => ReadS [Split m]
readsPrec :: Int -> ReadS (Split m)
$creadsPrec :: forall m. Read m => Int -> ReadS (Split m)
Read, Split m -> Split m -> Bool
forall m. Eq m => Split m -> Split m -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Split m -> Split m -> Bool
$c/= :: forall m. Eq m => Split m -> Split m -> Bool
== :: Split m -> Split m -> Bool
$c== :: forall m. Eq m => Split m -> Split m -> Bool
Eq, forall a b. a -> Split b -> Split a
forall a b. (a -> b) -> Split a -> Split b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> Split b -> Split a
$c<$ :: forall a b. a -> Split b -> Split a
fmap :: forall a b. (a -> b) -> Split a -> Split b
$cfmap :: forall a b. (a -> b) -> Split a -> Split b
Functor, forall a. Eq a => a -> Split a -> Bool
forall a. Num a => Split a -> a
forall a. Ord a => Split a -> a
forall m. Monoid m => Split m -> m
forall a. Split a -> Bool
forall a. Split a -> Int
forall a. Split a -> [a]
forall a. (a -> a -> a) -> Split a -> a
forall m a. Monoid m => (a -> m) -> Split a -> m
forall b a. (b -> a -> b) -> b -> Split a -> b
forall a b. (a -> b -> b) -> b -> Split a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: forall a. Num a => Split a -> a
$cproduct :: forall a. Num a => Split a -> a
sum :: forall a. Num a => Split a -> a
$csum :: forall a. Num a => Split a -> a
minimum :: forall a. Ord a => Split a -> a
$cminimum :: forall a. Ord a => Split a -> a
maximum :: forall a. Ord a => Split a -> a
$cmaximum :: forall a. Ord a => Split a -> a
elem :: forall a. Eq a => a -> Split a -> Bool
$celem :: forall a. Eq a => a -> Split a -> Bool
length :: forall a. Split a -> Int
$clength :: forall a. Split a -> Int
null :: forall a. Split a -> Bool
$cnull :: forall a. Split a -> Bool
toList :: forall a. Split a -> [a]
$ctoList :: forall a. Split a -> [a]
foldl1 :: forall a. (a -> a -> a) -> Split a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Split a -> a
foldr1 :: forall a. (a -> a -> a) -> Split a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Split a -> a
foldl' :: forall b a. (b -> a -> b) -> b -> Split a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Split a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Split a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Split a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Split a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Split a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Split a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Split a -> b
foldMap' :: forall m a. Monoid m => (a -> m) -> Split a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Split a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Split a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Split a -> m
fold :: forall m. Monoid m => Split m -> m
$cfold :: forall m. Monoid m => Split m -> m
Foldable, Functor Split
Foldable Split
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => Split (m a) -> m (Split a)
forall (f :: * -> *) a. Applicative f => Split (f a) -> f (Split a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Split a -> m (Split b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Split a -> f (Split b)
sequence :: forall (m :: * -> *) a. Monad m => Split (m a) -> m (Split a)
$csequence :: forall (m :: * -> *) a. Monad m => Split (m a) -> m (Split a)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Split a -> m (Split b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Split a -> m (Split b)
sequenceA :: forall (f :: * -> *) a. Applicative f => Split (f a) -> f (Split a)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Split (f a) -> f (Split a)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Split a -> f (Split b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Split a -> f (Split b)
Traversable)

-- | If @m@ is a @Semigroup@, then @Split m@ is a semigroup which
--   combines values on either side of a split, keeping only the
--   rightmost split.
instance Semigroup m => Semigroup (Split m) where
  (M m
m1)       <> :: Split m -> Split m -> Split m
<> (M m
m2)       = forall m. m -> Split m
M (m
m1 forall a. Semigroup a => a -> a -> a
<> m
m2)
  (M m
m1)       <> (m
m1' :| m
m2)  = m
m1 forall a. Semigroup a => a -> a -> a
<> m
m1'         forall m. m -> m -> Split m
:| m
m2
  (m
m1  :| m
m2)  <> (M m
m2')      = m
m1                forall m. m -> m -> Split m
:| m
m2 forall a. Semigroup a => a -> a -> a
<> m
m2'
  (m
m11 :| m
m12) <> (m
m21 :| m
m22) = m
m11 forall a. Semigroup a => a -> a -> a
<> m
m12 forall a. Semigroup a => a -> a -> a
<> m
m21 forall m. m -> m -> Split m
:| m
m22

  stimes :: forall b. Integral b => b -> Split m -> Split m
stimes b
n (M m
m     ) = forall m. m -> Split m
M (forall a b. (Semigroup a, Integral b) => b -> a -> a
stimes b
n m
m)
  stimes b
1 (Split m
m       ) = Split m
m
  stimes b
n (m
m1 :| m
m2) = m
m1 forall a. Semigroup a => a -> a -> a
<> forall a b. (Semigroup a, Integral b) => b -> a -> a
stimes (forall a. Enum a => a -> a
pred b
n) (m
m2 forall a. Semigroup a => a -> a -> a
<> m
m1) forall m. m -> m -> Split m
:| m
m2

instance (Semigroup m, Monoid m) => Monoid (Split m) where
  mempty :: Split m
mempty  = forall m. m -> Split m
M forall a. Monoid a => a
mempty
  mappend :: Split m -> Split m -> Split m
mappend = forall a. Semigroup a => a -> a -> a
(<>)

-- | A convenient name for @mempty :| mempty@, so @M a \<\> split \<\>
--   M b == a :| b@.
split :: Monoid m => Split m
split :: forall m. Monoid m => Split m
split = forall a. Monoid a => a
mempty forall m. m -> m -> Split m
:| forall a. Monoid a => a
mempty

-- | \"Unsplit\" a split monoid value, combining the two values into
--   one (or returning the single value if there is no split).
unsplit :: Semigroup m => Split m -> m
unsplit :: forall m. Semigroup m => Split m -> m
unsplit (M m
m)      = m
m
unsplit (m
m1 :| m
m2) = m
m1 forall a. Semigroup a => a -> a -> a
<> m
m2

-- | By default, the action of a split monoid is the same as for
--   the underlying monoid, as if the split were removed.
instance Action m n => Action (Split m) n where
  act :: Split m -> n -> n
act (M m
m) n
n      = forall m s. Action m s => m -> s -> s
act m
m n
n
  act (m
m1 :| m
m2) n
n = forall m s. Action m s => m -> s -> s
act m
m1 (forall m s. Action m s => m -> s -> s
act m
m2 n
n)