{- 
    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. 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 x :: m
x = case m -> [m]
forall m. Factorial m => m -> [m]
factors m
x
                        of [] -> Maybe (m, m)
forall a. Maybe a
Nothing
                           prefix :: m
prefix : rest :: [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 x :: m
x = case m -> [m]
forall m. Factorial m => m -> [m]
factors m
x
                        of [] -> Maybe (m, m)
forall a. Maybe a
Nothing
                           fs :: [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. [a] -> [a]
List.init [m]
fs), [m] -> m
forall a. [a] -> a
List.last [m]
fs)
   inits = (m -> [m] -> [m]) -> [m] -> m -> [m]
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr (\m :: m
m l :: [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] -> [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 p :: m -> Bool
p m0 :: 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 f :: m -> a
f m :: m
m = case m -> Maybe (m, m)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix m
m
                            of Just (prime :: m
prime, rest :: 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
                               _ -> (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 s0 :: s
s0 f :: s -> m -> Maybe s
f m0 :: 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 g :: m -> m
g s :: s
s m :: m
m = case m -> Maybe (m, m)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix m
m
                              of Just (prime :: m
prime, rest :: m
rest) | Just s' :: 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)
                                 Nothing -> (m
m0, m
m, s
s)
   spanMaybe' s0 :: s
s0 f :: s -> m -> Maybe s
f m0 :: 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 g :: m -> m
g s :: s
s m :: 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 (prime :: m
prime, rest :: m
rest) | Just s' :: 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)
                                 Nothing -> (m
m0, m
m, s
s)
   split p :: m -> Bool
p m :: m
m = m
prefix m -> [m] -> [m]
forall a. a -> [a] -> [a]
: [m]
splitRest
      where (prefix :: m
prefix, rest :: 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 Nothing -> []
                           Just (_, tl :: m
tl) -> (m -> Bool) -> m -> [m]
forall m. FactorialMonoid m => (m -> Bool) -> m -> [m]
split m -> Bool
p m
tl
   takeWhile p :: 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 p :: 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 n0 :: Int
n0 m0 :: m
m0 | Int
n0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 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' 0 f :: t -> c
f m :: t
m = (t -> c
f t
forall a. Monoid a => a
mempty, t
m)
            split' n :: t
n f :: t -> c
f m :: t
m = case t -> Maybe (t, t)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix t
m
                           of Nothing -> (t -> c
f t
forall a. Monoid a => a
mempty, t
m)
                              Just (prime :: t
prime, rest :: 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 n :: Int
n p :: 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 n :: Int
n p :: 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 #-}

{-# 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
a) = case a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a
                               of Nothing -> Maybe (Dual a, Dual a)
forall a. Maybe a
Nothing
                                  Just (p :: a
p, s :: 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
a) = case a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a
                               of Nothing -> Maybe (Dual a, Dual a)
forall a. Maybe a
Nothing
                                  Just (p :: a
p, s :: 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) = (a -> Dual a) -> [a] -> [Dual a]
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) = (a -> Dual a) -> [a] -> [Dual a]
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 0) = Maybe (Sum a, Sum a)
forall a. Maybe a
Nothing
   splitPrimePrefix (Sum a :: 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 0) = Maybe (Sum a, Sum a)
forall a. Maybe a
Nothing
   splitPrimeSuffix (Sum a :: 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 Nothing = Maybe (Maybe a, Maybe a)
forall a. Maybe a
Nothing
   splitPrimePrefix (Just a :: a
a) = case a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a
                               of 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 (p :: a
p, s :: 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
a, b :: 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 (ap :: a
ap, as :: a
as), _) -> ((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))
                                (Nothing, Just (bp :: b
bp, bs :: 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))
                                (Nothing, Nothing) -> Maybe ((a, b), (a, b))
forall a. Maybe a
Nothing
   splitPrimeSuffix :: (a, b) -> Maybe ((a, b), (a, b))
splitPrimeSuffix (a :: a
a, b :: 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 (_, Just (bp :: b
bp, bs :: 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 (ap :: a
ap, as :: a
as), Nothing) -> ((a, b), (a, b)) -> Maybe ((a, b), (a, b))
forall a. a -> Maybe a
Just ((a
ap, b
b), (a
as, b
b))
                                (Nothing, Nothing) -> Maybe ((a, b), (a, b))
forall a. Maybe a
Nothing
   inits :: (a, b) -> [(a, b)]
inits (a :: a
a, b :: 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. [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
a, b :: 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. [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 p :: (a, b) -> Bool
p (x :: a
x, y :: b
y) = ((a
xp, b
yp), (a
xs, b
ys))
      where (xp :: a
xp, xs :: 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
            (yp :: b
yp, ys :: 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 :: s -> (s -> (a, b) -> Maybe s) -> (a, b) -> ((a, b), (a, b), s)
spanMaybe s0 :: s
s0 f :: s -> (a, b) -> Maybe s
f (x :: a
x, y :: 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 (xp :: a
xp, xs :: a
xs, s1 :: s
s1) = 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-> 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
           (yp :: b
yp, ys :: b
ys, s2 :: s
s2) = 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-> 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' :: s -> (s -> (a, b) -> Maybe s) -> (a, b) -> ((a, b), (a, b), s)
spanMaybe' s0 :: s
s0 f :: s -> (a, b) -> Maybe s
f (x :: a
x, y :: 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 (xp :: a
xp, xs :: a
xs, s1 :: s
s1) = 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-> 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
           (yp :: b
yp, ys :: b
ys, s2 :: s
s2) = 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-> 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 p :: (a, b) -> Bool
p (x0 :: a
x0, y0 :: 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 (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 x :: a
x (~(y :: a
y:rest :: [a]
rest), 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 x :: a
x (rest :: [a]
rest, True) = (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
rest, Bool
True)
   splitAt :: Int -> (a, b) -> ((a, b), (a, b))
splitAt n :: Int
n (x :: a
x, y :: b
y) = ((a
xp, b
yp), (a
xs, b
ys))
      where (xp :: a
xp, xs :: a
xs) = Int -> a -> (a, a)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n a
x
            (yp :: b
yp, ys :: 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 :: a -> (a, b)
fromFst a :: a
a = (a
a, b
forall a. Monoid a => a
mempty)

{-# INLINE fromSnd #-}
fromSnd :: Monoid a => b -> (a, b)
fromSnd :: b -> (a, b)
fromSnd b :: 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
a, b :: b
b, c :: 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 (ap :: a
ap, as :: a
as), _, _) -> ((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))
                                   (Nothing, Just (bp :: b
bp, bs :: b
bs), _) -> ((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))
                                   (Nothing, Nothing, Just (cp :: c
cp, cs :: 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))
                                   (Nothing, Nothing, 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
a, b :: b
b, c :: 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 (_, _, Just (cp :: c
cp, cs :: 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))
                                   (_, Just (bp :: b
bp, bs :: b
bs), 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 (ap :: a
ap, as :: a
as), Nothing, 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))
                                   (Nothing, Nothing, Nothing) -> Maybe ((a, b, c), (a, b, c))
forall a. Maybe a
Nothing
   inits :: (a, b, c) -> [(a, b, c)]
inits (a :: a
a, b :: b
b, c :: c
c) = (a -> (a, b, c)) -> [a] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a1 :: 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 (\b1 :: b
b1-> (a
a, b
b1, c
forall a. Monoid a => a
mempty)) ([b] -> [b]
forall a. [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 (\c1 :: c
c1-> (a
a, b
b, c
c1)) ([c] -> [c]
forall a. [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
a, b :: b
b, c :: c
c) = (a -> (a, b, c)) -> [a] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a1 :: 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 (\b1 :: b
b1-> (a
forall a. Monoid a => a
mempty, b
b1, c
c)) ([b] -> [b]
forall a. [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 (\c1 :: c
c1-> (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
c1)) ([c] -> [c]
forall a. [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 p :: (a, b, c) -> Bool
p (a :: a
a, b :: b
b, c :: c
c) = ((a
ap, b
bp, c
cp), (a
as, b
bs, c
cs))
      where (ap :: a
ap, as :: 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
            (bp :: b
bp, bs :: 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)
            (cp :: c
cp, cs :: 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 :: s
-> (s -> (a, b, c) -> Maybe s)
-> (a, b, c)
-> ((a, b, c), (a, b, c), s)
spanMaybe s0 :: s
s0 f :: s -> (a, b, c) -> Maybe s
f (a :: a
a, b :: b
b, c :: 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 (ap :: a
ap, as :: a
as, s1 :: s
s1) = 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-> 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
           (bp :: b
bp, bs :: b
bs, s2 :: s
s2) = 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-> 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
           (cp :: c
cp, cs :: c
cs, s3 :: s
s3) = 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-> 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' :: s
-> (s -> (a, b, c) -> Maybe s)
-> (a, b, c)
-> ((a, b, c), (a, b, c), s)
spanMaybe' s0 :: s
s0 f :: s -> (a, b, c) -> Maybe s
f (a :: a
a, b :: b
b, c :: 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 (ap :: a
ap, as :: a
as, s1 :: s
s1) = 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-> 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
           (bp :: b
bp, bs :: b
bs, s2 :: s
s2) = 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-> 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
           (cp :: c
cp, cs :: c
cs, s3 :: s
s3) = 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-> 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 n :: Int
n (a :: a
a, b :: b
b, c :: c
c) = ((a
ap, b
bp, c
cp), (a
as, b
bs, c
cs))
      where (ap :: a
ap, as :: a
as) = Int -> a -> (a, a)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n a
a
            (bp :: b
bp, bs :: 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)
            (cp :: c
cp, cs :: 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 :: a -> (a, b, c)
fromFstOf3 a :: 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 :: b -> (a, b, c)
fromSndOf3 b :: 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 :: c -> (a, b, c)
fromThdOf3 c :: 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
a, b :: b
b, c :: c
c, d :: 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 (ap :: a
ap, as :: a
as), _, _, _) -> ((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))
                                      (Nothing, Just (bp :: b
bp, bs :: b
bs), _, _) -> ((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))
                                      (Nothing, Nothing, Just (cp :: c
cp, cs :: c
cs), _) -> ((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))
                                      (Nothing, Nothing, Nothing, Just (dp :: d
dp, ds :: 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))
                                      (Nothing, Nothing, Nothing, 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
a, b :: b
b, c :: c
c, d :: 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 (_, _, _, Just (dp :: d
dp, ds :: 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))
                                      (_, _, Just (cp :: c
cp, cs :: c
cs), 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))
                                      (_, Just (bp :: b
bp, bs :: b
bs), Nothing, 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 (ap :: a
ap, as :: a
as), Nothing, Nothing, 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))
                                      (Nothing, Nothing, Nothing, 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
a, b :: b
b, c :: c
c, d :: d
d) = (a -> (a, b, c, d)) -> [a] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a1 :: 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 (\b1 :: b
b1-> (a
a, b
b1, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)) ([b] -> [b]
forall a. [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 (\c1 :: c
c1-> (a
a, b
b, c
c1, d
forall a. Monoid a => a
mempty)) ([c] -> [c]
forall a. [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 (\d1 :: d
d1-> (a
a, b
b, c
c, d
d1)) ([d] -> [d]
forall a. [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
a, b :: b
b, c :: c
c, d :: d
d) = (a -> (a, b, c, d)) -> [a] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a1 :: 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 (\b1 :: b
b1-> (a
forall a. Monoid a => a
mempty, b
b1, c
c, d
d)) ([b] -> [b]
forall a. [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 (\c1 :: c
c1-> (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
c1, d
d)) ([c] -> [c]
forall a. [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 (\d1 :: 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. [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 p :: (a, b, c, d) -> Bool
p (a :: a
a, b :: b
b, c :: c
c, d :: d
d) = ((a
ap, b
bp, c
cp, d
dp), (a
as, b
bs, c
cs, d
ds))
      where (ap :: a
ap, as :: 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
            (bp :: b
bp, bs :: 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)
            (cp :: c
cp, cs :: 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)
            (dp :: d
dp, ds :: 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 :: s
-> (s -> (a, b, c, d) -> Maybe s)
-> (a, b, c, d)
-> ((a, b, c, d), (a, b, c, d), s)
spanMaybe s0 :: s
s0 f :: s -> (a, b, c, d) -> Maybe s
f (a :: a
a, b :: b
b, c :: c
c, d :: 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 (ap :: a
ap, as :: a
as, s1 :: s
s1) = 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-> 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
           (bp :: b
bp, bs :: b
bs, s2 :: s
s2) = 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-> 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
           (cp :: c
cp, cs :: c
cs, s3 :: s
s3) = 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-> 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
           (dp :: d
dp, ds :: d
ds, s4 :: s
s4) = 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-> 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' :: s
-> (s -> (a, b, c, d) -> Maybe s)
-> (a, b, c, d)
-> ((a, b, c, d), (a, b, c, d), s)
spanMaybe' s0 :: s
s0 f :: s -> (a, b, c, d) -> Maybe s
f (a :: a
a, b :: b
b, c :: c
c, d :: 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 (ap :: a
ap, as :: a
as, s1 :: s
s1) = 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-> 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
           (bp :: b
bp, bs :: b
bs, s2 :: s
s2) = 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-> 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
           (cp :: c
cp, cs :: c
cs, s3 :: s
s3) = 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-> 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
           (dp :: d
dp, ds :: d
ds, s4 :: s
s4) = 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-> 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 n :: Int
n (a :: a
a, b :: b
b, c :: c
c, d :: d
d) = ((a
ap, b
bp, c
cp, d
dp), (a
as, b
bs, c
cs, d
ds))
      where (ap :: a
ap, as :: a
as) = Int -> a -> (a, a)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n a
a
            (bp :: b
bp, bs :: 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)
            (cp :: c
cp, cs :: 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)
            (dp :: d
dp, ds :: 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 :: a -> (a, b, c, d)
fromFstOf4 a :: 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 :: b -> (a, b, c, d)
fromSndOf4 b :: 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 :: c -> (a, b, c, d)
fromThdOf4 c :: 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 :: d -> (a, b, c, d)
fromFthOf4 d :: 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]
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 xs :: [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 f :: [a] -> c
f last :: [a]
last@[_] = ([a] -> c
f [], [a]
last)
            splitLast f :: [a] -> c
f ~(x :: a
x:rest :: [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 f :: [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 f :: [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 f :: [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 f :: [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 :: s -> (s -> [x] -> Maybe s) -> [x] -> ([x], [x], s)
spanMaybe s0 :: s
s0 f :: s -> [x] -> Maybe s
f l :: [x]
l = ([x] -> [x]
prefix' [], [x] -> [x]
suffix' [], s
s')
      where (prefix' :: [x] -> [x]
prefix', suffix' :: [x] -> [x]
suffix', s' :: s
s', _) = (([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 (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 (prefix :: [x] -> c
prefix, suffix :: [x] -> [x]
suffix, s1 :: s
s1, live :: Bool
live) x :: x
x | Bool
live, Just s2 :: 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' :: s -> (s -> [x] -> Maybe s) -> [x] -> ([x], [x], s)
spanMaybe' s0 :: s
s0 f :: s -> [x] -> Maybe s
f l :: [x]
l = ([x] -> [x]
prefix' [], [x] -> [x]
suffix' [], s
s')
      where (prefix' :: [x] -> [x]
prefix', suffix' :: [x] -> [x]
suffix', s' :: s
s', _) = (([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 (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 (prefix :: [x] -> c
prefix, suffix :: [x] -> [x]
suffix, s1 :: s
s1, live :: Bool
live) x :: x
x | Bool
live, Just s2 :: 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 x :: 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 1 ByteString
x)
   splitPrimeSuffix :: ByteString -> Maybe (ByteString, ByteString)
splitPrimeSuffix x :: 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
- 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 f :: 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 f :: 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 :: s
-> (s -> ByteString -> Maybe s)
-> ByteString
-> (ByteString, ByteString, s)
spanMaybe s0 :: s
s0 f :: s -> ByteString -> Maybe s
f b :: 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 (0, s
s0)
                      of (i :: Int
i, s' :: s
s') | (prefix :: ByteString
prefix, suffix :: 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 w :: Word8
w cont :: (Int, s) -> (Int, s)
cont (i :: Int
i, s :: s
s) | Just s' :: 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' :: s
-> (s -> ByteString -> Maybe s)
-> ByteString
-> (ByteString, ByteString, s)
spanMaybe' s0 :: s
s0 f :: s -> ByteString -> Maybe s
f b :: 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 (0, s
s0)
                       of (i :: Int
i, s' :: s
s') | (prefix :: ByteString
prefix, suffix :: 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 w :: Word8
w cont :: (Int, s) -> (Int, s)
cont (i :: Int
i, s :: s
s) | Just s' :: 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 f :: 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 f :: 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 f :: 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 x :: 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 1 ByteString
x)
   splitPrimeSuffix :: ByteString -> Maybe (ByteString, ByteString)
splitPrimeSuffix x :: 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
- 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 f :: 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 f :: 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 :: s
-> (s -> ByteString -> Maybe s)
-> ByteString
-> (ByteString, ByteString, s)
spanMaybe s0 :: s
s0 f :: s -> ByteString -> Maybe s
f b :: 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 (0, s
s0)
                      of (i :: Int64
i, s' :: s
s') | (prefix :: ByteString
prefix, suffix :: 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 w :: Word8
w cont :: (Int64, s) -> (Int64, s)
cont (i :: Int64
i, s :: s
s) | Just s' :: 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' :: s
-> (s -> ByteString -> Maybe s)
-> ByteString
-> (ByteString, ByteString, s)
spanMaybe' s0 :: s
s0 f :: s -> ByteString -> Maybe s
f b :: 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 (0, s
s0)
                       of (i :: Int64
i, s' :: s
s') | (prefix :: ByteString
prefix, suffix :: 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 w :: Word8
w cont :: (Int64, s) -> (Int64, s)
cont (i :: Int64
i, s :: s
s)
              | Just s' :: 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 f :: 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 f :: 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 f :: 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 n :: 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 n :: 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 (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Char -> Text) -> (Char, Text) -> (Text, Text)
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 x :: 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 (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 f :: 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 f :: 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 f :: 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 f :: 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 :: s -> (s -> Text -> Maybe s) -> Text -> (Text, Text, s)
spanMaybe s0 :: s
s0 f :: s -> Text -> Maybe s
f t :: 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 (0, s
s0)
                      of (i :: Int
i, s' :: s
s') | (prefix :: Text
prefix, suffix :: 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 c :: Char
c cont :: (Int, s) -> (Int, s)
cont (i :: Int
i, s :: s
s) | Just s' :: 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' :: s -> (s -> Text -> Maybe s) -> Text -> (Text, Text, s)
spanMaybe' s0 :: s
s0 f :: s -> Text -> Maybe s
f t :: 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 (0, s
s0)
                       of (i :: Int
i, s' :: s
s') | (prefix :: Text
prefix, suffix :: 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 c :: Char
c cont :: (Int, s) -> (Int, s)
cont (i :: Int
i, s :: s
s) | Just s' :: 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 f :: 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 (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Char -> Text) -> (Char, Text) -> (Text, Text)
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 x :: 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 (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 f :: 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 f :: 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 f :: 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 f :: 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 :: s -> (s -> Text -> Maybe s) -> Text -> (Text, Text, s)
spanMaybe s0 :: s
s0 f :: s -> Text -> Maybe s
f t :: 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 (0, s
s0)
                      of (i :: Int64
i, s' :: s
s') | (prefix :: Text
prefix, suffix :: 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 c :: Char
c cont :: (Int64, s) -> (Int64, s)
cont (i :: Int64
i, s :: s
s) | Just s' :: 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' :: s -> (s -> Text -> Maybe s) -> Text -> (Text, Text, s)
spanMaybe' s0 :: s
s0 f :: s -> Text -> Maybe s
f t :: 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 (0, s
s0)
                       of (i :: Int64
i, s' :: s
s') | (prefix :: Text
prefix, suffix :: 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 c :: Char
c cont :: (Int64, s) -> (Int64, s)
cont (i :: Int64
i, s :: s
s) | Just s' :: 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 f :: 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 n :: 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 n :: 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 (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
k, v :: a
v), rest :: 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 (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
k, v :: a
v), rest :: 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 (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 ((k :: Int
k, v :: a
v), rest :: 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 (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 ((k :: Int
k, v :: a
v), rest :: 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 (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 (min :: Int
min, rest :: 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 (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 (max :: Int
max, rest :: 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 q :: Seq a
q = case Seq a -> ViewL a
forall a. Seq a -> ViewL a
Sequence.viewl Seq a
q
                        of Sequence.EmptyL -> Maybe (Seq a, Seq a)
forall a. Maybe a
Nothing
                           hd :: a
hd Sequence.:< rest :: 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 q :: Seq a
q = case Seq a -> ViewR a
forall a. Seq a -> ViewR a
Sequence.viewr Seq a
q
                        of Sequence.EmptyR -> Maybe (Seq a, Seq a)
forall a. Maybe a
Nothing
                           rest :: Seq a
rest Sequence.:> last :: 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 (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 (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 f :: 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 f :: 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 f :: 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 f :: 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 :: s -> (s -> Seq a -> Maybe s) -> Seq a -> (Seq a, Seq a, s)
spanMaybe s0 :: s
s0 f :: s -> Seq a -> Maybe s
f b :: Seq a
b = case (a -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> Seq a -> (Int, s) -> (Int, s)
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 (0, s
s0)
                      of (i :: Int
i, s' :: s
s') | (prefix :: Seq a
prefix, suffix :: 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 x :: a
x cont :: (Int, s) -> (Int, s)
cont (i :: Int
i, s :: s
s) | Just s' :: 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' :: s -> (s -> Seq a -> Maybe s) -> Seq a -> (Seq a, Seq a, s)
spanMaybe' s0 :: s
s0 f :: s -> Seq a -> Maybe s
f b :: Seq a
b = case (a -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> Seq a -> (Int, s) -> (Int, s)
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 (0, s
s0)
                       of (i :: Int
i, s' :: s
s') | (prefix :: Seq a
prefix, suffix :: 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 x :: a
x cont :: (Int, s) -> (Int, s)
cont (i :: Int
i, s :: s
s) | Just s' :: 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 (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 (min :: a
min, rest :: 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 (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 (max :: a
max, rest :: 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 x :: 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 1 Vector a
x)
   splitPrimeSuffix :: Vector a -> Maybe (Vector a, Vector a)
splitPrimeSuffix x :: 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
- 1) Vector a
x)
   inits :: Vector a -> [Vector a]
inits x0 :: 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 x :: Vector a
x rest :: [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 x :: 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 f :: 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 f :: 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 f :: 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 f :: 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 :: s
-> (s -> Vector a -> Maybe s)
-> Vector a
-> (Vector a, Vector a, s)
spanMaybe s0 :: s
s0 f :: s -> Vector a -> Maybe s
f v :: 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
s' -> (Vector a
v, Vector a
forall a. Vector a
Vector.empty, s
s')
                         Right (i :: Int
i, s' :: s
s') | (prefix :: Vector a
prefix, suffix :: 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 i :: a
i x :: a
x cont :: s -> Either a (a, s)
cont s :: s
s | Just s' :: 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' :: s
-> (s -> Vector a -> Maybe s)
-> Vector a
-> (Vector a, Vector a, s)
spanMaybe' s0 :: s
s0 f :: s -> Vector a -> Maybe s
f v :: 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
s' -> (Vector a
v, Vector a
forall a. Vector a
Vector.empty, s
s')
                          Right (i :: Int
i, s' :: s
s') | (prefix :: Vector a
prefix, suffix :: 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 i :: a
i x :: a
x cont :: s -> Either a (a, s)
cont s :: s
s | Just s' :: 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