{- 
    Copyright 2013-2017 Mario Blazevic

    License: BSD3 (see BSD3-LICENSE.txt file)
-}

-- | This module defines the 'FactorialMonoid' class and some of its instances.
-- 

{-# LANGUAGE Haskell2010, ConstraintKinds, FlexibleInstances, Trustworthy #-}

module Data.Monoid.Factorial (
   module Data.Semigroup.Factorial,
   FactorialMonoid(..), StableFactorialMonoid,
   )
where

import Control.Arrow (first)
import Data.Monoid -- (Monoid (..), Dual(..), Sum(..), Product(..), Endo(Endo, appEndo))
import qualified Data.Foldable as Foldable
import qualified Data.List as List
import qualified Data.ByteString as ByteString
import qualified Data.ByteString.Lazy as LazyByteString
import qualified Data.Text as Text
import qualified Data.Text.Lazy as LazyText
import qualified Data.IntMap as IntMap
import qualified Data.IntSet as IntSet
import qualified Data.Map as Map
import qualified Data.Sequence as Sequence
import qualified Data.Set as Set
import qualified Data.Vector as Vector
import Data.Int (Int64)

import Data.Semigroup.Factorial
import Data.Monoid.Null (MonoidNull(null), PositiveMonoid)

import Prelude hiding (break, drop, dropWhile, foldl, foldr, last, length, map, max, min,
                       null, reverse, span, splitAt, take, takeWhile)


-- | Class of monoids that can be split into irreducible (/i.e./, atomic or prime) 'factors' in a unique way. Note that
-- 'mempty' is not considered a factor. Factors of a 'Product' are literally its prime factors:
--
-- prop> factors (Product 12) == [Product 2, Product 2, Product 3]
--
-- Factors of a list are /not/ its elements but all its single-item sublists:
--
-- prop> factors "abc" == ["a", "b", "c"]
-- 
-- The methods of this class satisfy the following laws in addition to those of 'Factorial':
-- 
-- > null == List.null . factors
-- > factors == unfoldr splitPrimePrefix == List.reverse . unfoldr (fmap swap . splitPrimeSuffix)
-- > reverse == mconcat . List.reverse . factors
-- > primePrefix == maybe mempty fst . splitPrimePrefix
-- > primeSuffix == maybe mempty snd . splitPrimeSuffix
-- > inits == List.map mconcat . List.inits . factors
-- > tails == List.map mconcat . List.tails . factors
-- > span p m == (mconcat l, mconcat r) where (l, r) = List.span p (factors m)
-- > List.all (List.all (not . pred) . factors) . split pred
-- > mconcat . intersperse prime . split (== prime) == id
-- > splitAt i m == (mconcat l, mconcat r) where (l, r) = List.splitAt i (factors m)
-- > spanMaybe () (const $ bool Nothing (Maybe ()) . p) m == (takeWhile p m, dropWhile p m, ())
-- > spanMaybe s0 (\s m-> Just $ f s m) m0 == (m0, mempty, foldl f s0 m0)
-- > let (prefix, suffix, s') = spanMaybe s f m
-- >     foldMaybe = foldl g (Just s)
-- >     g s m = s >>= flip f m
-- > in all ((Nothing ==) . foldMaybe) (inits prefix)
-- >    && prefix == last (filter (isJust . foldMaybe) $ inits m)
-- >    && Just s' == foldMaybe prefix
-- >    && m == prefix <> suffix
--
-- A minimal instance definition should implement 'splitPrimePrefix' for performance reasons, and other methods where
-- beneficial.
class (Factorial m, MonoidNull m) => FactorialMonoid m where
   -- | Splits the argument into its prime prefix and the remaining suffix. Returns 'Nothing' for 'mempty'.
   splitPrimePrefix :: m -> Maybe (m, m)
   -- | Splits the argument into its prime suffix and the remaining prefix. Returns 'Nothing' for 'mempty'.
   splitPrimeSuffix :: m -> Maybe (m, m)
   -- | Returns the list of all prefixes of the argument, 'mempty' first.
   inits :: m -> [m]
   -- | Returns the list of all suffixes of the argument, 'mempty' last.
   tails :: m -> [m]
   -- | Like 'List.span' from "Data.List" on the list of prime 'factors'.
   span :: (m -> Bool) -> m -> (m, m)
   -- | Equivalent to 'List.break' from "Data.List".
   break :: (m -> Bool) -> m -> (m, m)
   -- | Splits the monoid into components delimited by prime separators satisfying the given predicate. The primes
   -- satisfying the predicate are not a part of the result.
   split :: (m -> Bool) -> m -> [m]
   -- | Equivalent to 'List.takeWhile' from "Data.List".
   takeWhile :: (m -> Bool) -> m -> m
   -- | Equivalent to 'List.dropWhile' from "Data.List".
   dropWhile :: (m -> Bool) -> m -> m
   -- | A stateful variant of 'span', threading the result of the test function as long as it returns 'Just'.
   spanMaybe :: s -> (s -> m -> Maybe s) -> m -> (m, m, s)
   -- | Strict version of 'spanMaybe'.
   spanMaybe' :: s -> (s -> m -> Maybe s) -> m -> (m, m, s)
   -- | Like 'List.splitAt' from "Data.List" on the list of prime 'factors'.
   splitAt :: Int -> m -> (m, m)
   -- | Equivalent to 'List.drop' from "Data.List".
   drop :: Int -> m -> m
   -- | Equivalent to 'List.take' from "Data.List".
   take :: Int -> m -> m

   splitPrimePrefix m
x = case m -> [m]
forall m. Factorial m => m -> [m]
factors m
x
                        of [] -> Maybe (m, m)
forall a. Maybe a
Nothing
                           m
prefix : [m]
rest -> (m, m) -> Maybe (m, m)
forall a. a -> Maybe a
Just (m
prefix, [m] -> m
forall a. Monoid a => [a] -> a
mconcat [m]
rest)
   splitPrimeSuffix m
x = case m -> [m]
forall m. Factorial m => m -> [m]
factors m
x
                        of [] -> Maybe (m, m)
forall a. Maybe a
Nothing
                           [m]
fs -> (m, m) -> Maybe (m, m)
forall a. a -> Maybe a
Just ([m] -> m
forall a. Monoid a => [a] -> a
mconcat ([m] -> [m]
forall a. HasCallStack => [a] -> [a]
List.init [m]
fs), [m] -> m
forall a. HasCallStack => [a] -> a
List.last [m]
fs)
   inits = (m -> [m] -> [m]) -> [m] -> m -> [m]
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
forall a. (m -> a -> a) -> a -> m -> a
foldr (\m
m [m]
l-> m
forall a. Monoid a => a
mempty m -> [m] -> [m]
forall a. a -> [a] -> [a]
: (m -> m) -> [m] -> [m]
forall a b. (a -> b) -> [a] -> [b]
List.map (m -> m -> m
forall a. Monoid a => a -> a -> a
mappend m
m) [m]
l) [m
forall a. Monoid a => a
mempty]
   tails m
m = m
m m -> [m] -> [m]
forall a. a -> [a] -> [a]
: [m] -> ((m, m) -> [m]) -> Maybe (m, m) -> [m]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe [] (m -> [m]
forall m. FactorialMonoid m => m -> [m]
tails (m -> [m]) -> ((m, m) -> m) -> (m, m) -> [m]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (m, m) -> m
forall a b. (a, b) -> b
snd) (m -> Maybe (m, m)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix m
m)
   span m -> Bool
p m
m0 = (m -> m) -> m -> (m, m)
forall {a}. (m -> a) -> m -> (a, m)
spanAfter m -> m
forall a. a -> a
id m
m0
      where spanAfter :: (m -> a) -> m -> (a, m)
spanAfter m -> a
f m
m = case m -> Maybe (m, m)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix m
m
                            of Just (m
prime, m
rest) | m -> Bool
p m
prime -> (m -> a) -> m -> (a, m)
spanAfter (m -> a
f (m -> a) -> (m -> m) -> m -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m -> m -> m
forall a. Monoid a => a -> a -> a
mappend m
prime) m
rest
                               Maybe (m, m)
_ -> (m -> a
f m
forall a. Monoid a => a
mempty, m
m)
   break = (m -> Bool) -> m -> (m, m)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((m -> Bool) -> m -> (m, m))
-> ((m -> Bool) -> m -> Bool) -> (m -> Bool) -> m -> (m, m)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Bool -> Bool
not (Bool -> Bool) -> (m -> Bool) -> m -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.)
   spanMaybe s
s0 s -> m -> Maybe s
f m
m0 = (m -> m) -> s -> m -> (m, m, s)
spanAfter m -> m
forall a. a -> a
id s
s0 m
m0
      where spanAfter :: (m -> m) -> s -> m -> (m, m, s)
spanAfter m -> m
g s
s m
m = case m -> Maybe (m, m)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix m
m
                              of Just (m
prime, m
rest) | Just s
s' <- s -> m -> Maybe s
f s
s m
prime -> (m -> m) -> s -> m -> (m, m, s)
spanAfter (m -> m
g (m -> m) -> (m -> m) -> m -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m -> m -> m
forall a. Monoid a => a -> a -> a
mappend m
prime) s
s' m
rest
                                                    | Bool
otherwise -> (m -> m
g m
forall a. Monoid a => a
mempty, m
m, s
s)
                                 Maybe (m, m)
Nothing -> (m
m0, m
m, s
s)
   spanMaybe' s
s0 s -> m -> Maybe s
f m
m0 = (m -> m) -> s -> m -> (m, m, s)
spanAfter m -> m
forall a. a -> a
id s
s0 m
m0
      where spanAfter :: (m -> m) -> s -> m -> (m, m, s)
spanAfter m -> m
g s
s m
m = s -> (m, m, s) -> (m, m, s)
forall a b. a -> b -> b
seq s
s ((m, m, s) -> (m, m, s)) -> (m, m, s) -> (m, m, s)
forall a b. (a -> b) -> a -> b
$
                              case m -> Maybe (m, m)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix m
m
                              of Just (m
prime, m
rest) | Just s
s' <- s -> m -> Maybe s
f s
s m
prime -> (m -> m) -> s -> m -> (m, m, s)
spanAfter (m -> m
g (m -> m) -> (m -> m) -> m -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m -> m -> m
forall a. Monoid a => a -> a -> a
mappend m
prime) s
s' m
rest
                                                    | Bool
otherwise -> (m -> m
g m
forall a. Monoid a => a
mempty, m
m, s
s)
                                 Maybe (m, m)
Nothing -> (m
m0, m
m, s
s)
   split m -> Bool
p m
m = m
prefix m -> [m] -> [m]
forall a. a -> [a] -> [a]
: [m]
splitRest
      where (m
prefix, m
rest) = (m -> Bool) -> m -> (m, m)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
break m -> Bool
p m
m
            splitRest :: [m]
splitRest = case m -> Maybe (m, m)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix m
rest
                        of Maybe (m, m)
Nothing -> []
                           Just (m
_, m
tl) -> (m -> Bool) -> m -> [m]
forall m. FactorialMonoid m => (m -> Bool) -> m -> [m]
split m -> Bool
p m
tl
   takeWhile m -> Bool
p = (m, m) -> m
forall a b. (a, b) -> a
fst ((m, m) -> m) -> (m -> (m, m)) -> m -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (m -> Bool) -> m -> (m, m)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span m -> Bool
p
   dropWhile m -> Bool
p = (m, m) -> m
forall a b. (a, b) -> b
snd ((m, m) -> m) -> (m -> (m, m)) -> m -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (m -> Bool) -> m -> (m, m)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span m -> Bool
p
   splitAt Int
n0 m
m0 | Int
n0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = (m
forall a. Monoid a => a
mempty, m
m0)
                 | Bool
otherwise = Int -> (m -> m) -> m -> (m, m)
forall {t} {t} {c}.
(Eq t, Num t, FactorialMonoid t, Enum t) =>
t -> (t -> c) -> t -> (c, t)
split' Int
n0 m -> m
forall a. a -> a
id m
m0
      where split' :: t -> (t -> c) -> t -> (c, t)
split' t
0 t -> c
f t
m = (t -> c
f t
forall a. Monoid a => a
mempty, t
m)
            split' t
n t -> c
f t
m = case t -> Maybe (t, t)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix t
m
                           of Maybe (t, t)
Nothing -> (t -> c
f t
forall a. Monoid a => a
mempty, t
m)
                              Just (t
prime, t
rest) -> t -> (t -> c) -> t -> (c, t)
split' (t -> t
forall a. Enum a => a -> a
pred t
n) (t -> c
f (t -> c) -> (t -> t) -> t -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> t -> t
forall a. Monoid a => a -> a -> a
mappend t
prime) t
rest
   drop Int
