{- 
    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 hiding (break, drop, dropWhile, foldl, foldr, last, length, map, mapM, mapM_, null, reverse)

-- | 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
foldr (:) []
   primePrefix m
s = (m -> m -> m) -> m -> m -> m
forall m a. Factorial m => (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
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 (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 (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 (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
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
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 #-}

-- | 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) = (a -> Dual a) -> [a] -> [Dual a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Dual a
forall a. a -> Dual a
Dual ([a] -> [a]
forall m. Factorial m => m -> m
reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a -> [a]
forall m. 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 (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 :: (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
foldl a -> b -> a
f2 ((a -> a -> a) -> a -> a -> a
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 ((a, b) -> a) -> (a -> (a, b)) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b)
forall b a. Monoid b => a -> (a, b)
fromFst
            f2 :: a -> b -> a
f2 a
a = a -> (a, b) -> a
f a
a ((a, b) -> a) -> (b -> (a, b)) -> b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b)
forall a b. Monoid a => b -> (a, b)
fromSnd
   foldl' :: (a -> (a, b) -> a) -> a -> (a, b) -> a
foldl' a -> (a, b) -> a
f a
a0 (a
x, b
y) = a
a' a -> a -> a
`seq` (a -> b -> a) -> a -> b -> a
forall m a. 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 ((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
foldl' a -> a -> a
f1 a
a0 a
x
   foldr :: ((a, b) -> a -> a) -> a -> (a, b) -> a
foldr (a, b) -> a -> a
f a
a (a
x, b
y) = (a -> a -> a) -> a -> a -> a
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b) -> a -> a
f ((a, b) -> a -> a) -> (a -> (a, b)) -> a -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b)
forall b a. Monoid b => a -> (a, b)
fromFst) ((b -> a -> a) -> a -> b -> a
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b) -> a -> a
f ((a, b) -> a -> a) -> (b -> (a, b)) -> b -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b)
forall a b. Monoid a => b -> (a, b)
fromSnd) a
a b
y) a
x
   foldMap :: ((a, b) -> n) -> (a, b) -> n
foldMap (a, b) -> n
f (a
x, b
y) = (a -> n) -> a -> n
forall m n. (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 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 :: a -> (a, b)
fromFst a
a = (a
a, b
forall a. Monoid a => a
mempty)

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

instance (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 :: (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
foldl a -> c -> a
f3 ((a -> b -> a) -> a -> b -> a
forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl a -> b -> a
f2 ((a -> a -> a) -> a -> a -> a
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 ((a, b, c) -> a) -> (a -> (a, b, c)) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c)
forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3
            f2 :: a -> b -> a
f2 a
x = a -> (a, b, c) -> a
f a
x ((a, b, c) -> a) -> (b -> (a, b, c)) -> b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c)
forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3
            f3 :: a -> c -> a
f3 a
x = a -> (a, b, c) -> a
f a
x ((a, b, c) -> a) -> (c -> (a, b, c)) -> c -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c)
forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3
   foldl' :: (a -> (a, b, c) -> a) -> a -> (a, b, c) -> a
foldl' a -> (a, b, c) -> a
f a
s0 (a
a, b
b, c
c) = a
a' a -> a -> a
`seq` a
b' a -> a -> a
`seq` (a -> c -> a) -> a -> c -> a
forall m a. 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 ((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
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
foldl' a -> b -> a
f2 a
a' b
b
   foldr :: ((a, b, c) -> a -> a) -> a -> (a, b, c) -> a
foldr (a, b, c) -> a -> a
f a
s (a
a, b
b, c
c) = (a -> a -> a) -> a -> a -> a
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c) -> a -> a
f ((a, b, c) -> a -> a) -> (a -> (a, b, c)) -> a -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c)
forall b c a. (Monoid b, Monoid c) => a -> (a, b, c)
fromFstOf3) ((b -> a -> a) -> a -> b -> a
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c) -> a -> a
f ((a, b, c) -> a -> a) -> (b -> (a, b, c)) -> b -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c)
forall a c b. (Monoid a, Monoid c) => b -> (a, b, c)
fromSndOf3) ((c -> a -> a) -> a -> c -> a
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c) -> a -> a
f ((a, b, c) -> a -> a) -> (c -> (a, b, c)) -> c -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c)
forall a b c. (Monoid a, Monoid b) => c -> (a, b, c)
fromThdOf3) a
s c
c) b
b) a
a
   foldMap :: ((a, b, c) -> n) -> (a, b, c) -> n
foldMap (a, b, c) -> n
f (a
a, b
b, c
c) = (a -> n) -> a -> n
forall m n. (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 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 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 :: a -> (a, b, c)
fromFstOf3 a
a = (a
a, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty)

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

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

instance (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 :: (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
foldl a -> d -> a
f4 ((a -> c -> a) -> a -> c -> a
forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl a -> c -> a
f3 ((a -> b -> a) -> a -> b -> a
forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl a -> b -> a
f2 ((a -> a -> a) -> a -> a -> a
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 ((a, b, c, d) -> a) -> (a -> (a, b, c, d)) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c, d)
forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4
            f2 :: a -> b -> a
f2 a
x = a -> (a, b, c, d) -> a
f a
x ((a, b, c, d) -> a) -> (b -> (a, b, c, d)) -> b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c, d)
forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4
            f3 :: a -> c -> a
f3 a
x = a -> (a, b, c, d) -> a
f a
x ((a, b, c, d) -> a) -> (c -> (a, b, c, d)) -> c -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c, d)
forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4
            f4 :: a -> d -> a
f4 a
x = a -> (a, b, c, d) -> a
f a
x ((a, b, c, d) -> a) -> (d -> (a, b, c, d)) -> d -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. d -> (a, b, c, d)
forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4
   foldl' :: (a -> (a, b, c, d) -> a) -> a -> (a, b, c, d) -> a
foldl' a -> (a, b, c, d) -> a
f a
s0 (a
a, b
b, c
c, d
d) = a
a' a -> a -> a
`seq` a
b' a -> a -> a
`seq` a
c' a -> a -> a
`seq` (a -> d -> a) -> a -> d -> a
forall m a. 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 ((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
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
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
foldl' a -> c -> a
f3 a
b' c
c
   foldr :: ((a, b, c, d) -> a -> a) -> a -> (a, b, c, d) -> a
foldr (a, b, c, d) -> a -> a
f a
s (a
a, b
b, c
c, d
d) =
      (a -> a -> a) -> a -> a -> a
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f ((a, b, c, d) -> a -> a) -> (a -> (a, b, c, d)) -> a -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> (a, b, c, d)
forall b c d a. (Monoid b, Monoid c, Monoid d) => a -> (a, b, c, d)
fromFstOf4) ((b -> a -> a) -> a -> b -> a
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f ((a, b, c, d) -> a -> a) -> (b -> (a, b, c, d)) -> b -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> (a, b, c, d)
forall a c d b. (Monoid a, Monoid c, Monoid d) => b -> (a, b, c, d)
fromSndOf4) ((c -> a -> a) -> a -> c -> a
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f ((a, b, c, d) -> a -> a) -> (c -> (a, b, c, d)) -> c -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> (a, b, c, d)
forall a b d c. (Monoid a, Monoid b, Monoid d) => c -> (a, b, c, d)
fromThdOf4) ((d -> a -> a) -> a -> d -> a
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr ((a, b, c, d) -> a -> a
f ((a, b, c, d) -> a -> a) -> (d -> (a, b, c, d)) -> d -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. d -> (a, b, c, d)
forall a b c d. (Monoid a, Monoid b, Monoid c) => d -> (a, b, c, d)
fromFthOf4) a
s d
d) c
c) b
b) a
a
   foldMap :: ((a, b, c, d) -> n) -> (a, b, c, d) -> n
foldMap (a, b, c, d) -> n
f (a
a, b
b, c
c, d
d) = (a -> n) -> a -> n
forall m n. (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 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 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 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 :: a -> (a, b, c, d)
fromFstOf4 a
a = (a
a, b
forall a. Monoid a => a
mempty, c
forall a. Monoid a => a
mempty, d
forall a. Monoid a => a
mempty)

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

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

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

instance 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. [a] -> a
List.last [x]
xs]
   foldl :: (a -> [x] -> a) -> a -> [x] -> a
foldl a -> [x] -> a
_ a
a [] = a
a
   foldl a -> [x] -> a
f a
a (x
x:[x]
xs) = (a -> [x] -> a) -> a -> [x] -> a
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' :: (a -> [x] -> a) -> a -> [x] -> a
foldl' a -> [x] -> a
_ a
a [] = a
a
   foldl' a -> [x] -> a
f a
a (x
x:[x]
xs) = let a' :: a
a' = a -> [x] -> a
f a
a [x
x] in a
a' a -> a -> a
`seq` (a -> [x] -> a) -> a -> [x] -> a
forall m a. Factorial m => (a -> m -> a) -> a -> m -> a
foldl' a -> [x] -> a
f a
a' [x]
xs
   foldr :: ([x] -> a -> a) -> a -> [x] -> a
foldr [x] -> a -> a
_ a
f0 [] = a
f0
   foldr [x] -> a -> a
f a
f0 (x
x:[x]
xs) = [x] -> a -> a
f [x
x] (([x] -> a -> a) -> a -> [x] -> a
forall m a. Factorial m => (m -> a -> a) -> a -> m -> a
foldr [x] -> a -> a
f a
f0 [x]
xs)
   length :: [x] -> Int
length = [x] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
List.length
   foldMap :: ([x] -> n) -> [x] -> n
foldMap [x] -> n
f = [n] -> n
forall a. Monoid a => [a] -> a
mconcat ([n] -> n) -> ([x] -> [n]) -> [x] -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> n) -> [x] -> [n]
forall a b. (a -> b) -> [a] -> [b]
List.map ([x] -> n
f ([x] -> n) -> (x -> [x]) -> x -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (x -> [x] -> [x]
forall a. a -> [a] -> [a]
:[]))
   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 :: (a -> ByteString -> a) -> a -> ByteString -> a
foldl a -> ByteString -> a
f = (a -> Word8 -> a) -> a -> ByteString -> a
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
ByteString.foldl a -> Word8 -> a
f'
      where f' :: a -> Word8 -> a
f' a
a Word8
byte = a -> ByteString -> a
f a
a (Word8 -> ByteString
ByteString.singleton Word8
byte)
   foldl' :: (a -> ByteString -> a) -> a -> ByteString -> a
foldl' a -> ByteString -> a
f = (a -> Word8 -> a) -> a -> ByteString -> a
forall a. (a -> Word8 -> a) -> a -> ByteString -> a
ByteString.foldl' a -> Word8 -> a
f'
      where f' :: a -> Word8 -> a
f' a
a Word8
byte = a -> ByteString -> a
f a
a (Word8 -> ByteString
ByteString.singleton Word8
byte)
   foldr :: (ByteString -> a -> a) -> a -> ByteString -> a
foldr ByteString -> a -> a
f = (Word8 -> a -> a) -> a -> ByteString -> a
forall a. (Word8 -> a -> a) -> a -> ByteString -> a
ByteString.foldr (ByteString -> a -> a
f (ByteString -> a -> a) -> (Word8 -> ByteString) -> Word8 -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word8 -> ByteString
ByteString.singleton)
   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 (Text -> Char
Text.last Text
x)
   foldl :: (a -> Text -> a) -> a -> Text -> a
foldl a -> Text -> a
f = (a -> Char -> a) -> a -> Text -> a
forall a. (a -> Char -> a) -> a -> Text -> a
Text.foldl a -> Char -> a
f'
      where f' :: a -> Char -> a
f' a
a Char
char = a -> Text -> a
f a
a (Char -> Text
Text.singleton Char
char)
   foldl' :: (a -> Text -> a) -> a -> Text -> a
foldl' a -> Text -> a
f = (a -> Char -> a) -> a -> Text -> a
forall a. (a -> Char -> a) -> a -> Text -> a
Text.foldl' a -> Char -> a
f'
      where f' :: a -> Char -> a
f' a
a Char
char = a -> Text -> a
f a
a (Char -> Text
Text.singleton Char
char)
   foldr :: (Text -> a -> a) -> a -> Text -> a
foldr Text -> a -> a
f = (Char -> a -> a) -> a -> Text -> a
forall a. (Char -> a -> a) -> a -> Text -> a
Text.foldr Char -> a -> a
f'
      where f' :: Char -> a -> a
f' Char
char a
a = Text -> a -> a
f (Char -> Text
Text.singleton Char
char) a
a
   length :: Text -> Int
length = Text -> Int
Text.length
   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 :: (a -> Text -> a) -> a -> Text -> a
foldl a -> Text -> a
f = (a -> Char -> a) -> a -> Text -> a
forall a. (a -> Char -> a) -> a -> Text -> a
LazyText.foldl a -> Char -> a
f'
      where f' :: a -> Char -> a
f' a
a Char
char = a -> Text -> a
f a
a (Char -> Text
LazyText.singleton Char
char)
   foldl' :: (a -> Text -> a) -> a -> Text -> a
foldl' a -> Text -> a
f = (a -> Char -> a) -> a -> Text -> a
forall a. (a -> Char -> a) -> a -> Text -> a
LazyText.foldl' a -> Char -> a
f'
      where f' :: a -> Char -> a
f' a
a Char
char = a -> Text -> a
f a
a (Char -> Text
LazyText.singleton Char
char)
   foldr :: (Text -> a -> a) -> a -> Text -> a
foldr Text -> a -> a
f = (Char -> a -> a) -> a -> Text -> a
forall a. (Char -> a -> a) -> a -> Text -> a
LazyText.foldr Char -> a -> a
f'
      where f' :: Char -> a -> a
f' Char
char a
a = Text -> a -> a
f (Char -> Text
LazyText.singleton Char
char) a
a
   length :: Text -> Int
length = Int64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int64 -> Int) -> (Text -> Int64) -> Text -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Text -> Int64
LazyText.length
   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 :: (a -> Map k v -> a) -> a -> Map k v -> a
foldl a -> Map k v -> a
f = (a -> k -> v -> a) -> a -> Map k v -> a
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey a -> k -> v -> a
f'
      where f' :: a -> k -> v -> a
f' a
a k
k v
v = a -> Map k v -> a
f a
a (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v)
   foldl' :: (a -> Map k v -> a) -> a -> Map k v -> a
foldl' a -> Map k v -> a
f = (a -> k -> v -> a) -> a -> Map k v -> a
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey' a -> k -> v -> a
f'
      where f' :: a -> k -> v -> a
f' a
a k
k v
v = a -> Map k v -> a
f a
a (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v)
   foldr :: (Map k v -> a -> a) -> a -> Map k v -> a
foldr Map k v -> a -> a
f = (k -> v -> a -> a) -> a -> Map k v -> a
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey k -> v -> a -> a
f'
      where f' :: k -> v -> a -> a
f' k
k v
v a
a = Map k v -> a -> a
f (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v) a
a
   length :: Map k v -> Int
length = Map k v -> Int
forall k a. Map k a -> Int
Map.size
   reverse :: Map k v -> Map k v
reverse = Map k v -> Map k v
forall a. a -> a
id

instance 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 :: (a -> IntMap a -> a) -> a -> IntMap a -> a
foldl a -> IntMap a -> a
f = (a -> Int -> a -> a) -> a -> IntMap a -> a
forall a b. (a -> Int -> b -> a) -> a -> IntMap b -> a
IntMap.foldlWithKey a -> Int -> a -> a
f'
      where f' :: a -> Int -> a -> a
