{- 
    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 forall m. Factorial m => m -> [m]
factors m
x
                        of [] -> forall a. Maybe a
Nothing
                           m
prefix : [m]
rest -> forall a. a -> Maybe a
Just (m
prefix, forall a. Monoid a => [a] -> a
mconcat [m]
rest)
   splitPrimeSuffix m
x = case forall m. Factorial m => m -> [m]
factors m
x
                        of [] -> forall a. Maybe a
Nothing
                           [m]
fs -> forall a. a -> Maybe a
Just (forall a. Monoid a => [a] -> a
mconcat (forall a. [a] -> [a]
List.init [m]
fs), forall a. [a] -> a
List.last [m]
fs)
   inits = forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr (\m
m [m]
l-> forall a. Monoid a => a
mempty forall a. a -> [a] -> [a]
: forall a b. (a -> b) -> [a] -> [b]
List.map (forall a. Monoid a => a -> a -> a
mappend m
m) [m]
l) [forall a. Monoid a => a
mempty]
   tails m
m = m
m forall a. a -> [a] -> [a]
: forall b a. b -> (a -> b) -> Maybe a -> b
maybe [] (forall m. FactorialMonoid m => m -> [m]
tails forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> b
snd) (forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix m
m)
   span m -> Bool
p m
m0 = forall {a}. (m -> a) -> m -> (a, m)
spanAfter forall a. a -> a
id m
m0
      where spanAfter :: (m -> a) -> m -> (a, m)
spanAfter m -> a
f m
m = case 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Monoid a => a -> a -> a
mappend m
prime) m
rest
                               Maybe (m, m)
_ -> (m -> a
f forall a. Monoid a => a
mempty, m
m)
   break = forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Bool -> Bool
not 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 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 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Monoid a => a -> a -> a
mappend m
prime) s
s' m
rest
                                                    | Bool
otherwise -> (m -> m
g 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 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 = seq :: forall a b. a -> b -> b
seq s
s forall a b. (a -> b) -> a -> b
$
                              case 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Monoid a => a -> a -> a
mappend m
prime) s
s' m
rest
                                                    | Bool
otherwise -> (m -> m
g 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 forall a. a -> [a] -> [a]
: [m]
splitRest
      where (m
prefix, m
rest) = forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
break m -> Bool
p m
m
            splitRest :: [m]
splitRest = case forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix m
rest
                        of Maybe (m, m)
Nothing -> []
                           Just (m
_, m
tl) -> forall m. FactorialMonoid m => (m -> Bool) -> m -> [m]
split m -> Bool
p m
tl
   takeWhile m -> Bool
p = forall a b. (a, b) -> a
fst forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span m -> Bool
p
   dropWhile m -> Bool
p = forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span m -> Bool
p
   splitAt Int
n0 m
m0 | Int
n0 forall a. Ord a => a -> a -> Bool
<= Int
0 = (forall a. Monoid a => a
mempty, m
m0)
                 | Bool
otherwise = forall {t} {t} {c}.
(Eq t, Num t, FactorialMonoid t, Enum t) =>
t -> (t -> c) -> t -> (c, t)
split' Int
n0 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 forall a. Monoid a => a
mempty, t
m)
            split' t
n t -> c
f t
m = case forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix t
m
                           of Maybe (t, t)
Nothing -> (t -> c
f forall a. Monoid a => a
mempty, t
m)
                              Just (t
prime, t
rest) -> t -> (t -> c) -> t -> (c, t)
split' (forall a. Enum a => a -> a
pred t
n) (t -> c
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Monoid a => a -> a -> a
mappend t
prime) t
rest
   drop Int
n m
p = forall a b. (a, b) -> b
snd (forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n m
p)
   take Int
n m
p = forall a b. (a, b) -> a
fst (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 () = forall a. Maybe a
Nothing
   splitPrimeSuffix :: () -> Maybe ((), ())
splitPrimeSuffix () = 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 forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a
                               of Maybe (a, a)
Nothing -> forall a. Maybe a
Nothing
                                  Just (a
p, a
s) -> forall a. a -> Maybe a
Just (forall a. a -> Dual a
Dual a
s, forall a. a -> Dual a
Dual a
p)
   splitPrimeSuffix :: Dual a -> Maybe (Dual a, Dual a)
splitPrimeSuffix (Dual a
a) = case forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a
                               of Maybe (a, a)
Nothing -> forall a. Maybe a
Nothing
                                  Just (a
p, a
s) -> forall a. a -> Maybe a
Just (forall a. a -> Dual a
Dual a
s, forall a. a -> Dual a
Dual a
p)
   inits :: Dual a -> [Dual a]
inits (Dual a
a) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Dual a
Dual (forall m. Factorial m => m -> m
reverse forall a b. (a -> b) -> a -> b
$ forall m. FactorialMonoid m => m -> [m]
tails a
a)
   tails :: Dual a -> [Dual a]
tails (Dual a
a) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Dual a
Dual (forall m. Factorial m => m -> m
reverse forall a b. (a -> b) -> a -> b
$ 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) = forall a. Maybe a
Nothing
   splitPrimePrefix (Sum a
a) = forall a. a -> Maybe a
Just (forall a. a -> Sum a
Sum (forall a. Num a => a -> a
signum a
a), forall a. a -> Sum a
Sum (a
a forall a. Num 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) = forall a. Maybe a
Nothing
   splitPrimeSuffix (Sum a
a) = forall a. a -> Maybe a
Just (forall a. a -> Sum a
Sum (a
a forall a. Num a => a -> a -> a
- forall a. Num a => a -> a
signum a
a), forall a. a -> Sum a
Sum (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 = forall a. Maybe a
Nothing
   splitPrimePrefix (Just a
a) = case forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a
                               of Maybe (a, a)
Nothing -> forall a. a -> Maybe a
Just (forall a. a -> Maybe a
Just a
a, forall a. Maybe a
Nothing)
                                  Just (a
p, a
s) -> forall a. a -> Maybe a
Just (forall a. a -> Maybe a
Just a
p, if forall m. MonoidNull m => m -> Bool
null a
s then forall a. Maybe a
Nothing else 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 (forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a, forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix b
b)
                             of (Just (a
ap, a
as), Maybe (b, b)
_) -> forall a. a -> Maybe a
Just ((a
ap, forall a. Monoid a => a
mempty), (a
as, b
b))
                                (Maybe (a, a)
Nothing, Just (b
bp, b
bs)) -> forall a. a -> Maybe a
Just ((a
a, b
bp), (a
a, b
bs))
                                (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing) -> forall a. Maybe a
Nothing
   splitPrimeSuffix :: (a, b) -> Maybe ((a, b), (a, b))
splitPrimeSuffix (a
a, b
b) = case (forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a, forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix b
b)
                             of (Maybe (a, a)
_, Just (b
bp, b
bs)) -> forall a. a -> Maybe a
Just ((a
a, b
bp), (forall a. Monoid a => a
mempty, b
bs))
                                (Just (a
ap, a
as), Maybe (b, b)
Nothing) -> forall a. a -> Maybe a
Just ((a
ap, b
b), (a
as, b
b))
                                (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing) -> forall a. Maybe a
Nothing
   inits :: (a, b) -> [(a, b)]
inits (a
a, b
b) = forall a b. (a -> b) -> [a] -> [b]
List.map (forall a b c. (a -> b -> c) -> b -> a -> c
flip (,) forall a. Monoid a => a
mempty) (forall m. FactorialMonoid m => m -> [m]
inits a
a) forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map ((,) a
a) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> b
$ forall m. FactorialMonoid m => m -> [m]
inits b
b)
   tails :: (a, b) -> [(a, b)]
tails (a
a, b
b) = forall a b. (a -> b) -> [a] -> [b]
List.map (forall a b c. (a -> b -> c) -> b -> a -> c
flip (,) b
b) (forall m. FactorialMonoid m => m -> [m]
tails a
a) forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map ((,) forall a. Monoid a => a
mempty) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> 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) = forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b) -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. Monoid b => a -> (a, b)
fromFst) a
x
            (b
yp, b
ys) | forall m. MonoidNull m => m -> Bool
null a
xs = forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b) -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. Monoid a => b -> (a, b)
fromSnd) b
y
                     | Bool
otherwise = (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) | forall m. MonoidNull m => m -> Bool
null a
xs = ((a
xp, b
yp), (a
xs, b
ys), s
s2)
                         | Bool