n m
p = (m, m) -> m
forall a b. (a, b) -> b
snd (Int -> m -> (m, m)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n m
p)
   take Int
n m
p = (m, m) -> m
forall a b. (a, b) -> a
fst (Int -> m -> (m, m)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n m
p)
   {-# MINIMAL #-}
   {-# INLINABLE splitPrimePrefix #-}
   {-# INLINABLE splitPrimeSuffix #-}
   {-# INLINABLE inits #-}
   {-# INLINABLE tails #-}
   {-# INLINABLE span #-}
   {-# INLINE break #-}
   {-# INLINABLE spanMaybe #-}
   {-# INLINABLE spanMaybe' #-}
   {-# INLINABLE split #-}
   {-# INLINE takeWhile #-}
   {-# INLINE dropWhile #-}
   {-# INLINABLE splitAt #-}

{-# DEPRECATED StableFactorialMonoid "Use Data.Semigroup.Factorial.StableFactorial instead." #-}
type StableFactorialMonoid m = (StableFactorial m, FactorialMonoid m, PositiveMonoid m)

instance FactorialMonoid () where
   splitPrimePrefix :: () -> Maybe ((), ())
splitPrimePrefix () = Maybe ((), ())
forall a. Maybe a
Nothing
   splitPrimeSuffix :: () -> Maybe ((), ())
splitPrimeSuffix () = Maybe ((), ())
forall a. Maybe a
Nothing

instance FactorialMonoid a => FactorialMonoid (Dual a) where
   splitPrimePrefix :: Dual a -> Maybe (Dual a, Dual a)
splitPrimePrefix (Dual a
a) = case a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a
                               of Maybe (a, a)
Nothing -> Maybe (Dual a, Dual a)
forall a. Maybe a
Nothing
                                  Just (a
p, a
s) -> (Dual a, Dual a) -> Maybe (Dual a, Dual a)
forall a. a -> Maybe a
Just (a -> Dual a
forall a. a -> Dual a
Dual a
s, a -> Dual a
forall a. a -> Dual a
Dual a
p)
   splitPrimeSuffix :: Dual a -> Maybe (Dual a, Dual a)
splitPrimeSuffix (Dual a
a) = case a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a
                               of Maybe (a, a)
Nothing -> Maybe (Dual a, Dual a)
forall a. Maybe a
Nothing
                                  Just (a
p, a
s) -> (Dual a, Dual a) -> Maybe (Dual a, Dual a)
forall a. a -> Maybe a
Just (a -> Dual a
forall a. a -> Dual a
Dual a
s, a -> Dual a
forall a. a -> Dual a
Dual a
p)
   inits :: Dual a -> [Dual a]
inits (Dual a
a) = (a -> Dual a) -> [a] -> [Dual a]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Dual a
forall a. a -> Dual a
Dual ([a] -> [a]
forall m. Factorial m => m -> m
reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a -> [a]
forall m. FactorialMonoid m => m -> [m]
tails a
a)
   tails :: Dual a -> [Dual a]
tails (Dual a
a) = (a -> Dual a) -> [a] -> [Dual a]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Dual a
forall a. a -> Dual a
Dual ([a] -> [a]
forall m. Factorial m => m -> m
reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a -> [a]
forall m. FactorialMonoid m => m -> [m]
inits a
a)

instance (Integral a, Eq a) => FactorialMonoid (Sum a) where
   splitPrimePrefix :: Sum a -> Maybe (Sum a, Sum a)
splitPrimePrefix (Sum a
0) = Maybe (Sum a, Sum a)
forall a. Maybe a
Nothing
   splitPrimePrefix (Sum a
a) = (Sum a, Sum a) -> Maybe (Sum a, Sum a)
forall a. a -> Maybe a
Just (a -> Sum a
forall a. a -> Sum a
Sum (a -> a
forall a. Num a => a -> a
signum a
a), a -> Sum a
forall a. a -> Sum a
Sum (a
a a -> a -> a
forall a. Num a => a -> a -> a
- a -> a
forall a. Num a => a -> a
signum a
a))
   splitPrimeSuffix :: Sum a -> Maybe (Sum a, Sum a)
splitPrimeSuffix (Sum a
0) = Maybe (Sum a, Sum a)
forall a. Maybe a
Nothing
   splitPrimeSuffix (Sum a
a) = (Sum a, Sum a) -> Maybe (Sum a, Sum a)
forall a. a -> Maybe a
Just (a -> Sum a
forall a. a -> Sum a
Sum (a
a a -> a -> a
forall a. Num a => a -> a -> a
- a -> a
forall a. Num a => a -> a
signum a
a), a -> Sum a
forall a. a -> Sum a
Sum (a -> a
forall a. Num a => a -> a
signum a
a))

instance Integral a => FactorialMonoid (Product a)

instance FactorialMonoid a => FactorialMonoid (Maybe a) where
   splitPrimePrefix :: Maybe a -> Maybe (Maybe a, Maybe a)
splitPrimePrefix Maybe a
Nothing = Maybe (Maybe a, Maybe a)
forall a. Maybe a
Nothing
   splitPrimePrefix (Just a
a) = case a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a
                               of Maybe (a, a)
Nothing -> (Maybe a, Maybe a) -> Maybe (Maybe a, Maybe a)
forall a. a -> Maybe a
Just (a -> Maybe a
forall a. a -> Maybe a
Just a
a, Maybe a
forall a. Maybe a
Nothing)
                                  Just (a
p, a
s) -> (Maybe a, Maybe a) -> Maybe (Maybe a, Maybe a)
forall a. a -> Maybe a
Just (a -> Maybe a
forall a. a -> Maybe a
Just a
p, if a -> Bool
forall m. MonoidNull m => m -> Bool
null a
s then Maybe a
forall a. Maybe a
Nothing else a -> Maybe a
forall a. a -> Maybe a
Just a
s)


instance (FactorialMonoid a, FactorialMonoid b) => FactorialMonoid (a, b) where
   splitPrimePrefix :: (a, b) -> Maybe ((a, b), (a, b))
splitPrimePrefix (a
a, b
b) = case (a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a, b -> Maybe (b, b)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix b
b)
                             of (Just (a
ap, a
as), Maybe (b, b)
_) -> ((a, b), (a, b)) -> Maybe ((a, b), (a, b))
forall a. a -> Maybe a
Just ((a
ap, b
forall a. Monoid a => a
mempty), (a
as, b
b))
                                (Maybe (a, a)
Nothing, Just (b
bp, b
bs)) -> ((a, b), (a, b)) -> Maybe ((a, b), (a, b))
forall a. a -> Maybe a
Just ((a
a, b
bp), (a
a, b
bs))
                                (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing) -> Maybe ((a, b), (a, b))
forall a. Maybe a
Nothing
   splitPrimeSuffix :: (a, b) -> Maybe ((a, b), (a, b))
splitPrimeSuffix (a
a, b
b) = case (a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a, b -> Maybe (b, b)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix b
b)
                             of (Maybe (a, a)
_, Just (b
bp, b
bs)) -> ((a, b), (a, b)) -> Maybe ((a, b), (a, b))
forall a. a -> Maybe a
Just ((a
a, b
bp), (a
forall a. Monoid a => a
mempty, b
bs))
                                (Just (a
ap, a
as), Maybe (b, b)
Nothing) -> ((a, b), (a, b)) -> Maybe ((a, b), (a, b))
forall a. a -> Maybe a
Just ((a
ap, b
b), (a
as, b
b))
                                (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing) -> Maybe ((a, b), (a, b))
forall a. Maybe a
Nothing
   inits :: (a, b) -> [(a, b)]
inits (a
a, b
b) = (a -> (a, b)) -> [a] -> [(a, b)]
forall a b. (a -> b) -> [a] -> [b]
List.map ((a -> b -> (a, b)) -> b -> a -> (a, b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (,) b
forall a. Monoid a => a
mempty) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
inits a
a) [(a, b)] -> [(a, b)] -> [(a, b)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b)) -> [b] -> [(a, b)]
forall a b. (a -> b) -> [a] -> [b]
List.map ((,) a
a) ([b] -> [b]
forall a. HasCallStack => [a] -> [a]
List.tail ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ b -> [b]
forall m. FactorialMonoid m => m -> [m]
inits b
b)
   tails :: (a, b) -> [(a, b)]
tails (a
a, b
b) = (a -> (a, b)) -> [a] -> [(a, b)]
forall a b. (a -> b) -> [a] -> [b]
List.map ((a -> b -> (a, b)) -> b -> a -> (a, b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (,) b
b) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
tails a
a) [(a, b)] -> [(a, b)] -> [(a, b)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b)) -> [b] -> [(a, b)]
forall a b. (a -> b) -> [a] -> [b]
List.map ((,) a
forall a. Monoid a => a
mempty) ([b] -> [b]
forall a. HasCallStack => [a] -> [a]
List.tail ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ b -> [b]
forall m. FactorialMonoid m => m -> [m]
tails b
b)
   span :: ((a, b) -> Bool) -> (a, b) -> ((a, b), (a, b))
span (a, b) -> Bool
p (a
x, b
y) = ((a
xp, b
yp), (a
xs, b
ys))
      where (a
xp, a
xs) = (a -> Bool) -> a -> (a, a)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b) -> Bool
p ((a, b) -> Bool) -> (a -> (a, b)) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b)
forall b a. Monoid b => a -> (a, b)
fromFst) a
x
            (b
yp, b
ys) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
xs = (b -> Bool) -> b -> (b, b)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b) -> Bool
p ((a, b) -> Bool) -> (b -> (a, b)) -> b -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b)
forall a b. Monoid a => b -> (a, b)
fromSnd) b
y
                     | Bool
otherwise = (b
forall a. Monoid a => a
mempty, b
y)
   spanMaybe :: forall s.
s -> (s -> (a, b) -> Maybe s) -> (a, b) -> ((a, b), (a, b), s)
spanMaybe s
s0 s -> (a, b) -> Maybe s
f (a
x, b
y) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
xs = ((a
xp, b
yp), (a
xs, b
ys), s
s2)
                         | Bool
otherwise = ((a
xp, b
forall a. Monoid a => a
mempty), (a
xs, b
y), s
s1)
     where (a
xp, a
xs, s
s1) = s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall s. s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s0 (\s
s-> s -> (a, b) -> Maybe s
f s
s ((a, b) -> Maybe s) -> (a -> (a, b)) -> a -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b)
forall b a. Monoid b => a -> (a, b)
fromFst) a
x
           (b
yp, b
ys, s
s2) = s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall s. s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s1 (\s
s-> s -> (a, b) -> Maybe s
f s
s ((a, b) -> Maybe s) -> (b -> (a, b)) -> b -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b)
forall a b. Monoid a => b -> (a, b)
fromSnd) b
y
   spanMaybe' :: forall s.
s -> (s -> (a, b) -> Maybe s) -> (a, b) -> ((a, b), (a, b), s)
spanMaybe' s
s0 s -> (a, b) -> Maybe s
f (a
x, b
y) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
xs = ((a
xp, b
yp), (a
xs, b
ys), s
s2)
                          | Bool
otherwise = ((a
xp, b
forall a. Monoid a => a
mempty), (a
xs, b
y), s
s1)
     where (a
xp, a
xs, s
s1) = s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall s. s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s0 (\s
s-> s -> (a, b) -> Maybe s
f s
s ((a, b) -> Maybe s) -> (a -> (a, b)) -> a -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b)
forall b a. Monoid b => a -> (a, b)
fromFst) a
x
           (b
yp, b
ys, s
s2) = s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall s. s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s1 (\s
s-> s -> (a, b) -> Maybe s
f s
s ((a, b) -> Maybe s) -> (b -> (a, b)) -> b -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b)
forall a b. Monoid a => b -> (a, b)
fromSnd) b
y
   split :: ((a, b) -> Bool) -> (a, b) -> [(a, b)]
split (a, b) -> Bool
p (a
x0, b
y0) = ([(a, b)], Bool) -> [(a, b)]
forall a b. (a, b) -> a
fst (([(a, b)], Bool) -> [(a, b)]) -> ([(a, b)], Bool) -> [(a, b)]
forall a b. (a -> b) -> a -> b
$ ((a, b) -> ([(a, b)], Bool) -> ([(a, b)], Bool))
-> ([(a, b)], Bool) -> [(a, b)] -> ([(a, b)], Bool)
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
List.foldr (a, b) -> ([(a, b)], Bool) -> ([(a, b)], Bool)
forall {a}. Monoid a => a -> ([a], Bool) -> ([a], Bool)
combine ([(a, b)]
ys, Bool
False) [(a, b)]
xs
      where xs :: [(a, b)]
xs = (a -> (a, b)) -> [a] -> [(a, b)]
forall a b. (a -> b) -> [a] -> [b]
List.map a -> (a, b)
forall b a. Monoid b => a -> (a, b)
fromFst ([a] -> [(a, b)]) -> [a] -> [(a, b)]
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> a -> [a]
forall m. FactorialMonoid m => (m -> Bool) -> m -> [m]
split ((a, b) -> Bool
p ((a, b) -> Bool) -> (a -> (a, b)) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b)
forall b a. Monoid b => a -> (a, b)
fromFst) a
x0
            ys :: [(a, b)]
ys = (b -> (a, b)) -> [b] -> [(a, b)]
forall a b. (a -> b) -> [a] -> [b]
List.map b -> (a, b)
forall a b. Monoid a => b -> (a, b)
fromSnd ([b] -> [(a, b)]) -> [b] -> [(a, b)]
forall a b. (a -> b) -> a -> b
$ (b -> Bool) -> b -> [b]
forall m. FactorialMonoid m => (m -> Bool) -> m -> [m]
split ((a, b) -> Bool
p ((a, b) -> Bool) -> (b -> (a, b)) -> b -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b)
forall a b. Monoid a => b -> (a, b)
fromSnd) b
y0
            combine :: a -> ([a], Bool) -> ([a], Bool)
