{- 
    Copyright 2013-2019 Mario Blazevic

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

-- | This module defines the 'Semigroup' => 'Factorial' => 'StableFactorial' classes and some of their instances.
-- 

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

module Data.Semigroup.Factorial (
   -- * Classes
   Factorial(..), StableFactorial,
   -- * Monad function equivalents
   mapM, mapM_
   )
where

import qualified Control.Monad as Monad
import Data.Semigroup -- (Semigroup (..), 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.List.NonEmpty (nonEmpty)
import Data.Numbers.Primes (primeFactors)
import Numeric.Natural (Natural)

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

import Prelude (Int, Maybe(..), Eq, Ord, Monoid, Applicative, Monad, Integral,
                (.), (-), (+), ($), (*>), (++), pure, return, mempty, mappend,
                mconcat, pred, id, seq, otherwise, uncurry, fromIntegral, not,
                fmap, max, abs, signum, replicate, maybe, succ, const)

-- | Class of semigroups 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:
-- 
-- > maybe id sconcat  . nonEmpty . factors == id
-- > List.all (\prime-> factors prime == [prime]) . factors
-- > primePrefix s == foldr const s s
-- > foldl f a == List.foldl f a . factors
-- > foldl' f a == List.foldl' f a . factors
-- > foldr f a == List.foldr f a . factors
--
-- A minimal instance definition must implement 'factors' or 'foldr'. Other methods can and should be implemented only
-- for performance reasons.
class Semigroup m => Factorial m where
   -- | Returns a list of all prime factors; inverse of mconcat.
   factors :: m -> [m]
   -- | The prime prefix; @primePrefix mempty == mempty@ for monoids.
   primePrefix :: m -> m
   -- | The prime suffix; @primeSuffix mempty == mempty@ for monoids.
   primeSuffix :: m -> m
   -- | Like 'List.foldl' from "Data.List" on the list of prime 'factors'.
   foldl :: (a -> m -> a) -> a -> m -> a
   -- | Like 'List.foldl'' from "Data.List" on the list of prime 'factors'.
   foldl' :: (a -> m -> a) -> a -> m -> a
   -- | Like 'List.foldr' from "Data.List" on the list of prime 'factors'.
   foldr :: (m -> a -> a) -> a -> m -> a
   -- | The 'length' of the list of prime 'factors'.
   length :: m -> Int
   -- | Generalizes 'Foldable.foldMap' from "Data.Foldable", except the function arguments are prime 'factors' rather
   -- than the structure elements.
   foldMap :: Monoid n => (m -> n) -> m -> n
   -- | Equivalent to 'List.reverse' from "Data.List".
   reverse :: m -> m

   factors = forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr (:) []
   primePrefix m
s = forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr forall a b. a -> b -> a
const m
s m
s
   primeSuffix m
s = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl (forall a b. a -> b -> a
const forall a. a -> a
id) m
s m
s
   foldl a -> m -> a
f a
f0 = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl a -> m -> a
f a
f0 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall m. Factorial m => m -> [m]
factors
   foldl' a -> m -> a
f a
f0 = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' a -> m -> a
f a
f0 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall m. Factorial m => m -> [m]
factors
   foldr m -> a -> a
f a
f0 = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
List.foldr m -> a -> a
f a
f0 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall m. Factorial m => m -> [m]
factors
   length = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl' (forall a b. a -> b -> a
const forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Enum a => a -> a
succ) Int
0
   foldMap m -> n
f = forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr (forall a. Monoid a => a -> a -> a
mappend forall b c a. (b -> c) -> (a -> b) -> a -> c
. m -> n
f) forall a. Monoid a => a
mempty
   reverse m
s = forall b a. b -> (a -> b) -> Maybe a -> b
maybe m
s forall a. Semigroup a => NonEmpty a -> a
sconcat (forall a. [a] -> Maybe (NonEmpty a)
nonEmpty forall a b. (a -> b) -> a -> b
$ forall a. [a] -> [a]
List.reverse forall a b. (a -> b) -> a -> b
$ forall m. Factorial m => m -> [m]
factors m
s)
   {-# MINIMAL factors | foldr #-}
   {-# INLINABLE factors #-}
   {-# INLINE primePrefix #-}
   {-# INLINE primeSuffix #-}
   {-# INLINABLE foldl #-}
   {-# INLINABLE foldl' #-}
   {-# INLINABLE foldr #-}
   {-# INLINE length #-}
   {-# INLINE foldMap #-}
   {-# INLINE reverse #-}

-- | A subclass of 'Factorial' whose instances satisfy the following additional laws:
--
-- > factors (a <> b) == factors a <> factors b
-- > factors . reverse == List.reverse . factors
-- > primeSuffix s == primePrefix (reverse s)
class Factorial m => StableFactorial m

instance Factorial () where
   factors :: () -> [()]
factors () = []
   primePrefix :: () -> ()
primePrefix () = ()
   primeSuffix :: () -> ()
primeSuffix () = ()
   length :: () -> Int
length () = Int
0
   reverse :: () -> ()
reverse = forall a. a -> a
id

instance Factorial a => Factorial (Dual a) where
   factors :: Dual a -> [Dual a]
factors (Dual a
a) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Dual a
Dual (forall m. Factorial m => m -> m
reverse forall a b. (a -> b) -> a -> b
$ forall m. Factorial m => m -> [m]
factors a
a)
   length :: Dual a -> Int
length (Dual a
a) = forall m. Factorial m => m -> Int
length a
a
   primePrefix :: Dual a -> Dual a
primePrefix (Dual a
a) = forall a. a -> Dual a
Dual (forall m. Factorial m => m -> m
primeSuffix a
a)
   primeSuffix :: Dual a -> Dual a
primeSuffix (Dual a
a) = forall a. a -> Dual a
Dual (forall m. Factorial m => m -> m
primePrefix a
a)
   reverse :: Dual a -> Dual a
reverse (Dual a
a) = forall a. a -> Dual a
Dual (forall m. Factorial m => m -> m
reverse a
a)

instance (Integral a, Eq a) => Factorial (Sum a) where
   primePrefix :: Sum a -> Sum a
primePrefix (Sum a
a) = forall a. a -> Sum a
Sum (forall a. Num a => a -> a
signum a
a )
   primeSuffix :: Sum a -> Sum a
primeSuffix = forall m. Factorial m => m -> m
primePrefix
   factors :: Sum a -> [Sum a]
factors (Sum a
n) = forall a. Int -> a -> [a]
replicate (forall a b. (Integral a, Num b) => a -> b
fromIntegral forall a b. (a -> b) -> a -> b
$ forall a. Num a => a -> a
abs a
n) (forall a. a -> Sum a
Sum forall a b. (a -> b) -> a -> b
$ forall a. Num a => a -> a
signum a
n)
   length :: Sum a -> Int
length (Sum a
a) = forall a. Num a => a -> a
abs (forall a b. (Integral a, Num b) => a -> b
fromIntegral a
a)
   reverse :: Sum a -> Sum a
reverse = forall a. a -> a
id

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

instance Factorial a => Factorial (Maybe a) where
   factors :: Maybe a -> [Maybe a]
factors Maybe a
Nothing = []
   factors (Just a
a) = case forall m. Factorial m => m -> [m]
factors a
a
                      of [] -> [forall a. a -> Maybe a
Just a
a]
                         [a]
as -> forall a b. (a -> b) -> [a] -> [b]
List.map forall a. a -> Maybe a
Just [a]
as
   length :: Maybe a -> Int
length Maybe a
Nothing = Int
0
   length (Just a
a) = forall a. Ord a => a -> a -> a
max Int
1 (forall m. Factorial m => m -> Int
length a
a)
   reverse :: Maybe a -> Maybe a
reverse = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall m. Factorial m => m -> m
reverse

instance (Factorial a, Factorial b, MonoidNull a, MonoidNull b) => Factorial (a, b) where
   factors :: (a, b) -> [(a, b)]
factors (a
a, b
b) = forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, forall a. Monoid a => a
mempty)) (forall m. Factorial m => m -> [m]
factors a
a) forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map ((,) forall a. Monoid a => a
mempty) (forall m. Factorial m => m -> [m]
factors b
b)
   primePrefix :: (a, b) -> (a, b)
primePrefix (a
a, b
b) | forall m. MonoidNull m => m -> Bool
null a
a = (a
a, forall m. Factorial m => m -> m
primePrefix b
b)
                      | Bool
otherwise = (forall m. Factorial m => m -> m
primePrefix a
a, forall a. Monoid a => a
mempty)
   primeSuffix :: (a, b) -> (a, b)
primeSuffix (a
a, b
b) | forall m. MonoidNull m => m -> Bool
null b
b = (forall m. Factorial m => m -> m
primeSuffix a
a, b
b)
                      | Bool
otherwise = (forall a. Monoid a => a
mempty, forall m. Factorial m => m -> m
primeSuffix b
b)
   foldl :: forall a. (a -> (a, b) -> a) -> a -> (a, b) -> a
foldl a -> (a, b) -> a
f a
a0 (a
x, b
y) = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl a -> b -> a
f2 (forall m a. Factorial 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. Monoid b => a -> (a, b)
fromFst
            f2 :: a -> b -> a
f2 a
a = a -> (a, b) -> a
f a
a forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. Monoid a => b -> (a, b)
fromSnd
   foldl' :: forall a. (a -> (a, b) -> a) -> a -> (a, b) -> a
foldl' a -> (a, b) -> a
f a
a0 (a
x, b
y) = a
a' seq :: forall a b. a -> b -> b
`seq` forall m a. Factorial 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. Monoid b => a -> (a, b)
fromFst
            f2 :: a -> b -> a
f2 a
a = a -> (a, b) -> a
f a
a forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. Monoid a => b -> (a, b)
fromSnd
            a' :: a
a' = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl' a -> a -> a
f1 a
a0 a
x
   foldr :: forall a. ((a, b) -> a -> a) -> a -> (a, b) -> a
foldr (a, b) -> a -> a
f a
a (a
x, b
y) = forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b) -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. Monoid b => a -> (a, b)
fromFst) (forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b) -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. Monoid a => b -> (a, b)
fromSnd) a
a b
y) a
x
   foldMap :: forall n. Monoid n => ((a, b) -> n) -> (a, b) -> n
foldMap (a, b) -> n
f (a
x, b
y) = forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
Data.Semigroup.Factorial.foldMap ((a, b) -> n
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. Monoid b => a -> (a, b)
fromFst) a
x forall a. Monoid a => a -> a -> a
`mappend`
                      forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
Data.Semigroup.Factorial.foldMap ((a, b) -> n
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. Monoid a => b -> (a, b)
fromSnd) b
y
   length :: (a, b) -> Int
length (a
a, b
b) = forall m. Factorial m => m -> Int
length a
a forall a. Num a => a -> a -> a
+ forall m. Factorial m => m -> Int
length b
b
   reverse :: (a, b) -> (a, b)
reverse (a
a, b
b) = (forall m. Factorial m => m -> m
reverse a
a, forall m. Factorial m => m -> m
reverse b
b)

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

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

instance (Factorial a, Factorial b, Factorial c,
          MonoidNull a, MonoidNull b, MonoidNull c) => Factorial (a, b, c) where
   factors :: (a, b, c) -> [(a, b, c)]
factors (a
a, b
b, c
c) = forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)) (forall m. Factorial m => m -> [m]
factors a
a)
                       forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (forall a. Monoid a => a
mempty, b
b1, forall a. Monoid a => a
mempty)) (forall m. Factorial m => m -> [m]
factors b
b)
                       forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, c
c1)) (forall m. Factorial m => m -> [m]
factors c
c)
   primePrefix :: (a, b, c) -> (a, b, c)
primePrefix (a
a, b
b, c
c) | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null a
a) = (forall m. Factorial m => m -> m
primePrefix a
a, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)
                         | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null b
b) = (forall a. Monoid a => a
mempty, forall m. Factorial m => m -> m
primePrefix b
b, forall a. Monoid a => a
mempty)
                         | Bool
otherwise = (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall m. Factorial m => m -> m
primePrefix c
c)
   primeSuffix :: (a, b, c) -> (a, b, c)
primeSuffix (a
a, b
b, c
c) | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null c
c) = (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall m. Factorial m => m -> m
primeSuffix c
c)
                         | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null b
b) = (forall a. Monoid a => a
mempty, forall m. Factorial m => m -> m
primeSuffix b
b, forall a. Monoid a => a
mempty)
                         | Bool
otherwise = (forall m. Factorial m => m -> m
primeSuffix a
a, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)
   foldl :: forall a. (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) = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl a -> c -> a
f3 (forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl a -> b -> a
f2 (forall m a. Factorial 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 forall b c a. (b -> c) -> (a -> b) -> a -> 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 forall b c a. (b -> c) -> (a -> b) -> a -> 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3
   foldl' :: forall a. (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' seq :: forall a b. a -> b -> b
`seq` a
b' seq :: forall a b. a -> b -> b
`seq` forall m a. Factorial 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 forall b c a. (b -> c) -> (a -> b) -> a -> 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 forall b c a. (b -> c) -> (a -> b) -> a -> 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3
            a' :: a
a' = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl' a -> a -> a
f1 a
s0 a
a
            b' :: a
b' = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl' a -> b -> a
f2 a
a' b
b
   foldr :: forall a. ((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) = forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c) -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) (forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c) -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) (forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c) -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3) a
s c
c) b
b) a
a
   foldMap :: forall n. Monoid n => ((a, b, c) -> n) -> (a, b, c) -> n
foldMap (a, b, c) -> n
f (a
a, b
b, c
c) = forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
Data.Semigroup.Factorial.foldMap ((a, b, c) -> n
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) a
a
                         forall a. Monoid a => a -> a -> a
`mappend` forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
Data.Semigroup.Factorial.foldMap ((a, b, c) -> n
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) b
b
                         forall a. Monoid a => a -> a -> a
`mappend` forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
Data.Semigroup.Factorial.foldMap ((a, b, c) -> n
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3) c
c
   length :: (a, b, c) -> Int
length (a
a, b
b, c
c) = forall m. Factorial m => m -> Int
length a
a forall a. Num a => a -> a -> a
+ forall m. Factorial m => m -> Int
length b
b forall a. Num a => a -> a -> a
+ forall m. Factorial m => m -> Int
length c
c
   reverse :: (a, b, c) -> (a, b, c)
reverse (a
a, b
b, c
c) = (forall m. Factorial m => m -> m
reverse a
a, forall m. Factorial m => m -> m
reverse b
b, forall m. Factorial m => m -> m
reverse c
c)

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

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

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

instance (Factorial a, Factorial b, Factorial c, Factorial d,
          MonoidNull a, MonoidNull b, MonoidNull c, MonoidNull d) => Factorial (a, b, c, d) where
   factors :: (a, b, c, d) -> [(a, b, c, d)]
factors (a
a, b
b, c
c, d
d) = forall a b. (a -> b) -> [a] -> [b]
List.map (\a
a1-> (a
a1, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)) (forall m. Factorial m => m -> [m]
factors a
a)
                          forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\b
b1-> (forall a. Monoid a => a
mempty, b
b1, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)) (forall m. Factorial m => m -> [m]
factors b
b)
                          forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\c
c1-> (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, c
c1, forall a. Monoid a => a
mempty)) (forall m. Factorial m => m -> [m]
factors c
c)
                          forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
List.map (\d
d1-> (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, d
d1)) (forall m. Factorial 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 (forall m. MonoidNull m => m -> Bool
null a
a) = (forall m. Factorial m => m -> m
primePrefix a
a, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)
                            | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null b
b) = (forall a. Monoid a => a
mempty, forall m. Factorial m => m -> m
primePrefix b
b, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)
                            | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null c
c) = (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall m. Factorial m => m -> m
primePrefix c
c, forall a. Monoid a => a
mempty)
                            | Bool
otherwise    = (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall m. Factorial 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 (forall m. MonoidNull m => m -> Bool
null d
d) = (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall m. Factorial m => m -> m
primeSuffix d
d)
                            | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null c
c) = (forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall m. Factorial m => m -> m
primeSuffix c
c, forall a. Monoid a => a
mempty)
                            | Bool -> Bool
not (forall m. MonoidNull m => m -> Bool
null b
b) = (forall a. Monoid a => a
mempty, forall m. Factorial m => m -> m
primeSuffix b
b, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)
                            | Bool
otherwise    = (forall m. Factorial m => m -> m
primeSuffix a
a, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty, forall a. Monoid a => a
mempty)
   foldl :: forall a. (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) = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl a -> d -> a
f4 (forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl a -> c -> a
f3 (forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl a -> b -> a
f2 (forall m a. Factorial 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4
            f2 :: a -> b -> a
f2 a
x = a -> (a, b, c, d) -> a
f a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4
            f3 :: a -> c -> a
f3 a
x = a -> (a, b, c, d) -> a
f a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4
            f4 :: a -> d -> a
f4 a
x = a -> (a, b, c, d) -> a
f a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4
   foldl' :: forall a. (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' seq :: forall a b. a -> b -> b
`seq` a
b' seq :: forall a b. a -> b -> b
`seq` a
c' seq :: forall a b. a -> b -> b
`seq` forall m a. Factorial 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4
            f2 :: a -> b -> a
f2 a
x = a -> (a, b, c, d) -> a
f a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4
            f3 :: a -> c -> a
f3 a
x = a -> (a, b, c, d) -> a
f a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4
            f4 :: a -> d -> a
f4 a
x = a -> (a, b, c, d) -> a
f a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4
            a' :: a
a' = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl' a -> a -> a
f1 a
s0 a
a
            b' :: a
b' = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl' a -> b -> a
f2 a
a' b
b
            c' :: a
c' = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl' a -> c -> a
f3 a
b' c
c
   foldr :: forall a. ((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) =
      forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4) (forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4) (forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4) (forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4) a
s d
d) c
c) b
b) a
a
   foldMap :: forall n. Monoid n => ((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) = forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
Data.Semigroup.Factorial.foldMap ((a, b, c, d) -> n
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4) a
a
                            forall a. Monoid a => a -> a -> a
`mappend` forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
Data.Semigroup.Factorial.foldMap ((a, b, c, d) -> n
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4) b
b
                            forall a. Monoid a => a -> a -> a
`mappend` forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
Data.Semigroup.Factorial.foldMap ((a, b, c, d) -> n
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4) c
c
                            forall a. Monoid a => a -> a -> a
`mappend` forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
Data.Semigroup.Factorial.foldMap ((a, b, c, d) -> n
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4) d
d
   length :: (a, b, c, d) -> Int
length (a
a, b
b, c
c, d
d) = forall m. Factorial m => m -> Int
length a
a forall a. Num a => a -> a -> a
+ forall m. Factorial m => m -> Int
length b
b forall a. Num a => a -> a -> a
+ forall m. Factorial m => m -> Int
length c
c forall a. Num a => a -> a -> a
+ forall m. Factorial m => m -> Int
length d
d
   reverse :: (a, b, c, d) -> (a, b, c, d)
reverse (a
a, b
b, c
c, d
d) = (forall m. Factorial m => m -> m
reverse a
a, forall m. Factorial m => m -> m
reverse b
b, forall m. Factorial m => m -> m
reverse c
c, forall m. Factorial m => m -> m
reverse d
d)

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

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

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

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

instance Factorial [x] where
   factors :: [x] -> [[x]]
factors [x]
xs = forall a b. (a -> b) -> [a] -> [b]
List.map (forall a. a -> [a] -> [a]
:[]) [x]
xs
   primePrefix :: [x] -> [x]
primePrefix [] = []
   primePrefix (x
x:[x]
_) = [x
x]
   primeSuffix :: [x] -> [x]
primeSuffix [] = []
   primeSuffix [x]
xs = [forall a. [a] -> a
List.last [x]
xs]
   foldl :: forall a. (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) = forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl a -> [x] -> a
f (a -> [x] -> a
f a
a [x
x]) [x]
xs
   foldl' :: forall a. (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' seq :: forall a b. a -> b -> b
`seq` forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl' a -> [x] -> a
f a
a' [x]
xs
   foldr :: forall a. ([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] (forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr [x] -> a -> a
f a
f0 [x]
xs)
   length :: [x] -> Int
length = forall (t :: * -> *) a. Foldable t => t a -> Int
List.length
   foldMap :: forall n. Monoid n => ([x] -> n) -> [x] -> n
foldMap [x] -> n
f = forall a. Monoid a => [a] -> a
mconcat forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
List.map ([x] -> n
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall a. a -> [a] -> [a]
:[]))
   reverse :: [x] -> [x]
reverse = forall a. [a] -> [a]
List.reverse

instance Factorial ByteString.ByteString where
   factors :: ByteString -> [ByteString]
factors ByteString
x = 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 forall a. a -> [a] -> [a]
: t -> ByteString -> [ByteString]
factorize (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 forall a. Num a => a -> a -> a
- Int
1) ByteString
x
   foldl :: forall a. (a -> ByteString -> a) -> a -> ByteString -> a
foldl a -> ByteString -> a
f = 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' :: forall a. (a -> ByteString -> a) -> a -> ByteString -> a
foldl' a -> ByteString -> a
f = 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 :: forall a. (ByteString -> a -> a) -> a -> ByteString -> a
foldr ByteString -> a -> a
f = forall a. (Word8 -> a -> a) -> a -> ByteString -> a
ByteString.foldr (ByteString -> a -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton)
   length :: ByteString -> Int
length = ByteString -> Int
ByteString.length
   reverse :: ByteString -> ByteString
reverse = ByteString -> ByteString
ByteString.reverse

instance Factorial LazyByteString.ByteString where
   factors :: ByteString -> [ByteString]
factors ByteString
x = 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 forall a. a -> [a] -> [a]
: t -> ByteString -> [ByteString]
factorize (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 forall a. Num a => a -> a -> a
- Int64
1) ByteString
x
   length :: ByteString -> Int
length = forall a b. (Integral a, Num b) => a -> b
fromIntegral forall b c a. (b -> c) -> (a -> b) -> a -> c
. ByteString -> Int64
LazyByteString.length
   reverse :: ByteString -> ByteString
reverse = ByteString -> ByteString
LazyByteString.reverse

instance Factorial 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)
   foldl :: forall a. (a -> Text -> a) -> a -> Text -> a
