{- 
    Copyright 2013-2015 Mario Blazevic

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

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

{-# LANGUAGE Haskell2010, Trustworthy #-}

module Data.Monoid.Factorial (
   -- * Classes
   FactorialMonoid(..), StableFactorialMonoid,
   -- * Monad function equivalents
   mapM, mapM_
   )
where

import Control.Arrow (first)
import qualified Control.Monad as Monad
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.Numbers.Primes (primeFactors)

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

import Prelude hiding (break, drop, dropWhile, foldl, foldr, last, length, map, mapM, mapM_, 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:
-- 
-- > mconcat . factors == id
-- > null == List.null . factors
-- > List.all (\prime-> factors prime == [prime]) . 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
-- > foldl f a == List.foldl f a . factors
-- > foldl' f a == List.foldl' f a . factors
-- > foldr f a == List.foldr f a . 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 must implement 'factors' or 'splitPrimePrefix'. Other methods are provided and should
-- be implemented only for performance reasons.
class MonoidNull m => FactorialMonoid m where
   -- | Returns a list of all prime factors; inverse of mconcat.
   factors :: m -> [m]
   -- | The prime prefix, 'mempty' if none.
   primePrefix :: m -> m
   -- | The prime suffix, 'mempty' if none.
   primeSuffix :: m -> m
   -- | 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.foldl' from "Data.List" on the list of 'primes'.
   foldl :: (a -> m -> a) -> a -> m -> a
   -- | Like 'List.foldl'' from "Data.List" on the list of 'primes'.
   foldl' :: (a -> m -> a) -> a -> m -> a
   -- | Like 'List.foldr' from "Data.List" on the list of 'primes'.
   foldr :: (m -> a -> a) -> a -> m -> a
   -- | The 'length' of the list of 'primes'.
   length :: m -> Int
   -- | Generalizes 'foldMap' from "Data.Foldable", except the function arguments are prime factors rather than the
   -- structure elements.
   foldMap :: Monoid n => (m -> n) -> m -> n
   -- | Like 'List.span' from "Data.List" on the list of 'primes'.
   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 'primes'.
   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
   -- | Equivalent to 'List.reverse' from "Data.List".
   reverse :: m -> m

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

-- | A subclass of 'FactorialMonoid' whose instances satisfy this additional law:
--
-- > factors (a <> b) == factors a <> factors b
class (FactorialMonoid m, PositiveMonoid m) => StableFactorialMonoid m

instance FactorialMonoid () where
   factors :: () -> [()]
factors () = []
   primePrefix :: () -> ()
primePrefix () = ()
   primeSuffix :: () -> ()
primeSuffix () = ()
   splitPrimePrefix :: () -> Maybe ((), ())
splitPrimePrefix () = Maybe ((), ())
forall a. Maybe a
Nothing
   splitPrimeSuffix :: () -> Maybe ((), ())
splitPrimeSuffix () = Maybe ((), ())
forall a. Maybe a
Nothing
   length :: () -> Int
length () = Int
0
   reverse :: () -> ()
reverse = () -> ()
forall a. a -> a
id

instance FactorialMonoid a => FactorialMonoid (Dual a) where
   factors :: Dual a -> [Dual a]
factors (Dual 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. FactorialMonoid m => m -> m
reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a -> [a]
forall m. FactorialMonoid m => m -> [m]
factors a
a)
   length :: Dual a -> Int
length (Dual a
a) = a -> Int
forall m. FactorialMonoid m => m -> Int
length a
a
   primePrefix :: Dual a -> Dual a
primePrefix (Dual a
a) = a -> Dual a
forall a. a -> Dual a
Dual (a -> a
forall m. FactorialMonoid m => m -> m
primeSuffix a
a)
   primeSuffix :: Dual a -> Dual a
primeSuffix (Dual a
a) = a -> Dual a
forall a. a -> Dual a
Dual (a -> a
forall m. FactorialMonoid m => m -> m
primePrefix a
a)
   splitPrimePrefix :: Dual a -> Maybe (Dual a, Dual a)
splitPrimePrefix (Dual a
a) = case a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a
                               of Maybe (a, a)
Nothing -> Maybe (Dual a, Dual a)
forall a. Maybe a
Nothing
                                  Just (a
p, a
s) -> (Dual a, Dual a) -> Maybe (Dual a, Dual a)
forall a. a -> Maybe a
Just (a -> Dual a
forall a. a -> Dual a
Dual a
s, a -> Dual a
forall a. a -> Dual a
Dual a
p)
   splitPrimeSuffix :: Dual a -> Maybe (Dual a, Dual a)
splitPrimeSuffix (Dual a
a) = case a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a
                               of Maybe (a, a)
Nothing -> Maybe (Dual a, Dual a)
forall a. Maybe a
Nothing
                                  Just (a
p, a
s) -> (Dual a, Dual a) -> Maybe (Dual a, Dual a)
forall a. a -> Maybe a
Just (a -> Dual a
forall a. a -> Dual a
Dual a
s, a -> Dual a
forall a. a -> Dual a
Dual a
p)
   inits :: Dual a -> [Dual a]
inits (Dual a
a) = (a -> Dual a) -> [a] -> [Dual a]
forall (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. FactorialMonoid m => m -> m
reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a -> [a]
forall m. FactorialMonoid m => m -> [m]
tails a
a)
   tails :: Dual a -> [Dual a]
tails (Dual a
a) = (a -> Dual a) -> [a] -> [Dual a]
forall (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. FactorialMonoid 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)
   reverse :: Dual a -> Dual a
reverse (Dual a
a) = a -> Dual a
forall a. a -> Dual a
Dual (a -> a
forall m. FactorialMonoid m => m -> m
reverse a
a)

instance (Integral a, Eq a) => FactorialMonoid (Sum a) where
   primePrefix :: Sum a -> Sum a
primePrefix (Sum a
a) = a -> Sum a
forall a. a -> Sum a
Sum (a -> a
forall a. Num a => a -> a
signum a
a )
   primeSuffix :: Sum a -> Sum a
primeSuffix = Sum a -> Sum a
forall m. FactorialMonoid m => m -> m
primePrefix
   splitPrimePrefix :: Sum a -> Maybe (Sum a, Sum a)
splitPrimePrefix (Sum a
0) = Maybe (Sum a, Sum a)
forall a. Maybe a
Nothing
   splitPrimePrefix (Sum a
a) = (Sum a, Sum a) -> Maybe (Sum a, Sum a)
forall a. a -> Maybe a
Just (a -> Sum a
forall a. a -> Sum a
Sum (a -> a
forall a. Num a => a -> a
signum a
a), a -> Sum a
forall a. a -> Sum a
Sum (a
a a -> a -> a
forall a. Num a => a -> a -> a
- a -> a
forall a. Num a => a -> a
signum a
a))
   splitPrimeSuffix :: Sum a -> Maybe (Sum a, Sum a)
splitPrimeSuffix (Sum a
0) = Maybe (Sum a, Sum a)
forall a. Maybe a
Nothing
   splitPrimeSuffix (Sum a
a) = (Sum a, Sum a) -> Maybe (Sum a, Sum a)
forall a. a -> Maybe a
Just (a -> Sum a
forall a. a -> Sum a
Sum (a
a a -> a -> a
forall a. Num a => a -> a -> a
- a -> a
forall a. Num a => a -> a
signum a
a), a -> Sum a
forall a. a -> Sum a
Sum (a -> a
forall a. Num a => a -> a
signum a
a))
   length :: Sum a -> Int
length (Sum a
a) = Int -> Int
forall a. Num a => a -> a
abs (a -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
a)
   reverse :: Sum a -> Sum a
reverse = Sum a -> Sum a
forall a. a -> a
id

instance Integral a => FactorialMonoid (Product a) where
   factors :: Product a -> [Product a]
factors (Product a
a) = (a -> Product a) -> [a] -> [Product a]
forall a b. (a -> b) -> [a] -> [b]
List.map a -> Product a
forall a. a -> Product a
Product (a -> [a]
forall int. Integral int => int -> [int]
primeFactors a
a)
   reverse :: Product a -> Product a
reverse = Product a -> Product a
forall a. a -> a
id

instance FactorialMonoid a => FactorialMonoid (Maybe a) where
   factors :: Maybe a -> [Maybe a]
factors Maybe a
Nothing = []
   factors (Just a
a) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
a = [a -> Maybe a
forall a. a -> Maybe a
Just a
a]
                    | Bool
otherwise = (a -> Maybe a) -> [a] -> [Maybe a]
forall a b. (a -> b) -> [a] -> [b]
List.map a -> Maybe a
forall a. a -> Maybe a
Just (a -> [a]
forall m. FactorialMonoid m => m -> [m]
factors a
a)
   length :: Maybe a -> Int
length Maybe a
Nothing = Int
0
   length (Just a
a) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
a = Int
1
                   | Bool
otherwise = a -> Int
forall m. FactorialMonoid m => m -> Int
length a
a
   reverse :: Maybe a -> Maybe a
reverse = (a -> a) -> Maybe a -> Maybe a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> a
forall m. FactorialMonoid m => m -> m
reverse

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

{-# INLINE fromFst #-}
fromFst :: Monoid b => a -> (a, b)
fromFst :: a -> (a, b)
fromFst 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 = (a
forall a. Monoid a => a
mempty, b
b)

instance (FactorialMonoid a, FactorialMonoid b, FactorialMonoid c) => FactorialMonoid (a, b, c) where
   factors :: (a, b, c) -> [(a, b, c)]
factors (a
a, b
b, c
c) = (a -> (a, b, c)) -> [a] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty)) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
factors a
a)
                       [(a, b, c)] -> [(a, b, c)] -> [(a, b, c)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b, c)) -> [b] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
forall a. Monoid a => a
mempty, b
b1, c
forall a. Monoid a => a
mempty)) (b -> [b]
forall m. FactorialMonoid m => m -> [m]
factors b
b)
                       [(a, b, c)] -> [(a, b, c)] -> [(a, b, c)]
forall a. [a] -> [a] -> [a]
++ (c -> (a, b, c)) -> [c] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
c1)) (c -> [c]
forall m. FactorialMonoid m => m -> [m]
factors c
c)
   primePrefix :: (a, b, c) -> (a, b, c)
primePrefix (a
a, b
b, c
c) | Bool -> Bool
not (a -> Bool
forall m. MonoidNull m => m -> Bool
null a
a) = (a -> a
forall m. FactorialMonoid m => m -> m
primePrefix a
a, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty)
                         | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
b) = (a
forall a. Monoid a => a
mempty, b -> b
forall m. FactorialMonoid m => m -> m
primePrefix b
b, c
forall a. Monoid a => a
mempty)
                         | Bool
otherwise = (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c -> c
forall m. FactorialMonoid m => m -> m
primePrefix c
c)
   primeSuffix :: (a, b, c) -> (a, b, c)
primeSuffix (a
a, b
b, c
c) | Bool -> Bool
not (c -> Bool
forall m. MonoidNull m => m -> Bool
null c
c) = (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c -> c
forall m. FactorialMonoid m => m -> m
primeSuffix c
c)
                         | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
b) = (a
forall a. Monoid a => a
mempty, b -> b
forall m. FactorialMonoid m => m -> m
primeSuffix b
b, c
forall a. Monoid a => a
mempty)
                         | Bool
otherwise = (a -> a
forall m. FactorialMonoid m => m -> m
primeSuffix a
a, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty)
   splitPrimePrefix :: (a, b, c) -> Maybe ((a, b, c), (a, b, c))
splitPrimePrefix (a
a, b
b, c
c) = case (a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a, b -> Maybe (b, b)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix b
b, c -> Maybe (c, c)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix c
c)
                                of (Just (a
ap, a
as), Maybe (b, b)
_, Maybe (c, c)
_) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty), (a
as, b
b, c
c))
                                   (Maybe (a, a)
Nothing, Just (b
bp, b
bs), Maybe (c, c)
_) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
a, b
bp, c
forall a. Monoid a => a
mempty), (a
a, b
bs, c
c))
                                   (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Just (c
cp, c
cs)) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
a, b
b, c
cp), (a
a, b
b, c
cs))
                                   (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Maybe (c, c)
Nothing) -> Maybe ((a, b, c), (a, b, c))
forall a. Maybe a
Nothing
   splitPrimeSuffix :: (a, b, c) -> Maybe ((a, b, c), (a, b, c))
