    {-
        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 #-}
    {-# LANGUAGE GeneralizedNewtypeDeriving #-}
    {-# LANGUAGE StandaloneDeriving #-}

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

    import qualified Control.Monad as Monad
    import Data.Functor.Const (Const (Const))
    import Data.Functor.Identity (Identity (Identity))
    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 = (m -> [m] -> [m]) -> [m] -> m -> [m]
    forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (m -> a -> a) -> a -> m -> a
    foldr (:) []
       primePrefix m
    s = (m -> m -> m) -> m -> m -> m
    forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (m -> a -> a) -> a -> m -> a
    foldr m -> m -> m
    forall a b. a -> b -> a
    const m
    s m
    s
       primeSuffix m
    s = (m -> m -> m) -> m -> m -> m
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> m -> a) -> a -> m -> a
    foldl ((m -> m) -> m -> m -> m
    forall a b. a -> b -> a
    const m -> m
    forall a. a -> a
    id) m
    s m
    s
       foldl a -> m -> a
    f a
    f0 = (a -> m -> a) -> a -> [m] -> a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    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. Factorial m => m -> [m]
    factors
       foldl' a -> m -> a
    f a
    f0 = (a -> m -> a) -> a -> [m] -> a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    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. Factorial m => m -> [m]
    factors
       foldr m -> a -> a
    f a
    f0 = (m -> a -> a) -> a -> [m] -> a
    forall a b. (a -> b -> b) -> b -> [a] -> b
    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. Factorial m => m -> [m]
    factors
       length = (Int -> m -> Int) -> Int -> m -> Int
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> m -> a) -> a -> m -> a
    foldl' (Int -> m -> Int
    forall a b. a -> b -> a
    const (Int -> m -> Int) -> (Int -> Int) -> Int -> m -> Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> Int
    forall a. Enum a => a -> a
    succ) Int
    0
       foldMap m -> n
    f = (m -> n -> n) -> n -> m -> n
    forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (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
       reverse m
    s = m -> (NonEmpty m -> m) -> Maybe (NonEmpty m) -> m
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe m
    s NonEmpty m -> m
    forall a. Semigroup a => NonEmpty a -> a
    sconcat ([m] -> Maybe (NonEmpty m)
    forall a. [a] -> Maybe (NonEmpty a)
    nonEmpty ([m] -> Maybe (NonEmpty m)) -> [m] -> Maybe (NonEmpty m)
    forall a b. (a -> b) -> a -> b
    $ [m] -> [m]
    forall a. [a] -> [a]
    List.reverse ([m] -> [m]) -> [m] -> [m]
    forall a b. (a -> b) -> a -> b
    $ m -> [m]
    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

    deriving instance Factorial a => Factorial (Identity a)

    deriving instance Factorial a => Factorial (Const a b)

    instance Factorial a => Factorial (Dual a) where
       factors :: Dual a -> [Dual a]
    factors (Dual a
    a) = (a -> Dual a) -> [a] -> [Dual a]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> Dual a
    forall a. a -> Dual a
    Dual ([a] -> [a]
    forall m. Factorial m => m -> m
    reverse ([a] -> [a]) -> [a] -> [a]
    forall a b. (a -> b) -> a -> b
    $ a -> [a]
    forall m. Factorial m => m -> [m]
    factors a
    a)
       length :: Dual a -> Int
    length (Dual a
    a) = a -> Int
    forall m. Factorial 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. Factorial 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. Factorial m => m -> m
    primePrefix a
    a)
       reverse :: Dual a -> Dual a
    reverse (Dual a
    a) = a -> Dual a
    forall a. a -> Dual a
    Dual (a -> a
    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) = 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. Factorial m => m -> m
    primePrefix
       factors :: Sum a -> [Sum a]
    factors (Sum a
    n) = Int -> Sum a -> [Sum a]
    forall a. Int -> a -> [a]
    replicate (a -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (a -> Int) -> a -> Int
    forall a b. (a -> b) -> a -> b
    $ a -> a
    forall a. Num a => a -> a
    abs a
    n) (a -> Sum a
    forall a. a -> Sum a
    Sum (a -> Sum a) -> a -> Sum a
    forall a b. (a -> b) -> a -> b
    $ a -> a
    forall a. Num a => a -> a
    signum a
    n)
       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 => Factorial (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 Factorial a => Factorial (Maybe a) where
       factors :: Maybe a -> [Maybe a]
    factors Maybe a
    Nothing = []
       factors (Just a
    a) = case a -> [a]
    forall m. Factorial m => m -> [m]
    factors a
    a
                          of [] -> [a -> Maybe a
    forall a. a -> Maybe a
    Just a
    a]
                             [a]
    as -> (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]
    as
       length :: Maybe a -> Int
    length Maybe a
    Nothing = Int
    0
       length (Just a
    a) = Int -> Int -> Int
    forall a. Ord a => a -> a -> a
    max Int
    1 (a -> Int
    forall m. Factorial m => m -> Int
    length a
    a)
       reverse :: Maybe a -> Maybe a
    reverse = (a -> a) -> Maybe a -> Maybe a
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> a
    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) = (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. Factorial 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. Factorial 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. Factorial m => m -> m
    primePrefix b
    b)
                          | Bool
    otherwise = (a -> a
    forall m. Factorial 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. Factorial m => m -> m
    primeSuffix a
    a, b
    b)
                          | Bool
    otherwise = (a
    forall a. Monoid a => a
    mempty, b -> b
    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) = (a -> b -> a) -> a -> b -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> b -> a) -> a -> b -> a
    foldl a -> b -> a
    f2 ((a -> a -> a) -> a -> a -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> a -> a) -> a -> a -> 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' :: forall a. (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
    forall a b. a -> b -> b
    `seq` (a -> b -> a) -> a -> b -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> b -> a) -> a -> b -> 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. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> a -> a) -> a -> a -> 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) = (a -> a -> a) -> a -> a -> a
    forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (a -> a -> a) -> a -> a -> 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. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (b -> a -> a) -> a -> b -> 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 :: forall n. Monoid n => ((a, b) -> n) -> (a, b) -> n
    foldMap (a, b) -> n
    f (a
    x, b
    y) = (a -> n) -> a -> n
    forall n. Monoid n => (a -> n) -> a -> n
    forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
    Data.Semigroup.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 n. Monoid n => (b -> n) -> b -> n
    forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
    Data.Semigroup.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. Factorial m => m -> Int
    length a
    a Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + b -> Int
    forall m. Factorial m => m -> Int
    length b
    b
       reverse :: (a, b) -> (a, b)
    reverse (a
    a, b
    b) = (a -> a
    forall m. Factorial m => m -> m
    reverse a
    a, b -> b
    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, b
    forall a. Monoid a => a
    mempty)

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

    instance (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) = (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. Factorial 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. Factorial 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. Factorial 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. Factorial 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. Factorial 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. Factorial 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. Factorial 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. Factorial m => m -> m
    primeSuffix b
    b, c
    forall a. Monoid a => a
    mempty)
                             | Bool
    otherwise = (a -> a
    forall m. Factorial m => m -> m
    primeSuffix a
    a, b
    forall a. Monoid a => a
    mempty, c
    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) = (a -> c -> a) -> a -> c -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> c -> a) -> a -> c -> a
    foldl a -> c -> a
    f3 ((a -> b -> a) -> a -> b -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> b -> a) -> a -> b -> a
    foldl a -> b -> a
    f2 ((a -> a -> a) -> a -> a -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> a -> a) -> a -> a -> 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' :: 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' a -> a -> a
    forall a b. a -> b -> b
    `seq` a
    b' a -> a -> a
    forall a b. a -> b -> b
    `seq` (a -> c -> a) -> a -> c -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> c -> a) -> a -> c -> 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. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> a -> a) -> a -> a -> a
    foldl' a -> a -> a
    f1 a
    s0 a
    a
                b' :: a
    b' = (a -> b -> a) -> a -> b -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> b -> a) -> a -> b -> 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) = (a -> a -> a) -> a -> a -> a
    forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (a -> a -> a) -> a -> a -> 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. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (b -> a -> a) -> a -> b -> 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. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (c -> a -> a) -> a -> c -> 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 :: forall n. Monoid n => ((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 n. Monoid n => (a -> n) -> a -> n
    forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
    Data.Semigroup.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 n. Monoid n => (b -> n) -> b -> n
    forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
    Data.Semigroup.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 n. Monoid n => (c -> n) -> c -> n
    forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
    Data.Semigroup.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. Factorial m => m -> Int
    length a
    a Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + b -> Int
    forall m. Factorial m => m -> Int
    length b
    b Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + c -> Int
    forall m. Factorial m => m -> Int
    length c
    c
       reverse :: (a, b, c) -> (a, b, c)
    reverse (a
    a, b
    b, c
    c) = (a -> a
    forall m. Factorial m => m -> m
    reverse a
    a, b -> b
    forall m. Factorial m => m -> m
    reverse b
    b, c -> c
    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, b
    forall a. Monoid a => a
    mempty, c
    forall a. Monoid a => a
    mempty)

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

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

    instance (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) = (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. Factorial 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. Factorial 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. Factorial 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. 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 (a -> Bool
    forall m. MonoidNull m => m -> Bool
    null a
    a) = (a -> a
    forall m. Factorial 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. Factorial 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. Factorial 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. 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 (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. Factorial 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. Factorial 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. Factorial 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. Factorial 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)
       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 -> d -> a) -> a -> d -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> d -> a) -> a -> d -> a
    foldl a -> d -> a
    f4 ((a -> c -> a) -> a -> c -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> c -> a) -> a -> c -> a
    foldl a -> c -> a
    f3 ((a -> b -> a) -> a -> b -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> b -> a) -> a -> b -> a
    foldl a -> b -> a
    f2 ((a -> a -> a) -> a -> a -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> a -> a) -> a -> a -> 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' :: 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' a -> a -> a
    forall a b. a -> b -> b
    `seq` a
    b' a -> a -> a
    forall a b. a -> b -> b
    `seq` a
    c' a -> a -> a
    forall a b. a -> b -> b
    `seq` (a -> d -> a) -> a -> d -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> d -> a) -> a -> d -> 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. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> a -> a) -> a -> a -> a
    foldl' a -> a -> a
    f1 a
    s0 a
    a
                b' :: a
    b' = (a -> b -> a) -> a -> b -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> b -> a) -> a -> b -> a
    foldl' a -> b -> a
    f2 a
    a' b
    b
                c' :: a
    c' = (a -> c -> a) -> a -> c -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> c -> a) -> a -> c -> 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) =
          (a -> a -> a) -> a -> a -> a
    forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (a -> a -> a) -> a -> a -> 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. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (b -> a -> a) -> a -> b -> 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. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (c -> a -> a) -> a -> c -> 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. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (d -> a -> a) -> a -> d -> 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 :: 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) = (a -> n) -> a -> n
    forall n. Monoid n => (a -> n) -> a -> n
    forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
    Data.Semigroup.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 n. Monoid n => (b -> n) -> b -> n
    forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
    Data.Semigroup.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 n. Monoid n => (c -> n) -> c -> n
    forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
    Data.Semigroup.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 n. Monoid n => (d -> n) -> d -> n
    forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
    Data.Semigroup.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. Factorial m => m -> Int
    length a
    a Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + b -> Int
    forall m. Factorial m => m -> Int
    length b
    b Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + c -> Int
    forall m. Factorial m => m -> Int
    length c
    c Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + d -> Int
    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) = (a -> a
    forall m. Factorial m => m -> m
    reverse a
    a, b -> b
    forall m. Factorial m => m -> m
    reverse b
    b, c -> c
    forall m. Factorial m => m -> m
    reverse c
    c, d -> d
    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, b
    forall a. Monoid a => a
    mempty, c
    forall a. Monoid a => a
    mempty, d
    forall a. Monoid a => a
    mempty)

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

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

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

    instance Factorial [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. HasCallStack => [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) = (a -> [x] -> a) -> a -> [x] -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> [x] -> a) -> a -> [x] -> 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' a -> a -> a
    forall a b. a -> b -> b
    `seq` (a -> [x] -> a) -> a -> [x] -> a
    forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
    forall a. (a -> [x] -> a) -> a -> [x] -> 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] (([x] -> a -> a) -> a -> [x] -> a
    forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. ([x] -> a -> a) -> a -> [x] -> a
    foldr [x] -> a -> a
    f a
    f0 [x]
    xs)
       length :: [x] -> Int
    length = [x] -> Int
    forall x. [x] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    List.length
       foldMap :: forall n. Monoid n => ([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]
    :[]))
       reverse :: [x] -> [x]
    reverse = [x] -> [x]
    forall a. [a] -> [a]
    List.reverse

    instance Factorial 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
       foldl :: forall a. (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' :: forall a. (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 :: forall a. (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)
       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 = 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
       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
       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 (HasCallStack => Text -> Char
    Text -> Char
    Text.last Text
    x)
       foldl :: forall a. (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' :: forall a. (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 :: forall a. (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
       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 (HasCallStack => Text -> Char
    Text -> Char
    LazyText.last Text
    x)
       foldl :: forall a. (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' :: forall a. (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 :: forall a. (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
       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 = ((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
       foldl :: forall a. (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' :: forall a. (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 :: forall a. (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 Factorial (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
       foldl :: forall a. (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' :: forall a. (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 :: forall a. (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 Factorial 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
       foldl :: forall a. (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' :: forall a. (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 :: forall a. (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 Factorial (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 a. 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
       foldl :: forall a. (a -> Seq a -> a) -> a -> Seq a -> a
    foldl a -> Seq a -> a
    f = (a -> a -> a) -> a -> Seq a -> a
    forall b a. (b -> a -> b) -> b -> Seq a -> b
    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' :: forall a. (a -> Seq a -> a) -> a -> Seq a -> a
    foldl' a -> Seq a -> a
    f = (a -> a -> a) -> a -> Seq a -> a
    forall b a. (b -> a -> b) -> b -> Seq a -> b
    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 :: forall a. (Seq a -> a -> a) -> a -> Seq a -> a
    foldr Seq a -> a -> a
    f = (a -> a -> a) -> a -> Seq a -> a
    forall a b. (a -> b -> b) -> b -> Seq a -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    Foldable.foldr a -> 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
       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 => Factorial (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
       foldl :: forall a. (a -> Set a -> a) -> a -> Set a -> a
    foldl a -> Set a -> a
    f = (a -> a -> a) -> a -> Set a -> a
    forall b a. (b -> a -> b) -> b -> Set a -> b
    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' :: forall a. (a -> Set a -> a) -> a -> Set a -> a
    foldl' a -> Set a -> a
    f = (a -> a -> a) -> a -> Set a -> a
    forall b a. (b -> a -> b) -> b -> Set a -> b
    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 :: forall a. (Set a -> a -> a) -> a -> Set a -> a
    foldr Set a -> a -> a
    f = (a -> a -> a) -> a -> Set a -> a
    forall a b. (a -> b -> b) -> b -> Set a -> b
    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 Factorial (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
       foldl :: forall a. (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' :: forall a. (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 :: forall a. (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
       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 StableFactorial ()
    instance StableFactorial a => StableFactorial (Identity a)
    instance StableFactorial a => StableFactorial (Const a b)
    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 = ((m b -> m b) -> m b -> m b
    forall a b. (a -> b) -> a -> b
    $ b -> m b
    forall a. a -> m a
    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 n. Monoid n => (a -> n) -> a -> n
    forall m n. (Factorial m, Monoid n) => (m -> n) -> m -> n
    Data.Semigroup.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_ :: (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 = (a -> m () -> m ()) -> m () -> a -> m ()
    forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
    forall a. (a -> a -> a) -> a -> a -> a
    foldr (m b -> m () -> m ()
    forall a b. m a -> m b -> m b
    forall (f :: * -> *) a b. Applicative f => f a -> f b -> f 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 a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure ())