fact package:monoid-subclasses

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

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

Class of monoids that can be split into irreducible (i.e., atomic or prime) factors in a unique way. Note that mempty is not considered a factor. 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 in addition to those of Factorial:

null == List.null . 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
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 should implement splitPrimePrefix for performance reasons, and other methods where beneficial.

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

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:

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:

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.

Deprecated: Use Data.Semigroup.Factorial.StableFactorial instead.

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)