foldl a -> Text -> a
f = 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' :: forall a. (a -> Text -> a) -> a -> Text -> a
foldl' a -> Text -> a
f = 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 :: forall a. (Text -> a -> a) -> a -> Text -> a
foldr Text -> a -> a
f = 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
   reverse :: Text -> Text
reverse = Text -> Text
Text.reverse

instance Factorial 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)
   foldl :: forall a. (a -> Text -> a) -> a -> Text -> a
foldl a -> Text -> a
f = 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' :: forall a. (a -> Text -> a) -> a -> Text -> a
foldl' a -> Text -> a
f = 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 :: forall a. (Text -> a -> a) -> a -> Text -> a
foldr Text -> a -> a
f = 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 = forall a b. (Integral a, Num b) => a -> b
fromIntegral forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Int64
LazyText.length
   reverse :: Text -> Text
reverse = Text -> Text
LazyText.reverse

instance Ord k => Factorial (Map.Map k v) where
   factors :: Map k v -> [Map k v]
factors = forall a b. (a -> b) -> [a] -> [b]
List.map (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall k a. k -> a -> Map k a
Map.singleton) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Map k a -> [(k, a)]
Map.toAscList
   primePrefix :: Map k v -> Map k v
primePrefix Map k v
map | forall k a. Map k a -> Bool
Map.null Map k v
map = Map k v
map
                   | Bool