combine a
x (~(a
y:[a]
rest), Bool
False) = (a -> a -> a
forall a. Monoid a => a -> a -> a
mappend a
x a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
rest, Bool
True)
            combine a
x ([a]
rest, Bool
True) = (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
rest, Bool
True)
   splitAt :: Int -> (a, b) -> ((a, b), (a, b))
splitAt Int
n (a
x, b
y) = ((a
xp, b
yp), (a
xs, b
ys))
      where (a
xp, a
xs) = Int -> a -> (a, a)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n a
x
            (b
yp, b
ys) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
xs = Int -> b -> (b, b)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall m. Factorial m => m -> Int
length a
x) b
y
                     | Bool
otherwise = (b
forall a. Monoid a => a
mempty, b
y)

{-# INLINE fromFst #-}
fromFst :: Monoid b => a -> (a, b)
fromFst :: forall b a. Monoid b => a -> (a, b)
fromFst a
a = (a
a, b
forall a. Monoid a => a
mempty)

{-# INLINE fromSnd #-}
fromSnd :: Monoid a => b -> (a, b)
fromSnd :: forall a b. Monoid a => b -> (a, b)
fromSnd b
b = (a
forall a. Monoid a => a
mempty, b
b)

instance (FactorialMonoid a, FactorialMonoid b, FactorialMonoid c) => FactorialMonoid (a, b, c) where
   splitPrimePrefix :: (a, b, c) -> Maybe ((a, b, c), (a, b, c))
splitPrimePrefix (a
a, b
b, c
c) = case (a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a, b -> Maybe (b, b)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix b
b, c -> Maybe (c, c)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix c
c)
                                of (Just (a
ap, a
as), Maybe (b, b)
_, Maybe (c, c)
_) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty), (a
as, b
b, c
c))
                                   (Maybe (a, a)
Nothing, Just (b
bp, b
bs), Maybe (c, c)
_) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
a, b
bp, c
forall a. Monoid a => a
mempty), (a
a, b
bs, c
c))
                                   (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Just (c
cp, c
cs)) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
a, b
b, c
cp), (a
a, b
b, c
cs))
                                   (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Maybe (c, c)
Nothing) -> Maybe ((a, b, c), (a, b, c))
forall a. Maybe a
Nothing
   splitPrimeSuffix :: (a, b, c) -> Maybe ((a, b, c), (a, b, c))
splitPrimeSuffix (a
a, b
b, c
c) = case (a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a, b -> Maybe (b, b)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix b
b, c -> Maybe (c, c)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix c
c)
                                of (Maybe (a, a)
_, Maybe (b, b)
_, Just (c
cp, c
cs)) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
a, b
b, c
cp), (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
cs))
                                   (Maybe (a, a)
_, Just (b
bp, b
bs), Maybe (c, c)
Nothing) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
a, b
bp, c
c), (a
forall a. Monoid a => a
mempty, b
bs, c
c))
                                   (Just (a
ap, a
as), Maybe (b, b)
Nothing, Maybe (c, c)
Nothing) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
ap, b
b, c
c), (a
as, b
b, c
c))
                                   (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Maybe (c, c)
Nothing) -> Maybe ((a, b, c), (a, b, c))
forall a. Maybe a
Nothing
   inits :: (a, b, c) -> [(a, b, c)]
inits (a
a, b
b, c
c) = (a -> (a, b, c)) -> [a] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty)) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
inits a
a)
                     [(a, b, c)] -> [(a, b, c)] -> [(a, b, c)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b, c)) -> [b] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
a, b
b1, c
forall a. Monoid a => a
mempty)) ([b] -> [b]
forall a. HasCallStack => [a] -> [a]
List.tail ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ b -> [b]
forall m. FactorialMonoid m => m -> [m]
inits b
b)
                     [(a, b, c)] -> [(a, b, c)] -> [(a, b, c)]
forall a. [a] -> [a] -> [a]
++ (c -> (a, b, c)) -> [c] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
a, b
b, c
c1)) ([c] -> [c]
forall a. HasCallStack => [a] -> [a]
List.tail ([c] -> [c]) -> [c] -> [c]
forall a b. (a -> b) -> a -> b
$ c -> [c]
forall m. FactorialMonoid m => m -> [m]
inits c
c)
   tails :: (a, b, c) -> [(a, b, c)]
tails (a
a, b
b, c
c) = (a -> (a, b, c)) -> [a] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
b, c
c)) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
tails a
a)
                     [(a, b, c)] -> [(a, b, c)] -> [(a, b, c)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b, c)) -> [b] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
forall a. Monoid a => a
mempty, b
b1, c
c)) ([b] -> [b]
forall a. HasCallStack => [a] -> [a]
List.tail ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ b -> [b]
forall m. FactorialMonoid m => m -> [m]
tails b
b)
                     [(a, b, c)] -> [(a, b, c)] -> [(a, b, c)]
forall a. [a] -> [a] -> [a]
++ (c -> (a, b, c)) -> [c] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
c1)) ([c] -> [c]
forall a. HasCallStack => [a] -> [a]
List.tail ([c] -> [c]) -> [c] -> [c]
forall a b. (a -> b) -> a -> b
$ c -> [c]
forall m. FactorialMonoid m => m -> [m]
tails c
c)
   span :: ((a, b, c) -> Bool) -> (a, b, c) -> ((a, b, c), (a, b, c))
span (a, b, c) -> Bool
p (a
a, b
b, c
c) = ((a
ap, b
bp, c
cp), (a
as, b
bs, c
cs))
      where (a
ap, a
as) = (a -> Bool) -> a -> (a, a)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c) -> Bool
p ((a, b, c) -> Bool) -> (a -> (a, b, c)) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c)
forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) a
a
            (b
bp, b
bs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as = (b -> Bool) -> b -> (b, b)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c) -> Bool
p ((a, b, c) -> Bool) -> (b -> (a, b, c)) -> b -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c)
forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) b
b
                     | Bool
otherwise = (b
forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs = (c -> Bool) -> c -> (c, c)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c) -> Bool
p ((a, b, c) -> Bool) -> (c -> (a, b, c)) -> c -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c)
forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3) c
c
                     | Bool
otherwise = (c
forall a. Monoid a => a
mempty, c
c)
   spanMaybe :: forall s.
s
-> (s -> (a, b, c) -> Maybe s)
-> (a, b, c)
-> ((a, b, c), (a, b, c), s)
spanMaybe s
s0 s -> (a, b, c) -> Maybe s
f (a
a, b
b, c
c) | Bool -> Bool
not (a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty), (a
as, b
b, c
c), s
s1)
                            | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, c
forall a. Monoid a => a
mempty), (a
as, b
bs, c
c), s
s2)
                            | Bool
otherwise = ((a
ap, b
bp, c
cp), (a
as, b
bs, c
cs), s
s3)
     where (a
ap, a
as, s
s1) = s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall s. s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s0 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (a -> (a, b, c)) -> a -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c)
forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) a
a
           (b
bp, b
bs, s
s2) = s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall s. s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s1 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (b -> (a, b, c)) -> b -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c)
forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) b
b
           (c
cp, c
cs, s
s3) = s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall s. s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s2 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (c -> (a, b, c)) -> c -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c)
forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3) c
c
   spanMaybe' :: forall s.
s
-> (s -> (a, b, c) -> Maybe s)
-> (a, b, c)
-> ((a, b, c), (a, b, c), s)
spanMaybe' s
s0 s -> (a, b, c) -> Maybe s
f (a
a, b
b, c
c) | Bool -> Bool
not (a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty), (a
as, b
b, c
c), s
s1)
                             | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, c
forall a. Monoid a => a
mempty), (a
as, b
bs, c
c), s
s2)
                             | Bool
otherwise = ((a
ap, b
bp, c
cp), (a
as, b
bs, c
cs), s
s3)
     where (a
ap, a
as, s
s1) = s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall s. s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s0 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (a -> (a, b, c)) -> a -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c)
forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) a
a
           (b
bp, b
bs, s
s2) = s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall s. s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s1 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (b -> (a, b, c)) -> b -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c)
forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) b
b
           (c
cp, c
cs, s
s3) = s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall s. s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s2 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (c -> (a, b, c)) -> c -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c)
forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3) c
c
   splitAt :: Int -> (a, b, c) -> ((a, b, c), (a, b, c))
splitAt Int
n (a
a, b
b, c
c) = ((a
ap, b
bp, c
cp), (a
as, b
bs, c
cs))
      where (a
ap, a
as) = Int -> a -> (a, a)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n a
a
            (b
bp, b
bs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as = Int -> b -> (b, b)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall m. Factorial m => m -> Int
length a
a) b
b
                     | Bool
otherwise = (b
forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs = Int -> c -> (c, c)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall m. Factorial m => m -> Int
length a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall m. Factorial m => m -> Int
length b
b) c
c
                     | Bool
otherwise = (c
forall a. Monoid a => a
mempty, c
c)

{-# INLINE fromFstOf3 #-}
fromFstOf3 :: (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3 :: forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3 a
a = (a
a, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty)

{-# INLINE fromSndOf3 #-}
fromSndOf3 :: (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3 :: forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3 b
b = (a
forall a. Monoid a => a
mempty, b
b, c
forall a. Monoid a => a
mempty)

{-# INLINE fromThdOf3 #-}
fromThdOf3 :: (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3 :: forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3 c
c = (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
c)

instance (FactorialMonoid a, FactorialMonoid b, FactorialMonoid c, FactorialMonoid d) =>
         FactorialMonoid (a, b, c, d) where
   splitPrimePrefix :: (a, b, c, d) -> Maybe ((a, b, c, d), (a, b, c, d))
splitPrimePrefix (a
a, b
b, c
c, d
d) = case (a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a, b -> Maybe (b, b)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix b
b, c -> Maybe (c, c)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix c
c, d -> Maybe (d, d)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix d
d)
                                   of (Just (a
ap, a
as), Maybe (b, b)
_, Maybe (c, c)
_, Maybe (d, d)
_) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
as, b
b, c
c, d
d))
                                      (Maybe (a, a)
Nothing, Just (b
bp, b
bs), Maybe (c, c)
_, Maybe (d, d)
_) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
bp, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
a, b
bs, c
c, d
d))
                                      (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Just (c
cp, c
cs), Maybe (d, d)
_) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
b, c
cp, d
forall a. Monoid a => a
mempty), (a
a, b
b, c
cs, d
d))
                                      (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Maybe (c, c)
Nothing, Just (d
dp, d
ds)) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
b, c
c, d
dp), (a
a, b
b, c
c, d
ds))
                                      (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Maybe (c, c)
Nothing, Maybe (d, d)
Nothing) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. Maybe a
Nothing
   splitPrimeSuffix :: (a, b, c, d) -> Maybe ((a, b, c, d), (a, b, c, d))