otherwise = ((a
xp, forall a. Monoid a => a
mempty), (a
xs, b
y), s
s1)
     where (a
xp, a
xs, s
s1) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. Monoid b => a -> (a, b)
fromFst) a
x
           (b
yp, b
ys, s
s2) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) | forall m. MonoidNull m => m -> Bool
null a
xs = ((a
xp, b
yp), (a
xs, b
ys), s
s2)
                          | Bool
otherwise = ((a
xp, forall a. Monoid a => a
mempty), (a
xs, b
y), s
s1)
     where (a
xp, a
xs, s
s1) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. Monoid b => a -> (a, b)
fromFst) a
x
           (b
yp, b
ys, s
s2) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = forall a b. (a, b) -> a
fst forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
List.foldr forall {a}. Monoid a => a -> ([a], Bool) -> ([a], Bool)
combine ([(a, b)]
ys, Bool
False) [(a, b)]
xs
      where xs :: [(a, b)]
xs = forall a b. (a -> b) -> [a] -> [b]
List.map forall b a. Monoid b => a -> (a, b)
fromFst forall a b. (a -> b) -> a -> b
$ forall m. FactorialMonoid m => (m -> Bool) -> m -> [m]
split ((a, b) -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. Monoid b => a -> (a, b)
fromFst) a
x0
            ys :: [(a, b)]
ys = forall a b. (a -> b) -> [a] -> [b]
List.map forall a b. Monoid a => b -> (a, b)
fromSnd forall a b. (a -> b) -> a -> b
$ forall m. FactorialMonoid m => (m -> Bool) -> m -> [m]
split ((a, b) -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = (forall a. Monoid a => a -> a -> a
mappend a
x a
y forall a. a -> [a] -> [a]
: [a]
rest, Bool
True)
            combine a
x ([a]
rest, Bool
True) = (a
xforall 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) = forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n a
x
            (b
yp, b
ys) | forall m. MonoidNull m => m -> Bool
null a
xs = forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n forall a. Num a => a -> a -> a
- forall m. Factorial m => m -> Int
length a
x) b
y
                     | Bool
otherwise = (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, 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 = (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 (forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a, forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix b
b, forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix c
c)
                                of (Just (a
ap, a
as), Maybe (b, b)
_, Maybe (c, c)
_) -> forall a. a -> Maybe a
Just ((a
ap, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty), (a
as, b
b, c
c))
                                   (Maybe (a, a)
Nothing, Just (b
bp, b
bs), Maybe (c, c)
_) -> forall a. a -> Maybe a
Just ((a
a, b
bp, 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)) -> 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) -> forall a. Maybe a
Nothing
   splitPrimeSuffix :: (a, b, c) -> Maybe ((a, b, c), (a, b, c))
splitPrimeSuffix (a
a, b
b, c
c) = case (forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a, forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix b
b, forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix c
c)
                                of (Maybe (a, a)
_, Maybe (b, b)
_, Just (c
cp, c
cs)) -> forall a. a -> Maybe a
Just ((a
a, b
b, c
cp), (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, c
cs))
                                   (Maybe (a, a)
_, Just (b
bp, b
bs), Maybe (c, c)
Nothing) -> forall a. a -> Maybe a
Just ((a
a, b
bp, c
c), (forall a. Monoid a => a
mempty, b
bs, c
c))
                                   (Just (a
ap, a
as), Maybe (b, b)
Nothing, Maybe (c, c)
Nothing) -> 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) -> forall a. Maybe a
Nothing
   inits :: (a, b, c) -> [(a, b, c)]
inits (a
a, b
b, c
c) = forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)) (forall m. FactorialMonoid m => m -> [m]
inits a
a)
                     forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
a, b
b1, forall a. Monoid a => a
mempty)) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> b
$ forall m. FactorialMonoid m => m -> [m]
inits b
b)
                     forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
a, b
b, c
c1)) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> b
$ forall m. FactorialMonoid m => m -> [m]
inits c
c)
   tails :: (a, b, c) -> [(a, b, c)]
tails (a
a, b
b, c
c) = forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
b, c
c)) (forall m. FactorialMonoid m => m -> [m]
tails a
a)
                     forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (forall a. Monoid a => a
mempty, b
b1, c
c)) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> b
$ forall m. FactorialMonoid m => m -> [m]
tails b
b)
                     forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, c
c1)) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> b
$ 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) = forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c) -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) a
a
            (b
bp, b
bs) | forall m. MonoidNull m => m -> Bool
null a
as = forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c) -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) b
b
                     | Bool