otherwise = forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall k a. k -> a -> Map k a
Map.singleton forall a b. (a -> b) -> a -> b
$ 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 | forall k a. Map k a -> Bool
Map.null Map k v
map = Map k v
map
                   | Bool
otherwise = forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall k a. k -> a -> Map k a
Map.singleton forall a b. (a -> b) -> a -> b
$ forall k a. Map k a -> (k, a)
Map.findMax Map k v
map
   foldl :: forall a. (a -> Map k v -> a) -> a -> Map k v -> a
foldl a -> Map k v -> a
f = 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 (forall k a. k -> a -> Map k a
Map.singleton k
k v
v)
   foldl' :: forall a. (a -> Map k v -> a) -> a -> Map k v -> a
foldl' a -> Map k v -> a
f = 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 (forall k a. k -> a -> Map k a
Map.singleton k
k v
v)
   foldr :: forall a. (Map k v -> a -> a) -> a -> Map k v -> a
foldr Map k v -> a -> a
f = 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 (forall k a. k -> a -> Map k a
Map.singleton k
k v
v) a
a
   length :: Map k v -> Int
length = forall k a. Map k a -> Int
Map.size
   reverse :: Map k v -> Map k v
reverse = forall a. a -> a
id

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

instance Factorial IntSet.IntSet where
   factors :: IntSet -> [IntSet]
factors = forall a b. (a -> b) -> [a] -> [b]
List.map Int -> IntSet
IntSet.singleton 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 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 forall a b. (a -> b) -> a -> b
$ IntSet -> Int
IntSet.findMax IntSet
set
   foldl :: forall a. (a -> IntSet -> a) -> a -> IntSet -> a
foldl a -> IntSet -> a
f = 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' :: forall a. (a -> IntSet -> a) -> a -> IntSet -> a
foldl' a -> IntSet -> a
f = 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 :: forall a. (IntSet -> a -> a) -> a -> IntSet -> a
foldr IntSet -> a -> a
f = 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 = forall a. a -> a
id

instance Factorial (Sequence.Seq a) where
   factors :: Seq a -> [Seq a]
factors = forall a b. (a -> b) -> [a] -> [b]
List.map forall a. a -> Seq a
Sequence.singleton forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) a. Foldable t => t a -> [a]
Foldable.toList
   primePrefix :: Seq a -> Seq a
primePrefix = forall a. Int -> Seq a -> Seq a
Sequence.take Int
1
   primeSuffix :: Seq a -> Seq a
primeSuffix Seq a
q = forall a. Int -> Seq a -> Seq a
Sequence.drop (forall a. Seq a -> Int
Sequence.length Seq a
q forall a. Num a => a -> a -> a
- Int
1) Seq a
q
   foldl :: forall a. (a -> Seq a -> a) -> a -> Seq a -> a
foldl a -> Seq a -> a
f = 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 (forall a. a -> Seq a
Sequence.singleton a
b)
   foldl' :: forall a. (a -> Seq a -> a) -> a -> Seq a -> a
foldl' a -> Seq a -> a
f = 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 (forall a. a -> Seq a
Sequence.singleton a
b)
   foldr :: forall a. (Seq a -> a -> a) -> a -> Seq a -> a
foldr Seq a -> a -> a
f = 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 (forall a. a -> Seq a
Sequence.singleton a
a) a
b
   length :: Seq a -> Int
length = forall a. Seq a -> Int
Sequence.length
   reverse :: Seq a -> Seq a
reverse = forall a. Seq a -> Seq a
Sequence.reverse

instance Ord a => Factorial (Set.Set a) where
   factors :: Set a -> [Set a]
factors = forall a b. (a -> b) -> [a] -> [b]
List.map forall a. a -> Set a
Set.singleton forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Set a -> [a]
Set.toAscList
   primePrefix :: Set a -> Set a
primePrefix Set a
set | forall a. Set a -> Bool
Set.null Set a
set = Set a
set
                   | Bool
otherwise = forall a. a -> Set a
Set.singleton forall a b. (a -> b) -> a -> b
$ forall a. Set a -> a
Set.findMin Set a
set
   primeSuffix :: Set a -> Set a
primeSuffix Set a
set | forall a. Set a -> Bool
Set.null Set a
set = Set a
set
                   | Bool
otherwise = forall a. a -> Set a
Set.singleton forall a b. (a -> b) -> a -> b
$ forall a. Set a -> a
Set.findMax Set a
set
   foldl :: forall a. (a -> Set a -> a) -> a -> Set a -> a
foldl a -> Set a -> a
f = 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 (forall a. a -> Set a
Set.singleton a
b)
   foldl' :: forall a. (a -> Set a -> a) -> a -> Set a -> a
foldl' a -> Set a -> a
f = 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 (forall a. a -> Set a
Set.singleton a
b)
   foldr :: forall a. (Set a -> a -> a) -> a -> Set a -> a
foldr Set a -> a -> a
f = 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 (forall a. a -> Set a
Set.singleton a
a) a
b
   length :: Set a -> Int
length = forall a. Set a -> Int
Set.size
   reverse :: Set a -> Set a
reverse = forall a. a -> a
id

instance Factorial (Vector.Vector a) where
   factors :: Vector a -> [Vector a]
factors Vector a
x = forall {t} {a}.
(Eq t, Num t, Enum t) =>
t -> Vector a -> [Vector a]
factorize (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 forall a. a -> [a] -> [a]
: t -> Vector a -> [Vector a]
factorize (forall a. Enum a => a -> a
pred t
n) Vector a
xs'
               where (Vector a
xs1, Vector a
xs') = forall a. Int -> Vector a -> (Vector a, Vector a)
Vector.splitAt Int
1 Vector a
xs
   primePrefix :: Vector a -> Vector a
primePrefix = forall a. Int -> Vector a -> Vector a
Vector.take Int
1
   primeSuffix :: Vector a -> Vector a
primeSuffix Vector a
x = forall a. Int -> Vector a -> Vector a
Vector.drop (forall a. Vector a -> Int
Vector.length Vector a
x forall a. Num a => a -> a -> a
- Int
1) Vector a
x
   foldl :: forall a. (a -> Vector a -> a) -> a -> Vector a -> a
foldl a -> Vector a -> a
f = 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 (forall a. a -> Vector a
Vector.singleton a
byte)
   foldl' :: forall a. (a -> Vector a -> a) -> a -> Vector a -> a
foldl' a -> Vector a -> a
f = 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 (forall a. a -> Vector a
Vector.singleton a
byte)
   foldr :: forall a. (Vector a -> a -> a) -> a -> Vector a -> a
foldr Vector a -> a -> a
f = 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 (forall a. a -> Vector a
Vector.singleton a
byte) a
a
   length :: Vector a -> Int
length = forall a. Vector a -> Int
Vector.length
   reverse :: Vector a -> Vector a
reverse = forall a. Vector a -> Vector a
Vector.reverse

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

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

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