splitPrimeSuffix (a
a, b
b, c
c, d
d) = case (a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a, b -> Maybe (b, b)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix b
b, c -> Maybe (c, c)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix c
c, d -> Maybe (d, d)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix d
d)
                                   of (Maybe (a, a)
_, Maybe (b, b)
_, Maybe (c, c)
_, Just (d
dp, d
ds)) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
b, c
c, d
dp), (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
ds))
                                      (Maybe (a, a)
_, Maybe (b, b)
_, Just (c
cp, c
cs), Maybe (d, d)
Nothing) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
b, c
cp, d
d), (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
cs, d
d))
                                      (Maybe (a, a)
_, Just (b
bp, b
bs), Maybe (c, c)
Nothing, Maybe (d, d)
Nothing) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
bp, c
c, d
d), (a
forall a. Monoid a => a
mempty, b
bs, c
c, d
d))
                                      (Just (a
ap, a
as), Maybe (b, b)
Nothing, Maybe (c, c)
Nothing, Maybe (d, d)
Nothing) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
ap, b
b, c
c, d
d), (a
as, b
b, c
c, d
d))
                                      (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Maybe (c, c)
Nothing, Maybe (d, d)
Nothing) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. Maybe a
Nothing
   inits :: (a, b, c, d) -> [(a, b, c, d)]
inits (a
a, b
b, c
c, d
d) = (a -> (a, b, c, d)) -> [a] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
inits a
a)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b, c, d)) -> [b] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
a, b
b1, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)) ([b] -> [b]
forall a. HasCallStack => [a] -> [a]
List.tail ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ b -> [b]
forall m. FactorialMonoid m => m -> [m]
inits b
b)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (c -> (a, b, c, d)) -> [c] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
a, b
b, c
c1, d
forall a. Monoid a => a
mempty)) ([c] -> [c]
forall a. HasCallStack => [a] -> [a]
List.tail ([c] -> [c]) -> [c] -> [c]
forall a b. (a -> b) -> a -> b
$ c -> [c]
forall m. FactorialMonoid m => m -> [m]
inits c
c)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (d -> (a, b, c, d)) -> [d] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\d
d1-> (a
a, b
b, c
c, d
d1)) ([d] -> [d]
forall a. HasCallStack => [a] -> [a]
List.tail ([d] -> [d]) -> [d] -> [d]
forall a b. (a -> b) -> a -> b
$ d -> [d]
forall m. FactorialMonoid m => m -> [m]
inits d
d)
   tails :: (a, b, c, d) -> [(a, b, c, d)]
tails (a
a, b
b, c
c, d
d) = (a -> (a, b, c, d)) -> [a] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
b, c
c, d
d)) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
tails a
a)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b, c, d)) -> [b] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
forall a. Monoid a => a
mempty, b
b1, c
c, d
d)) ([b] -> [b]
forall a. HasCallStack => [a] -> [a]
List.tail ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ b -> [b]
forall m. FactorialMonoid m => m -> [m]
tails b
b)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (c -> (a, b, c, d)) -> [c] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
c1, d
d)) ([c] -> [c]
forall a. HasCallStack => [a] -> [a]
List.tail ([c] -> [c]) -> [c] -> [c]
forall a b. (a -> b) -> a -> b
$ c -> [c]
forall m. FactorialMonoid m => m -> [m]
tails c
c)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (d -> (a, b, c, d)) -> [d] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\d
d1-> (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
d1)) ([d] -> [d]
forall a. HasCallStack => [a] -> [a]
List.tail ([d] -> [d]) -> [d] -> [d]
forall a b. (a -> b) -> a -> b
$ d -> [d]
forall m. FactorialMonoid m => m -> [m]
tails d
d)
   span :: ((a, b, c, d) -> Bool)
-> (a, b, c, d) -> ((a, b, c, d), (a, b, c, d))
span (a, b, c, d) -> Bool
p (a
a, b
b, c
c, d
d) = ((a
ap, b
bp, c
cp, d
dp), (a
as, b
bs, c
cs, d
ds))
      where (a
ap, a
as) = (a -> Bool) -> a -> (a, a)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p ((a, b, c, d) -> Bool) -> (a -> (a, b, c, d)) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c, d)
forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4) a
a
            (b
bp, b
bs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as = (b -> Bool) -> b -> (b, b)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p ((a, b, c, d) -> Bool) -> (b -> (a, b, c, d)) -> b -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c, d)
forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4) b
b
                     | Bool
otherwise = (b
forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs = (c -> Bool) -> c -> (c, c)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p ((a, b, c, d) -> Bool) -> (c -> (a, b, c, d)) -> c -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c, d)
forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4) c
c
                     | Bool
otherwise = (c
forall a. Monoid a => a
mempty, c
c)
            (d
dp, d
ds) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs Bool -> Bool -> Bool
&& c -> Bool
forall m. MonoidNull m => m -> Bool
null c
cs = (d -> Bool) -> d -> (d, d)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p ((a, b, c, d) -> Bool) -> (d -> (a, b, c, d)) -> d -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. d -> (a, b, c, d)
forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4) d
d
                     | Bool
otherwise = (d
forall a. Monoid a => a
mempty, d
d)
   spanMaybe :: forall s.
s
-> (s -> (a, b, c, d) -> Maybe s)
-> (a, b, c, d)
-> ((a, b, c, d), (a, b, c, d), s)
spanMaybe s
s0 s -> (a, b, c, d) -> Maybe s
f (a
a, b
b, c
c, d
d) | Bool -> Bool
not (a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
as, b
b, c
c, d
d), s
s1)
                               | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
as, b
bs, c
c, d
d), s
s2)
                               | Bool -> Bool
not (c -> Bool
forall m. MonoidNull m => m -> Bool
null c
cs) = ((a
ap, b
bp, c
cp, d
forall a. Monoid a => a
mempty), (a
as, b
bs, c
cs, d
d), s
s3)
                               | Bool
otherwise = ((a
ap, b
bp, c
cp, d
dp), (a
as, b
bs, c
cs, d
ds), s
s4)
     where (a
ap, a
as, s
s1) = s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall s. s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s0 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (a -> (a, b, c, d)) -> a -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c, d)
forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4) a
a
           (b
bp, b
bs, s
s2) = s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall s. s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s1 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (b -> (a, b, c, d)) -> b -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c, d)
forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4) b
b
           (c
cp, c
cs, s
s3) = s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall s. s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s2 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (c -> (a, b, c, d)) -> c -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c, d)
forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4) c
c
           (d
dp, d
ds, s
s4) = s -> (s -> d -> Maybe s) -> d -> (d, d, s)
forall s. s -> (s -> d -> Maybe s) -> d -> (d, d, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s3 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (d -> (a, b, c, d)) -> d -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. d -> (a, b, c, d)
forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4) d
d
   spanMaybe' :: forall s.
s
-> (s -> (a, b, c, d) -> Maybe s)
-> (a, b, c, d)
-> ((a, b, c, d), (a, b, c, d), s)
spanMaybe' s
s0 s -> (a, b, c, d) -> Maybe s
f (a
a, b
b, c
c, d
d) | Bool -> Bool
not (a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
as, b
b, c
c, d
d), s
s1)
                               | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
as, b
bs, c
c, d
d), s
s2)
                               | Bool -> Bool
not (c -> Bool
forall m. MonoidNull m => m -> Bool
null c
cs) = ((a
ap, b
bp, c
cp, d
forall a. Monoid a => a
mempty), (a
as, b
bs, c
cs, d
d), s
s3)
                               | Bool
otherwise = ((a
ap, b
bp, c
cp, d
dp), (a
as, b
bs, c
cs, d
ds), s
s4)
     where (a
ap, a
as, s
s1) = s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall s. s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s0 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (a -> (a, b, c, d)) -> a -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c, d)
forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4) a
a
           (b
bp, b
bs, s
s2) = s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall s. s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s1 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (b -> (a, b, c, d)) -> b -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c, d)
forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4) b
b
           (c
cp, c
cs, s
s3) = s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall s. s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s2 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (c -> (a, b, c, d)) -> c -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c, d)
forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4) c
c
           (d
dp, d
ds, s
s4) = s -> (s -> d -> Maybe s) -> d -> (d, d, s)
forall s. s -> (s -> d -> Maybe s) -> d -> (d, d, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s3 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (d -> (a, b, c, d)) -> d -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. d -> (a, b, c, d)
forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4) d
d
   splitAt :: Int -> (a, b, c, d) -> ((a, b, c, d), (a, b, c, d))
splitAt Int
n (a
a, b
b, c
c, d
d) = ((a
ap, b
bp, c
cp, d
dp), (a
as, b
bs, c
cs, d
ds))
      where (a
ap, a
as) = Int -> a -> (a, a)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n a
a
            (b
bp, b
bs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as = Int -> b -> (b, b)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall m. Factorial m => m -> Int
length a
a) b
b
                     | Bool
otherwise = (b
forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs = Int -> c -> (c, c)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall m. Factorial m => m -> Int
length a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall m. Factorial m => m -> Int
length b
b) c
c
                     | Bool
otherwise = (c
forall a. Monoid a => a
mempty, c
c)
            (d
dp, d
ds) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs Bool -> Bool -> Bool
&& c -> Bool
forall m. MonoidNull m => m -> Bool
null c
cs = Int -> d -> (d, d)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall m. Factorial m => m -> Int
length a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall m. Factorial m => m -> Int
length b
b Int -> Int -> Int
forall a. Num a => a -> a -> a
- c -> Int
forall m. Factorial m => m -> Int
length c
c) d
d
                     | Bool
otherwise = (d
forall a. Monoid a => a
mempty, d
d)