splitPrimeSuffix (a
a, b
b, c
c) = case (a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a, b -> Maybe (b, b)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix b
b, c -> Maybe (c, c)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix c
c)
                                of (Maybe (a, a)
_, Maybe (b, b)
_, Just (c
cp, c
cs)) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
a, b
b, c
cp), (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
cs))
                                   (Maybe (a, a)
_, Just (b
bp, b
bs), Maybe (c, c)
Nothing) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
a, b
bp, c
c), (a
forall a. Monoid a => a
mempty, b
bs, c
c))
                                   (Just (a
ap, a
as), Maybe (b, b)
Nothing, Maybe (c, c)
Nothing) -> ((a, b, c), (a, b, c)) -> Maybe ((a, b, c), (a, b, c))
forall a. a -> Maybe a
Just ((a
ap, b
b, c
c), (a
as, b
b, c
c))
                                   (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Maybe (c, c)
Nothing) -> Maybe ((a, b, c), (a, b, c))
forall a. Maybe a
Nothing
   inits :: (a, b, c) -> [(a, b, c)]
inits (a
a, b
b, c
c) = (a -> (a, b, c)) -> [a] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty)) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
inits a
a)
                     [(a, b, c)] -> [(a, b, c)] -> [(a, b, c)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b, c)) -> [b] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
a, b
b1, c
forall a. Monoid a => a
mempty)) ([b] -> [b]
forall a. [a] -> [a]
List.tail ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ b -> [b]
forall m. FactorialMonoid m => m -> [m]
inits b
b)
                     [(a, b, c)] -> [(a, b, c)] -> [(a, b, c)]
forall a. [a] -> [a] -> [a]
++ (c -> (a, b, c)) -> [c] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
a, b
b, c
c1)) ([c] -> [c]
forall a. [a] -> [a]
List.tail ([c] -> [c]) -> [c] -> [c]
forall a b. (a -> b) -> a -> b
$ c -> [c]
forall m. FactorialMonoid m => m -> [m]
inits c
c)
   tails :: (a, b, c) -> [(a, b, c)]
tails (a
a, b
b, c
c) = (a -> (a, b, c)) -> [a] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
b, c
c)) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
tails a
a)
                     [(a, b, c)] -> [(a, b, c)] -> [(a, b, c)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b, c)) -> [b] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
forall a. Monoid a => a
mempty, b
b1, c
c)) ([b] -> [b]
forall a. [a] -> [a]
List.tail ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ b -> [b]
forall m. FactorialMonoid m => m -> [m]
tails b
b)
                     [(a, b, c)] -> [(a, b, c)] -> [(a, b, c)]
forall a. [a] -> [a] -> [a]
++ (c -> (a, b, c)) -> [c] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
c1)) ([c] -> [c]
forall a. [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)
   foldl :: (a -> (a, b, c) -> a) -> a -> (a, b, c) -> a
foldl a -> (a, b, c) -> a
f a
s0 (a
a, b
b, c
c) = (a -> c -> a) -> a -> c -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl a -> c -> a
f3 ((a -> b -> a) -> a -> b -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl a -> b -> a
f2 ((a -> a -> a) -> a -> a -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl a -> a -> a
f1 a
s0 a
a) b
b) c
c
      where f1 :: a -> a -> a
f1 a
x = a -> (a, b, c) -> a
f a
x ((a, b, c) -> a) -> (a -> (a, b, c)) -> a -> a
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
            f2 :: a -> b -> a
f2 a
x = a -> (a, b, c) -> a
f a
x ((a, b, c) -> a) -> (b -> (a, b, c)) -> b -> a
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
            f3 :: a -> c -> a
f3 a
x = a -> (a, b, c) -> a
f a
x ((a, b, c) -> a) -> (c -> (a, b, c)) -> c -> a
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
   foldl' :: (a -> (a, b, c) -> a) -> a -> (a, b, c) -> a
foldl' a -> (a, b, c) -> a
f a
s0 (a
a, b
b, c
c) = a
a' a -> a -> a
`seq` a
b' a -> a -> a
`seq` (a -> c -> a) -> a -> c -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl' a -> c -> a
f3 a
b' c
c
      where f1 :: a -> a -> a
f1 a
x = a -> (a, b, c) -> a
f a
x ((a, b, c) -> a) -> (a -> (a, b, c)) -> a -> a
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
            f2 :: a -> b -> a
f2 a
x = a -> (a, b, c) -> a
f a
x ((a, b, c) -> a) -> (b -> (a, b, c)) -> b -> a
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
            f3 :: a -> c -> a
f3 a
x = a -> (a, b, c) -> a
f a
x ((a, b, c) -> a) -> (c -> (a, b, c)) -> c -> a
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
            a' :: a
a' = (a -> a -> a) -> a -> a -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl' a -> a -> a
f1 a
s0 a
a
            b' :: a
b' = (a -> b -> a) -> a -> b -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl' a -> b -> a
f2 a
a' b
b
   foldr :: ((a, b, c) -> a -> a) -> a -> (a, b, c) -> a
foldr (a, b, c) -> a -> a
f a
s (a
a, b
b, c
c) = (a -> a -> a) -> a -> a -> a
forall m a. FactorialMonoid m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c) -> a -> a
f ((a, b, c) -> a -> a) -> (a -> (a, b, c)) -> a -> a -> a
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) ((b -> a -> a) -> a -> b -> a
forall m a. FactorialMonoid m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c) -> a -> a
f ((a, b, c) -> a -> a) -> (b -> (a, b, c)) -> b -> a -> a
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) ((c -> a -> a) -> a -> c -> a
forall m a. FactorialMonoid m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c) -> a -> a
f ((a, b, c) -> a -> a) -> (c -> (a, b, c)) -> c -> a -> a
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) a
s c
c) b
b) a
a
   foldMap :: ((a, b, c) -> n) -> (a, b, c) -> n
foldMap (a, b, c) -> n
f (a
a, b
b, c
c) = (a -> n) -> a -> n
forall m n. (FactorialMonoid m, Monoid n) => (m -> n) -> m -> n
Data.Monoid.Factorial.foldMap ((a, b, c) -> n
f ((a, b, c) -> n) -> (a -> (a, b, c)) -> a -> n
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
                         n -> n -> n
forall a. Monoid a => a -> a -> a
`mappend` (b -> n) -> b -> n
forall m n. (FactorialMonoid m, Monoid n) => (m -> n) -> m -> n
Data.Monoid.Factorial.foldMap ((a, b, c) -> n
f ((a, b, c) -> n) -> (b -> (a, b, c)) -> b -> n
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
                         n -> n -> n
forall a. Monoid a => a -> a -> a
`mappend` (c -> n) -> c -> n
forall m n. (FactorialMonoid m, Monoid n) => (m -> n) -> m -> n
Data.Monoid.Factorial.foldMap ((a, b, c) -> n
f ((a, b, c) -> n) -> (c -> (a, b, c)) -> c -> n
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
   length :: (a, b, c) -> Int
length (a
a, b
b, c
c) = a -> Int
forall m. FactorialMonoid m => m -> Int
length a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ b -> Int
forall m. FactorialMonoid m => m -> Int
length b
b Int -> Int -> Int
forall a. Num a => a -> a -> a
+ c -> Int
forall m. FactorialMonoid m => m -> Int
length c
c
   span :: ((a, b, c) -> Bool) -> (a, b, c) -> ((a, b, c), (a, b, c))
span (a, b, c) -> Bool
p (a
a, b
b, c
c) = ((a
ap, b
bp, c
cp), (a
as, b
bs, c
cs))
      where (a
ap, a
as) = (a -> Bool) -> a -> (a, a)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c) -> Bool
p ((a, b, c) -> Bool) -> (a -> (a, b, c)) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c)
forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) a
a
            (b
bp, b
bs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as = (b -> Bool) -> b -> (b, b)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c) -> Bool
p ((a, b, c) -> Bool) -> (b -> (a, b, c)) -> b -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c)
forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) b
b
                     | Bool
otherwise = (b
forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs = (c -> Bool) -> c -> (c, c)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c) -> Bool
p ((a, b, c) -> Bool) -> (c -> (a, b, c)) -> c -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c)
forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3) c
c
                     | Bool
otherwise = (c
forall a. Monoid a => a
mempty, c
c)
   spanMaybe :: s
-> (s -> (a, b, c) -> Maybe s)
-> (a, b, c)
-> ((a, b, c), (a, b, c), s)
spanMaybe s
s0 s -> (a, b, c) -> Maybe s
f (a
a, b
b, c
c) | Bool -> Bool
not (a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty), (a
as, b
b, c
c), s
s1)
                            | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, c
forall a. Monoid a => a
mempty), (a
as, b
bs, c
c), s
s2)
                            | Bool
otherwise = ((a
ap, b
bp, c
cp), (a
as, b
bs, c
cs), s
s3)
     where (a
ap, a
as, s
s1) = s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s0 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (a -> (a, b, c)) -> a -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c)
forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) a
a
           (b
bp, b
bs, s
s2) = s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s1 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (b -> (a, b, c)) -> b -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c)
forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) b
b
           (c
cp, c
cs, s
s3) = s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s2 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (c -> (a, b, c)) -> c -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c)
forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3) c
c
   spanMaybe' :: s
-> (s -> (a, b, c) -> Maybe s)
-> (a, b, c)
-> ((a, b, c), (a, b, c), s)
spanMaybe' s
s0 s -> (a, b, c) -> Maybe s
f (a
a, b
b, c
c) | Bool -> Bool
not (a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty), (a
as, b
b, c
c), s
s1)
                             | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, c
forall a. Monoid a => a
mempty), (a
as, b
bs, c
c), s
s2)
                             | Bool
otherwise = ((a
ap, b
bp, c
cp), (a
as, b
bs, c
cs), s
s3)
     where (a
ap, a
as, s
s1) = s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s0 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (a -> (a, b, c)) -> a -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c)
forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) a
a
           (b
bp, b
bs, s
s2) = s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s1 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (b -> (a, b, c)) -> b -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c)
forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) b
b
           (c
cp, c
cs, s
s3) = s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s2 (\s
s-> s -> (a, b, c) -> Maybe s
f s
s ((a, b, c) -> Maybe s) -> (c -> (a, b, c)) -> c -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c)
forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3) c
c
   splitAt :: Int -> (a, b, c) -> ((a, b, c), (a, b, c))
splitAt Int
n (a
a, b
b, c
c) = ((a
ap, b
bp, c
cp), (a
as, b
bs, c
cs))
      where (a
ap, a
as) = Int -> a -> (a, a)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n a
a
            (b
bp, b
bs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as = Int -> b -> (b, b)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall m. FactorialMonoid m => m -> Int
length a
a) b
b
                     | Bool
otherwise = (b
forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs = Int -> c -> (c, c)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall m. FactorialMonoid m => m -> Int
length a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall m. FactorialMonoid m => m -> Int
length b
b) c
c
                     | Bool
otherwise = (c
forall a. Monoid a => a
mempty, c
c)
   reverse :: (a, b, c) -> (a, b, c)
reverse (a
a, b
b, c
c) = (a -> a
forall m. FactorialMonoid m => m -> m
reverse a
a, b -> b
forall m. FactorialMonoid m => m -> m
reverse b
b, c -> c
forall m. FactorialMonoid m => m -> m
reverse c
c)

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

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

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

instance (FactorialMonoid a, FactorialMonoid b, FactorialMonoid c, FactorialMonoid d) =>
         FactorialMonoid (a, b, c, d) where
   factors :: (a, b, c, d) -> [(a, b, c, d)]
factors (a
a, b
b, c
c, d
d) = (a -> (a, b, c, d)) -> [a] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
factors a
a)
                          [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b, c, d)) -> [b] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
forall a. Monoid a => a
mempty, b
b1, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)) (b -> [b]
forall m. FactorialMonoid m => m -> [m]
factors b
b)
                          [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (c -> (a, b, c, d)) -> [c] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
c1, d
forall a. Monoid a => a
mempty)) (c -> [c]
forall m. FactorialMonoid m => m -> [m]
factors c
c)
                          [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (d -> (a, b, c, d)) -> [d] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\d
d1-> (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
d1)) (d -> [d]
forall m. FactorialMonoid m => m -> [m]
factors d
d)
   primePrefix :: (a, b, c, d) -> (a, b, c, d)
primePrefix (a
a, b
b, c
c, d
d) | Bool -> Bool
not (a -> Bool
forall m. MonoidNull m => m -> Bool
null a
a) = (a -> a
forall m. FactorialMonoid m => m -> m
primePrefix a
a, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)
                            | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
