monoids 0.1.13 → 0.1.17
raw patch · 35 files changed
+424/−159 lines, 35 filesdep +reflectiondep ~QuickCheck
Dependencies added: reflection
Dependency ranges changed: QuickCheck
Files
- Data/Group/Combinators.hs +8/−1
- Data/Group/Sugar.hs +1/−1
- Data/Monoid/Additive.hs +1/−1
- Data/Monoid/Additive/Sugar.hs +1/−1
- Data/Monoid/Applicative.hs +25/−23
- Data/Monoid/Categorical.hs +24/−14
- Data/Monoid/Combinators.hs +131/−21
- Data/Monoid/FromString.hs +1/−1
- Data/Monoid/Generator.hs +18/−5
- Data/Monoid/Generator/Free.hs +51/−34
- Data/Monoid/Generator/LZ78.hs +5/−1
- Data/Monoid/Generator/RLE.hs +1/−1
- Data/Monoid/Instances.hs +1/−1
- Data/Monoid/Lexical/SourcePosition.hs +1/−1
- Data/Monoid/Lexical/UTF8/Decoder.hs +1/−1
- Data/Monoid/Lexical/Words.hs +1/−1
- Data/Monoid/Monad.hs +34/−23
- Data/Monoid/Multiplicative.hs +1/−1
- Data/Monoid/Multiplicative/Sugar.hs +1/−1
- Data/Monoid/Ord.hs +1/−1
- Data/Monoid/Reducer.hs +1/−1
- Data/Monoid/Reducer/Char.hs +1/−1
- Data/Monoid/Reducer/With.hs +1/−1
- Data/Monoid/Self.hs +1/−1
- Data/Ring/Boolean.hs +4/−3
- Data/Ring/FromNum.hs +3/−2
- Data/Ring/ModularArithmetic.hs +71/−0
- Data/Ring/Module.hs +1/−1
- Data/Ring/Module/AutomaticDifferentiation.hs +9/−0
- Data/Ring/Semi.hs +1/−1
- Data/Ring/Semi/Near.hs +1/−1
- Data/Ring/Semi/Ord.hs +9/−4
- Data/Ring/Semi/Tropical.hs +5/−3
- Data/Ring/Sugar.hs +1/−1
- monoids.cabal +7/−5
Data/Group/Combinators.hs view
@@ -3,7 +3,7 @@ -- Module : Data.Group.Combinators -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --@@ -17,11 +17,15 @@ module Data.Group.Combinators ( module Data.Group+ -- * Combinators , replicate+ -- * QuickCheck Properties+ , prop_replicate_right_distributive ) where import Prelude hiding (replicate) import Data.Group+import Test.QuickCheck -- shamelessly stolen from Lennart Augustsson's post: -- http://augustss.blogspot.com/2008/07/lost-and-found-if-i-write-108-in.html@@ -41,3 +45,6 @@ | y == 1 = x `mappend` z | otherwise = g (x `mappend` x) ((y - 1) `quot` 2) (x `mappend` z) +prop_replicate_right_distributive :: (Eq g, Group g, Arbitrary g, Integral n) => g -> n -> n -> Bool+prop_replicate_right_distributive g x y + = replicate g (x + y) == replicate g x `mappend` replicate g y
Data/Group/Sugar.hs view
@@ -3,7 +3,7 @@ -- Module : Data.Group.Sugar -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --
Data/Monoid/Additive.hs view
@@ -3,7 +3,7 @@ -- Module : Data.Monoid.Additive -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --
Data/Monoid/Additive/Sugar.hs view
@@ -3,7 +3,7 @@ -- Module : Data.Monoid.Additive.Sugar -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --
Data/Monoid/Applicative.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Applicative -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs) --@@ -18,8 +18,8 @@ , module Data.Ring.Semi.Near , module Data.Ring.Module , Traversal(Traversal,getTraversal)- , WrappedApplicative(WrappedApplicative,getWrappedApplicative)- , TraversalWith(TraversalWith,getTraversalWith)+ , Alt(Alt,getAlt)+ , App(App,getApp) , snocTraversal ) where @@ -43,57 +43,59 @@ a `cons` Traversal b = Traversal (a *> b) Traversal a `snoc` b = Traversal (a *> b *> pure ()) -{-# RULES "unitTraversal" unit = Traversal #-}-{-# RULES "snocTraversal" snoc = snocTraversal #-} -- | Efficiently avoid needlessly rebinding when using 'snoc' on an action that already returns () -- A rewrite rule automatically applies this when possible snocTraversal :: Reducer (f ()) (Traversal f) => Traversal f -> f () -> Traversal f snocTraversal a = mappend a . Traversal-+{-# RULES "unitTraversal" unit = Traversal #-}+{-# RULES "snocTraversal" snoc = snocTraversal #-} --- | A 'WrappedApplicative' turns any 'Alternative' instance into a 'Monoid'.+-- | A 'Alt' turns any 'Alternative' instance into a 'Monoid'. -- It also provides a 'Multiplicative' instance for an 'Applicative' functor wrapped around a 'Monoid' -- and asserts that any 'Alternative' applied to a 'Monoid' forms a 'LeftSemiNearRing' -- under these operations. -newtype WrappedApplicative f a = WrappedApplicative { getWrappedApplicative :: f a } - deriving (Eq,Ord,Show,Read,Functor,Pointed,Applicative,Alternative,Copointed)+newtype Alt f a = Alt { getAlt :: f a } + deriving (Eq,Ord,Show,Read,Functor,Applicative,Alternative,Copointed) -instance Alternative f => Monoid (WrappedApplicative f a) where+instance Alternative f => Monoid (Alt f a) where mempty = empty - WrappedApplicative a `mappend` WrappedApplicative b = WrappedApplicative (a <|> b) + Alt a `mappend` Alt b = Alt (a <|> b) -instance (Alternative f, Monoid a) => Multiplicative (WrappedApplicative f a) where+instance (Applicative f, Monoid a) => Multiplicative (Alt f a) where one = pure mempty times = liftA2 mappend -instance (Alternative f, c `Reducer` a) => Reducer c (WrappedApplicative f a) where- unit = WrappedApplicative . pure . unit+instance Applicative f => Pointed (Alt f) where+ point = pure -instance (Alternative f, Monoid a) => LeftSemiNearRing (WrappedApplicative f a)+instance Alternative f => Reducer (f a) (Alt f a) where+ unit = Alt --- | if @m@ is a 'Module' and @f@ is a 'Applicative' then @f `TraversalWith` m@ is a 'Module' as well+instance (Alternative f, Monoid a) => LeftSemiNearRing (Alt f a) -newtype TraversalWith f m = TraversalWith { getTraversalWith :: f m } +-- | if @m@ is a 'Module' over @r@ and @f@ is a 'Applicative' then @f `App` m@ is a 'Module' over @r@ as well++newtype App f m = App { getApp :: f m } deriving (Eq,Ord,Show,Read,Functor,Pointed,Applicative,Alternative,Copointed) -instance (Monoid m, Applicative f) => Monoid (f `TraversalWith` m) where+instance (Monoid m, Applicative f) => Monoid (f `App` m) where mempty = pure mempty mappend = liftA2 mappend -instance (Group m, Applicative f) => Group (f `TraversalWith` m) where+instance (Group m, Applicative f) => Group (f `App` m) where gnegate = fmap gnegate minus = liftA2 minus gsubtract = liftA2 gsubtract -instance (c `Reducer` m, Applicative f) => Reducer c (f `TraversalWith` m) where+instance (c `Reducer` m, Applicative f) => Reducer c (f `App` m) where unit = pure . unit -instance (LeftModule r m, Applicative f) => LeftModule r (f `TraversalWith` m) where+instance (LeftModule r m, Applicative f) => LeftModule r (f `App` m) where x *. m = (x *.) <$> m -instance (RightModule r m, Applicative f) => RightModule r (f `TraversalWith` m) where+instance (RightModule r m, Applicative f) => RightModule r (f `App` m) where m .* y = (.* y) <$> m -instance (Module r m, Applicative f) => Module r (f `TraversalWith` m)+instance (Module r m, Applicative f) => Module r (f `App` m)
Data/Monoid/Categorical.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Categorical -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --@@ -17,8 +17,9 @@ -- * Generalized Endo , GEndo(GEndo, getGEndo) -- * Monoids as Categories- , Mon(Mon)- , getMon+ , CMonoid+ , categoryToMonoid+ , monoidToCategory ) where import Prelude hiding ((.),id)@@ -32,21 +33,30 @@ mempty = GEndo id GEndo f `mappend` GEndo g = GEndo (f . g) --- | A 'Monoid' is just a 'Category' with one object. -data Mon m n o where- Mon :: Monoid m => m -> Mon m a a+-- | A 'Monoid' is just a 'Category' with one object. This fakes that with a GADT+data CMonoid m n o where+ M :: Monoid m => m -> CMonoid m a a -- | Extract the 'Monoid' from its representation as a 'Category'-getMon :: Mon m m m -> m -getMon (Mon m) = m+categoryToMonoid :: CMonoid m m m -> m +categoryToMonoid (M m) = m+{-# INLINE categoryToMonoid #-} -instance Monoid m => Category (Mon m) where- id = Mon mempty- Mon a . Mon b = Mon (a `mappend` b)+-- | Convert a value in a 'Monoid' into an arrow in a 'Category'.+monoidToCategory :: Monoid m => m -> CMonoid m m m +monoidToCategory = M +{-# INLINE monoidToCategory #-} -instance Monoid m => Monoid (Mon m m m) where+instance Monoid m => Category (CMonoid m) where+ id = M mempty+ M a . M b = M (a `mappend` b)++instance Monoid m => Monoid (CMonoid m m m) where mempty = id mappend = (.) -instance (c `Reducer` m) => Reducer c (Mon m m m) where- unit = Mon . unit+instance (c `Reducer` m) => Reducer c (CMonoid m m m) where+ unit = M . unit++instance Monoid m => Reducer (CMonoid m m m) m where+ unit (M m) = m
Data/Monoid/Combinators.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Combinators -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (type families, MPTCs) --@@ -21,9 +21,11 @@ -- * Monadic Reduction , mapM_ , forM_+ , msum -- * Applicative Reduction , traverse_ , for_+ , asum -- * Logical Reduction , and , or@@ -32,96 +34,199 @@ -- * Monoidal Reduction , foldMap , fold+ , toList -- * List-Like Reduction , concatMap , elem , filter+ , filterWith , find , sum , product , notElem- -- * List-Like Monoid Generation+ -- * List-Like Monoid Production , repeat , replicate , cycle+ -- * QuickCheck Properties+ , prop_replicate_right_distributive ) where import Prelude hiding (mapM_, any, elem, filter, concatMap, and, or, all, sum, product, notElem, replicate, cycle, repeat) import Control.Applicative+import Control.Monad (MonadPlus) import Data.Monoid.Generator import Data.Monoid.Applicative import Data.Monoid.Self import Data.Monoid.Monad+import Test.QuickCheck --- | Efficiently 'mapReduce' a 'Generator' using the 'Traversal' monoid. A specialized version of its namesake in "Data.Foldable"+-- | Efficiently 'mapReduce' a 'Generator' using the 'Traversal' monoid. A specialized version of its namesake from "Data.Foldable"+--+-- @+-- 'mapReduce' 'getTraversal'+-- @ traverse_ :: (Generator c, Applicative f) => (Elem c -> f b) -> c -> f ()-traverse_ f = getTraversal . mapReduce f+traverse_ = mapReduceWith getTraversal+{-# INLINE traverse_ #-} --- | flipped 'traverse_' as in "Data.Foldable"+-- | Convenience function as found in "Data.Foldable"+--+-- @+-- 'flip' 'traverse_'+-- @ for_ :: (Generator c, Applicative f) => c -> (Elem c -> f b) -> f () for_ = flip traverse_+{-# INLINE for_ #-} +-- | The sum of a collection of actions, generalizing 'concat'+--+-- @+-- 'reduceWith' 'getAlt'+-- @ +asum :: (Generator c, Alternative f, f a ~ Elem c) => c -> f a+asum = reduceWith getAlt+{-# INLINE asum #-}+ -- | Efficiently 'mapReduce' a 'Generator' using the 'Action' monoid. A specialized version of its namesake from "Data.Foldable" and "Control.Monad"+-- +-- @+-- 'mapReduceWith' 'getAction'+-- @ mapM_ :: (Generator c, Monad m) => (Elem c -> m b) -> c -> m ()-mapM_ f = getAction . mapReduce f+mapM_ = mapReduceWith getAction+{-# INLINE mapM_ #-} --- | flipped 'mapM_' as in "Data.Foldable" and "Control.Monad"+-- | Convenience function as found in "Data.Foldable" and "Control.Monad"+--+-- @+-- 'flip' 'mapM_'+-- @ forM_ :: (Generator c, Monad m) => c -> (Elem c -> m b) -> m () forM_ = flip mapM_+{-# INLINE forM_ #-} +-- | The sum of a collection of actions, generalizing 'concat'+--+-- @+-- 'reduceWith' 'getMonadSum'+-- @+msum :: (Generator c, MonadPlus m, m a ~ Elem c) => c -> m a+msum = reduceWith getMonadSum+{-# INLINE msum #-}+ -- | Efficiently 'mapReduce' a 'Generator' using the 'Self' monoid. A specialized version of its namesake from "Data.Foldable"+--+-- @+-- 'mapReduceWith' 'getSelf'+-- @ foldMap :: (Monoid m, Generator c) => (Elem c -> m) -> c -> m-foldMap f = getSelf . mapReduce f+foldMap = mapReduceWith getSelf+{-# INLINE foldMap #-} +-- | Type specialization of "foldMap" above+concatMap :: Generator c => (Elem c -> [b]) -> c -> [b]+concatMap = foldMap+{-# INLINE concatMap #-}+ -- | Efficiently 'reduce' a 'Generator' using the 'Self' monoid. A specialized version of its namesake from "Data.Foldable"+--+-- @+-- 'reduceWith' 'getSelf'+-- @ fold :: (Monoid m, Generator c, Elem c ~ m) => c -> m-fold = getSelf . reduce+fold = reduceWith getSelf+{-# INLINE fold #-} --- | A further specialization of "foldMap"-concatMap :: Generator c => (Elem c -> [b]) -> c -> [b]-concatMap = foldMap+-- | Convert any 'Generator' to a list of its contents. Specialization of 'reduce'+toList :: Generator c => c -> [Elem c]+toList = reduce+{-# INLINE toList #-} -- | Efficiently 'reduce' a 'Generator' that contains values of type 'Bool'+--+-- @+-- 'reduceWith' 'getAll'+-- @ and :: (Generator c, Elem c ~ Bool) => c -> Bool-and = getAll . reduce+and = reduceWith getAll+{-# INLINE and #-} -- | Efficiently 'reduce' a 'Generator' that contains values of type 'Bool'+--+-- @+-- 'reduceWith' 'getAny'+-- @ or :: (Generator c, Elem c ~ Bool) => c -> Bool-or = getAny . reduce+or = reduceWith getAny+{-# INLINE or #-} -- | Efficiently 'mapReduce' any 'Generator' checking to see if any of its values match the supplied predicate+--+-- @+-- 'mapReduceWith' 'getAny'+-- @ any :: Generator c => (Elem c -> Bool) -> c -> Bool-any f = getAny . mapReduce f+any = mapReduceWith getAny+{-# INLINE any #-} -- | Efficiently 'mapReduce' any 'Generator' checking to see if all of its values match the supplied predicate+--+-- @+-- 'mapReduceWith' 'getAll'+-- @ all :: Generator c => (Elem c -> Bool) -> c -> Bool-all f = getAll . mapReduce f+all = mapReduceWith getAll+{-# INLINE all #-} --- | Efficiently 'mapReduce' any 'Generator' using the 'Sum' 'Monoid'+-- | Efficiently sum over the members of any 'Generator'+--+-- @+-- 'reduceWith' 'getSum'+-- @ sum :: (Generator c, Num (Elem c)) => c -> Elem c-sum = getSum . reduce+sum = reduceWith getSum+{-# INLINE sum #-} --- | Efficiently 'mapReduce' any 'Generator' using the 'Product' 'Monoid'+-- | Efficiently take the product of every member of a 'Generator'+--+-- @+-- 'reduceWith' 'getProduct'+-- @ product :: (Generator c, Num (Elem c)) => c -> Elem c-product = getProduct . reduce+product = reduceWith getProduct+{-# INLINE product #-} -- | Check to see if 'any' member of the 'Generator' matches the supplied value elem :: (Generator c, Eq (Elem c)) => Elem c -> c -> Bool elem = any . (==)+{-# INLINE elem #-} -- | Check to make sure that the supplied value is not a member of the 'Generator' notElem :: (Generator c, Eq (Elem c)) => Elem c -> c -> Bool notElem x = not . elem x+{-# INLINE notElem #-} -- | Efficiently 'mapReduce' a subset of the elements in a 'Generator' filter :: (Generator c, Elem c `Reducer` m) => (Elem c -> Bool) -> c -> m filter p = foldMap f where f x | p x = unit x | otherwise = mempty+{-# INLINE filter #-} +-- | Allows idiomatic specialization of filter by proving a function that will be used to transform the output+filterWith :: (Generator c, Elem c `Reducer` m) => (m -> n) -> (Elem c -> Bool) -> c -> n +filterWith f p = f . filter p+{-# INLINE filterWith #-}+ -- | A specialization of 'filter' using the 'First' 'Monoid', analogous to 'Data.List.find'+--+-- @+-- 'filterWith' 'getFirst'+-- @ find :: Generator c => (Elem c -> Bool) -> c -> Maybe (Elem c)-find p = getFirst . filter p+find = filterWith getFirst+{-# INLINE find #-} -- | A generalization of 'Data.List.replicate' to an arbitrary 'Monoid'. Adapted from -- <http://augustss.blogspot.com/2008/07/lost-and-found-if-i-write-108-in.html>@@ -139,6 +244,7 @@ | even y = g (x `mappend` x) (y `quot` 2) z | y == 1 = x `mappend` z | otherwise = g (x `mappend` x) ((y - 1) `quot` 2) (x `mappend` z)+{-# INLINE replicate #-} -- | A generalization of 'Data.List.cycle' to an arbitrary 'Monoid'. May fail to terminate for some values in some monoids. cycle :: Monoid m => m -> m@@ -147,3 +253,7 @@ -- | A generalization of 'Data.List.repeat' to an arbitrary 'Monoid'. May fail to terminate for some values in some monoids. repeat :: (e `Reducer` m) => e -> m repeat x = xs where xs = cons x xs ++prop_replicate_right_distributive :: (Eq m, Monoid m, Arbitrary m, Integral n) => m -> n -> n -> Bool+prop_replicate_right_distributive m x y+ = replicate m (x + y) == replicate m x `mappend` replicate m y
Data/Monoid/FromString.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Additive -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (overloaded strings, MPTCs) --
Data/Monoid/Generator.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Generator -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --@@ -20,15 +20,20 @@ module Data.Monoid.Generator ( module Data.Monoid.Reducer+ -- * Generators , Generator , Elem , mapReduce , mapTo , mapFrom- , reduce+ -- * Generator Transformers , Keys(Keys, getKeys) , Values(Values, getValues) , Char8(Char8, getChar8)+ -- * Combinators+ , reduce+ , mapReduceWith+ , reduceWith ) where import Data.Array @@ -152,6 +157,9 @@ type Elem (Char8 Lazy.ByteString) = Char mapReduce f = fold . parMap rwhnf (mapReduce f . Char8) . Lazy8.toChunks . getChar8 +-- | Apply a 'Reducer' directly to the elements of a 'Generator'+reduce :: (Generator c, Elem c `Reducer` m) => c -> m+reduce = mapReduce id {-# SPECIALIZE reduce :: (Word8 `Reducer` m) => Strict.ByteString -> m #-} {-# SPECIALIZE reduce :: (Word8 `Reducer` m) => Lazy.ByteString -> m #-} {-# SPECIALIZE reduce :: (Char `Reducer` m) => Char8 Strict.ByteString -> m #-}@@ -168,6 +176,11 @@ {-# SPECIALIZE reduce :: (k `Reducer` m) => Keys (Map k v) -> m #-} {-# SPECIALIZE reduce :: (v `Reducer` m) => Values (IntMap v) -> m #-} {-# SPECIALIZE reduce :: (v `Reducer` m) => Values (Map k v) -> m #-}--- | Apply a 'Reducer' directly to the elements of a 'Generator'-reduce :: (Generator c, Elem c `Reducer` m) => c -> m-reduce = mapReduce id++mapReduceWith :: (Generator c, e `Reducer` m) => (m -> n) -> (Elem c -> e) -> c -> n+mapReduceWith f g = f . mapReduce g+{-# INLINE mapReduceWith #-}++reduceWith :: (Generator c, Elem c `Reducer` m) => (m -> n) -> c -> n+reduceWith f = f . reduce+{-# INLINE reduceWith #-}
Data/Monoid/Generator/Free.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Generator.Free -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs) --@@ -14,14 +14,16 @@ module Data.Monoid.Generator.Free ( module Data.Monoid.Generator , module Data.Monoid.Reducer- , Free -- (AnyGen)+ , Free (AnyGenerator) ) where import Control.Functor.Pointed+import Control.Monad import Data.Monoid.Generator import Data.Foldable import Data.Monoid.Reducer import Data.Monoid.Additive+import qualified Data.Monoid.Combinators as M import Data.Monoid.Self data Free a @@ -30,8 +32,19 @@ | Free a `Plus` Free a | Unit a | Empty--- | forall c. (Generator c, Elem c ~ a) => AnyGen c+ | forall c. (Generator c, Elem c ~ a) => AnyGenerator c +instance Eq a => Eq (Free a) where+ a == b = M.toList a == M.toList b+ a /= b = M.toList a == M.toList b++instance Ord a => Ord (Free a) where+ a <= b = M.toList a <= M.toList b+ a >= b = M.toList a >= M.toList b+ a < b = M.toList a < M.toList b+ a > b = M.toList a > M.toList b+ a `compare` b = M.toList a `compare` M.toList b+ instance Monoid (Free a) where mempty = Empty mappend = Plus@@ -51,47 +64,51 @@ fmap f (a `Plus` b) = fmap f a `Plus` fmap f b fmap f (Unit a) = Unit (f a) fmap _ Empty = Empty--- fmap f (AnyGen c) = mapReduce f c+ fmap f (AnyGenerator c) = mapReduce f c instance Pointed Free where point = Unit instance Monad Free where return = Unit- a `Cons` b >>= k = k a `Plus` (b >>= k)- a `Snoc` b >>= k = (a >>= k) `Plus` k b- a `Plus` b >>= k = (a >>= k) `Plus` (b >>= k)- Unit a >>= k = k a- Empty >>= _ = Empty--- AnyGen c >>= k = ...+ a `Cons` b >>= k = k a `Plus` (b >>= k)+ a `Snoc` b >>= k = (a >>= k) `Plus` k b+ a `Plus` b >>= k = (a >>= k) `Plus` (b >>= k)+ Unit a >>= k = k a+ Empty >>= _ = Empty+ AnyGenerator c >>= k = getSelf (mapReduce k c) +instance MonadPlus Free where+ mzero = Empty+ mplus = Plus+ instance Foldable Free where- foldMap f (a `Cons` b) = f a `mappend` foldMap f b- foldMap f (a `Snoc` b) = foldMap f a `mappend` f b- foldMap f (a `Plus` b) = foldMap f a `mappend` foldMap f b- foldMap f (Unit a) = f a - foldMap _ Empty = mempty--- foldMap f (AnyGen c) = getSelf . mapReduce f c+ foldMap f (a `Cons` b) = f a `mappend` foldMap f b+ foldMap f (a `Snoc` b) = foldMap f a `mappend` f b+ foldMap f (a `Plus` b) = foldMap f a `mappend` foldMap f b+ foldMap f (Unit a) = f a + foldMap _ Empty = mempty+ foldMap f (AnyGenerator c) = M.foldMap f c instance Generator (Free a) where type Elem (Free a) = a- mapReduce f (a `Cons` b) = f a `cons` mapReduce f b- mapReduce f (a `Snoc` b) = mapReduce f a `snoc` f b- mapReduce f (a `Plus` b) = mapReduce f a `plus` mapReduce f b- mapReduce f (Unit a) = unit (f a)- mapReduce _ Empty = mempty--- mapReduce f (AnyGen c) = getSelf . mapReduce f c+ mapReduce f (a `Cons` b) = f a `cons` mapReduce f b+ mapReduce f (a `Snoc` b) = mapReduce f a `snoc` f b+ mapReduce f (a `Plus` b) = mapReduce f a `plus` mapReduce f b+ mapReduce f (Unit a) = unit (f a)+ mapReduce _ Empty = mempty+ mapReduce f (AnyGenerator c) = mapReduce f c - mapTo f m (a `Cons` b) = m `plus` (f a `cons` mapReduce f b)- mapTo f m (a `Snoc` b) = mapTo f m a `snoc` f b- mapTo f m (a `Plus` b) = mapTo f m a `plus` mapReduce f b- mapTo f m (Unit a) = m `snoc` f a- mapTo _ m Empty = m --- mapTo f m (AnyGen c) = getSelf . mapTo f m c+ mapTo f m (a `Cons` b) = m `plus` (f a `cons` mapReduce f b)+ mapTo f m (a `Snoc` b) = mapTo f m a `snoc` f b+ mapTo f m (a `Plus` b) = mapTo f m a `plus` mapReduce f b+ mapTo f m (Unit a) = m `snoc` f a+ mapTo _ m Empty = m + mapTo f m (AnyGenerator c) = mapTo f m c - mapFrom f (a `Cons` b) m = f a `cons` mapFrom f b m - mapFrom f (a `Snoc` b) m = mapFrom f a (f b `cons` m)- mapFrom f (a `Plus` b) m = mapReduce f a `plus` mapFrom f b m- mapFrom f (Unit a) m = f a `cons` m- mapFrom _ Empty m = m --- mapFrom f (AnyGen c) m = getSelf . mapFrom f c m + mapFrom f (a `Cons` b) m = f a `cons` mapFrom f b m + mapFrom f (a `Snoc` b) m = mapFrom f a (f b `cons` m)+ mapFrom f (a `Plus` b) m = mapReduce f a `plus` mapFrom f b m+ mapFrom f (Unit a) m = f a `cons` m+ mapFrom _ Empty m = m + mapFrom f (AnyGenerator c) m = mapFrom f c m
Data/Monoid/Generator/LZ78.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Generator.LZ78 -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --@@ -23,10 +23,14 @@ module Data.Monoid.Generator.LZ78 ( module Data.Monoid.Generator+ -- * Lempel-Ziv 78 , LZ78+ -- * Decoding , decode+ -- * Encoding , encode , encodeEq+ -- * QuickCheck Properties , prop_decode_encode , prop_decode_encodeEq ) where
Data/Monoid/Generator/RLE.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Generator.RLE -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --
Data/Monoid/Instances.hs view
@@ -6,7 +6,7 @@ -- Module : Data.Monoid.Instances -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --
Data/Monoid/Lexical/SourcePosition.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Lexical.SourcePosition -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs, OverloadedStrings) --
Data/Monoid/Lexical/UTF8/Decoder.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Lexical.UTF8.Decoder -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs) --
Data/Monoid/Lexical/Words.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Lexical.Words -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs, OverloadedStrings) --
Data/Monoid/Monad.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Applicative -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs) --@@ -19,12 +19,13 @@ -- * Actions , Action(Action,getAction) , snocAction+ -- * MonadPlus Monoid+ , MonadSum(MonadSum, getMonadSum) -- * Lifting Modules- , ActionWith(ActionWith,getActionWith)- -- * Wrapped Monads- , WrappedMonad(WrappedMonad, getWrappedMonad)+ , Mon(Mon,getMon) ) where +import Control.Applicative import Control.Functor.Pointed import Data.Monoid.Reducer import Data.Ring.Semi.Near@@ -53,48 +54,58 @@ snocAction :: Reducer (m ()) (Action m) => Action m -> m () -> Action m snocAction a = mappend a . Action --- | A 'WrappedMonad' turns any 'MonadPlus' instance into a 'Monoid'.+-- | A 'MonadSum' turns any 'MonadPlus' instance into a 'Monoid'. -- It also provides a 'Multiplicative' instance for a 'Monad' wrapped around a 'Monoid' -- and asserts that any 'MonadPlus' applied to a 'Monoid' forms a 'LeftSemiNearRing' -- under these operations. -newtype WrappedMonad m a = WrappedMonad { getWrappedMonad :: m a } - deriving (Eq,Ord,Show,Read,Functor,Pointed, Monad,MonadPlus)+newtype MonadSum m a = MonadSum { getMonadSum :: m a } + deriving (Eq,Ord,Show,Read,Monad,MonadPlus) -instance (Monad m, Monoid a) => Multiplicative (WrappedMonad m a) where- one = WrappedMonad (return mempty)- WrappedMonad m `times` WrappedMonad n = WrappedMonad (liftM2 mappend m n)- -instance (MonadPlus m) => Monoid (WrappedMonad m a) where+instance MonadPlus m => Monoid (MonadSum m a) where mempty = mzero mappend = mplus -instance (MonadPlus m, c `Reducer` a) => Reducer c (WrappedMonad m a) where- unit = WrappedMonad . return . unit+instance (Monad m, Monoid a) => Multiplicative (MonadSum m a) where+ one = return mempty+ times = liftM2 mappend -instance (MonadPlus m, Monoid a) => LeftSemiNearRing (WrappedMonad m a)+instance Monad m => Functor (MonadSum m) where+ fmap = liftM --- | if @m@ is a 'Module' over @r@ and @f@ is a 'Monad' then @f `ActionWith` m@ is a 'Module' as well+instance Monad m => Applicative (MonadSum m) where+ pure = return+ (<*>) = ap -newtype ActionWith f m = ActionWith { getActionWith :: f m } +instance Monad m => Pointed (MonadSum m) where+ point = return++instance MonadPlus m => Reducer (m a) (MonadSum m a) where+ unit = MonadSum++instance (MonadPlus m, Monoid a) => LeftSemiNearRing (MonadSum m a)++-- | if @m@ is a 'Module' over @r@ and @f@ is a 'Monad' then @f `Mon` m@ is a 'Module' as well++newtype Mon f m = Mon { getMon :: f m } deriving (Eq,Ord,Show,Read,Functor,Pointed, Monad,MonadPlus) -instance (Monoid m, Monad f) => Monoid (f `ActionWith` m) where+instance (Monoid m, Monad f) => Monoid (f `Mon` m) where mempty = return mempty mappend = liftM2 mappend -instance (Group m, Monad f) => Group (f `ActionWith` m) where+instance (Group m, Monad f) => Group (f `Mon` m) where gnegate = liftM gnegate minus = liftM2 minus gsubtract = liftM2 gsubtract -instance (c `Reducer` m, Monad f) => Reducer c (f `ActionWith` m) where+instance (c `Reducer` m, Monad f) => Reducer c (f `Mon` m) where unit = return . unit -instance (LeftModule r m, Monad f) => LeftModule r (f `ActionWith` m) where+instance (LeftModule r m, Monad f) => LeftModule r (f `Mon` m) where x *. m = liftM (x *.) m -instance (RightModule r m, Monad f) => RightModule r (f `ActionWith` m) where+instance (RightModule r m, Monad f) => RightModule r (f `Mon` m) where m .* y = liftM (.* y) m -instance (Module r m, Monad f) => Module r (f `ActionWith` m)+instance (Module r m, Monad f) => Module r (f `Mon` m)
Data/Monoid/Multiplicative.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Multiplicative -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable (but instances use MPTCs) --
Data/Monoid/Multiplicative/Sugar.hs view
@@ -3,7 +3,7 @@ -- Module : Data.Monoid.Multiplicative.Sugar -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --
Data/Monoid/Ord.hs view
@@ -4,7 +4,7 @@ ---- Module : Data.Monoid.Ord ---- Copyright : (c) Edward Kmett 2009 ---- License : BSD-style----- Maintainer : libraries@haskell.org+---- Maintainer : ekmett@gmail.com ---- Stability : experimental ---- Portability : portable ----
Data/Monoid/Reducer.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Reducer -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs) --
Data/Monoid/Reducer/Char.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Reducer.Char -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs) --
Data/Monoid/Reducer/With.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Reducer.With -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs) --
Data/Monoid/Self.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Monoid.Self -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --
Data/Ring/Boolean.hs view
@@ -1,11 +1,11 @@-{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}+{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, GeneralizedNewtypeDeriving #-} ----------------------------------------------------------------------------- -- | -- Module : Data.Ring.Boolean -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs) --@@ -22,8 +22,9 @@ import Data.Ring import Data.Monoid.Reducer+import Test.QuickCheck -newtype BoolRing = BoolRing { getBoolRing :: Bool } deriving (Eq,Ord,Show,Read)+newtype BoolRing = BoolRing { getBoolRing :: Bool } deriving (Eq,Ord,Show,Read,Arbitrary,CoArbitrary) instance Monoid BoolRing where mempty = BoolRing False
Data/Ring/FromNum.hs view
@@ -5,7 +5,7 @@ -- Module : Data.Ring.FromNum -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs) --@@ -21,8 +21,9 @@ import Data.Ring import Data.Monoid.Reducer+import Test.QuickCheck -newtype FromNum a = FromNum { getFromNum :: a } deriving (Eq,Show,Num)+newtype FromNum a = FromNum { getFromNum :: a } deriving (Eq,Show,Num,Arbitrary,CoArbitrary) instance Num a => Monoid (FromNum a) where mempty = fromInteger 0
+ Data/Ring/ModularArithmetic.hs view
@@ -0,0 +1,71 @@+{-# LANGUAGE RankNTypes, FlexibleInstances, MultiParamTypeClasses, ScopedTypeVariables, EmptyDataDecls, FunctionalDependencies, TypeOperators #-}+-----------------------------------------------------------------------------+-- |+-- Module : Data.Ring.ModularArithmetic+-- Copyright : Edward Kmett 2009, Oleg Kiselyov and Chung-chieh Shan 2004+-- +-- License : BSD-style+-- Maintainer : Edward Kmett <ekmett@gmail.com>+-- Stability : experimental+-- Portability : non-portable (MPTCs, scoped types, empty decls, type operators)+--+-----------------------------------------------------------------------------++module Data.Ring.ModularArithmetic+ ( module Data.Ring+ , Mod(getMod), Modular, modulus+ , withIntegralModulus+ ) where++import Data.Ring+import Data.Reflection++newtype (a `Mod` s) = M { getMod :: a } + deriving (Eq,Show)++class Modular s a | s -> a where+ modulus :: s -> a++normalize :: (Modular s a, Integral a) => a -> (a `Mod` s)+normalize = normalize' undefined where+ normalize' :: (Modular s a, Integral a) => s -> a -> (a `Mod` s)+ normalize' s a = M (a `mod` modulus s)++data ModulusNum s a++instance (ReflectNum s, Num a) => Modular (ModulusNum s a) a where+ modulus _ = reflectNum (undefined :: s)++withIntegralModulus :: Integral a => a -> (forall s. Modular s a => w `Mod` s) -> w+withIntegralModulus = withIntegralModulus' undefined where+ withIntegralModulus' :: Integral a => w -> a -> (forall s. Modular s a => w `Mod` s) -> w+ withIntegralModulus' (_ :: w) (i :: a) k = + reifyIntegral i (\(_ :: t) -> + getMod (k :: w `Mod` ModulusNum t a))++instance (Modular s a, Integral a) => Num (a `Mod` s) where+ M a + M b = normalize (a + b)+ M a - M b = normalize (a - b)+ M a * M b = normalize (a * b)+ negate (M a) = normalize (negate a)+ fromInteger i = normalize (fromInteger i)+ signum = error "broken numerical type tower"+ abs = error "broken numerical type tower"++instance (Modular s a, Integral a) => Monoid (a `Mod` s) where+ mempty = 0+ mappend = (+)++instance (Modular s a, Integral a) => Multiplicative (a `Mod` s) where+ one = 1+ times = (*)++instance (Modular s a, Integral a) => Group (a `Mod` s) where+ gnegate = negate+ minus = (-)+ gsubtract = subtract++instance (Modular s a, Integral a) => LeftSemiNearRing (a `Mod` s)+instance (Modular s a, Integral a) => RightSemiNearRing (a `Mod` s)+instance (Modular s a, Integral a) => SemiRing (a `Mod` s)+instance (Modular s a, Integral a) => Ring (a `Mod` s)
Data/Ring/Module.hs view
@@ -4,7 +4,7 @@ -- Module : Data.Ring.Module -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs) --
Data/Ring/Module/AutomaticDifferentiation.hs view
@@ -8,6 +8,8 @@ import Data.Ring.Sugar import Data.Ring.Module import Data.Monoid.Reducer+import Test.QuickCheck+import Control.Monad data D r m = D r m @@ -33,6 +35,13 @@ unit c = D (unit c) (unit c) c `cons` D x m = D (c `cons` x) (c `cons` m) D x m `snoc` c = D (x `snoc` c) (m `snoc` c)++instance (Arbitrary r, Arbitrary m) => Arbitrary (D r m) where+ arbitrary = liftM2 D arbitrary arbitrary+ shrink (D r m) = liftM2 D (shrink r) (shrink m)++instance (CoArbitrary r, CoArbitrary m) => CoArbitrary (D r m) where+ coarbitrary (D r m) = coarbitrary r >< coarbitrary m {-- infix 0 ><
Data/Ring/Semi.hs view
@@ -3,7 +3,7 @@ -- Module : Data.Ring.Semi -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : non-portable (MPTCs) --
Data/Ring/Semi/Near.hs view
@@ -6,7 +6,7 @@ -- Module : Data.Ring.Semi.Near -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable (instances use MPTCs) --
Data/Ring/Semi/Ord.hs view
@@ -25,7 +25,7 @@ import Data.Monoid.Reducer -- | A 'SemiRing' using a type's built-in Bounded instance.-newtype Order a = Order { getOrder :: a } deriving (Eq,Ord,Read,Show,Bounded,Arbitrary)+newtype Order a = Order { getOrder :: a } deriving (Eq,Ord,Read,Show,Bounded,Arbitrary,CoArbitrary) instance (Bounded a, Ord a) => Monoid (Order a) where mappend = max@@ -81,9 +81,14 @@ arbitrary = frequency [ (1 ,return MinBound) , (10, fmap Priority arbitrary) , (1 ,return MaxBound) ]- coarbitrary MinBound = variant 0- coarbitrary (Priority a) = variant 1 . coarbitrary a- coarbitrary MaxBound = variant 2+ shrink (Priority x) = MinBound : MaxBound : fmap Priority (shrink x)+ shrink MinBound = []+ shrink MaxBound = []++instance CoArbitrary a => CoArbitrary (Priority a) where+ coarbitrary MinBound = variant (0 :: Int)+ coarbitrary (Priority a) = variant (1 :: Int) . coarbitrary a+ coarbitrary MaxBound = variant (2 :: Int) instance Ord a => Monoid (Priority a) where mappend = max
Data/Ring/Semi/Tropical.hs view
@@ -1,10 +1,10 @@-{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}+{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, GeneralizedNewtypeDeriving #-} ----------------------------------------------------------------------------- ---- | ---- Module : Data.Ring.Semi.Tropical ---- Copyright : (c) Edward Kmett 2009 ---- License : BSD-style----- Maintainer : libraries@haskell.org+---- Maintainer : ekmett@gmail.com ---- Stability : experimental ---- Portability : portable ----@@ -18,6 +18,7 @@ , Tropical(Tropical,getTropical) ) where +import Test.QuickCheck import Control.Functor.Pointed import Data.Monoid.Reducer (Reducer, unit, Monoid, mappend, mempty) import Data.Ring.Semi@@ -33,7 +34,8 @@ -- -- <http://hal.archives-ouvertes.fr/docs/00/11/37/79/PDF/Tropical.pdf> -newtype Tropical a = Tropical { getTropical :: Maybe a } deriving (Eq,Show,Read)+newtype Tropical a = Tropical { getTropical :: Maybe a } + deriving (Eq,Show,Read,Arbitrary,CoArbitrary) instance Ord a => Ord (Tropical a) where Tropical Nothing `compare` Tropical Nothing = EQ
Data/Ring/Sugar.hs view
@@ -3,7 +3,7 @@ -- Module : Data.Ring.Sugar -- Copyright : (c) Edward Kmett 2009 -- License : BSD-style--- Maintainer : libraries@haskell.org+-- Maintainer : ekmett@gmail.com -- Stability : experimental -- Portability : portable --
monoids.cabal view
@@ -1,5 +1,5 @@ name: monoids-version: 0.1.13+version: 0.1.17 license: BSD3 license-file: LICENSE author: Edward A. Kmett@@ -7,8 +7,8 @@ stability: experimental homepage: http://comonad.com/reader category: Data-synopsis: Lots of Monoids-description: Lots of Monoids+synopsis: Monoids, specialized containers and a general map/reduce framework+description: Monoids, specialized containers and a general map/reduce framework copyright: (c) 2009 Edward A. Kmett build-type: Simple cabal-version: >=1.2@@ -26,8 +26,9 @@ mtl >= 1.0 && < 1.2, stm >= 2.1 && < 2.2, bitset >= 1.0 && < 1.1, - QuickCheck < 2.2, - array >= 0.2 && < 0.3+ QuickCheck >= 2.1 && < 2.2, + array >= 0.2 && < 0.3,+ reflection >= 0.0 && < 0.1 exposed-modules: Data.Group Data.Group.Combinators@@ -58,6 +59,7 @@ Data.Ring Data.Ring.Boolean Data.Ring.FromNum+ Data.Ring.ModularArithmetic Data.Ring.Module Data.Ring.Module.AutomaticDifferentiation Data.Ring.Semi