{-# INLINE fromFstOf4 #-}
fromFstOf4 :: (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4 :: forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4 a
a = (a
a, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)

{-# INLINE fromSndOf4 #-}
fromSndOf4 :: (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4 :: forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4 b
b = (a
forall a. Monoid a => a
mempty, b
b, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)

{-# INLINE fromThdOf4 #-}
fromThdOf4 :: (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4 :: forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4 c
c = (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
c, d
forall a. Monoid a => a
mempty)

{-# INLINE fromFthOf4 #-}
fromFthOf4 :: (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4 :: forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4 d
d = (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
d)

instance FactorialMonoid [x] where
   splitPrimePrefix :: [x] -> Maybe ([x], [x])
splitPrimePrefix [] = Maybe ([x], [x])
forall a. Maybe a
Nothing
   splitPrimePrefix (x
x:[x]
xs) = ([x], [x]) -> Maybe ([x], [x])
forall a. a -> Maybe a
Just ([x
x], [x]
xs)
   splitPrimeSuffix :: [x] -> Maybe ([x], [x])
splitPrimeSuffix [] = Maybe ([x], [x])
forall a. Maybe a
Nothing
   splitPrimeSuffix [x]
xs = ([x], [x]) -> Maybe ([x], [x])
forall a. a -> Maybe a
Just (([x] -> [x]) -> [x] -> ([x], [x])
forall {a} {c}. ([a] -> c) -> [a] -> (c, [a])
splitLast [x] -> [x]
forall a. a -> a
id [x]
xs)
      where splitLast :: ([a] -> c) -> [a] -> (c, [a])
splitLast [a] -> c
f last :: [a]
last@[a
_] = ([a] -> c
f [], [a]
last)
            splitLast [a] -> c
f ~(a
x:[a]
rest) = ([a] -> c) -> [a] -> (c, [a])
splitLast ([a] -> c
f ([a] -> c) -> ([a] -> [a]) -> [a] -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) [a]
rest
   inits :: [x] -> [[x]]
inits = [x] -> [[x]]
forall x. [x] -> [[x]]
List.inits
   tails :: [x] -> [[x]]
tails = [x] -> [[x]]
forall x. [x] -> [[x]]
List.tails
   break :: ([x] -> Bool) -> [x] -> ([x], [x])
break [x] -> Bool
f = (x -> Bool) -> [x] -> ([x], [x])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.break ([x] -> Bool
f ([x] -> Bool) -> (x -> [x]) -> x -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> [x] -> [x]
forall a. a -> [a] -> [a]
:[]))
   span :: ([x] -> Bool) -> [x] -> ([x], [x])
span [x] -> Bool
f = (x -> Bool) -> [x] -> ([x], [x])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.span ([x] -> Bool
f ([x] -> Bool) -> (x -> [x]) -> x -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> [x] -> [x]
forall a. a -> [a] -> [a]
:[]))
   dropWhile :: ([x] -> Bool) -> [x] -> [x]
dropWhile [x] -> Bool
f = (x -> Bool) -> [x] -> [x]
forall a. (a -> Bool) -> [a] -> [a]
List.dropWhile ([x] -> Bool
f ([x] -> Bool) -> (x -> [x]) -> x -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> [x] -> [x]
forall a. a -> [a] -> [a]
:[]))
   takeWhile :: ([x] -> Bool) -> [x] -> [x]
takeWhile [x] -> Bool
f = (x -> Bool) -> [x] -> [x]
forall a. (a -> Bool) -> [a] -> [a]
List.takeWhile ([x] -> Bool
f ([x] -> Bool) -> (x -> [x]) -> x -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> [x] -> [x]
forall a. a -> [a] -> [a]
:[]))
   spanMaybe :: forall s. s -> (s -> [x] -> Maybe s) -> [x] -> ([x], [x], s)
spanMaybe s
s0 s -> [x] -> Maybe s
f [x]
l = ([x] -> [x]
prefix' [], [x] -> [x]
suffix' [], s
s')
      where ([x] -> [x]
prefix', [x] -> [x]
suffix', s
s', Bool
_) = (([x] -> [x], [x] -> [x], s, Bool)
 -> x -> ([x] -> [x], [x] -> [x], s, Bool))
-> ([x] -> [x], [x] -> [x], s, Bool)
-> [x]
-> ([x] -> [x], [x] -> [x], s, Bool)
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' ([x] -> [x], [x] -> [x], s, Bool)
-> x -> ([x] -> [x], [x] -> [x], s, Bool)
forall {c}.
([x] -> c, [x] -> [x], s, Bool)
-> x -> ([x] -> c, [x] -> [x], s, Bool)
g ([x] -> [x]
forall a. a -> a
id, [x] -> [x]
forall a. a -> a
id, s
s0, Bool
True) [x]
l
            g :: ([x] -> c, [x] -> [x], s, Bool)
-> x -> ([x] -> c, [x] -> [x], s, Bool)
g ([x] -> c
prefix, [x] -> [x]
suffix, s
s1, Bool
live) x
x | Bool
live, Just s
s2 <- s -> [x] -> Maybe s
f s
s1 [x
x] = ([x] -> c
prefix ([x] -> c) -> ([x] -> [x]) -> [x] -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x
xx -> [x] -> [x]
forall a. a -> [a] -> [a]
:), [x] -> [x]
forall a. a -> a
id, s
s2, Bool
True)
                                           | Bool
otherwise = ([x] -> c
prefix, [x] -> [x]
suffix ([x] -> [x]) -> ([x] -> [x]) -> [x] -> [x]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x
xx -> [x] -> [x]
forall a. a -> [a] -> [a]
:), s
s1, Bool
False)
   spanMaybe' :: forall s. s -> (s -> [x] -> Maybe s) -> [x] -> ([x], [x], s)
spanMaybe' s
s0 s -> [x] -> Maybe s
f [x]
l = ([x] -> [x]
prefix' [], [x] -> [x]
suffix' [], s
s')
      where ([x] -> [x]
prefix', [x] -> [x]
suffix', s
s', Bool
_) = (([x] -> [x], [x] -> [x], s, Bool)
 -> x -> ([x] -> [x], [x] -> [x], s, Bool))
-> ([x] -> [x], [x] -> [x], s, Bool)
-> [x]
-> ([x] -> [x], [x] -> [x], s, Bool)
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' ([x] -> [x], [x] -> [x], s, Bool)
-> x -> ([x] -> [x], [x] -> [x], s, Bool)
forall {c}.
([x] -> c, [x] -> [x], s, Bool)
-> x -> ([x] -> c, [x] -> [x], s, Bool)
g ([x] -> [x]
forall a. a -> a
id, [x] -> [x]
forall a. a -> a
id, s
s0, Bool
True) [x]
l
            g :: ([x] -> c, [x] -> [x], s, Bool)
-> x -> ([x] -> c, [x] -> [x], s, Bool)
g ([x] -> c
prefix, [x] -> [x]
suffix, s
s1, Bool
live) x
x | Bool
live, Just s
s2 <- s -> [x] -> Maybe s
f s
s1 [x
x] = s
-> ([x] -> c, [x] -> [x], s, Bool)
-> ([x] -> c, [x] -> [x], s, Bool)
forall a b. a -> b -> b
seq s
s2 (([x] -> c, [x] -> [x], s, Bool)
 -> ([x] -> c, [x] -> [x], s, Bool))
-> ([x] -> c, [x] -> [x], s, Bool)
-> ([x] -> c, [x] -> [x], s, Bool)
forall a b. (a -> b) -> a -> b
$ ([x] -> c
prefix ([x] -> c) -> ([x] -> [x]) -> [x] -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x
xx -> [x] -> [x]
forall a. a -> [a] -> [a]
:), [x] -> [x]
forall a. a -> a
id, s
s2, Bool
True)
                                           | Bool
otherwise = ([x] -> c
prefix, [x] -> [x]
suffix ([x] -> [x]) -> ([x] -> [x]) -> [x] -> [x]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x
xx -> [x] -> [x]
forall a. a -> [a] -> [a]
:), s
s1, Bool
False)
   splitAt :: Int -> [x] -> ([x], [x])
splitAt = Int -> [x] -> ([x], [x])
forall x. Int -> [x] -> ([x], [x])
List.splitAt
   drop :: Int -> [x] -> [x]
drop = Int -> [x] -> [x]
forall x. Int -> [x] -> [x]
List.drop
   take :: Int -> [x] -> [x]
take = Int -> [x] -> [x]
forall x. Int -> [x] -> [x]
List.take

instance FactorialMonoid ByteString.ByteString where
   splitPrimePrefix :: ByteString -> Maybe (ByteString, ByteString)
splitPrimePrefix ByteString
x = if ByteString -> Bool
ByteString.null ByteString
x then Maybe (ByteString, ByteString)
forall a. Maybe a
Nothing else (ByteString, ByteString) -> Maybe (ByteString, ByteString)
forall a. a -> Maybe a
Just (Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt Int
1 ByteString
x)
   splitPrimeSuffix :: ByteString -> Maybe (ByteString, ByteString)
splitPrimeSuffix ByteString
x = if ByteString -> Bool
ByteString.null ByteString
x then Maybe (ByteString, ByteString)
forall a. Maybe a
Nothing else (ByteString, ByteString) -> Maybe (ByteString, ByteString)
forall a. a -> Maybe a
Just (Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt (ByteString -> Int
ByteString.length ByteString
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) ByteString
x)
   inits :: ByteString -> [ByteString]
inits = ByteString -> [ByteString]
ByteString.inits
   tails :: ByteString -> [ByteString]
tails = ByteString -> [ByteString]
ByteString.tails
   break :: (ByteString -> Bool) -> ByteString -> (ByteString, ByteString)
break ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> (ByteString, ByteString)
ByteString.break (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton)
   span :: (ByteString -> Bool) -> ByteString -> (ByteString, ByteString)
span ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> (ByteString, ByteString)
ByteString.span (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton)
   spanMaybe :: forall s.
s
-> (s -> ByteString -> Maybe s)
-> ByteString
-> (ByteString, ByteString, s)
spanMaybe s
s0 s -> ByteString -> Maybe s
f ByteString
b = case (Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> ByteString -> (Int, s) -> (Int, s)
forall a. (Word8 -> a -> a) -> a -> ByteString -> a
ByteString.foldr Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g (Int, s) -> (Int, s)
forall a. a -> a
id ByteString
b (Int
0, s
s0)
                      of (Int
i, s
s') | (ByteString
prefix, ByteString
suffix) <- Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt Int
i ByteString
b -> (ByteString
prefix, ByteString
suffix, s
s')
      where g :: Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g Word8
w (Int, s) -> (Int, s)
cont (Int
i, s
s) | Just s
s' <- s -> ByteString -> Maybe s
f s
s (Word8 -> ByteString
ByteString.singleton Word8
w) = let i' :: Int
i' = Int -> Int
forall a. Enum a => a -> a
succ Int
i :: Int in Int -> (Int, s) -> (Int, s)
forall a b. a -> b -> b
seq Int
i' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ (Int, s) -> (Int, s)
cont (Int
i', s
s')
                            | Bool
otherwise = (Int
i, s
s)
   spanMaybe' :: forall s.
s
-> (s -> ByteString -> Maybe s)
-> ByteString
-> (ByteString, ByteString, s)
spanMaybe' s
s0 s -> ByteString -> Maybe s
f ByteString
b = case (Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> ByteString -> (Int, s) -> (Int, s)
forall a. (Word8 -> a -> a) -> a -> ByteString -> a
ByteString.foldr Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g (Int, s) -> (Int, s)
forall a. a -> a
id ByteString
b (Int
0, s
s0)
                       of (Int
i, s
s') | (ByteString
prefix, ByteString
suffix) <- Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt Int
i ByteString
b -> (ByteString
prefix, ByteString
suffix, s
s')
      where g :: Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g Word8
w (Int, s) -> (Int, s)
cont (Int
i, s
s) | Just s
s' <- s -> ByteString -> Maybe s
f s
s (Word8 -> ByteString
ByteString.singleton Word8
w) = let i' :: Int
i' = Int -> Int
forall a. Enum a => a -> a
succ Int
i :: Int in Int -> (Int, s) -> (Int, s)
forall a b. a -> b -> b
seq Int
i' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ s -> (Int, s) -> (Int, s)
forall a b. a -> b -> b
seq s
s' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ (Int, s) -> (Int, s)
cont (Int
i', s
s')
                            | Bool
otherwise = (Int
i, s
s)
   dropWhile :: (ByteString -> Bool) -> ByteString -> ByteString
dropWhile ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> ByteString
ByteString.dropWhile (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton)
   takeWhile :: (ByteString -> Bool) -> ByteString -> ByteString
takeWhile ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> ByteString
ByteString.takeWhile (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton)
   split :: (ByteString -> Bool) -> ByteString -> [ByteString]
split ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> [ByteString]
ByteString.splitWith Word8 -> Bool
f'
      where f' :: Word8 -> Bool
f' = ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton
   splitAt :: Int -> ByteString -> (ByteString, ByteString)
splitAt = Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt
   drop :: Int -> ByteString -> ByteString
drop = Int -> ByteString -> ByteString
ByteString.drop
   take :: Int -> ByteString -> ByteString
take = Int -> ByteString -> ByteString
ByteString.take

instance FactorialMonoid LazyByteString.ByteString where
   splitPrimePrefix :: ByteString -> Maybe (ByteString, ByteString)
splitPrimePrefix ByteString
x = if ByteString -> Bool
LazyByteString.null ByteString
x then Maybe (ByteString, ByteString)
forall a. Maybe a
Nothing
                        else (ByteString, ByteString) -> Maybe (ByteString, ByteString)
forall a. a -> Maybe a
Just (Int64 -> ByteString -> (ByteString, ByteString)
LazyByteString.splitAt Int64
1 ByteString
x)
   splitPrimeSuffix :: ByteString -> Maybe (ByteString, ByteString)
splitPrimeSuffix ByteString
x = if ByteString -> Bool
LazyByteString.null ByteString
x then Maybe (ByteString, ByteString)
forall a. Maybe a
Nothing
                        else (ByteString, ByteString) -> Maybe (ByteString, ByteString)
forall a. a -> Maybe a
Just (Int64 -> ByteString -> (ByteString, ByteString)
LazyByteString.splitAt (ByteString -> Int64
LazyByteString.length ByteString
x Int64 -> Int64 -> Int64
forall a. Num a => a -> a -> a
- Int64
1) ByteString
x)
   inits :: ByteString -> [ByteString]
inits = ByteString -> [ByteString]
LazyByteString.inits
   tails :: ByteString -> [ByteString]
tails = ByteString -> [ByteString]
LazyByteString.tails
   break :: (ByteString -> Bool) -> ByteString -> (ByteString, ByteString)
break ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> (ByteString, ByteString)
LazyByteString.break (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
LazyByteString.singleton)
   span :: (ByteString -> Bool) -> ByteString -> (ByteString, ByteString)
span ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> (ByteString, ByteString)
LazyByteString.span (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
LazyByteString.singleton)
   spanMaybe :: forall s.
s
-> (s -> ByteString -> Maybe s)
-> ByteString
-> (ByteString, ByteString, s)
spanMaybe s
s0 s -> ByteString -> Maybe s
f ByteString
b = case (Word8 -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s))
-> ((Int64, s) -> (Int64, s))
-> ByteString
-> (Int64, s)
-> (Int64, s)
forall a. (Word8 -> a -> a) -> a -> ByteString -> a
LazyByteString.foldr Word8 -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g (Int64, s) -> (Int64, s)
forall a. a -> a
id ByteString
b (Int64
0, s
s0)
                      of (Int64
i, s
s') | (ByteString
prefix, ByteString
suffix) <- Int64 -> ByteString -> (ByteString, ByteString)
LazyByteString.splitAt Int64
i ByteString
b -> (ByteString
prefix, ByteString
suffix, s
s')
      where g :: Word8 -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g Word8
w (Int64, s) -> (Int64, s)
cont (Int64
i, s
s) | Just s
s' <- s -> ByteString -> Maybe s
f s
s (Word8 -> ByteString
LazyByteString.singleton Word8
w) = let i' :: Int64
i' = Int64 -> Int64
forall a. Enum a => a -> a
succ Int64
i :: Int64 in Int64 -> (Int64, s) -> (Int64, s)
forall a b. a -> b -> b
seq Int64
i' ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
forall a b. (a -> b) -> a -> b
$ (Int64, s) -> (Int64, s)
cont (Int64
i', s
s')
                            | Bool
otherwise = (Int64
i, s
s)
   spanMaybe' :: forall s.
s
-> (s -> ByteString -> Maybe s)
-> ByteString
-> (ByteString, ByteString, s)
spanMaybe' s
s0 s -> ByteString -> Maybe s
f ByteString
b = case (Word8 -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s))
-> ((Int64, s) -> (Int64, s))
-> ByteString
-> (Int64, s)
-> (Int64, s)
forall a. (Word8 -> a -> a) -> a -> ByteString -> a
LazyByteString.foldr Word8 -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g (Int64, s) -> (Int64, s)
forall a. a -> a
id ByteString
b (Int64
0, s
s0)
                       of (Int64
i, s
s') | (ByteString
prefix, ByteString
suffix) <- Int64 -> ByteString -> (ByteString, ByteString)
LazyByteString.splitAt Int64
i ByteString
b -> (ByteString
prefix, ByteString
suffix, s
s')
      where g :: Word8 -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g Word8
w (Int64, s) -> (Int64, s)
cont (Int64
i, s
s)
              | Just s
s' <- s -> ByteString -> Maybe s
f s
s (Word8 -> ByteString
LazyByteString.singleton Word8
w) = let i' :: Int64
i' = Int64 -> Int64
forall a. Enum a => a -> a
succ Int64
i :: Int64 in Int64 -> (Int64, s) -> (Int64, s)
forall a b. a -> b -> b
seq Int64
i' ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
forall a b. (a -> b) -> a -> b
$ s -> (Int64, s) -> (Int64, s)
forall a b. a -> b -> b
seq s
s' ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
forall a b. (a -> b) -> a -> b
$ (Int64, s) -> (Int64, s)
cont (Int64
i', s
s')
              | Bool
otherwise = (Int64
i, s
s)
   dropWhile :: (ByteString -> Bool) -> ByteString -> ByteString
dropWhile ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> ByteString
LazyByteString.dropWhile (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
LazyByteString.singleton)
   takeWhile :: (ByteString -> Bool) -> ByteString -> ByteString
takeWhile ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> ByteString
LazyByteString.takeWhile (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
LazyByteString.singleton)
   split :: (ByteString -> Bool) -> ByteString -> [ByteString]
split ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> [ByteString]
LazyByteString.splitWith Word8 -> Bool
f'
      where f' :: Word8 -> Bool
f' = ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
LazyByteString.singleton
   splitAt :: Int -> ByteString -> (ByteString, ByteString)
splitAt = Int64 -> ByteString -> (ByteString, ByteString)
LazyByteString.splitAt (Int64 -> ByteString -> (ByteString, ByteString))
-> (Int -> Int64) -> Int -> ByteString -> (ByteString, ByteString)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral
   drop :: Int -> ByteString -> ByteString
drop Int
n = Int64 -> ByteString -> ByteString
LazyByteString.drop (Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n)
   take :: Int -> ByteString -> ByteString
take Int
n = Int64 -> ByteString -> ByteString
LazyByteString.take (Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n)

instance FactorialMonoid Text.Text where
   splitPrimePrefix :: Text -> Maybe (Text, Text)
splitPrimePrefix = ((Char, Text) -> (Text, Text))
-> Maybe (Char, Text) -> Maybe (Text, Text)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Char -> Text) -> (Char, Text) -> (Text, Text)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Char -> Text
Text.singleton) (Maybe (Char, Text) -> Maybe (Text, Text))
-> (Text -> Maybe (Char, Text)) -> Text -> Maybe (Text, Text)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Maybe (Char, Text)
Text.uncons
   splitPrimeSuffix :: Text -> Maybe (Text, Text)
splitPrimeSuffix Text
x = if Text -> Bool
Text.null Text
x then Maybe (Text, Text)
forall a. Maybe a
Nothing else (Text, Text) -> Maybe (Text, Text)
forall a. a -> Maybe a
Just (HasCallStack => Text -> Text
Text -> Text
Text.init Text
x, Char -> Text
Text.singleton (HasCallStack => Text -> Char
Text -> Char
Text.last Text
x))
   inits :: Text -> [Text]
inits = Text -> [Text]
Text.inits
   tails :: Text -> [Text]
tails = Text -> [Text]
Text.tails
   span :: (Text -> Bool) -> Text -> (Text, Text)
span Text -> Bool
f = (Char -> Bool) -> Text -> (Text, Text)
Text.span (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
Text.singleton)
   break :: (Text -> Bool) -> Text -> (Text, Text)
break Text -> Bool
f = (Char -> Bool) -> Text -> (Text, Text)
Text.break (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
Text.singleton)
   dropWhile :: (Text -> Bool) -> Text -> Text
dropWhile Text -> Bool
f = (Char -> Bool) -> Text -> Text
Text.dropWhile (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
Text.singleton)
   takeWhile :: (Text -> Bool) -> Text -> Text
takeWhile Text -> Bool
f = (Char -> Bool) -> Text -> Text
Text.takeWhile (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
Text.singleton)
   spanMaybe :: forall s. s -> (s -> Text -> Maybe s) -> Text -> (Text, Text, s)
spanMaybe s
s0 s -> Text -> Maybe s
f Text
t = case (Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> Text -> (Int, s) -> (Int, s)
forall a. (Char -> a -> a) -> a -> Text -> a
Text.foldr Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g (Int, s) -> (Int, s)
forall a. a -> a
id Text
t (Int
0, s
s0)
                      of (Int
i, s
s') | (Text
prefix, Text
suffix) <- Int -> Text -> (Text, Text)
Text.splitAt Int
i Text
t -> (Text
prefix, Text
suffix, s
s')
      where g :: Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g Char
c (Int, s) -> (Int, s)
cont (Int
i, s
s) | Just s
s' <- s -> Text -> Maybe s
f s
s (Char -> Text
Text.singleton Char
c) = let i' :: Int
i' = Int -> Int
forall a. Enum a => a -> a
succ Int
i :: Int in Int -> (Int, s) -> (Int, s)
forall a b. a -> b -> b
seq Int
i' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ (Int, s) -> (Int, s)
cont (Int
i', s
s')
                            | Bool
otherwise = (Int
i, s
s)
   spanMaybe' :: forall s. s -> (s -> Text -> Maybe s) -> Text -> (Text, Text, s)
spanMaybe' s
s0 s -> Text -> Maybe s
f Text
t = case (Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> Text -> (Int, s) -> (Int, s)
forall a. (Char -> a -> a) -> a -> Text -> a
Text.foldr Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g (Int, s) -> (Int, s)
forall a. a -> a
id Text
t (Int
0, s
s0)
                       of (Int
i, s
s') | (Text
prefix, Text
suffix) <- Int -> Text -> (Text, Text)
Text.splitAt Int
i Text
t -> (Text
prefix, Text
suffix, s
s')
      where g :: Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g Char
c (Int, s) -> (Int, s)
cont (Int
i, s
s) | Just s
s' <- s -> Text -> Maybe s
f s
s (Char -> Text
Text.singleton Char
c) = let i' :: Int
i' = Int -> Int
forall a. Enum a => a -> a
succ Int
i :: Int in Int -> (Int, s) -> (Int, s)
forall a b. a -> b -> b
seq Int
i' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ s -> (Int, s) -> (Int, s)
forall a b. a -> b -> b
seq s
s' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ (Int, s) -> (Int, s)
cont (Int
i', s
s')
                            | Bool
otherwise = (Int
i, s
s)
   split :: (Text -> Bool) -> Text -> [Text]
split Text -> Bool
f = (Char -> Bool) -> Text -> [Text]
Text.split Char -> Bool
f'
      where f' :: Char -> Bool
f' = Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
Text.singleton
   splitAt :: Int -> Text -> (Text, Text)
splitAt = Int -> Text -> (Text, Text)
Text.splitAt
   drop :: Int -> Text -> Text
drop = Int -> Text -> Text
Text.drop
   take :: Int -> Text -> Text
take = Int -> Text -> Text
Text.take

instance FactorialMonoid LazyText.Text where
   splitPrimePrefix :: Text -> Maybe (Text, Text)
splitPrimePrefix = ((Char, Text) -> (Text, Text))
-> Maybe (Char, Text) -> Maybe (Text, Text)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Char -> Text) -> (Char, Text) -> (Text, Text)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Char -> Text
LazyText.singleton) (Maybe (Char, Text) -> Maybe (Text, Text))
-> (Text -> Maybe (Char, Text)) -> Text -> Maybe (Text, Text)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Maybe (Char, Text)
LazyText.uncons
   splitPrimeSuffix :: Text -> Maybe (Text, Text)
splitPrimeSuffix Text
x = if Text -> Bool
LazyText.null Text
x
                        then Maybe (Text, Text)
forall a. Maybe a
Nothing
                        else (Text, Text) -> Maybe (Text, Text)
forall a. a -> Maybe a
Just (HasCallStack => Text -> Text
Text -> Text
LazyText.init Text
x, Char -> Text
LazyText.singleton (HasCallStack => Text -> Char
Text -> Char
LazyText.last Text
x))
   inits :: Text -> [Text]
inits = Text -> [Text]
LazyText.inits
   tails :: Text -> [Text]
tails = Text -> [Text]
LazyText.tails
   span :: (Text -> Bool) -> Text -> (Text, Text)
span Text -> Bool
f = (Char -> Bool) -> Text -> (Text, Text)
LazyText.span (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
LazyText.singleton)
   break :: (Text -> Bool) -> Text -> (Text, Text)
break Text -> Bool
f = (Char -> Bool) -> Text -> (Text, Text)
LazyText.break (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
LazyText.singleton)
   dropWhile :: (Text -> Bool) -> Text -> Text
dropWhile Text -> Bool
f = (Char -> Bool) -> Text -> Text
LazyText.dropWhile (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
LazyText.singleton)
   takeWhile :: (Text -> Bool) -> Text -> Text
takeWhile Text -> Bool
f = (Char -> Bool) -> Text -> Text
LazyText.takeWhile (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
LazyText.singleton)
   spanMaybe :: forall s. s -> (s -> Text -> Maybe s) -> Text -> (Text, Text, s)
spanMaybe s
s0 s -> Text -> Maybe s
f Text
t = case (Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s))
-> ((Int64, s) -> (Int64, s)) -> Text -> (Int64, s) -> (Int64, s)
forall a. (Char -> a -> a) -> a -> Text -> a
LazyText.foldr Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g (Int64, s) -> (Int64, s)
forall a. a -> a
id Text
t (Int64
0, s
s0)
                      of (Int64
i, s
s') | (Text
prefix, Text
suffix) <- Int64 -> Text -> (Text, Text)
LazyText.splitAt Int64
i Text
t -> (Text
prefix, Text
suffix, s
s')
      where g :: Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g Char
c (Int64, s) -> (Int64, s)
cont (Int64
i, s
s) | Just s
s' <- s -> Text -> Maybe s
f s
s (Char -> Text
LazyText.singleton Char
c) = let i' :: Int64
i' = Int64 -> Int64
forall a. Enum a => a -> a
succ Int64
i :: Int64 in Int64 -> (Int64, s) -> (Int64, s)
forall a b. a -> b -> b
seq Int64
i' ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
forall a b. (a -> b) -> a -> b
$ (Int64, s) -> (Int64, s)
cont (Int64
i', s
s')
                            | Bool
otherwise = (Int64
i, s
s)
   spanMaybe' :: forall s. s -> (s -> Text -> Maybe s) -> Text -> (Text, Text, s)
spanMaybe' s
s0 s -> Text -> Maybe s
f Text
t = case (Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s))
-> ((Int64, s) -> (Int64, s)) -> Text -> (Int64, s) -> (Int64, s)
forall a. (Char -> a -> a) -> a -> Text -> a
LazyText.foldr Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g (Int64, s) -> (Int64, s)
forall a. a -> a
id Text
t (Int64
0, s
s0)
                       of (Int64
i, s
s') | (Text
prefix, Text
suffix) <- Int64 -> Text -> (Text, Text)
LazyText.splitAt Int64
i Text
t -> (Text
prefix, Text
suffix, s
s')
      where g :: Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g Char
c (Int64, s) -> (Int64, s)
cont (Int64
i, s
s) | Just s
s' <- s -> Text -> Maybe s
f s
s (Char -> Text
LazyText.singleton Char
c) = let i' :: Int64
i' = Int64 -> Int64
forall a. Enum a => a -> a
succ Int64
i :: Int64 in Int64 -> (Int64, s) -> (Int64, s)
forall a b. a -> b -> b
seq Int64
i' ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
forall a b. (a -> b) -> a -> b
$ s -> (Int64, s) -> (Int64, s)
forall a b. a -> b -> b
seq s
s' ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
forall a b. (a -> b) -> a -> b
$ (Int64, s) -> (Int64, s)
cont (Int64
i', s
s')
                            | Bool
otherwise = (Int64
i, s
s)
   split :: (Text -> Bool) -> Text -> [Text]
split Text -> Bool
f = (Char -> Bool) -> Text -> [Text]
LazyText.split Char -> Bool
f'
      where f' :: Char -> Bool
f' = Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
LazyText.singleton
   splitAt :: Int -> Text -> (Text, Text)
splitAt = Int64 -> Text -> (Text, Text)
LazyText.splitAt (Int64 -> Text -> (Text, Text))
-> (Int -> Int64) -> Int -> Text -> (Text, Text)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral
   drop :: Int -> Text -> Text
drop Int
n = Int64 -> Text -> Text
LazyText.drop (Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n)
   take :: Int -> Text -> Text
take Int
n = Int64 -> Text -> Text
LazyText.take (Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n)

instance Ord k => FactorialMonoid (Map.Map k v) where
   splitPrimePrefix :: Map k v -> Maybe (Map k v, Map k v)
splitPrimePrefix = (((k, v), Map k v) -> (Map k v, Map k v))
-> Maybe ((k, v), Map k v) -> Maybe (Map k v, Map k v)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k, v), Map k v) -> (Map k v, Map k v)
forall {k} {a} {b}. ((k, a), b) -> (Map k a, b)
singularize (Maybe ((k, v), Map k v) -> Maybe (Map k v, Map k v))
-> (Map k v -> Maybe ((k, v), Map k v))
-> Map k v
-> Maybe (Map k v, Map k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k v -> Maybe ((k, v), Map k v)
forall k a. Map k a -> Maybe ((k, a), Map k a)
Map.minViewWithKey
      where singularize :: ((k, a), b) -> (Map k a, b)
singularize ((k
k, a
v), b
rest) = (k -> a -> Map k a
forall k a. k -> a -> Map k a
Map.singleton k
k a
v, b
rest)
   splitPrimeSuffix :: Map k v -> Maybe (Map k v, Map k v)
splitPrimeSuffix = (((k, v), Map k v) -> (Map k v, Map k v))
-> Maybe ((k, v), Map k v) -> Maybe (Map k v, Map k v)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k, v), Map k v) -> (Map k v, Map k v)
forall {k} {a} {a}. ((k, a), a) -> (a, Map k a)
singularize (Maybe ((k, v), Map k v) -> Maybe (Map k v, Map k v))
-> (Map k v -> Maybe ((k, v), Map k v))
-> Map k v
-> Maybe (Map k v, Map k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k v -> Maybe ((k, v), Map k v)
forall k a. Map k a -> Maybe ((k, a), Map k a)
Map.maxViewWithKey
      where singularize :: ((k, a), a) -> (a, Map k a)
singularize ((k
k, a
v), a
rest) = (a
rest, k -> a -> Map k a
forall k a. k -> a -> Map k a
Map.singleton k
k a
v)

instance FactorialMonoid (IntMap.IntMap a) where
   splitPrimePrefix :: IntMap a -> Maybe (IntMap a, IntMap a)
splitPrimePrefix = (((Int, a), IntMap a) -> (IntMap a, IntMap a))
-> Maybe ((Int, a), IntMap a) -> Maybe (IntMap a, IntMap a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Int, a), IntMap a) -> (IntMap a, IntMap a)
forall {a} {b}. ((Int, a), b) -> (IntMap a, b)
singularize (Maybe ((Int, a), IntMap a) -> Maybe (IntMap a, IntMap a))
-> (IntMap a -> Maybe ((Int, a), IntMap a))
-> IntMap a
-> Maybe (IntMap a, IntMap a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap a -> Maybe ((Int, a), IntMap a)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IntMap.minViewWithKey
      where singularize :: ((Int, a), b) -> (IntMap a, b)
singularize ((Int
k, a
v), b
rest) = (Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v, b
rest)
   splitPrimeSuffix :: IntMap a -> Maybe (IntMap a, IntMap a)
splitPrimeSuffix = (((Int, a), IntMap a) -> (IntMap a, IntMap a))
-> Maybe ((Int, a), IntMap a) -> Maybe (IntMap a, IntMap a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Int, a), IntMap a) -> (IntMap a, IntMap a)
forall {a} {a}. ((Int, a), a) -> (a, IntMap a)
singularize (Maybe ((Int, a), IntMap a) -> Maybe (IntMap a, IntMap a))
-> (IntMap a -> Maybe ((Int, a), IntMap a))
-> IntMap a
-> Maybe (IntMap a, IntMap a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap a -> Maybe ((Int, a), IntMap a)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IntMap.maxViewWithKey
      where singularize :: ((Int, a), a) -> (a, IntMap a)
singularize ((Int
k, a
v), a
rest) = (a
rest, Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v)

instance FactorialMonoid IntSet.IntSet where
   splitPrimePrefix :: IntSet -> Maybe (IntSet, IntSet)
splitPrimePrefix = ((Int, IntSet) -> (IntSet, IntSet))
-> Maybe (Int, IntSet) -> Maybe (IntSet, IntSet)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int, IntSet) -> (IntSet, IntSet)
forall {b}. (Int, b) -> (IntSet, b)
singularize (Maybe (Int, IntSet) -> Maybe (IntSet, IntSet))
-> (IntSet -> Maybe (Int, IntSet))
-> IntSet
-> Maybe (IntSet, IntSet)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> Maybe (Int, IntSet)
IntSet.minView
      where singularize :: (Int, b) -> (IntSet, b)
singularize (Int
min, b
rest) = (Int -> IntSet
IntSet.singleton Int
min, b
rest)
   splitPrimeSuffix :: IntSet -> Maybe (IntSet, IntSet)
splitPrimeSuffix = ((Int, IntSet) -> (IntSet, IntSet))
-> Maybe (Int, IntSet) -> Maybe (IntSet, IntSet)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int, IntSet) -> (IntSet, IntSet)
forall {a}. (Int, a) -> (a, IntSet)
singularize (Maybe (Int, IntSet) -> Maybe (IntSet, IntSet))
-> (IntSet -> Maybe (Int, IntSet))
-> IntSet
-> Maybe (IntSet, IntSet)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> Maybe (Int, IntSet)
IntSet.maxView
      where singularize :: (Int, a) -> (a, IntSet)
singularize (Int
max, a
rest) = (a
rest, Int -> IntSet
IntSet.singleton Int
max)

instance FactorialMonoid (Sequence.Seq a) where
   splitPrimePrefix :: Seq a -> Maybe (Seq a, Seq a)
splitPrimePrefix Seq a
q = case Seq a -> ViewL a
forall a. Seq a -> ViewL a
Sequence.viewl Seq a
q
                        of ViewL a
Sequence.EmptyL -> Maybe (Seq a, Seq a)
forall a. Maybe a
Nothing
                           a
hd Sequence.:< Seq a
rest -> (Seq a, Seq a) -> Maybe (Seq a, Seq a)
forall a. a -> Maybe a
Just (a -> Seq a
forall a. a -> Seq a
Sequence.singleton a
hd, Seq a
rest)
   splitPrimeSuffix :: Seq a -> Maybe (Seq a, Seq a)
splitPrimeSuffix Seq a
q = case Seq a -> ViewR a
forall a. Seq a -> ViewR a
Sequence.viewr Seq a
q
                        of ViewR a
Sequence.EmptyR -> Maybe (Seq a, Seq a)
forall a. Maybe a
Nothing
                           Seq a
rest Sequence.:> a
last -> (Seq a, Seq a) -> Maybe (Seq a, Seq a)
forall a. a -> Maybe a
Just (Seq a
rest, a -> Seq a
forall a. a -> Seq a
Sequence.singleton a
last)
   inits :: Seq a -> [Seq a]
inits = Seq (Seq a) -> [Seq a]
forall a. Seq a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
Foldable.toList (Seq (Seq a) -> [Seq a])
-> (Seq a -> Seq (Seq a)) -> Seq a -> [Seq a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Seq a -> Seq (Seq a)
forall a. Seq a -> Seq (Seq a)
Sequence.inits
   tails :: Seq a -> [Seq a]
tails = Seq (Seq a) -> [Seq a]
forall a. Seq a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
Foldable.toList (Seq (Seq a) -> [Seq a])
-> (Seq a -> Seq (Seq a)) -> Seq a -> [Seq a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Seq a -> Seq (Seq a)
forall a. Seq a -> Seq (Seq a)
Sequence.tails
   span :: (Seq a -> Bool) -> Seq a -> (Seq a, Seq a)
span Seq a -> Bool
f = (a -> Bool) -> Seq a -> (Seq a, Seq a)
forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
Sequence.spanl (Seq a -> Bool
f (Seq a -> Bool) -> (a -> Seq a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Seq a
forall a. a -> Seq a
Sequence.singleton)
   break :: (Seq a -> Bool) -> Seq a -> (Seq a, Seq a)
break Seq a -> Bool
f = (a -> Bool) -> Seq a -> (Seq a, Seq a)
forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
Sequence.breakl (Seq a -> Bool
f (Seq a -> Bool) -> (a -> Seq a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Seq a
forall a. a -> Seq a
Sequence.singleton)
   dropWhile :: (Seq a -> Bool) -> Seq a -> Seq a
dropWhile Seq a -> Bool
f = (a -> Bool) -> Seq a -> Seq a
forall a. (a -> Bool) -> Seq a -> Seq a
Sequence.dropWhileL (Seq a -> Bool
f (Seq a -> Bool) -> (a -> Seq a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Seq a
forall a. a -> Seq a
Sequence.singleton)
   takeWhile :: (Seq a -> Bool) -> Seq a -> Seq a
takeWhile Seq a -> Bool
f = (a -> Bool) -> Seq a -> Seq a
forall a. (a -> Bool) -> Seq a -> Seq a
Sequence.takeWhileL (Seq a -> Bool
f (Seq a -> Bool) -> (a -> Seq a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Seq a
forall a. a -> Seq a
Sequence.singleton)
   spanMaybe :: forall s.
s -> (s -> Seq a -> Maybe s) -> Seq a -> (Seq a, Seq a, s)
spanMaybe s
s0 s -> Seq a -> Maybe s
f Seq a
b = case (a -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> Seq a -> (Int, s) -> (Int, s)
forall a b. (a -> b -> b) -> b -> Seq a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr a -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g (Int, s) -> (Int, s)
forall a. a -> a
id Seq a
b (Int
0, s
s0)
                      of (Int
i, s
s') | (Seq a
prefix, Seq a
suffix) <- Int -> Seq a -> (Seq a, Seq a)
forall a. Int -> Seq a -> (Seq a, Seq a)
Sequence.splitAt Int
i Seq a
b -> (Seq a
prefix, Seq a
suffix, s
s')
      where g :: a -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g a
x (Int, s) -> (Int, s)
cont (Int
i, s
s) | Just s
s' <- s -> Seq a -> Maybe s
f s
s (a -> Seq a
forall a. a -> Seq a
Sequence.singleton a
x) = let i' :: Int
i' = Int -> Int
forall a. Enum a => a -> a
succ Int
i :: Int in Int -> (Int, s) -> (Int, s)
forall a b. a -> b -> b
seq Int
i' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ (Int, s) -> (Int, s)
cont (Int
i', s
s')
                            | Bool
otherwise = (Int
i, s
s)
   spanMaybe' :: forall s.
s -> (s -> Seq a -> Maybe s) -> Seq a -> (Seq a, Seq a, s)
spanMaybe' s
s0 s -> Seq a -> Maybe s
f Seq a
b = case (a -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> Seq a -> (Int, s) -> (Int, s)
forall a b. (a -> b -> b) -> b -> Seq a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr a -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g (Int, s) -> (Int, s)
forall a. a -> a
id Seq a
b (Int
0, s
s0)
                       of (Int
i, s
s') | (Seq a
prefix, Seq a
suffix) <- Int -> Seq a -> (Seq a, Seq a)
forall a. Int -> Seq a -> (Seq a, Seq a)
Sequence.splitAt Int
i Seq a
b -> (Seq a
prefix, Seq a
suffix, s
s')
      where g :: a -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g a
x (Int, s) -> (Int, s)
cont (Int
i, s
s) | Just s
s' <- s -> Seq a -> Maybe s
f s
s (a -> Seq a
forall a. a -> Seq a
Sequence.singleton a
x) = let i' :: Int
i' = Int -> Int
forall a. Enum a => a -> a
succ Int
i :: Int in Int -> (Int, s) -> (Int, s)
forall a b. a -> b -> b
seq Int
i' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ s -> (Int, s) -> (Int, s)
forall a b. a -> b -> b
seq s
s' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ (Int, s) -> (Int, s)
cont (Int
i', s
s')
                            | Bool
otherwise = (Int
i, s
s)
   splitAt :: Int -> Seq a -> (Seq a, Seq a)
splitAt = Int -> Seq a -> (Seq a, Seq a)
forall a. Int -> Seq a -> (Seq a, Seq a)
Sequence.splitAt
   drop :: Int -> Seq a -> Seq a
drop = Int -> Seq a -> Seq a
forall a. Int -> Seq a -> Seq a
Sequence.drop
   take :: Int -> Seq a -> Seq a
take = Int -> Seq a -> Seq a
forall a. Int -> Seq a -> Seq a
Sequence.take

instance Ord a => FactorialMonoid (Set.Set a) where
   splitPrimePrefix :: Set a -> Maybe (Set a, Set a)
splitPrimePrefix = ((a, Set a) -> (Set a, Set a))
-> Maybe (a, Set a) -> Maybe (Set a, Set a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, Set a) -> (Set a, Set a)
forall {a} {b}. (a, b) -> (Set a, b)
singularize (Maybe (a, Set a) -> Maybe (Set a, Set a))
-> (Set a -> Maybe (a, Set a)) -> Set a -> Maybe (Set a, Set a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> Maybe (a, Set a)
forall a. Set a -> Maybe (a, Set a)
Set.minView
      where singularize :: (a, b) -> (Set a, b)
singularize (a
min, b
rest) = (a -> Set a
forall a. a -> Set a
Set.singleton a
min, b
rest)
   splitPrimeSuffix :: Set a -> Maybe (Set a, Set a)
splitPrimeSuffix = ((a, Set a) -> (Set a, Set a))
-> Maybe (a, Set a) -> Maybe (Set a, Set a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, Set a) -> (Set a, Set a)
forall {a} {a}. (a, a) -> (a, Set a)
singularize (Maybe (a, Set a) -> Maybe (Set a, Set a))
-> (Set a -> Maybe (a, Set a)) -> Set a -> Maybe (Set a, Set a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> Maybe (a, Set a)
forall a. Set a -> Maybe (a, Set a)
Set.maxView
      where singularize :: (a, a) -> (a, Set a)
singularize (a
max, a
rest) = (a
rest, a -> Set a
forall a. a -> Set a
Set.singleton a
max)

instance FactorialMonoid (Vector.Vector a) where
   splitPrimePrefix :: Vector a -> Maybe (Vector a, Vector a)
splitPrimePrefix Vector a
x = if Vector a -> Bool
forall a. Vector a -> Bool
Vector.null Vector a
x then Maybe (Vector a, Vector a)
forall a. Maybe a
Nothing else (Vector a, Vector a) -> Maybe (Vector a, Vector a)
forall a. a -> Maybe a
Just (Int -> Vector a -> (Vector a, Vector a)
forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt Int
1 Vector a
x)
   splitPrimeSuffix :: Vector a -> Maybe (Vector a, Vector a)
splitPrimeSuffix Vector a
x = if Vector a -> Bool
forall a. Vector a -> Bool
Vector.null Vector a
x then Maybe (Vector a, Vector a)
forall a. Maybe a
Nothing else (Vector a, Vector a) -> Maybe (Vector a, Vector a)
forall a. a -> Maybe a
Just (Int -> Vector a -> (Vector a, Vector a)
forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt (Vector a -> Int
forall a. Vector a -> Int
Vector.length Vector a
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Vector a
x)
   inits :: Vector a -> [Vector a]
inits Vector a
x0 = Vector a -> [Vector a] -> [Vector a]
forall {a}. Vector a -> [Vector a] -> [Vector a]
initsWith Vector a
x0 []
      where initsWith :: Vector a -> [Vector a] -> [Vector a]
initsWith Vector a
x [Vector a]
rest | Vector a -> Bool
forall a. Vector a -> Bool
Vector.null Vector a
x = Vector a
xVector a -> [Vector a] -> [Vector a]
forall a. a -> [a] -> [a]
:[Vector a]
rest
                             | Bool
otherwise = Vector a -> [Vector a] -> [Vector a]
initsWith (Vector a -> Vector a
forall a. Vector a -> Vector a
Vector.unsafeInit Vector a
x) (Vector a
xVector a -> [Vector a] -> [Vector a]
forall a. a -> [a] -> [a]
:[Vector a]
rest)
   tails :: Vector a -> [Vector a]
tails Vector a
x = Vector a
x Vector a -> [Vector a] -> [Vector a]
forall a. a -> [a] -> [a]
: if Vector a -> Bool
forall a. Vector a -> Bool
Vector.null Vector a
x then [] else Vector a -> [Vector a]
forall m. FactorialMonoid m => m -> [m]
tails (Vector a -> Vector a
forall a. Vector a -> Vector a
Vector.unsafeTail Vector a
x)
   break :: (Vector a -> Bool) -> Vector a -> (Vector a, Vector a)
break Vector a -> Bool
f = (a -> Bool) -> Vector a -> (Vector a, Vector a)
forall a. (a -> Bool) -> Vector a -> (Vector a, Vector a)
Vector.break (Vector a -> Bool
f (Vector a -> Bool) -> (a -> Vector a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Vector a
forall a. a -> Vector a
Vector.singleton)
   span :: (Vector a -> Bool) -> Vector a -> (Vector a, Vector a)
span Vector a -> Bool
f = (a -> Bool) -> Vector a -> (Vector a, Vector a)
forall a. (a -> Bool) -> Vector a -> (Vector a, Vector a)
Vector.span (Vector a -> Bool
f (Vector a -> Bool) -> (a -> Vector a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Vector a
forall a. a -> Vector a
Vector.singleton)
   dropWhile :: (Vector a -> Bool) -> Vector a -> Vector a
dropWhile Vector a -> Bool
f = (a -> Bool) -> Vector a -> Vector a
forall a. (a -> Bool) -> Vector a -> Vector a
Vector.dropWhile (Vector a -> Bool
f (Vector a -> Bool) -> (a -> Vector a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Vector a
forall a. a -> Vector a
Vector.singleton)
   takeWhile :: (Vector a -> Bool) -> Vector a -> Vector a
takeWhile Vector a -> Bool
f = (a -> Bool) -> Vector a -> Vector a
forall a. (a -> Bool) -> Vector a -> Vector a
Vector.takeWhile (Vector a -> Bool
f (Vector a -> Bool) -> (a -> Vector a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Vector a
forall a. a -> Vector a
Vector.singleton)
   spanMaybe :: forall s.
s
-> (s -> Vector a -> Maybe s)
-> Vector a
-> (Vector a, Vector a, s)
spanMaybe s
s0 s -> Vector a -> Maybe s
f Vector a
v = case (Int -> a -> (s -> Either s (Int, s)) -> s -> Either s (Int, s))
-> (s -> Either s (Int, s)) -> Vector a -> s -> Either s (Int, s)
forall a b. (Int -> a -> b -> b) -> b -> Vector a -> b
Vector.ifoldr Int -> a -> (s -> Either s (Int, s)) -> s -> Either s (Int, s)
forall {a} {a}.
a -> a -> (s -> Either a (a, s)) -> s -> Either a (a, s)
g s -> Either s (Int, s)
forall a b. a -> Either a b
Left Vector a
v s
s0
                      of Left s
s' -> (Vector a
v, Vector a
forall a. Vector a
Vector.empty, s
s')
                         Right (Int
i, s
s') | (Vector a
prefix, Vector a
suffix) <- Int -> Vector a -> (Vector a, Vector a)
forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt Int
i Vector a
v -> (Vector a
prefix, Vector a
suffix, s
s')
      where g :: a -> a -> (s -> Either a (a, s)) -> s -> Either a (a, s)
g a
i a
x s -> Either a (a, s)
cont s
s | Just s
s' <- s -> Vector a -> Maybe s
f s
s (a -> Vector a
forall a. a -> Vector a
Vector.singleton a
x) = s -> Either a (a, s)
cont s
s'
                         | Bool
otherwise = (a, s) -> Either a (a, s)
forall a b. b -> Either a b
Right (a
i, s
s)
   spanMaybe' :: forall s.
s
-> (s -> Vector a -> Maybe s)
-> Vector a
-> (Vector a, Vector a, s)
spanMaybe' s
s0 s -> Vector a -> Maybe s
f Vector a
v = case (Int -> a -> (s -> Either s (Int, s)) -> s -> Either s (Int, s))
-> (s -> Either s (Int, s)) -> Vector a -> s -> Either s (Int, s)
forall a b. (Int -> a -> b -> b) -> b -> Vector a -> b
Vector.ifoldr' Int -> a -> (s -> Either s (Int, s)) -> s -> Either s (Int, s)
forall {a} {a}.
a -> a -> (s -> Either a (a, s)) -> s -> Either a (a, s)
g s -> Either s (Int, s)
forall a b. a -> Either a b
Left Vector a
v s
s0
                       of Left s
s' -> (Vector a
v, Vector a
forall a. Vector a
Vector.empty, s
s')
                          Right (Int
i, s
s') | (Vector a
prefix, Vector a
suffix) <- Int -> Vector a -> (Vector a, Vector a)
forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt Int
i Vector a
v -> (Vector a
prefix, Vector a
suffix, s
s')
      where g :: a -> a -> (s -> Either a (a, s)) -> s -> Either a (a, s)
g a
i a
x s -> Either a (a, s)
cont s
s | Just s
s' <- s -> Vector a -> Maybe s
f s
s (a -> Vector a
forall a. a -> Vector a
Vector.singleton a
x) = s -> Either a (a, s) -> Either a (a, s)
forall a b. a -> b -> b
seq s
s' (s -> Either a (a, s)
cont s
s')
                         | Bool
otherwise = (a, s) -> Either a (a, s)
forall a b. b -> Either a b
Right (a
i, s
s)
   splitAt :: Int -> Vector a -> (Vector a, Vector a)
splitAt = Int -> Vector a -> (Vector a, Vector a)
forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt
   drop :: Int -> Vector a -> Vector a
drop = Int -> Vector a -> Vector a
forall a. Int -> Vector a -> Vector a
Vector.drop
   take :: Int -> Vector a -> Vector a
take = Int -> Vector a -> Vector a
forall a. Int -> Vector a -> Vector a
Vector.take