b) = (a
forall a. Monoid a => a
mempty, b -> b
forall m. FactorialMonoid m => m -> m
primePrefix b
b, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)
                            | Bool -> Bool
not (c -> Bool
forall m. MonoidNull m => m -> Bool
null c
c) = (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c -> c
forall m. FactorialMonoid m => m -> m
primePrefix c
c, d
forall a. Monoid a => a
mempty)
                            | Bool
otherwise    = (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d -> d
forall m. FactorialMonoid m => m -> m
primePrefix d
d)
   primeSuffix :: (a, b, c, d) -> (a, b, c, d)
primeSuffix (a
a, b
b, c
c, d
d) | Bool -> Bool
not (d -> Bool
forall m. MonoidNull m => m -> Bool
null 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
forall m. FactorialMonoid m => m -> m
primeSuffix d
d)
                            | Bool -> Bool
not (c -> Bool
forall m. MonoidNull m => m -> Bool
null c
c) = (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c -> c
forall m. FactorialMonoid m => m -> m
primeSuffix c
c, d
forall a. Monoid a => a
mempty)
                            | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
b) = (a
forall a. Monoid a => a
mempty, b -> b
forall m. FactorialMonoid m => m -> m
primeSuffix b
b, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)
                            | Bool
otherwise    = (a -> a
forall m. FactorialMonoid m => m -> m
primeSuffix a
a, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)
   splitPrimePrefix :: (a, b, c, d) -> Maybe ((a, b, c, d), (a, b, c, d))
splitPrimePrefix (a
a, b
b, c
c, d
d) = case (a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix a
a, b -> Maybe (b, b)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix b
b, c -> Maybe (c, c)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix c
c, d -> Maybe (d, d)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimePrefix d
d)
                                   of (Just (a
ap, a
as), Maybe (b, b)
_, Maybe (c, c)
_, Maybe (d, d)
_) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
as, b
b, c
c, d
d))
                                      (Maybe (a, a)
Nothing, Just (b
bp, b
bs), Maybe (c, c)
_, Maybe (d, d)
_) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
bp, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
a, b
bs, c
c, d
d))
                                      (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Just (c
cp, c
cs), Maybe (d, d)
_) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
b, c
cp, d
forall a. Monoid a => a
mempty), (a
a, b
b, c
cs, d
d))
                                      (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Maybe (c, c)
Nothing, Just (d
dp, d
ds)) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
b, c
c, d
dp), (a
a, b
b, c
c, d
ds))
                                      (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Maybe (c, c)
Nothing, Maybe (d, d)
Nothing) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. Maybe a
Nothing
   splitPrimeSuffix :: (a, b, c, d) -> Maybe ((a, b, c, d), (a, b, c, d))
splitPrimeSuffix (a
a, b
b, c
c, d
d) = case (a -> Maybe (a, a)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix a
a, b -> Maybe (b, b)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix b
b, c -> Maybe (c, c)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix c
c, d -> Maybe (d, d)
forall m. FactorialMonoid m => m -> Maybe (m, m)
splitPrimeSuffix d
d)
                                   of (Maybe (a, a)
_, Maybe (b, b)
_, Maybe (c, c)
_, Just (d
dp, d
ds)) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
b, c
c, d
dp), (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
ds))
                                      (Maybe (a, a)
_, Maybe (b, b)
_, Just (c
cp, c
cs), Maybe (d, d)
Nothing) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
b, c
cp, d
d), (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
cs, d
d))
                                      (Maybe (a, a)
_, Just (b
bp, b
bs), Maybe (c, c)
Nothing, Maybe (d, d)
Nothing) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
a, b
bp, c
c, d
d), (a
forall a. Monoid a => a
mempty, b
bs, c
c, d
d))
                                      (Just (a
ap, a
as), Maybe (b, b)
Nothing, Maybe (c, c)
Nothing, Maybe (d, d)
Nothing) -> ((a, b, c, d), (a, b, c, d)) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. a -> Maybe a
Just ((a
ap, b
b, c
c, d
d), (a
as, b
b, c
c, d
d))
                                      (Maybe (a, a)
Nothing, Maybe (b, b)
Nothing, Maybe (c, c)
Nothing, Maybe (d, d)
Nothing) -> Maybe ((a, b, c, d), (a, b, c, d))
forall a. Maybe a
Nothing
   inits :: (a, b, c, d) -> [(a, b, c, d)]
inits (a
a, b
b, c
c, d
d) = (a -> (a, b, c, d)) -> [a] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
inits a
a)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b, c, d)) -> [b] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
a, b
b1, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)) ([b] -> [b]
forall a. [a] -> [a]
List.tail ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ b -> [b]
forall m. FactorialMonoid m => m -> [m]
inits b
b)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (c -> (a, b, c, d)) -> [c] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
a, b
b, c
c1, d
forall a. Monoid a => a
mempty)) ([c] -> [c]
forall a. [a] -> [a]
List.tail ([c] -> [c]) -> [c] -> [c]
forall a b. (a -> b) -> a -> b
$ c -> [c]
forall m. FactorialMonoid m => m -> [m]
inits c
c)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (d -> (a, b, c, d)) -> [d] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\d
d1-> (a
a, b
b, c
c, d
d1)) ([d] -> [d]
forall a. [a] -> [a]
List.tail ([d] -> [d]) -> [d] -> [d]
forall a b. (a -> b) -> a -> b
$ d -> [d]
forall m. FactorialMonoid m => m -> [m]
inits d
d)
   tails :: (a, b, c, d) -> [(a, b, c, d)]
tails (a
a, b
b, c
c, d
d) = (a -> (a, b, c, d)) -> [a] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, b
b, c
c, d
d)) (a -> [a]
forall m. FactorialMonoid m => m -> [m]
tails a
a)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (b -> (a, b, c, d)) -> [b] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (a
forall a. Monoid a => a
mempty, b
b1, c
c, d
d)) ([b] -> [b]
forall a. [a] -> [a]
List.tail ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ b -> [b]
forall m. FactorialMonoid m => m -> [m]
tails b
b)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (c -> (a, b, c, d)) -> [c] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
c1, d
d)) ([c] -> [c]
forall a. [a] -> [a]
List.tail ([c] -> [c]) -> [c] -> [c]
forall a b. (a -> b) -> a -> b
$ c -> [c]
forall m. FactorialMonoid m => m -> [m]
tails c
c)
                        [(a, b, c, d)] -> [(a, b, c, d)] -> [(a, b, c, d)]
forall a. [a] -> [a] -> [a]
++ (d -> (a, b, c, d)) -> [d] -> [(a, b, c, d)]
forall a b. (a -> b) -> [a] -> [b]
List.map (\d
d1-> (a
forall a. Monoid a => a
mempty, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
d1)) ([d] -> [d]
forall a. [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)
   foldl :: (a -> (a, b, c, d) -> a) -> a -> (a, b, c, d) -> a
foldl a -> (a, b, c, d) -> a
f a
s0 (a
a, b
b, c
c, d
d) = (a -> d -> a) -> a -> d -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl a -> d -> a
f4 ((a -> c -> a) -> a -> c -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl a -> c -> a
f3 ((a -> b -> a) -> a -> b -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl a -> b -> a
f2 ((a -> a -> a) -> a -> a -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl a -> a -> a
f1 a
s0 a
a) b
b) c
c) d
d
      where f1 :: a -> a -> a
f1 a
x = a -> (a, b, c, d) -> a
f a
x ((a, b, c, d) -> a) -> (a -> (a, b, c, d)) -> a -> a
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
            f2 :: a -> b -> a
f2 a
x = a -> (a, b, c, d) -> a
f a
x ((a, b, c, d) -> a) -> (b -> (a, b, c, d)) -> b -> a
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
            f3 :: a -> c -> a
f3 a
x = a -> (a, b, c, d) -> a
f a
x ((a, b, c, d) -> a) -> (c -> (a, b, c, d)) -> c -> a
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
            f4 :: a -> d -> a
f4 a
x = a -> (a, b, c, d) -> a
f a
x ((a, b, c, d) -> a) -> (d -> (a, b, c, d)) -> d -> a
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
   foldl' :: (a -> (a, b, c, d) -> a) -> a -> (a, b, c, d) -> a
foldl' a -> (a, b, c, d) -> a
f a
s0 (a
a, b
b, c
c, d
d) = a
a' a -> a -> a
`seq` a
b' a -> a -> a
`seq` a
c' a -> a -> a
`seq` (a -> d -> a) -> a -> d -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl' a -> d -> a
f4 a
c' d
d
      where f1 :: a -> a -> a
f1 a
x = a -> (a, b, c, d) -> a
f a
x ((a, b, c, d) -> a) -> (a -> (a, b, c, d)) -> a -> a
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
            f2 :: a -> b -> a
f2 a
x = a -> (a, b, c, d) -> a
f a
x ((a, b, c, d) -> a) -> (b -> (a, b, c, d)) -> b -> a
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
            f3 :: a -> c -> a
f3 a
x = a -> (a, b, c, d) -> a
f a
x ((a, b, c, d) -> a) -> (c -> (a, b, c, d)) -> c -> a
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
            f4 :: a -> d -> a
f4 a
x = a -> (a, b, c, d) -> a
f a
x ((a, b, c, d) -> a) -> (d -> (a, b, c, d)) -> d -> a
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
            a' :: a
a' = (a -> a -> a) -> a -> a -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl' a -> a -> a
f1 a
s0 a
a
            b' :: a
b' = (a -> b -> a) -> a -> b -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl' a -> b -> a
f2 a
a' b
b
            c' :: a
c' = (a -> c -> a) -> a -> c -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl' a -> c -> a
f3 a
b' c
c
   foldr :: ((a, b, c, d) -> a -> a) -> a -> (a, b, c, d) -> a
foldr (a, b, c, d) -> a -> a
f a
s (a
a, b
b, c
c, d
d) =
      (a -> a -> a) -> a -> a -> a
forall m a. FactorialMonoid m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f ((a, b, c, d) -> a -> a) -> (a -> (a, b, c, d)) -> a -> a -> a
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) ((b -> a -> a) -> a -> b -> a
forall m a. FactorialMonoid m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f ((a, b, c, d) -> a -> a) -> (b -> (a, b, c, d)) -> b -> a -> a
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) ((c -> a -> a) -> a -> c -> a
forall m a. FactorialMonoid m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f ((a, b, c, d) -> a -> a) -> (c -> (a, b, c, d)) -> c -> a -> a
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) ((d -> a -> a) -> a -> d -> a
forall m a. FactorialMonoid m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f ((a, b, c, d) -> a -> a) -> (d -> (a, b, c, d)) -> d -> a -> a
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) a
s d
d) c
c) b
b) a
a
   foldMap :: ((a, b, c, d) -> n) -> (a, b, c, d) -> n
foldMap (a, b, c, d) -> n
f (a
a, b
b, c
c, d
d) = (a -> n) -> a -> n
forall m n. (FactorialMonoid m, Monoid n) => (m -> n) -> m -> n
Data.Monoid.Factorial.foldMap ((a, b, c, d) -> n
f ((a, b, c, d) -> n) -> (a -> (a, b, c, d)) -> a -> n
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
                            n -> n -> n
forall a. Monoid a => a -> a -> a
`mappend` (b -> n) -> b -> n
forall m n. (FactorialMonoid m, Monoid n) => (m -> n) -> m -> n
Data.Monoid.Factorial.foldMap ((a, b, c, d) -> n
f ((a, b, c, d) -> n) -> (b -> (a, b, c, d)) -> b -> n
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
                            n -> n -> n
forall a. Monoid a => a -> a -> a
`mappend` (c -> n) -> c -> n
forall m n. (FactorialMonoid m, Monoid n) => (m -> n) -> m -> n
Data.Monoid.Factorial.foldMap ((a, b, c, d) -> n
f ((a, b, c, d) -> n) -> (c -> (a, b, c, d)) -> c -> n
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
                            n -> n -> n
forall a. Monoid a => a -> a -> a
`mappend` (d -> n) -> d -> n
forall m n. (FactorialMonoid m, Monoid n) => (m -> n) -> m -> n
Data.Monoid.Factorial.foldMap ((a, b, c, d) -> n
f ((a, b, c, d) -> n) -> (d -> (a, b, c, d)) -> d -> n
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
   length :: (a, b, c, d) -> Int
length (a
a, b
b, c
c, d
d) = a -> Int
forall m. FactorialMonoid m => m -> Int
length a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ b -> Int
forall m. FactorialMonoid m => m -> Int
length b
b Int -> Int -> Int
forall a. Num a => a -> a -> a
+ c -> Int
forall m. FactorialMonoid m => m -> Int
length c
c Int -> Int -> Int
forall a. Num a => a -> a -> a
+ d -> Int
forall m. FactorialMonoid m => m -> Int
length d
d
   span :: ((a, b, c, d) -> Bool)
-> (a, b, c, d) -> ((a, b, c, d), (a, b, c, d))
span (a, b, c, d) -> Bool
p (a
a, b
b, c
c, d
d) = ((a
ap, b
bp, c
cp, d
dp), (a
as, b
bs, c
cs, d
ds))
      where (a
ap, a
as) = (a -> Bool) -> a -> (a, a)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p ((a, b, c, d) -> Bool) -> (a -> (a, b, c, d)) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c, d)
forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4) a
a
            (b
bp, b
bs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as = (b -> Bool) -> b -> (b, b)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p ((a, b, c, d) -> Bool) -> (b -> (a, b, c, d)) -> b -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c, d)
forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4) b
b
                     | Bool
otherwise = (b
forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs = (c -> Bool) -> c -> (c, c)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p ((a, b, c, d) -> Bool) -> (c -> (a, b, c, d)) -> c -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c, d)
forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4) c
c
                     | Bool
