Safe Haskell | None |
---|

This module defines the `FactorialMonoid`

class and some of its instances.

- class MonoidNull m => FactorialMonoid m where
- factors :: m -> [m]
- primePrefix :: m -> m
- primeSuffix :: m -> m
- splitPrimePrefix :: m -> Maybe (m, m)
- splitPrimeSuffix :: m -> Maybe (m, m)
- foldl :: (a -> m -> a) -> a -> m -> a
- foldl' :: (a -> m -> a) -> a -> m -> a
- foldr :: (m -> a -> a) -> a -> m -> a
- length :: m -> Int
- foldMap :: (FactorialMonoid m, Monoid n) => (m -> n) -> m -> n
- span :: (m -> Bool) -> m -> (m, m)
- break :: FactorialMonoid m => (m -> Bool) -> m -> (m, m)
- split :: (m -> Bool) -> m -> [m]
- takeWhile :: FactorialMonoid m => (m -> Bool) -> m -> m
- dropWhile :: FactorialMonoid m => (m -> Bool) -> m -> m
- splitAt :: Int -> m -> (m, m)
- drop :: FactorialMonoid m => Int -> m -> m
- take :: FactorialMonoid m => Int -> m -> m
- reverse :: FactorialMonoid m => m -> m

- class (FactorialMonoid m, PositiveMonoid m) => StableFactorialMonoid m
- mapM :: (FactorialMonoid a, Monoid b, Monad m) => (a -> m b) -> a -> m b
- mapM_ :: (FactorialMonoid a, Monad m) => (a -> m b) -> a -> m ()

# Classes

class MonoidNull m => FactorialMonoid m whereSource

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 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)

A minimal instance definition must implement `factors`

or `splitPrimePrefix`

. Other methods are provided and should
be implemented only for performance reasons.

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

primePrefix :: m -> mSource

The prime prefix, `mempty`

if none.

primeSuffix :: m -> mSource

The prime suffix, `mempty`

if none.

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

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

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

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

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

The `length`

of the list of `primes`

.

foldMap :: (FactorialMonoid m, Monoid n) => (m -> n) -> m -> nSource

Generalizes `foldMap`

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

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

break :: FactorialMonoid m => (m -> Bool) -> m -> (m, m)Source

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

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 :: FactorialMonoid m => (m -> Bool) -> m -> mSource

dropWhile :: FactorialMonoid m => (m -> Bool) -> m -> mSource

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

drop :: FactorialMonoid m => Int -> m -> mSource

take :: FactorialMonoid m => Int -> m -> mSource

reverse :: FactorialMonoid m => m -> mSource

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 (Seq a) | |

FactorialMonoid (IntMap a) | |

Ord a => FactorialMonoid (Set a) | |

FactorialMonoid (Vector a) | |

FactorialMonoid a => FactorialMonoid (Concat a) | |

StableFactorialMonoid a => FactorialMonoid (Measured a) | |

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

Ord k => FactorialMonoid (Map k v) |

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

A subclass of `FactorialMonoid`

whose instances satisfy this additional law:

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

# Monad function equivalents

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

A `mapM_`

equivalent.