Data.Monoid.Factorial

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

Classes

class MonoidNull m => FactorialMonoid m where

Class of monoids that can be split into irreducible (i.e., atomic or prime) factors in a unique way. Factors of a Product are literally its prime factors:

factors (Product 12) == [Product 2, Product 2, Product 3]

Factors of a list are not its elements but all its single-item sublists:

factors "abc" == ["a", "b", "c"]

The methods of this class satisfy the following laws:

mconcat . factors == id
null == List.null . factors
List.all (\prime-> factors prime == [prime]) . factors
factors == unfoldr splitPrimePrefix == List.reverse . unfoldr (fmap swap . splitPrimeSuffix)
reverse == mconcat . List.reverse . factors
primePrefix == maybe mempty fst . splitPrimePrefix
primeSuffix == maybe mempty snd . splitPrimeSuffix
inits == List.map mconcat . List.inits . factors
tails == List.map mconcat . List.tails . factors
foldl f a == List.foldl f a . factors
foldl' f a == List.foldl' f a . factors
foldr f a == List.foldr f a . factors
span p m == (mconcat l, mconcat r) where (l, r) = List.span p (factors m)
List.all (List.all (not . pred) . factors) . split pred
mconcat . intersperse prime . split (== prime) == id
splitAt i m == (mconcat l, mconcat r) where (l, r) = List.splitAt i (factors m)
spanMaybe () (const $ bool Nothing (Maybe ()) . p) m == (takeWhile p m, dropWhile p m, ())
spanMaybe s0 (\s m-> Just $ f s m) m0 == (m0, mempty, foldl f s0 m0)
let (prefix, suffix, s') = spanMaybe s f m
    foldMaybe = foldl g (Just s)
    g s m = s >>= flip f m
in all ((Nothing ==) . foldMaybe) (inits prefix)
   && prefix == last (filter (isJust . foldMaybe) $ inits m)
   && Just s' == foldMaybe prefix
   && m == prefix <> suffix

A minimal instance definition must implement factors or splitPrimePrefix. Other methods are provided and should be implemented only for performance reasons.

Minimal complete definition

factors | splitPrimePrefix

Methods

factors :: m -> [m]

Returns a list of all prime factors; inverse of mconcat.

primePrefix :: m -> m

The prime prefix, mempty if none.

primeSuffix :: m -> m

The prime suffix, mempty if none.

splitPrimePrefix :: m -> Maybe (m, m)

Splits the argument into its prime prefix and the remaining suffix. Returns Nothing for mempty.

splitPrimeSuffix :: m -> Maybe (m, m)

Splits the argument into its prime suffix and the remaining prefix. Returns Nothing for mempty.

inits :: m -> [m]

Returns the list of all prefixes of the argument, mempty first.

tails :: m -> [m]

Returns the list of all suffixes of the argument, mempty last.

foldl :: (a -> m -> a) -> a -> m -> a

Like foldl from Data.List on the list of primes.

foldl' :: (a -> m -> a) -> a -> m -> a

Like foldl' from Data.List on the list of primes.

foldr :: (m -> a -> a) -> a -> m -> a

Like foldr from Data.List on the list of primes.

length :: m -> Int

The length of the list of primes.

foldMap :: Monoid n => (m -> n) -> m -> n

Generalizes foldMap from Data.Foldable, except the function arguments are prime factors rather than the structure elements.

span :: (m -> Bool) -> m -> (m, m)

Like span from Data.List on the list of primes.

break :: (m -> Bool) -> m -> (m, m)

Equivalent to break from Data.List.

split :: (m -> Bool) -> m -> [m]

Splits the monoid into components delimited by prime separators satisfying the given predicate. The primes satisfying the predicate are not a part of the result.

takeWhile :: (m -> Bool) -> m -> m

Equivalent to takeWhile from Data.List.

dropWhile :: (m -> Bool) -> m -> m

Equivalent to dropWhile from Data.List.

spanMaybe :: s -> (s -> m -> Maybe s) -> m -> (m, m, s)

A stateful variant of span, threading the result of the test function as long as it returns Just.

spanMaybe' :: s -> (s -> m -> Maybe s) -> m -> (m, m, s)

Strict version of spanMaybe.

splitAt :: Int -> m -> (m, m)

Like splitAt from Data.List on the list of primes.

drop :: Int -> m -> m

Equivalent to drop from Data.List.

take :: Int -> m -> m

Equivalent to take from Data.List.

reverse :: m -> m

Equivalent to reverse from Data.List.

Instances

FactorialMonoid ()

FactorialMonoid ByteString

FactorialMonoid ByteString

FactorialMonoid IntSet

FactorialMonoid Text

FactorialMonoid Text

FactorialMonoid ByteStringUTF8

FactorialMonoid [x]

FactorialMonoid a => FactorialMonoid (Dual a)

(Integral a, Eq a) => FactorialMonoid (Sum a)

Integral a => FactorialMonoid (Product a)

FactorialMonoid a => FactorialMonoid (Maybe a)

FactorialMonoid (IntMap a)

Ord a => FactorialMonoid (Set a)

FactorialMonoid (Seq a)

FactorialMonoid (Vector a)

FactorialMonoid a => FactorialMonoid (Concat a)

StableFactorialMonoid a => FactorialMonoid (Measured a)

(StableFactorialMonoid m, TextualMonoid m) => FactorialMonoid (LinePositioned m)

StableFactorialMonoid m => FactorialMonoid (OffsetPositioned m)

(FactorialMonoid a, FactorialMonoid b) => FactorialMonoid (a, b)

Ord k => FactorialMonoid (Map k v)

(FactorialMonoid a, FactorialMonoid b) => FactorialMonoid (Stateful a b)

class (FactorialMonoid m, PositiveMonoid m) => StableFactorialMonoid m

A subclass of FactorialMonoid whose instances satisfy this additional law:

factors (a <> b) == factors a <> factors b

Instances

StableFactorialMonoid ()

StableFactorialMonoid ByteString

StableFactorialMonoid ByteString

StableFactorialMonoid Text

StableFactorialMonoid Text

StableFactorialMonoid [x]

StableFactorialMonoid a => StableFactorialMonoid (Dual a)

StableFactorialMonoid (Seq a)

StableFactorialMonoid (Vector a)

StableFactorialMonoid a => StableFactorialMonoid (Measured a)

(StableFactorialMonoid m, TextualMonoid m) => StableFactorialMonoid (LinePositioned m)

StableFactorialMonoid m => StableFactorialMonoid (OffsetPositioned m)

(StableFactorialMonoid a, StableFactorialMonoid b) => StableFactorialMonoid (Stateful a b)

Monad function equivalents

mapM :: (FactorialMonoid a, Monoid b, Monad m) => (a -> m b) -> a -> m b

A mapM equivalent.

mapM_ :: (FactorialMonoid a, Monad m) => (a -> m b) -> a -> m ()

A mapM_ equivalent.