otherwise = (c
forall a. Monoid a => a
mempty, c
c)
            (d
dp, d
ds) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs Bool -> Bool -> Bool
&& c -> Bool
forall m. MonoidNull m => m -> Bool
null c
cs = (d -> Bool) -> d -> (d, d)
forall m. FactorialMonoid m => (m -> Bool) -> m -> (m, m)
span ((a, b, c, d) -> Bool
p ((a, b, c, d) -> Bool) -> (d -> (a, b, c, d)) -> d -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. d -> (a, b, c, d)
forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4) d
d
                     | Bool
otherwise = (d
forall a. Monoid a => a
mempty, d
d)
   spanMaybe :: s
-> (s -> (a, b, c, d) -> Maybe s)
-> (a, b, c, d)
-> ((a, b, c, d), (a, b, c, d), s)
spanMaybe s
s0 s -> (a, b, c, d) -> Maybe s
f (a
a, b
b, c
c, d
d) | Bool -> Bool
not (a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
as, b
b, c
c, d
d), s
s1)
                               | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
as, b
bs, c
c, d
d), s
s2)
                               | Bool -> Bool
not (c -> Bool
forall m. MonoidNull m => m -> Bool
null c
cs) = ((a
ap, b
bp, c
cp, d
forall a. Monoid a => a
mempty), (a
as, b
bs, c
cs, d
d), s
s3)
                               | Bool
otherwise = ((a
ap, b
bp, c
cp, d
dp), (a
as, b
bs, c
cs, d
ds), s
s4)
     where (a
ap, a
as, s
s1) = s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s0 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (a -> (a, b, c, d)) -> a -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c, d)
forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4) a
a
           (b
bp, b
bs, s
s2) = s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s1 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (b -> (a, b, c, d)) -> b -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c, d)
forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4) b
b
           (c
cp, c
cs, s
s3) = s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s2 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (c -> (a, b, c, d)) -> c -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c, d)
forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4) c
c
           (d
dp, d
ds, s
s4) = s -> (s -> d -> Maybe s) -> d -> (d, d, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe s
s3 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (d -> (a, b, c, d)) -> d -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. d -> (a, b, c, d)
forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4) d
d
   spanMaybe' :: s
-> (s -> (a, b, c, d) -> Maybe s)
-> (a, b, c, d)
-> ((a, b, c, d), (a, b, c, d), s)
spanMaybe' s
s0 s -> (a, b, c, d) -> Maybe s
f (a
a, b
b, c
c, d
d) | Bool -> Bool
not (a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as) = ((a
ap, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
as, b
b, c
c, d
d), s
s1)
                               | Bool -> Bool
not (b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs) = ((a
ap, b
bp, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty), (a
as, b
bs, c
c, d
d), s
s2)
                               | Bool -> Bool
not (c -> Bool
forall m. MonoidNull m => m -> Bool
null c
cs) = ((a
ap, b
bp, c
cp, d
forall a. Monoid a => a
mempty), (a
as, b
bs, c
cs, d
d), s
s3)
                               | Bool
otherwise = ((a
ap, b
bp, c
cp, d
dp), (a
as, b
bs, c
cs, d
ds), s
s4)
     where (a
ap, a
as, s
s1) = s -> (s -> a -> Maybe s) -> a -> (a, a, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s0 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (a -> (a, b, c, d)) -> a -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c, d)
forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4) a
a
           (b
bp, b
bs, s
s2) = s -> (s -> b -> Maybe s) -> b -> (b, b, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s1 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (b -> (a, b, c, d)) -> b -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c, d)
forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4) b
b
           (c
cp, c
cs, s
s3) = s -> (s -> c -> Maybe s) -> c -> (c, c, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s2 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (c -> (a, b, c, d)) -> c -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c, d)
forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4) c
c
           (d
dp, d
ds, s
s4) = s -> (s -> d -> Maybe s) -> d -> (d, d, s)
forall m s.
FactorialMonoid m =>
s -> (s -> m -> Maybe s) -> m -> (m, m, s)
spanMaybe' s
s3 (\s
s-> s -> (a, b, c, d) -> Maybe s
f s
s ((a, b, c, d) -> Maybe s) -> (d -> (a, b, c, d)) -> d -> Maybe s
forall b c a. (b -> c) -> (a -> b) -> a -> c
. d -> (a, b, c, d)
forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4) d
d
   splitAt :: Int -> (a, b, c, d) -> ((a, b, c, d), (a, b, c, d))
splitAt Int
n (a
a, b
b, c
c, d
d) = ((a
ap, b
bp, c
cp, d
dp), (a
as, b
bs, c
cs, d
ds))
      where (a
ap, a
as) = Int -> a -> (a, a)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt Int
n a
a
            (b
bp, b
bs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as = Int -> b -> (b, b)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall m. FactorialMonoid m => m -> Int
length a
a) b
b
                     | Bool
otherwise = (b
forall a. Monoid a => a
mempty, b
b)
            (c
cp, c
cs) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs = Int -> c -> (c, c)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall m. FactorialMonoid m => m -> Int
length a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall m. FactorialMonoid m => m -> Int
length b
b) c
c
                     | Bool
otherwise = (c
forall a. Monoid a => a
mempty, c
c)
            (d
dp, d
ds) | a -> Bool
forall m. MonoidNull m => m -> Bool
null a
as Bool -> Bool -> Bool
&& b -> Bool
forall m. MonoidNull m => m -> Bool
null b
bs Bool -> Bool -> Bool
&& c -> Bool
forall m. MonoidNull m => m -> Bool
null c
cs = Int -> d -> (d, d)
forall m. FactorialMonoid m => Int -> m -> (m, m)
splitAt (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall m. FactorialMonoid m => m -> Int
length a
a Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall m. FactorialMonoid m => m -> Int
length b
b Int -> Int -> Int
forall a. Num a => a -> a -> a
- c -> Int
forall m. FactorialMonoid m => m -> Int
length c
c) d
d
                     | Bool
otherwise = (d
forall a. Monoid a => a
mempty, d
d)
   reverse :: (a, b, c, d) -> (a, b, c, d)
reverse (a
a, b
b, c
c, d
d) = (a -> a
forall m. FactorialMonoid m => m -> m
reverse a
a, b -> b
forall m. FactorialMonoid m => m -> m
reverse b
b, c -> c
forall m. FactorialMonoid m => m -> m
reverse c
c, d -> d
forall m. FactorialMonoid m => m -> m
reverse 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, 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 = (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 = (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 = (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
   factors :: [x] -> [[x]]
factors [x]
xs = (x -> [x]) -> [x] -> [[x]]
forall a b. (a -> b) -> [a] -> [b]
List.map (x -> [x] -> [x]
forall a. a -> [a] -> [a]
:[]) [x]
xs
   primePrefix :: [x] -> [x]
primePrefix [] = []
   primePrefix (x
x:[x]
_) = [x
x]
   primeSuffix :: [x] -> [x]
primeSuffix [] = []
   primeSuffix [x]
xs = [[x] -> x
forall a. [a] -> a
List.last [x]
xs]
   splitPrimePrefix :: [x] -> Maybe ([x], [x])
splitPrimePrefix [] = Maybe ([x], [x])
forall a. Maybe a
Nothing
   splitPrimePrefix (x
x:[x]
xs) = ([x], [x]) -> Maybe ([x], [x])
forall a. a -> Maybe a
Just ([x
x], [x]
xs)
   splitPrimeSuffix :: [x] -> Maybe ([x], [x])
splitPrimeSuffix [] = Maybe ([x], [x])
forall a. Maybe a
Nothing
   splitPrimeSuffix [x]
xs = ([x], [x]) -> Maybe ([x], [x])
forall a. a -> Maybe a
Just (([x] -> [x]) -> [x] -> ([x], [x])
forall a c. ([a] -> c) -> [a] -> (c, [a])
splitLast [x] -> [x]
forall a. a -> a
id [x]
xs)
      where splitLast :: ([a] -> c) -> [a] -> (c, [a])
splitLast [a] -> c
f last :: [a]
last@[a
_] = ([a] -> c
f [], [a]
last)
            splitLast [a] -> c
f ~(a
x:[a]
rest) = ([a] -> c) -> [a] -> (c, [a])
splitLast ([a] -> c
f ([a] -> c) -> ([a] -> [a]) -> [a] -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) [a]
rest
   inits :: [x] -> [[x]]
inits = [x] -> [[x]]
forall x. [x] -> [[x]]
List.inits
   tails :: [x] -> [[x]]
tails = [x] -> [[x]]
forall x. [x] -> [[x]]
List.tails
   foldl :: (a -> [x] -> a) -> a -> [x] -> a
foldl a -> [x] -> a
_ a
a [] = a
a
   foldl a -> [x] -> a
f a
a (x
x:[x]
xs) = (a -> [x] -> a) -> a -> [x] -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl a -> [x] -> a
f (a -> [x] -> a
f a
a [x
x]) [x]
xs
   foldl' :: (a -> [x] -> a) -> a -> [x] -> a
foldl' a -> [x] -> a
_ a
a [] = a
a
   foldl' a -> [x] -> a
f a
a (x
x:[x]
xs) = let a' :: a
a' = a -> [x] -> a
f a
a [x
x] in a
a' a -> a -> a
`seq` (a -> [x] -> a) -> a -> [x] -> a
forall m a. FactorialMonoid m => (a -> m -> a) -> a -> m -> a
foldl' a -> [x] -> a
f a
a' [x]
xs
   foldr :: ([x] -> a -> a) -> a -> [x] -> a
foldr [x] -> a -> a
_ a
f0 [] = a
f0
   foldr [x] -> a -> a
f a
f0 (x
x:[x]
xs) = [x] -> a -> a
f [x
x] (([x] -> a -> a) -> a -> [x] -> a
forall m a. FactorialMonoid m => (m -> a -> a) -> a -> m -> a
foldr [x] -> a -> a
f a
f0 [x]
xs)
   length :: [x] -> Int
length = [x] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
List.length
   foldMap :: ([x] -> n) -> [x] -> n
foldMap [x] -> n
f = [n] -> n
forall a. Monoid a => [a] -> a
mconcat ([n] -> n) -> ([x] -> [n]) -> [x] -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> n) -> [x] -> [n]
forall a b. (a -> b) -> [a] -> [b]
List.map ([x] -> n
f ([x] -> n) -> (x -> [x]) -> x -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> [x] -> [x]
forall a. a -> [a] -> [a]
:[]))
   break :: ([x] -> Bool) -> [x] -> ([x], [x])
break [x] -> Bool
f = (x -> Bool) -> [x] -> ([x], [x])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.break ([x] -> Bool
f ([x] -> Bool) -> (x -> [x]) -> x -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> [x] -> [x]
forall a. a -> [a] -> [a]
:[]))
   span :: ([x] -> Bool) -> [x] -> ([x], [x])
span [x] -> Bool
f = (x -> Bool) -> [x] -> ([x], [x])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.span ([x] -> Bool
f ([x] -> Bool) -> (x -> [x]) -> x -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> [x] -> [x]
forall a. a -> [a] -> [a]
:[]))
   dropWhile :: ([x] -> Bool) -> [x] -> [x]