otherwise = (forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& forall m. MonoidNull m => m -> Bool
null b
bs = forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c) -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3) c
c
                     | Bool
otherwise = (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 (forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty), (a
as, b
b, c
c), s
s1)
                            | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, 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) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) a
a
           (b
bp, b
bs, s
s2) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) b
b
           (c
cp, c
cs, s
s3) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> 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 (forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty), (a
as, b
b, c
c), s
s1)
                             | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, 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) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) a
a
           (b
bp, b
bs, s
s2) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) b
b
           (c
cp, c
cs, s
s3) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> 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) = forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n a
a
            (b
bp, b
bs) | forall m. MonoidNull m => m -> Bool
null a
as = forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n forall a. Num a => a -> a -> a
- forall m. Factorial m => m -> Int
length a
a) b
b
                     | Bool
otherwise = (forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& forall m. MonoidNull m => m -> Bool
null b
bs = forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n forall a. Num a => a -> a -> a
- forall m. Factorial m => m -> Int
length a
a forall a. Num a => a -> a -> a
- forall m. Factorial m => m -> Int
length b
b) c
c
                     | Bool
otherwise = (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, forall a. Monoid a => a
mempty, 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 = (forall a. Monoid a => a
mempty, b
b, 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 = (forall a. Monoid a => a
mempty, 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 (forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a, forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix b
b, forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix c
c, 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)
_) -> forall a. a -> Maybe a
Just ((a
ap, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, 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)
_) -> forall a. a -> Maybe a
Just ((a
a, b
bp, forall a. Monoid a => a
mempty, 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)
_) -> forall a. a -> Maybe a
Just ((a
a, b
b, c
cp, 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)) -> 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) -> 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 (forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a, forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix b
b, forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix c
c, 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)) -> forall a. a -> Maybe a
Just ((a
a, b
b, c
c, d
dp), (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, d
ds))
                                      (Maybe (a, a)
_, Maybe (b, b)
_, Just (c
cp, c
cs), Maybe (d, d)
Nothing) -> forall a. a -> Maybe a
Just ((a
a, b
b, c
cp, d
d), (forall a. Monoid a => a
mempty, 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) -> forall a. a -> Maybe a
Just ((a
a, b
bp, c
c, d
d), (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) -> 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) -> forall a. Maybe a
Nothing
   inits :: (a, b, c, d) -> [(a, b, c, d)]
inits (a
a, b
b, c
c, d
d) = forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)) (forall m. FactorialMonoid m => m -> [m]
inits a
a)
                        forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
a, b
b1, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> b
$ forall m. FactorialMonoid m => m -> [m]
inits b
b)
                        forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
a, b
b, c
c1, forall a. Monoid a => a
mempty)) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> b
$ forall m. FactorialMonoid m => m -> [m]
inits c
c)
                        forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\d
d1-> (a
a, b
b, c
c, d
d1)) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> b
$ 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) = forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
b, c
c, d
d)) (forall m. FactorialMonoid m => m -> [m]
tails a
a)
                        forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (forall a. Monoid a => a
mempty, b
b1, c
c, d
d)) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> b
$ forall m. FactorialMonoid m => m -> [m]
tails b
b)
                        forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, c
c1, d
d)) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> b
$ forall m. FactorialMonoid m => m -> [m]
tails c
c)
                        forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\d
d1-> (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, d
d1)) (forall a. [a] -> [a]
List.tail forall a b. (a -> b) -> a -> b
$ 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) = forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4) a
a
            (b
bp, b
bs) | forall m. MonoidNull m => m -> Bool
null a
as = forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4) b
b
                     | Bool
otherwise = (forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& forall m. MonoidNull m => m -> Bool
null b
bs = forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4) c
c
                     | Bool
otherwise = (forall a. Monoid a => a
mempty, c
c)
            (d
dp, d
ds) | forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& forall m. MonoidNull m => m -> Bool
null b
bs Bool -> Bool -> Bool
&& forall m. MonoidNull m => m -> Bool
null c
cs = forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4) d
d
                     | Bool
otherwise = (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 (forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty), (a
as, b
b, c
c, d
d), s
s1)
                               | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty), (a
as, b
bs, c
c, d
d), s
s2)
                               | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null c