f' a
a Int
k a
v = a -> IntMap a -> a
f a
a (Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v)
   foldl' :: (a -> IntMap a -> a) -> a -> IntMap a -> a
foldl' a -> IntMap a -> a
f = (a -> Int -> a -> a) -> a -> IntMap a -> a
forall a b. (a -> Int -> b -> a) -> a -> IntMap b -> a
IntMap.foldlWithKey' a -> Int -> a -> a
f'
      where f' :: a -> Int -> a -> a
f' a
a Int
k a
v = a -> IntMap a -> a
f a
a (Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v)
   foldr :: (IntMap a -> a -> a) -> a -> IntMap a -> a
foldr IntMap a -> a -> a
f = (Int -> a -> a -> a) -> a -> IntMap a -> a
forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
IntMap.foldrWithKey Int -> a -> a -> a
f'
      where f' :: Int -> a -> a -> a
f' Int
k a
v a
a = IntMap a -> a -> a
f (Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IntMap.singleton Int
k a
v) a
a
   length :: IntMap a -> Int
length = IntMap a -> Int
forall a. IntMap a -> Int
IntMap.size
   reverse :: IntMap a -> IntMap a
reverse = IntMap a -> IntMap a
forall a. a -> a
id

instance 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 :: (a -> IntSet -> a) -> a -> IntSet -> a
foldl a -> IntSet -> a
f = (a -> Int -> a) -> a -> IntSet -> a
forall a. (a -> Int -> a) -> a -> IntSet -> a
IntSet.foldl a -> Int -> a
f'
      where f' :: a -> Int -> a
f' a
a Int
b = a -> IntSet -> a
f a
a (Int -> IntSet
IntSet.singleton Int
b)
   foldl' :: (a -> IntSet -> a) -> a -> IntSet -> a
foldl' a -> IntSet -> a
f = (a -> Int -> a) -> a -> IntSet -> a
forall a. (a -> Int -> a) -> a -> IntSet -> a
IntSet.foldl' a -> Int -> a
f'
      where f' :: a -> Int -> a
f' a
a Int
b = a -> IntSet -> a
f a
a (Int -> IntSet
IntSet.singleton Int
b)
   foldr :: (IntSet -> a -> a) -> a -> IntSet -> a
foldr IntSet -> a -> a
f = (Int -> a -> a) -> a -> IntSet -> a
forall b. (Int -> b -> b) -> b -> IntSet -> b
IntSet.foldr Int -> a -> a
f'
      where f' :: Int -> a -> a
f' Int
a a
b = IntSet -> a -> a
f (Int -> IntSet
IntSet.singleton Int
a) a
b
   length :: IntSet -> Int
length = IntSet -> Int
IntSet.size
   reverse :: IntSet -> IntSet
reverse = IntSet -> IntSet
forall a. a -> a
id

instance 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 (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 :: (a -> Seq a -> a) -> a -> Seq a -> a
foldl a -> Seq a -> a
f = (a -> a -> a) -> a -> Seq a -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
b = a -> Seq a -> a
f a
a (a -> Seq a
forall a. a -> Seq a
Sequence.singleton a
b)
   foldl' :: (a -> Seq a -> a) -> a -> Seq a -> a
foldl' a -> Seq a -> a
f = (a -> a -> a) -> a -> Seq a -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl' a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
b = a -> Seq a -> a
f a
a (a -> Seq a
forall a. a -> Seq a
Sequence.singleton a
b)
   foldr :: (Seq a -> a -> a) -> a -> Seq a -> a
foldr Seq a -> a -> a
f = (a -> a -> a) -> a -> Seq a -> a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
b = Seq a -> a -> a
f (a -> Seq a
forall a. a -> Seq a
Sequence.singleton a
a) a
b
   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 :: (a -> Set a -> a) -> a -> Set a -> a
foldl a -> Set a -> a
f = (a -> a -> a) -> a -> Set a -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
b = a -> Set a -> a
f a
a (a -> Set a
forall a. a -> Set a
Set.singleton a
b)
   foldl' :: (a -> Set a -> a) -> a -> Set a -> a
foldl' a -> Set a -> a
f = (a -> a -> a) -> a -> Set a -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Foldable.foldl' a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
b = a -> Set a -> a
f a
a (a -> Set a
forall a. a -> Set a
Set.singleton a
b)
   foldr :: (Set a -> a -> a) -> a -> Set a -> a
foldr Set a -> a -> a
f = (a -> a -> a) -> a -> Set a -> a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Foldable.foldr a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
b = Set a -> a -> a
f (a -> Set a
forall a. a -> Set a
Set.singleton a
a) a
b
   length :: Set a -> Int
length = Set a -> Int
forall a. Set a -> Int
Set.size
   reverse :: Set a -> Set a
reverse = Set a -> Set a
forall a. a -> a
id

instance 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 :: (a -> Vector a -> a) -> a -> Vector a -> a
foldl a -> Vector a -> a
f = (a -> a -> a) -> a -> Vector a -> a
forall a b. (a -> b -> a) -> a -> Vector b -> a
Vector.foldl a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
byte = a -> Vector a -> a
f a
a (a -> Vector a
forall a. a -> Vector a
Vector.singleton a
byte)
   foldl' :: (a -> Vector a -> a) -> a -> Vector a -> a
foldl' a -> Vector a -> a
f = (a -> a -> a) -> a -> Vector a -> a
forall a b. (a -> b -> a) -> a -> Vector b -> a
Vector.foldl' a -> a -> a
f'
      where f' :: a -> a -> a
f' a
a a
byte = a -> Vector a -> a
f a
a (a -> Vector a
forall a. a -> Vector a
Vector.singleton a
byte)
   foldr :: (Vector a -> a -> a) -> a -> Vector a -> a
foldr Vector a -> a -> a
f = (a -> a -> a) -> a -> Vector a -> a
forall a b. (a -> b -> b) -> b -> Vector a -> b
Vector.foldr a -> a -> a
f'
      where f' :: a -> a -> a
f' a
byte a
a = Vector a -> a -> a
f (a -> Vector a
forall a. a -> Vector a
Vector.singleton a
byte) a
a
   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 (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 :: (a -> m b) -> a -> m b
mapM a -> m b
f = ((m b -> m b) -> m b -> m b
forall a b. (a -> b) -> a -> b
$ b -> m b
forall (m :: * -> *) a. Monad m => a -> m a
return b
forall a. Monoid a => a
mempty) ((m b -> m b) -> m b) -> (a -> m b -> m b) -> a -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Endo (m b) -> m b -> m b
forall a. Endo a -> a -> a
appEndo (Endo (m b) -> m b -> m b) -> (a -> Endo (m b)) -> a -> m b -> m b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Endo (m b)) -> a -> Endo (m b)
forall m n. (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_ :: (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
foldr (m b -> m () -> m ()
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 (f :: * -> *) a. Applicative f => a -> f a
pure ())