dropWhile [x] -> Bool
f = (x -> Bool) -> [x] -> [x]
forall a. (a -> Bool) -> [a] -> [a]
List.dropWhile ([x] -> Bool
f ([x] -> Bool) -> (x -> [x]) -> x -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> [x] -> [x]
forall a. a -> [a] -> [a]
:[]))
   takeWhile :: ([x] -> Bool) -> [x] -> [x]
takeWhile [x] -> Bool
f = (x -> Bool) -> [x] -> [x]
forall a. (a -> Bool) -> [a] -> [a]
List.takeWhile ([x] -> Bool
f ([x] -> Bool) -> (x -> [x]) -> x -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> [x] -> [x]
forall a. a -> [a] -> [a]
:[]))
   spanMaybe :: s -> (s -> [x] -> Maybe s) -> [x] -> ([x], [x], s)
spanMaybe s
s0 s -> [x] -> Maybe s
f [x]
l = ([x] -> [x]
prefix' [], [x] -> [x]
suffix' [], s
s')
      where ([x] -> [x]
prefix', [x] -> [x]
suffix', s
s', Bool
_) = (([x] -> [x], [x] -> [x], s, Bool)
 -> x -> ([x] -> [x], [x] -> [x], s, Bool))
-> ([x] -> [x], [x] -> [x], s, Bool)
-> [x]
-> ([x] -> [x], [x] -> [x], s, Bool)
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' ([x] -> [x], [x] -> [x], s, Bool)
-> x -> ([x] -> [x], [x] -> [x], s, Bool)
forall c.
([x] -> c, [x] -> [x], s, Bool)
-> x -> ([x] -> c, [x] -> [x], s, Bool)
g ([x] -> [x]
forall a. a -> a
id, [x] -> [x]
forall a. a -> a
id, s
s0, Bool
True) [x]
l
            g :: ([x] -> c, [x] -> [x], s, Bool)
-> x -> ([x] -> c, [x] -> [x], s, Bool)
g ([x] -> c
prefix, [x] -> [x]
suffix, s
s1, Bool
live) x
x | Bool
live, Just s
s2 <- s -> [x] -> Maybe s
f s
s1 [x
x] = ([x] -> c
prefix ([x] -> c) -> ([x] -> [x]) -> [x] -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x
xx -> [x] -> [x]
forall a. a -> [a] -> [a]
:), [x] -> [x]
forall a. a -> a
id, s
s2, Bool
True)
                                           | Bool
otherwise = ([x] -> c
prefix, [x] -> [x]
suffix ([x] -> [x]) -> ([x] -> [x]) -> [x] -> [x]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x
xx -> [x] -> [x]
forall a. a -> [a] -> [a]
:), s
s1, Bool
False)
   spanMaybe' :: s -> (s -> [x] -> Maybe s) -> [x] -> ([x], [x], s)