cs) = ((a
ap, b
bp, c
cp, 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) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 (forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty), (a
as, b
b, c
c, d
d), s
s1)
                               | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty), (a
as, b
bs, c
c, d
d), s
s2)
                               | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null c
cs) = ((a
ap, b
bp, c
cp, 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) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n a
a
            (b
bp, b
bs) | forall m. MonoidNull m => m -> Bool
null a
as = forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n forall a. Num a => a -> a -> a
- forall m. Factorial m => m -> Int
length a
a) b
b
                     | Bool
otherwise = (forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& forall m. MonoidNull m => m -> Bool
null b
bs = forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n forall a. Num a => a -> a -> a
- forall m. Factorial m => m -> Int
length a
a forall a. Num a => a -> a -> a
- forall m. Factorial m => m -> Int
length b
b) c
c
                     | Bool
otherwise = (forall a. Monoid a => a
mempty, c
c)
            (d
dp, d
ds) | forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& forall m. MonoidNull m => m -> Bool
null b
bs Bool -> Bool -> Bool
&& forall m. MonoidNull m => m -> Bool
null c
cs = forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n forall a. Num a => a -> a -> a
- forall m. Factorial m => m -> Int
length a
a forall a. Num a => a -> a -> a
- forall m. Factorial m => m -> Int
length b
b forall a. Num a => a -> a -> a
- forall m. Factorial m => m -> Int
length c
c) d
d
                     | Bool
otherwise = (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, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, 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 = (forall a. Monoid a => a
mempty, b
b, forall a. Monoid a => a
mempty, 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 = (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, c
c, 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 = (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, d
d)

instance FactorialMonoid [x] where
   splitPrimePrefix :: [x] -> Maybe ([x], [x])
splitPrimePrefix [] = forall a. Maybe a
Nothing
   splitPrimePrefix (x
x:[x]
xs) = forall a. a -> Maybe a
Just ([x
x], [x]
xs)
   splitPrimeSuffix :: [x] -> Maybe ([x], [x])
splitPrimeSuffix [] = forall a. Maybe a
Nothing
   splitPrimeSuffix [x]
xs = forall a. a -> Maybe a
Just (forall {a} {c}. ([a] -> c) -> [a] -> (c, [a])
splitLast 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
xforall a. a -> [a] -> [a]
:)) [a]
rest
   inits :: [x] -> [[x]]
inits = forall x. [x] -> [[x]]
List.inits
   tails :: [x] -> [[x]]
tails = forall x. [x] -> [[x]]
List.tails
   break :: ([x] -> Bool) -> [x] -> ([x], [x])
break [x] -> Bool
f = forall a. (a -> Bool) -> [a] -> ([a], [a])
List.break ([x] -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall a. a -> [a] -> [a]
:[]))
   span :: ([x] -> Bool) -> [x] -> ([x], [x])
span [x] -> Bool
f = forall a. (a -> Bool) -> [a] -> ([a], [a])
List.span ([x] -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall a. a -> [a] -> [a]
:[]))
   dropWhile :: ([x] -> Bool) -> [x] -> [x]
dropWhile [x] -> Bool
f = forall a. (a -> Bool) -> [a] -> [a]
List.dropWhile ([x] -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall a. a -> [a] -> [a]
:[]))
   takeWhile :: ([x] -> Bool) -> [x] -> [x]
takeWhile [x] -> Bool
f = forall a. (a -> Bool) -> [a] -> [a]
List.takeWhile ([x] -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. (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
_) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' forall {c}.
([x] -> c, [x] -> [x], s, Bool)
-> x -> ([x] -> c, [x] -> [x], s, Bool)
g (forall a. a -> a
id, 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x
xforall a. a -> [a] -> [a]
:), forall a. a -> a
id, s
s2, Bool
True)
                                           | Bool
otherwise = ([x] -> c
prefix, [x] -> [x]
suffix forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x
xforall 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
_) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' forall {c}.
([x] -> c, [x] -> [x], s, Bool)
-> x -> ([x] -> c, [x] -> [x], s, Bool)
g (forall a. a -> a
id, 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] = seq :: forall a b. a -> b -> b
seq s
s2 forall a b. (a -> b) -> a -> b
$ ([x] -> c
prefix forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x
xforall a. a -> [a] -> [a]
:), forall a. a -> a
id, s
s2, Bool
True)
                                           | Bool
otherwise = ([x] -> c
prefix, [x] -> [x]
suffix forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x
xforall a. a -> [a] -> [a]
:), s
s1, Bool
False)
   splitAt :: Int -> [x] -> ([x], [x])
splitAt = forall x. Int -> [x] -> ([x], [x])
List.splitAt
   drop :: Int -> [x] -> [x]
drop = forall x. Int -> [x] -> [x]
List.drop
   take :: Int -> [x] -> [x]
take = 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 forall a. Maybe a
Nothing else 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 forall a. Maybe a
Nothing else forall a. a -> Maybe a
Just (Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt (ByteString -> Int
ByteString.length ByteString
x 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 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 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 forall a. (Word8 -> a -> a) -> a -> ByteString -> a
ByteString.foldr Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g 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' = forall a. Enum a => a -> a
succ Int
i :: Int in seq :: forall a b. a -> b -> b
seq Int
i' 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 forall a. (Word8 -> a -> a) -> a -> ByteString -> a
ByteString.foldr Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g 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' = forall a. Enum a => a -> a
succ Int
i :: Int in seq :: forall a b. a -> b -> b
seq Int
i' forall a b. (a -> b) -> a -> b
$ seq :: forall a b. a -> b -> b
seq s
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 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 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 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 forall a. Maybe a
Nothing
                        else 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 forall a. Maybe a
Nothing
                        else forall a. a -> Maybe a
Just (Int64 -> ByteString -> (ByteString, ByteString)
LazyByteString.splitAt (ByteString -> Int64
LazyByteString.length ByteString
x 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 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 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 forall a. (Word8 -> a -> a) -> a -> ByteString -> a
LazyByteString.foldr Word8 -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g 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' = forall a. Enum a => a -> a
succ Int64
i :: Int64 in seq :: forall a b. a -> b -> b
seq Int64
i' 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 forall a. (Word8 -> a -> a) -> a -> ByteString -> a
LazyByteString.foldr Word8 -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g 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' = forall a. Enum a => a -> a
succ Int64
i :: Int64 in seq :: forall a b. a -> b -> b
seq Int64
i' forall a b. (a -> b) -> a -> b
$ seq :: forall a b. a -> b -> b
seq s
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 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 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 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral
   drop :: Int -> ByteString -> ByteString
drop Int
n = Int64 -> ByteString -> ByteString
LazyByteString.drop (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n)
   take :: Int -> ByteString -> ByteString
take Int
n = Int64 -> ByteString -> ByteString
LazyByteString.take (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n)

instance FactorialMonoid Text.Text where
   splitPrimePrefix :: Text -> Maybe (Text, Text)
splitPrimePrefix = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Char -> Text
Text.singleton) 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 forall a. Maybe a
Nothing else forall a. a -> Maybe a
Just (Text -> Text
Text.init Text
x, Char -> Text
Text.singleton (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 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 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 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 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 forall a. (Char -> a -> a) -> a -> Text -> a
Text.foldr Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g 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' = forall a. Enum a => a -> a
succ Int
i :: Int in seq :: forall a b. a -> b -> b
seq Int
i' 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 forall a. (Char -> a -> a) -> a -> Text -> a
Text.foldr Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g 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' = forall a. Enum a => a -> a
succ Int
i :: Int in seq :: forall a b. a -> b -> b
seq Int
i' forall a b. (a -> b) -> a -> b
$ seq :: forall a b. a -> b -> b
seq s
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 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 = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Char -> Text
LazyText.singleton) 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 forall a. Maybe a
Nothing
                        else forall a. a -> Maybe a
Just (Text -> Text
LazyText.init Text
x, Char -> Text
LazyText.singleton (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 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 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 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 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 forall a. (Char -> a -> a) -> a -> Text -> a
LazyText.foldr Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g 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' = forall a. Enum a => a -> a
succ Int64
i :: Int64 in seq :: forall a b. a -> b -> b
seq Int64
i' 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 forall a. (Char -> a -> a) -> a -> Text -> a
LazyText.foldr Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g 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' = forall a. Enum a => a -> a
succ Int64
i :: Int64 in seq :: forall a b. a -> b -> b
seq Int64
i' forall a b. (a -> b) -> a -> b
$ seq :: forall a b. a -> b -> b
seq s
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 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (Integral a, Num b) => a -> b
fromIntegral
   drop :: Int -> Text -> Text
drop Int
n = Int64 -> Text -> Text
LazyText.drop (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n)
   take :: Int -> Text -> Text
take Int
n = Int64 -> Text -> Text
LazyText.take (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 = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall {k} {a} {b}. ((k, a), b) -> (Map k a, b)
singularize forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = (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 = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall {k} {a} {a}. ((k, a), a) -> (a, Map k a)
singularize forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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, 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 = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall {a} {b}. ((Int, a), b) -> (IntMap a, b)
singularize forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = (forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v, b
rest)
   splitPrimeSuffix :: IntMap a -> Maybe (IntMap a, IntMap a)
splitPrimeSuffix = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall {a} {a}. ((Int, a), a) -> (a, IntMap a)
singularize forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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, forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v)

instance FactorialMonoid IntSet.IntSet where
   splitPrimePrefix :: IntSet -> Maybe (IntSet, IntSet)
splitPrimePrefix = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall {b}. (Int, b) -> (IntSet, b)
singularize 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 = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall {a}. (Int, a) -> (a, IntSet)
singularize 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 forall a. Seq a -> ViewL a
Sequence.viewl Seq a
q
                        of ViewL a
Sequence.EmptyL -> forall a. Maybe a
Nothing
                           a
hd Sequence.:< Seq a
rest -> forall a. a -> Maybe a
Just (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 forall a. Seq a -> ViewR a
Sequence.viewr Seq a
q
                        of ViewR a
Sequence.EmptyR -> forall a. Maybe a
Nothing
                           Seq a
rest Sequence.:> a
last -> forall a. a -> Maybe a
Just (Seq a
rest, forall a. a -> Seq a
Sequence.singleton a
last)
   inits :: Seq a -> [Seq a]
inits = forall (t :: * -> *) a. Foldable t => t a -> [a]
Foldable.toList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Seq a -> Seq (Seq a)
Sequence.inits
   tails :: Seq a -> [Seq a]
tails = forall (t :: * -> *) a. Foldable t => t a -> [a]
Foldable.toList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Seq a -> Seq (Seq a)
Sequence.tails
   span :: (Seq a -> Bool) -> Seq a -> (Seq a, Seq a)
span Seq a -> Bool
f = forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
Sequence.spanl (Seq a -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Seq a
Sequence.singleton)
   break :: (Seq a -> Bool) -> Seq a -> (Seq a, Seq a)
break Seq a -> Bool
f = forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
Sequence.breakl (Seq a -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Seq a
Sequence.singleton)
   dropWhile :: (Seq a -> Bool) -> Seq a -> Seq a
dropWhile Seq a -> Bool
f = forall a. (a -> Bool) -> Seq a -> Seq a
Sequence.dropWhileL (Seq a -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Seq a
Sequence.singleton)
   takeWhile :: (Seq a -> Bool) -> Seq a -> Seq a
takeWhile Seq a -> Bool
f = forall a. (a -> Bool) -> Seq a -> Seq a
Sequence.takeWhileL (Seq a -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 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 forall a. a -> a
id Seq a
b (Int
0, s
s0)
                      of (Int
i, s
s') | (Seq a
prefix, Seq a
suffix) <- 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 (forall a. a -> Seq a
Sequence.singleton a
x) = let i' :: Int
i' = forall a. Enum a => a -> a
succ Int
i :: Int in seq :: forall a b. a -> b -> b
seq Int
i' 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 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 forall a. a -> a
id Seq a
b (Int
0, s
s0)
                       of (Int
i, s
s') | (Seq a
prefix, Seq a
suffix) <- 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 (forall a. a -> Seq a
Sequence.singleton a
x) = let i' :: Int
i' = forall a. Enum a => a -> a
succ Int
i :: Int in seq :: forall a b. a -> b -> b
seq Int
i' forall a b. (a -> b) -> a -> b
$ seq :: forall a b. a -> b -> b
seq s
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 = forall a. Int -> Seq a -> (Seq a, Seq a)
Sequence.splitAt
   drop :: Int -> Seq a -> Seq a
drop = forall a. Int -> Seq a -> Seq a
Sequence.drop
   take :: Int -> Seq a -> Seq a
take = 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 = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall {a} {b}. (a, b) -> (Set a, b)
singularize forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Set a -> Maybe (a, Set a)
Set.minView
      where singularize :: (a, b) -> (Set a, b)
singularize (a
min, b
rest) = (forall a. a -> Set a
Set.singleton a
min, b
rest)
   splitPrimeSuffix :: Set a -> Maybe (Set a, Set a)
splitPrimeSuffix = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall {a} {a}. (a, a) -> (a, Set a)
singularize forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Set a -> Maybe (a, Set a)
Set.maxView
      where singularize :: (a, a) -> (a, Set a)
singularize (a
max, a
rest) = (a
rest, 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 forall a. Vector a -> Bool
Vector.null Vector a
x then forall a. Maybe a
Nothing else forall a. a -> Maybe a
Just (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 forall a. Vector a -> Bool
Vector.null Vector a
x then forall a. Maybe a
Nothing else forall a. a -> Maybe a
Just (forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt (forall a. Vector a -> Int
Vector.length Vector a
x forall a. Num a => a -> a -> a
- Int
1) Vector a
x)
   inits :: Vector a -> [Vector a]
inits Vector a
x0 = 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 | forall a. Vector a -> Bool
Vector.null Vector a
x = Vector a
xforall a. a -> [a] -> [a]
:[Vector a]
rest
                             | Bool
otherwise = Vector a -> [Vector a] -> [Vector a]
initsWith (forall a. Vector a -> Vector a
Vector.unsafeInit Vector a
x) (Vector a
xforall a. a -> [a] -> [a]
:[Vector a]
rest)
   tails :: Vector a -> [Vector a]
tails Vector a
x = Vector a
x forall a. a -> [a] -> [a]
: if forall a. Vector a -> Bool
Vector.null Vector a
x then [] else forall m. FactorialMonoid m => m -> [m]
tails (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 = forall a. (a -> Bool) -> Vector a -> (Vector a, Vector a)
Vector.break (Vector a -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Vector a
Vector.singleton)
   span :: (Vector a -> Bool) -> Vector a -> (Vector a, Vector a)
span Vector a -> Bool
f = forall a. (a -> Bool) -> Vector a -> (Vector a, Vector a)
Vector.span (Vector a -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Vector a
Vector.singleton)
   dropWhile :: (Vector a -> Bool) -> Vector a -> Vector a
dropWhile Vector a -> Bool
f = forall a. (a -> Bool) -> Vector a -> Vector a
Vector.dropWhile (Vector a -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Vector a
Vector.singleton)
   takeWhile :: (Vector a -> Bool) -> Vector a -> Vector a
takeWhile Vector a -> Bool
f = forall a. (a -> Bool) -> Vector a -> Vector a
Vector.takeWhile (Vector a -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 forall a b. (Int -> a -> b -> b) -> b -> Vector a -> b
Vector.ifoldr forall {a} {a}.
a -> a -> (s -> Either a (a, s)) -> s -> Either a (a, s)
g forall a b. a -> Either a b
Left Vector a
v s
s0
                      of Left s
s' -> (Vector a
v, forall a. Vector a
Vector.empty, s
s')
                         Right (Int
i, s
s') | (Vector a
prefix, Vector a
suffix) <- 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 (forall a. a -> Vector a
Vector.singleton a
x) = s -> Either a (a, s)
cont s
s'
                         | Bool
otherwise = 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 forall a b. (Int -> a -> b -> b) -> b -> Vector a -> b
Vector.ifoldr' forall {a} {a}.
a -> a -> (s -> Either a (a, s)) -> s -> Either a (a, s)
g forall a b. a -> Either a b
Left Vector a
v s
s0
                       of Left s
s' -> (Vector a
v, forall a. Vector a
Vector.empty, s
s')
                          Right (Int
i, s
s') | (Vector a
prefix, Vector a
suffix) <- 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 (forall a. a -> Vector a
Vector.singleton a
x) = seq :: forall a b. a -> b -> b
seq s
s' (s -> Either a (a, s)
cont s
s')
                         | Bool
otherwise = forall a b. b -> Either a b
Right (a
i, s
s)
   splitAt :: Int -> Vector a -> (Vector a, Vector a)
splitAt = forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt
   drop :: Int -> Vector a -> Vector a
drop = forall a. Int -> Vector a -> Vector a
Vector.drop
   take :: Int -> Vector a -> Vector a
take = forall a. Int -> Vector a -> Vector a
Vector.take