spanMaybe' s
s0 s -> [x] -> Maybe s
f [x]
l = ([x] -> [x]
prefix' [], [x] -> [x]
suffix' [], s
s')
      where ([x] -> [x]
prefix', [x] -> [x]
suffix', s
s', Bool
_) = (([x] -> [x], [x] -> [x], s, Bool)
 -> x -> ([x] -> [x], [x] -> [x], s, Bool))
-> ([x] -> [x], [x] -> [x], s, Bool)
-> [x]
-> ([x] -> [x], [x] -> [x], s, Bool)
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' ([x] -> [x], [x] -> [x], s, Bool)
-> x -> ([x] -> [x], [x] -> [x], s, Bool)
forall c.
([x] -> c, [x] -> [x], s, Bool)
-> x -> ([x] -> c, [x] -> [x], s, Bool)
g ([x] -> [x]
forall a. a -> a
id, [x] -> [x]
forall a. a -> a
id, s
s0, Bool
True) [x]
l
            g :: ([x] -> c, [x] -> [x], s, Bool)
-> x -> ([x] -> c, [x] -> [x], s, Bool)
g ([x] -> c
prefix, [x] -> [x]
suffix, s
s1, Bool
live) x
x | Bool
live, Just s
s2 <- s -> [x] -> Maybe s
f s
s1 [x
x] = s
-> ([x] -> c, [x] -> [x], s, Bool)
-> ([x] -> c, [x] -> [x], s, Bool)
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
   reverse :: [x] -> [x]
reverse = [x] -> [x]
forall a. [a] -> [a]
List.reverse

instance FactorialMonoid ByteString.ByteString where
   factors :: ByteString -> [ByteString]
factors ByteString
x = Int -> ByteString -> [ByteString]
forall t. (Eq t, Num t, Enum t) => t -> ByteString -> [ByteString]
factorize (ByteString -> Int
ByteString.length ByteString
x) ByteString
x
      where factorize :: t -> ByteString -> [ByteString]
factorize t
0 ByteString
_ = []
            factorize t
n ByteString
xs = ByteString
xs1 ByteString -> [ByteString] -> [ByteString]
forall a. a -> [a] -> [a]
: t -> ByteString -> [ByteString]
factorize (t -> t
forall a. Enum a => a -> a
pred t
n) ByteString
xs'
              where (ByteString
xs1, ByteString
xs') = Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt Int
1 ByteString
xs
   primePrefix :: ByteString -> ByteString
primePrefix = Int -> ByteString -> ByteString
ByteString.take Int
1
   primeSuffix :: ByteString -> ByteString
primeSuffix ByteString
x = Int -> ByteString -> ByteString
ByteString.drop (ByteString -> Int
ByteString.length ByteString
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) ByteString
x
   splitPrimePrefix :: ByteString -> Maybe (ByteString, ByteString)
splitPrimePrefix ByteString
x = if ByteString -> Bool
ByteString.null ByteString
x then Maybe (ByteString, ByteString)
forall a. Maybe a
Nothing else (ByteString, ByteString) -> Maybe (ByteString, ByteString)
forall a. a -> Maybe a
Just (Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt Int
1 ByteString
x)
   splitPrimeSuffix :: ByteString -> Maybe (ByteString, ByteString)
splitPrimeSuffix ByteString
x = if ByteString -> Bool
ByteString.null ByteString
x then Maybe (ByteString, ByteString)
forall a. Maybe a
Nothing else (ByteString, ByteString) -> Maybe (ByteString, ByteString)
forall a. a -> Maybe a
Just (Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt (ByteString -> Int
ByteString.length ByteString
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) ByteString
x)
   inits :: ByteString -> [ByteString]
inits = ByteString -> [ByteString]
ByteString.inits
   tails :: ByteString -> [ByteString]
tails = ByteString -> [ByteString]
ByteString.tails
   foldl :: (a -> ByteString -> a) -> a -> ByteString -> a
foldl a -> ByteString -> a
f = (a -> Word8 -> a) -> a -> ByteString -> a
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
ByteString.foldl a -> Word8 -> a
f'
      where f' :: a -> Word8 -> a
f' a
a Word8
byte = a -> ByteString -> a
f a
a (Word8 -> ByteString
ByteString.singleton Word8
byte)
   foldl' :: (a -> ByteString -> a) -> a -> ByteString -> a
foldl' a -> ByteString -> a
f = (a -> Word8 -> a) -> a -> ByteString -> a
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
ByteString.foldl' a -> Word8 -> a
f'
      where f' :: a -> Word8 -> a
f' a
a Word8
byte = a -> ByteString -> a
f a
a (Word8 -> ByteString
ByteString.singleton Word8
byte)
   foldr :: (ByteString -> a -> a) -> a -> ByteString -> a
foldr ByteString -> a -> a
f = (Word8 -> a -> a) -> a -> ByteString -> a
forall a. (Word8 -> a -> a) -> a -> ByteString -> a
ByteString.foldr (ByteString -> a -> a
f (ByteString -> a -> a) -> (Word8 -> ByteString) -> Word8 -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton)
   break :: (ByteString -> Bool) -> ByteString -> (ByteString, ByteString)
break ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> (ByteString, ByteString)
ByteString.break (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton)
   span :: (ByteString -> Bool) -> ByteString -> (ByteString, ByteString)
span ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> (ByteString, ByteString)
ByteString.span (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton)
   spanMaybe :: s
-> (s -> ByteString -> Maybe s)
-> ByteString
-> (ByteString, ByteString, s)
spanMaybe s
s0 s -> ByteString -> Maybe s
f ByteString
b = case (Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> ByteString -> (Int, s) -> (Int, s)
forall a. (Word8 -> a -> a) -> a -> ByteString -> a
ByteString.foldr Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g (Int, s) -> (Int, s)
forall a. a -> a
id ByteString
b (Int
0, s
s0)
                      of (Int
i, s
s') | (ByteString
prefix, ByteString
suffix) <- Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt Int
i ByteString
b -> (ByteString
prefix, ByteString
suffix, s
s')
      where g :: Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g Word8
w (Int, s) -> (Int, s)
cont (Int
i, s
s) | Just s
s' <- s -> ByteString -> Maybe s
f s
s (Word8 -> ByteString
ByteString.singleton Word8
w) = let i' :: Int
i' = Int -> Int
forall a. Enum a => a -> a
succ Int
i :: Int in Int -> (Int, s) -> (Int, s)
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' s
s0 s -> ByteString -> Maybe s
f ByteString
b = case (Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> ByteString -> (Int, s) -> (Int, s)
forall a. (Word8 -> a -> a) -> a -> ByteString -> a
ByteString.foldr Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g (Int, s) -> (Int, s)
forall a. a -> a
id ByteString
b (Int
0, s
s0)
                       of (Int
i, s
s') | (ByteString
prefix, ByteString
suffix) <- Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt Int
i ByteString
b -> (ByteString
prefix, ByteString
suffix, s
s')
      where g :: Word8 -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g Word8
w (Int, s) -> (Int, s)
cont (Int
i, s
s) | Just s
s' <- s -> ByteString -> Maybe s
f s
s (Word8 -> ByteString
ByteString.singleton Word8
w) = let i' :: Int
i' = Int -> Int
forall a. Enum a => a -> a
succ Int
i :: Int in Int -> (Int, s) -> (Int, s)
seq Int
i' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ s -> (Int, s) -> (Int, s)
seq s
s' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ (Int, s) -> (Int, s)
cont (Int
i', s
s')
                            | Bool
otherwise = (Int
i, s
s)
   dropWhile :: (ByteString -> Bool) -> ByteString -> ByteString
dropWhile ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> ByteString
ByteString.dropWhile (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton)
   takeWhile :: (ByteString -> Bool) -> ByteString -> ByteString
takeWhile ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> ByteString
ByteString.takeWhile (ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton)
   length :: ByteString -> Int
length = ByteString -> Int
ByteString.length
   split :: (ByteString -> Bool) -> ByteString -> [ByteString]
split ByteString -> Bool
f = (Word8 -> Bool) -> ByteString -> [ByteString]
ByteString.splitWith Word8 -> Bool
f'
      where f' :: Word8 -> Bool
f' = ByteString -> Bool
f (ByteString -> Bool) -> (Word8 -> ByteString) -> Word8 -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton
   splitAt :: Int -> ByteString -> (ByteString, ByteString)
splitAt = Int -> ByteString -> (ByteString, ByteString)
ByteString.splitAt
   drop :: Int -> ByteString -> ByteString
drop = Int -> ByteString -> ByteString
ByteString.drop
   take :: Int -> ByteString -> ByteString
take = Int -> ByteString -> ByteString
ByteString.take
   reverse :: ByteString -> ByteString
reverse = ByteString -> ByteString
ByteString.reverse

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

instance FactorialMonoid Text.Text where
   factors :: Text -> [Text]
factors = Int -> Text -> [Text]
Text.chunksOf Int
1
   primePrefix :: Text -> Text
primePrefix = Int -> Text -> Text
Text.take Int
1
   primeSuffix :: Text -> Text
primeSuffix Text
x = if Text -> Bool
Text.null Text
x then Text
Text.empty else Char -> Text
Text.singleton (Text -> Char
Text.last Text
x)
   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 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
   foldl :: (a -> Text -> a) -> a -> Text -> a
foldl a -> Text -> a
f = (a -> Char -> a) -> a -> Text -> a
forall a. (a -> Char -> a) -> a -> Text -> a
Text.foldl a -> Char -> a
f'
      where f' :: a -> Char -> a
f' a
a Char
char = a -> Text -> a
f a
a (Char -> Text
Text.singleton Char
char)
   foldl' :: (a -> Text -> a) -> a -> Text -> a
foldl' a -> Text -> a
f = (a -> Char -> a) -> a -> Text -> a
forall a. (a -> Char -> a) -> a -> Text -> a
Text.foldl' a -> Char -> a
f'
      where f' :: a -> Char -> a
f' a
a Char
char = a -> Text -> a
f a
a (Char -> Text
Text.singleton Char
char)
   foldr :: (Text -> a -> a) -> a -> Text -> a
foldr Text -> a -> a
f = (Char -> a -> a) -> a -> Text -> a
forall a. (Char -> a -> a) -> a -> Text -> a
Text.foldr Char -> a -> a
f'
      where f' :: Char -> a -> a
f' Char
char a
a = Text -> a -> a
f (Char -> Text
Text.singleton Char
char) a
a
   length :: Text -> Int
length = Text -> Int
Text.length
   span :: (Text -> Bool) -> Text -> (Text, Text)
span Text -> Bool
f = (Char -> Bool) -> Text -> (Text, Text)
Text.span (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
Text.singleton)
   break :: (Text -> Bool) -> Text -> (Text, Text)
break Text -> Bool
f = (Char -> Bool) -> Text -> (Text, Text)
Text.break (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
Text.singleton)
   dropWhile :: (Text -> Bool) -> Text -> Text
dropWhile Text -> Bool
f = (Char -> Bool) -> Text -> Text
Text.dropWhile (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
Text.singleton)
   takeWhile :: (Text -> Bool) -> Text -> Text
takeWhile Text -> Bool
f = (Char -> Bool) -> Text -> Text
Text.takeWhile (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
Text.singleton)
   spanMaybe :: s -> (s -> Text -> Maybe s) -> Text -> (Text, Text, s)
spanMaybe s
s0 s -> Text -> Maybe s
f Text
t = case (Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> Text -> (Int, s) -> (Int, s)
forall a. (Char -> a -> a) -> a -> Text -> a
Text.foldr Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g (Int, s) -> (Int, s)
forall a. a -> a
id Text
t (Int
0, s
s0)
                      of (Int
i, s
s') | (Text
prefix, Text
suffix) <- Int -> Text -> (Text, Text)
Text.splitAt Int
i Text
t -> (Text
prefix, Text
suffix, s
s')
      where g :: Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g Char
c (Int, s) -> (Int, s)
cont (Int
i, s
s) | Just s
s' <- s -> Text -> Maybe s
f s
s (Char -> Text
Text.singleton Char
c) = let i' :: Int
i' = Int -> Int
forall a. Enum a => a -> a
succ Int
i :: Int in Int -> (Int, s) -> (Int, s)
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' s
s0 s -> Text -> Maybe s
f Text
t = case (Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s))
-> ((Int, s) -> (Int, s)) -> Text -> (Int, s) -> (Int, s)
forall a. (Char -> a -> a) -> a -> Text -> a
Text.foldr Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g (Int, s) -> (Int, s)
forall a. a -> a
id Text
t (Int
0, s
s0)
                       of (Int
i, s
s') | (Text
prefix, Text
suffix) <- Int -> Text -> (Text, Text)
Text.splitAt Int
i Text
t -> (Text
prefix, Text
suffix, s
s')
      where g :: Char -> ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
g Char
c (Int, s) -> (Int, s)
cont (Int
i, s
s) | Just s
s' <- s -> Text -> Maybe s
f s
s (Char -> Text
Text.singleton Char
c) = let i' :: Int
i' = Int -> Int
forall a. Enum a => a -> a
succ Int
i :: Int in Int -> (Int, s) -> (Int, s)
seq Int
i' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ s -> (Int, s) -> (Int, s)
seq s
s' ((Int, s) -> (Int, s)) -> (Int, s) -> (Int, s)
forall a b. (a -> b) -> a -> b
$ (Int, s) -> (Int, s)
cont (Int
i', s
s')
                            | Bool
otherwise = (Int
i, s
s)
   split :: (Text -> Bool) -> Text -> [Text]
split Text -> Bool
f = (Char -> Bool) -> Text -> [Text]
Text.split Char -> Bool
f'
      where f' :: Char -> Bool
f' = Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
Text.singleton
   splitAt :: Int -> Text -> (Text, Text)
splitAt = Int -> Text -> (Text, Text)
Text.splitAt
   drop :: Int -> Text -> Text
drop = Int -> Text -> Text
Text.drop
   take :: Int -> Text -> Text
take = Int -> Text -> Text
Text.take
   reverse :: Text -> Text
reverse = Text -> Text
Text.reverse

instance FactorialMonoid LazyText.Text where
   factors :: Text -> [Text]
factors = Int64 -> Text -> [Text]
LazyText.chunksOf Int64
1
   primePrefix :: Text -> Text
primePrefix = Int64 -> Text -> Text
LazyText.take Int64
1
   primeSuffix :: Text -> Text
primeSuffix Text
x = if Text -> Bool
LazyText.null Text
x then Text
LazyText.empty else Char -> Text
LazyText.singleton (Text -> Char
LazyText.last Text
x)
   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 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
   foldl :: (a -> Text -> a) -> a -> Text -> a
foldl a -> Text -> a
f = (a -> Char -> a) -> a -> Text -> a
forall a. (a -> Char -> a) -> a -> Text -> a
LazyText.foldl a -> Char -> a
f'
      where f' :: a -> Char -> a
f' a
a Char
char = a -> Text -> a
f a
a (Char -> Text
LazyText.singleton Char
char)
   foldl' :: (a -> Text -> a) -> a -> Text -> a
foldl' a -> Text -> a
f = (a -> Char -> a) -> a -> Text -> a
forall a. (a -> Char -> a) -> a -> Text -> a
LazyText.foldl' a -> Char -> a
f'
      where f' :: a -> Char -> a
f' a
a Char
char = a -> Text -> a
f a
a (Char -> Text
LazyText.singleton Char
char)
   foldr :: (Text -> a -> a) -> a -> Text -> a
foldr Text -> a -> a
f = (Char -> a -> a) -> a -> Text -> a
forall a. (Char -> a -> a) -> a -> Text -> a
LazyText.foldr Char -> a -> a
f'
      where f' :: Char -> a -> a
f' Char
char a
a = Text -> a -> a
f (Char -> Text
LazyText.singleton Char
char) a
a
   length :: Text -> Int
length = Int64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int64 -> Int) -> (Text -> Int64) -> Text -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Int64
LazyText.length
   span :: (Text -> Bool) -> Text -> (Text, Text)
span Text -> Bool
f = (Char -> Bool) -> Text -> (Text, Text)
LazyText.span (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
LazyText.singleton)
   break :: (Text -> Bool) -> Text -> (Text, Text)
break Text -> Bool
f = (Char -> Bool) -> Text -> (Text, Text)
LazyText.break (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
LazyText.singleton)
   dropWhile :: (Text -> Bool) -> Text -> Text
dropWhile Text -> Bool
f = (Char -> Bool) -> Text -> Text
LazyText.dropWhile (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
LazyText.singleton)
   takeWhile :: (Text -> Bool) -> Text -> Text
takeWhile Text -> Bool
f = (Char -> Bool) -> Text -> Text
LazyText.takeWhile (Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
LazyText.singleton)
   spanMaybe :: s -> (s -> Text -> Maybe s) -> Text -> (Text, Text, s)
spanMaybe s
s0 s -> Text -> Maybe s
f Text
t = case (Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s))
-> ((Int64, s) -> (Int64, s)) -> Text -> (Int64, s) -> (Int64, s)
forall a. (Char -> a -> a) -> a -> Text -> a
LazyText.foldr Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g (Int64, s) -> (Int64, s)
forall a. a -> a
id Text
t (Int64
0, s
s0)
                      of (Int64
i, s
s') | (Text
prefix, Text
suffix) <- Int64 -> Text -> (Text, Text)
LazyText.splitAt Int64
i Text
t -> (Text
prefix, Text
suffix, s
s')
      where g :: Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g Char
c (Int64, s) -> (Int64, s)
cont (Int64
i, s
s) | Just s
s' <- s -> Text -> Maybe s
f s
s (Char -> Text
LazyText.singleton Char
c) = let i' :: Int64
i' = Int64 -> Int64
forall a. Enum a => a -> a
succ Int64
i :: Int64 in Int64 -> (Int64, s) -> (Int64, s)
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' s
s0 s -> Text -> Maybe s
f Text
t = case (Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s))
-> ((Int64, s) -> (Int64, s)) -> Text -> (Int64, s) -> (Int64, s)
forall a. (Char -> a -> a) -> a -> Text -> a
LazyText.foldr Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g (Int64, s) -> (Int64, s)
forall a. a -> a
id Text
t (Int64
0, s
s0)
                       of (Int64
i, s
s') | (Text
prefix, Text
suffix) <- Int64 -> Text -> (Text, Text)
LazyText.splitAt Int64
i Text
t -> (Text
prefix, Text
suffix, s
s')
      where g :: Char -> ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
g Char
c (Int64, s) -> (Int64, s)
cont (Int64
i, s
s) | Just s
s' <- s -> Text -> Maybe s
f s
s (Char -> Text
LazyText.singleton Char
c) = let i' :: Int64
i' = Int64 -> Int64
forall a. Enum a => a -> a
succ Int64
i :: Int64 in Int64 -> (Int64, s) -> (Int64, s)
seq Int64
i' ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
forall a b. (a -> b) -> a -> b
$ s -> (Int64, s) -> (Int64, s)
seq s
s' ((Int64, s) -> (Int64, s)) -> (Int64, s) -> (Int64, s)
forall a b. (a -> b) -> a -> b
$ (Int64, s) -> (Int64, s)
cont (Int64
i', s
s')
                            | Bool
otherwise = (Int64
i, s
s)
   split :: (Text -> Bool) -> Text -> [Text]
split Text -> Bool
f = (Char -> Bool) -> Text -> [Text]
LazyText.split Char -> Bool
f'
      where f' :: Char -> Bool
f' = Text -> Bool
f (Text -> Bool) -> (Char -> Text) -> Char -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> Text
LazyText.singleton
   splitAt :: Int -> Text -> (Text, Text)
splitAt = Int64 -> Text -> (Text, Text)
LazyText.splitAt (Int64 -> Text -> (Text, Text))
-> (Int -> Int64) -> Int -> Text -> (Text, Text)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral
   drop :: Int -> Text -> Text
drop Int
n = Int64 -> Text -> Text
LazyText.drop (Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n)
   take :: Int -> Text -> Text
take Int
n = Int64 -> Text -> Text
LazyText.take (Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n)
   reverse :: Text -> Text
reverse = Text -> Text
LazyText.reverse

instance Ord k => FactorialMonoid (Map.Map k v) where
   factors :: Map k v -> [Map k v]
factors = ((k, v) -> Map k v) -> [(k, v)] -> [Map k v]
forall a b. (a -> b) -> [a] -> [b]
List.map ((k -> v -> Map k v) -> (k, v) -> Map k v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton) ([(k, v)] -> [Map k v])
-> (Map k v -> [(k, v)]) -> Map k v -> [Map k v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k v -> [(k, v)]
forall k a. Map k a -> [(k, a)]
Map.toAscList
   primePrefix :: Map k v -> Map k v
primePrefix Map k v
map | Map k v -> Bool
forall k a. Map k a -> Bool
Map.null Map k v
map = Map k v
map
                   | Bool
otherwise = (k -> v -> Map k v) -> (k, v) -> Map k v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton ((k, v) -> Map k v) -> (k, v) -> Map k v
forall a b. (a -> b) -> a -> b
$ Map k v -> (k, v)
forall k a. Map k a -> (k, a)
Map.findMin Map k v
map
   primeSuffix :: Map k v -> Map k v
primeSuffix Map k v
map | Map k v -> Bool
forall k a. Map k a -> Bool
Map.null Map k v
map = Map k v
map
                   | Bool
otherwise = (k -> v -> Map k v) -> (k, v) -> Map k v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton ((k, v) -> Map k v) -> (k, v) -> Map k v
forall a b. (a -> b) -> a -> b
$ Map k v -> (k, v)
forall k a. Map k a -> (k, a)
Map.findMax Map k v
map
   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, a
v), b
rest) = (k -> a -> Map k a
forall k a. k -> a -> Map k a
Map.singleton k
k a
v, b
rest)
   splitPrimeSuffix :: Map k v -> Maybe (Map k v, Map k v)
splitPrimeSuffix = (((k, v), Map k v) -> (Map k v, Map k v))
-> Maybe ((k, v), Map k v) -> Maybe (Map k v, Map k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k, v), Map k v) -> (Map k v, Map k v)
forall k a a. ((k, a), a) -> (a, Map k a)
singularize (Maybe ((k, v), Map k v) -> Maybe (Map k v, Map k v))
-> (Map k v -> Maybe ((k, v), Map k v))
-> Map k v
-> Maybe (Map k v, Map k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k v -> Maybe ((k, v), Map k v)
forall k a. Map k a -> Maybe ((k, a), Map k a)
Map.maxViewWithKey
      where singularize :: ((k, a), a) -> (a, Map k a)
singularize ((k
k, a
v), a
rest) = (a
rest, k -> a -> Map k a
forall k a. k -> a -> Map k a
Map.singleton k
k a
v)
   foldl :: (a -> Map k v -> a) -> a -> Map k v -> a
foldl a -> Map k v -> a
f = (a -> k -> v -> a) -> a -> Map k v -> a
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey a -> k -> v -> a
f'
      where f' :: a -> k -> v -> a
f' a
a k
k v
v = a -> Map k v -> a
f a
a (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v)
   foldl' :: (a -> Map k v -> a) -> a -> Map k v -> a
foldl' a -> Map k v -> a
f = (a -> k -> v -> a) -> a -> Map k v -> a
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey' a -> k -> v -> a
f'
      where f' :: a -> k -> v -> a
f' a
a k
k v
v = a -> Map k v -> a
f a
a (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v)
   foldr :: (Map k v -> a -> a) -> a -> Map k v -> a
foldr Map k v -> a -> a
f = (k -> v -> a -> a) -> a -> Map k v -> a
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey k -> v -> a -> a
f'
      where f' :: k -> v -> a -> a
f' k
k v
v a
a = Map k v -> a -> a
f (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v) a
a
   length :: Map k v -> Int
length = Map k v -> Int
forall k a. Map k a -> Int
Map.size
   reverse :: Map k v -> Map k v
reverse = Map k v -> Map k v
forall a. a -> a
id

instance FactorialMonoid (IntMap.IntMap a) where
   factors :: IntMap a -> [IntMap a]
factors = ((Int, a) -> IntMap a) -> [(Int, a)] -> [IntMap a]
forall a b. (a -> b) -> [a] -> [b]
List.map ((Int -> a -> IntMap a) -> (Int, a) -> IntMap a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton) ([(Int, a)] -> [IntMap a])
-> (IntMap a -> [(Int, a)]) -> IntMap a -> [IntMap a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap a -> [(Int, a)]
forall a. IntMap a -> [(Int, a)]
IntMap.toAscList
   primePrefix :: IntMap a -> IntMap a
primePrefix IntMap a
map | IntMap a -> Bool
forall a. IntMap a -> Bool
IntMap.null IntMap a
map = IntMap a
map
                   | Bool
otherwise = (Int -> a -> IntMap a) -> (Int, a) -> IntMap a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton ((Int, a) -> IntMap a) -> (Int, a) -> IntMap a
forall a b. (a -> b) -> a -> b
$ IntMap a -> (Int, a)
forall a. IntMap a -> (Int, a)
IntMap.findMin IntMap a
map
   primeSuffix :: IntMap a -> IntMap a
primeSuffix IntMap a
map | IntMap a -> Bool
forall a. IntMap a -> Bool
IntMap.null IntMap a
map = IntMap a
map
                   | Bool
otherwise = (Int -> a -> IntMap a) -> (Int, a) -> IntMap a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton ((Int, a) -> IntMap a) -> (Int, a) -> IntMap a
forall a b. (a -> b) -> a -> b
$ IntMap a -> (Int, a)
forall a. IntMap a -> (Int, a)
IntMap.findMax IntMap a
map
   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 ((Int
k, a
v), b
rest) = (Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v, b
rest)
   splitPrimeSuffix :: IntMap a -> Maybe (IntMap a, IntMap a)
splitPrimeSuffix = (((Int, a), IntMap a) -> (IntMap a, IntMap a))
-> Maybe ((Int, a), IntMap a) -> Maybe (IntMap a, IntMap a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Int, a), IntMap a) -> (IntMap a, IntMap a)
forall a a. ((Int, a), a) -> (a, IntMap a)
singularize (Maybe ((Int, a), IntMap a) -> Maybe (IntMap a, IntMap a))
-> (IntMap a -> Maybe ((Int, a), IntMap a))
-> IntMap a
-> Maybe (IntMap a, IntMap a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap a -> Maybe ((Int, a), IntMap a)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IntMap.maxViewWithKey
      where singularize :: ((Int, a), a) -> (a, IntMap a)
singularize ((Int
k, a
v), a
rest) = (a
rest, Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v)
   foldl :: (a -> IntMap a -> a) -> a -> IntMap a -> a
foldl a -> IntMap a -> a
f = (a -> Int -> a -> a) -> a -> IntMap a -> a
forall a b. (a -> Int -> b -> a) -> a -> IntMap b -> a
IntMap.foldlWithKey a -> Int -> a -> a
f'
      where f' :: a -> Int -> a -> a
f' a
a Int
k a
v = a -> IntMap a -> a
f a
a (Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v)
   foldl' :: (a -> IntMap a -> a) -> a -> IntMap a -> a
foldl' a -> IntMap a -> a
f = (a -> Int -> a -> a) -> a -> IntMap a -> a
forall a b. (a -> Int -> b -> a) -> a -> IntMap b -> a
IntMap.foldlWithKey' a -> Int -> a -> a
f'
      where f' :: a -> Int -> a -> a
f' a
a Int
k a
v = a -> IntMap a -> a
f a
a (Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v)
   foldr :: (IntMap a -> a -> a) -> a -> IntMap a -> a
foldr IntMap a -> a -> a
f = (Int -> a -> a -> a) -> a -> IntMap a -> a
forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
IntMap.foldrWithKey Int -> a -> a -> a
f'
      where f' :: Int -> a -> a -> a
f' Int
k a
v a
a = IntMap a -> a -> a
f (Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v) a
a
   length :: IntMap a -> Int
length = IntMap a -> Int
forall a. IntMap a -> Int
IntMap.size
   reverse :: IntMap a -> IntMap a
reverse = IntMap a -> IntMap a
forall a. a -> a
id

instance FactorialMonoid IntSet.IntSet where
   factors :: IntSet -> [IntSet]
factors = (Int -> IntSet) -> [Int] -> [IntSet]
forall a b. (a -> b) -> [a] -> [b]
List.map Int -> IntSet
IntSet.singleton ([Int] -> [IntSet]) -> (IntSet -> [Int]) -> IntSet -> [IntSet]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> [Int]
IntSet.toAscList
   primePrefix :: IntSet -> IntSet
primePrefix IntSet
set | IntSet -> Bool
IntSet.null IntSet
set = IntSet
set
                   | Bool
otherwise = Int -> IntSet
IntSet.singleton (Int -> IntSet) -> Int -> IntSet
forall a b. (a -> b) -> a -> b
$ IntSet -> Int
IntSet.findMin IntSet
set
   primeSuffix :: IntSet -> IntSet
primeSuffix IntSet
set | IntSet -> Bool
IntSet.null IntSet
set = IntSet
set
                   | Bool
otherwise = Int -> IntSet
IntSet.singleton (Int -> IntSet) -> Int -> IntSet
forall a b. (a -> b) -> a -> b
$ IntSet -> Int
IntSet.findMax IntSet
set
   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 (Int
min, b
rest) = (Int -> IntSet
IntSet.singleton Int
min, b
rest)
   splitPrimeSuffix :: IntSet -> Maybe (IntSet, IntSet)
splitPrimeSuffix = ((Int, IntSet) -> (IntSet, IntSet))
-> Maybe (Int, IntSet) -> Maybe (IntSet, IntSet)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int, IntSet) -> (IntSet, IntSet)
forall a. (Int, a) -> (a, IntSet)
singularize (Maybe (Int, IntSet) -> Maybe (IntSet, IntSet))
-> (IntSet -> Maybe (Int, IntSet))
-> IntSet
-> Maybe (IntSet, IntSet)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> Maybe (Int, IntSet)
IntSet.maxView
      where singularize :: (Int, a) -> (a, IntSet)
singularize (Int
max, a
rest) = (a
rest, Int -> IntSet
IntSet.singleton Int
max)
   foldl :: (a -> IntSet -> a) -> a -> IntSet -> a
foldl a -> IntSet -> a
f = (a -> Int -> a) -> a -> IntSet -> a
forall a. (a -> Int -> a) -> a -> IntSet -> a
IntSet.foldl a -> Int -> a
f'
      where f' :: a -> Int -> a
f' a
a Int
b = a -> IntSet -> a
f a
a (Int -> IntSet
IntSet.singleton Int
b)
   foldl' :: (a -> IntSet -> a) -> a -> IntSet -> a
foldl' a -> IntSet -> a
f = (a -> Int -> a) -> a -> IntSet -> a
forall a. (a -> Int -> a) -> a -> IntSet -> a
IntSet.foldl' a -> Int -> a
f'
      where f' :: a -> Int -> a
f' a
a Int
b = a -> IntSet -> a
f a
a (Int -> IntSet
IntSet.singleton Int
b)
   foldr :: (IntSet -> a -> a) -> a -> IntSet -> a
foldr IntSet -> a -> a
f = (Int -> a -> a) -> a -> IntSet -> a
forall b. (Int -> b -> b) -> b -> IntSet -> b
IntSet.foldr Int -> a -> a
f'
      where f' :: Int -> a -> a
f' Int
a a
b = IntSet -> a -> a
f (Int -> IntSet
IntSet.singleton Int
a) a
b
   length :: IntSet -> Int
length = IntSet -> Int
IntSet.size
   reverse :: IntSet -> IntSet
reverse = IntSet -> IntSet
forall a. a -> a
id

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

instance Ord a => FactorialMonoid (Set.Set a) where
   factors :: Set a -> [Set a]
factors = (a -> Set a) -> [a] -> [Set a]
forall a b. (a -> b) -> [a] -> [b]
List.map a -> Set a
forall a. a -> Set a
Set.singleton ([a] -> [Set a]) -> (Set a -> [a]) -> Set a -> [Set a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> [a]
forall a. Set a -> [a]
Set.toAscList
   primePrefix :: Set a -> Set a
primePrefix Set a
set | Set a -> Bool
forall a. Set a -> Bool
Set.null Set a
set = Set a
set
                   | Bool
otherwise = a -> Set a
forall a. a -> Set a
Set.singleton (a -> Set a) -> a -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a
forall a. Set a -> a
Set.findMin Set a
set
   primeSuffix :: Set a -> Set a
primeSuffix Set a
set | Set a -> Bool
forall a. Set a -> Bool
Set.null Set a
set = Set a
set
                   | Bool
otherwise = a -> Set a
forall a. a -> Set a
Set.singleton (a -> Set a) -> a -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a
forall a. Set a -> a
Set.findMax Set a
set
   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 (a
min, b
rest) = (a -> Set a
forall a. a -> Set a
Set.singleton a
min, b
rest)
   splitPrimeSuffix :: Set a -> Maybe (Set a, Set a)
splitPrimeSuffix = ((a, Set a) -> (Set a, Set a))
-> Maybe (a, Set a) -> Maybe (Set a, Set a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, Set a) -> (Set a, Set a)
forall a a. (a, a) -> (a, Set a)
singularize (Maybe (a, Set a) -> Maybe (Set a, Set a))
-> (Set a -> Maybe (a, Set a)) -> Set a -> Maybe (Set a, Set a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> Maybe (a, Set a)
forall a. Set a -> Maybe (a, Set a)
Set.maxView
      where singularize :: (a, a) -> (a, Set a)
singularize (a
max, a
rest) = (a
rest, a -> Set a
forall a. a -> Set a
Set.singleton a
max)
   foldl :: (a -> Set a -> a) -> a -> Set a -> a
foldl a -> Set a -> a
f = (a -> a -> a) -> a -> Set a -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
b = a -> Set a -> a
f a
a (a -> Set a
forall a. a -> Set a
Set.singleton a
b)
   foldl' :: (a -> Set a -> a) -> a -> Set a -> a
foldl' a -> Set a -> a
f = (a -> a -> a) -> a -> Set a -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl' a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
b = a -> Set a -> a
f a
a (a -> Set a
forall a. a -> Set a
Set.singleton a
b)
   foldr :: (Set a -> a -> a) -> a -> Set a -> a
foldr Set a -> a -> a
f = (a -> a -> a) -> a -> Set a -> a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
b = Set a -> a -> a
f (a -> Set a
forall a. a -> Set a
Set.singleton a
a) a
b
   length :: Set a -> Int
length = Set a -> Int
forall a. Set a -> Int
Set.size
   reverse :: Set a -> Set a
reverse = Set a -> Set a
forall a. a -> a
id

instance FactorialMonoid (Vector.Vector a) where
   factors :: Vector a -> [Vector a]
factors Vector a
x = Int -> Vector a -> [Vector a]
forall t a. (Eq t, Num t, Enum t) => t -> Vector a -> [Vector a]
factorize (Vector a -> Int
forall a. Vector a -> Int
Vector.length Vector a
x) Vector a
x
      where factorize :: t -> Vector a -> [Vector a]
factorize t
0 Vector a
_ = []
            factorize t
n Vector a
xs = Vector a
xs1 Vector a -> [Vector a] -> [Vector a]
forall a. a -> [a] -> [a]
: t -> Vector a -> [Vector a]
factorize (t -> t
forall a. Enum a => a -> a
pred t
n) Vector a
xs'
               where (Vector a
xs1, Vector a
xs') = Int -> Vector a -> (Vector a, Vector a)
forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt Int
1 Vector a
xs
   primePrefix :: Vector a -> Vector a
primePrefix = Int -> Vector a -> Vector a
forall a. Int -> Vector a -> Vector a
Vector.take Int
1
   primeSuffix :: Vector a -> Vector a
primeSuffix Vector a
x = Int -> Vector a -> Vector a
forall a. Int -> Vector a -> Vector a
Vector.drop (Vector a -> Int
forall a. Vector a -> Int
Vector.length Vector a
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Vector a
x
   splitPrimePrefix :: Vector a -> Maybe (Vector a, Vector a)
splitPrimePrefix Vector a
x = if Vector a -> Bool
forall a. Vector a -> Bool
Vector.null Vector a
x then Maybe (Vector a, Vector a)
forall a. Maybe a
Nothing else (Vector a, Vector a) -> Maybe (Vector a, Vector a)
forall a. a -> Maybe a
Just (Int -> Vector a -> (Vector a, Vector a)
forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt Int
1 Vector a
x)
   splitPrimeSuffix :: Vector a -> Maybe (Vector a, Vector a)
splitPrimeSuffix Vector a
x = if Vector a -> Bool
forall a. Vector a -> Bool
Vector.null Vector a
x then Maybe (Vector a, Vector a)
forall a. Maybe a
Nothing else (Vector a, Vector a) -> Maybe (Vector a, Vector a)
forall a. a -> Maybe a
Just (Int -> Vector a -> (Vector a, Vector a)
forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt (Vector a -> Int
forall a. Vector a -> Int
Vector.length Vector a
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Vector a
x)
   inits :: Vector a -> [Vector a]
inits Vector a
x0 = Vector a -> [Vector a] -> [Vector a]
forall a. Vector a -> [Vector a] -> [Vector a]
initsWith Vector a
x0 []
      where initsWith :: Vector a -> [Vector a] -> [Vector a]
initsWith Vector a
x [Vector a]
rest | Vector a -> Bool
forall a. Vector a -> Bool
Vector.null Vector a
x = Vector a
xVector a -> [Vector a] -> [Vector a]
forall a. a -> [a] -> [a]
:[Vector a]
rest
                             | Bool
otherwise = Vector a -> [Vector a] -> [Vector a]
initsWith (Vector a -> Vector a
forall a. Vector a -> Vector a
Vector.unsafeInit Vector a
x) (Vector a
xVector a -> [Vector a] -> [Vector a]
forall a. a -> [a] -> [a]
:[Vector a]
rest)
   tails :: Vector a -> [Vector a]
tails Vector a
x = Vector a
x Vector a -> [Vector a] -> [Vector a]
forall a. a -> [a] -> [a]
: if Vector a -> Bool
forall a. Vector a -> Bool
Vector.null Vector a
x then [] else Vector a -> [Vector a]
forall m. FactorialMonoid m => m -> [m]
tails (Vector a -> Vector a
forall a. Vector a -> Vector a
Vector.unsafeTail Vector a
x)
   foldl :: (a -> Vector a -> a) -> a -> Vector a -> a
foldl a -> Vector a -> a
f = (a -> a -> a) -> a -> Vector a -> a
forall a b. (a -> b -> a) -> a -> Vector b -> a
Vector.foldl a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
byte = a -> Vector a -> a
f a
a (a -> Vector a
forall a. a -> Vector a
Vector.singleton a
byte)
   foldl' :: (a -> Vector a -> a) -> a -> Vector a -> a
foldl' a -> Vector a -> a
f = (a -> a -> a) -> a -> Vector a -> a
forall a b. (a -> b -> a) -> a -> Vector b -> a
Vector.foldl' a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
byte = a -> Vector a -> a
f a
a (a -> Vector a
forall a. a -> Vector a
Vector.singleton a
byte)
   foldr :: (Vector a -> a -> a) -> a -> Vector a -> a
foldr Vector a -> a -> a
f = (a -> a -> a) -> a -> Vector a -> a
forall a b. (a -> b -> b) -> b -> Vector a -> b
Vector.foldr a -> a -> a
f'
      where f' :: a -> a -> a
f' a
byte a
a = Vector a -> a -> a
f (a -> Vector a
forall a. a -> Vector a
Vector.singleton a
byte) a
a
   break :: (Vector a -> Bool) -> Vector a -> (Vector a, Vector a)
break Vector a -> Bool
f = (a -> Bool) -> Vector a -> (Vector a, Vector a)
forall a. (a -> Bool) -> Vector a -> (Vector a, Vector a)
Vector.break (Vector a -> Bool
f (Vector a -> Bool) -> (a -> Vector a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Vector a
forall a. a -> Vector a
Vector.singleton)
   span :: (Vector a -> Bool) -> Vector a -> (Vector a, Vector a)
span Vector a -> Bool
f = (a -> Bool) -> Vector a -> (Vector a, Vector a)
forall a. (a -> Bool) -> Vector a -> (Vector a, Vector a)
Vector.span (Vector a -> Bool
f (Vector a -> Bool) -> (a -> Vector a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Vector a
forall a. a -> Vector a
Vector.singleton)
   dropWhile :: (Vector a -> Bool) -> Vector a -> Vector a
dropWhile Vector a -> Bool
f = (a -> Bool) -> Vector a -> Vector a
forall a. (a -> Bool) -> Vector a -> Vector a
Vector.dropWhile (Vector a -> Bool
f (Vector a -> Bool) -> (a -> Vector a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Vector a
forall a. a -> Vector a
Vector.singleton)
   takeWhile :: (Vector a -> Bool) -> Vector a -> Vector a
takeWhile Vector a -> Bool
f = (a -> Bool) -> Vector a -> Vector a
forall a. (a -> Bool) -> Vector a -> Vector a
Vector.takeWhile (Vector a -> Bool
f (Vector a -> Bool) -> (a -> Vector a) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Vector a
forall a. a -> Vector a
Vector.singleton)
   spanMaybe :: s
-> (s -> Vector a -> Maybe s)
-> Vector a
-> (Vector a, Vector a, s)
spanMaybe s
s0 s -> Vector a -> Maybe s
f Vector a
v = case (Int -> a -> (s -> Either s (Int, s)) -> s -> Either s (Int, s))
-> (s -> Either s (Int, s)) -> Vector a -> s -> Either s (Int, s)
forall a b. (Int -> a -> b -> b) -> b -> Vector a -> b
Vector.ifoldr Int -> a -> (s -> Either s (Int, s)) -> s -> Either s (Int, s)
forall a a.
a -> a -> (s -> Either a (a, s)) -> s -> Either a (a, s)
g s -> Either s (Int, s)
forall a b. a -> Either a b
Left Vector a
v s
s0
                      of Left s
s' -> (Vector a
v, Vector a
forall a. Vector a
Vector.empty, s
s')
                         Right (Int
i, s
s') | (Vector a
prefix, Vector a
suffix) <- Int -> Vector a -> (Vector a, Vector a)
forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt Int
i Vector a
v -> (Vector a
prefix, Vector a
suffix, s
s')
      where g :: a -> a -> (s -> Either a (a, s)) -> s -> Either a (a, s)
g a
i a
x s -> Either a (a, s)
cont s
s | Just s
s' <- s -> Vector a -> Maybe s
f s
s (a -> Vector a
forall a. a -> Vector a
Vector.singleton a
x) = s -> Either a (a, s)
cont s
s'
                         | Bool
otherwise = (a, s) -> Either a (a, s)
forall a b. b -> Either a b
Right (a
i, s
s)
   spanMaybe' :: s
-> (s -> Vector a -> Maybe s)
-> Vector a
-> (Vector a, Vector a, s)
spanMaybe' s
s0 s -> Vector a -> Maybe s
f Vector a
v = case (Int -> a -> (s -> Either s (Int, s)) -> s -> Either s (Int, s))
-> (s -> Either s (Int, s)) -> Vector a -> s -> Either s (Int, s)
forall a b. (Int -> a -> b -> b) -> b -> Vector a -> b
Vector.ifoldr' Int -> a -> (s -> Either s (Int, s)) -> s -> Either s (Int, s)
forall a a.
a -> a -> (s -> Either a (a, s)) -> s -> Either a (a, s)
g s -> Either s (Int, s)
forall a b. a -> Either a b
Left Vector a
v s
s0
                       of Left s
s' -> (Vector a
v, Vector a
forall a. Vector a
Vector.empty, s
s')
                          Right (Int
i, s
s') | (Vector a
prefix, Vector a
suffix) <- Int -> Vector a -> (Vector a, Vector a)
forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt Int
i Vector a
v -> (Vector a
prefix, Vector a
suffix, s
s')
      where g :: a -> a -> (s -> Either a (a, s)) -> s -> Either a (a, s)
g a
i a
x s -> Either a (a, s)
cont s
s | Just s
s' <- s -> Vector a -> Maybe s
f s
s (a -> Vector a
forall a. a -> Vector a
Vector.singleton a
x) = s -> Either a (a, s) -> Either a (a, s)
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
   length :: Vector a -> Int
length = Vector a -> Int
forall a. Vector a -> Int
Vector.length
   reverse :: Vector a -> Vector a
reverse = Vector a -> Vector a
forall a. Vector a -> Vector a
Vector.reverse

instance StableFactorialMonoid ()
instance StableFactorialMonoid a => StableFactorialMonoid (Dual a)
instance StableFactorialMonoid [x]
instance StableFactorialMonoid ByteString.ByteString
instance StableFactorialMonoid LazyByteString.ByteString
instance StableFactorialMonoid Text.Text
instance StableFactorialMonoid LazyText.Text
instance StableFactorialMonoid (Sequence.Seq a)
instance StableFactorialMonoid (Vector.Vector a)

-- | A 'Monad.mapM' equivalent.
mapM :: (FactorialMonoid a, Monoid b, Monad m) => (a -> m b) -> a -> m b
mapM :: (a -> m b) -> a -> m b
mapM a -> m b
f = ((m b -> m b) -> m b -> m b
forall a b. (a -> b) -> a -> b
$ b -> m b
forall (m :: * -> *) a. Monad m => a -> m a
return b
forall a. Monoid a => a
mempty) ((m b -> m b) -> m b) -> (a -> m b -> m b) -> a -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Endo (m b) -> m b -> m b
forall a. Endo a -> a -> a
appEndo (Endo (m b) -> m b -> m b) -> (a -> Endo (m b)) -> a -> m b -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Endo (m b)) -> a -> Endo (m b)
forall m n. (FactorialMonoid m, Monoid n) => (m -> n) -> m -> n
Data.Monoid.Factorial.foldMap ((m b -> m b) -> Endo (m b)
forall a. (a -> a) -> Endo a
Endo ((m b -> m b) -> Endo (m b))
-> (a -> m b -> m b) -> a -> Endo (m b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> b -> b) -> m b -> m b -> m b
forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
Monad.liftM2 b -> b -> b
forall a. Monoid a => a -> a -> a
mappend (m b -> m b -> m b) -> (a -> m b) -> a -> m b -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> m b
f)

-- | A 'Monad.mapM_' equivalent.
mapM_ :: (FactorialMonoid a, Monad m) => (a -> m b) -> a -> m ()
mapM_ :: (a -> m b) -> a -> m ()
mapM_ a -> m b
f = (a -> m () -> m ()) -> m () -> a -> m ()
forall m a. FactorialMonoid m => (m -> a -> a) -> a -> m -> a
foldr (m b -> m () -> m ()
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
(>>) (m b -> m () -> m ()) -> (a -> m b) -> a -> m () -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> m b
f) (() -> m ()
forall (m :: * -> *) a. Monad m => a -> m a
return ())