-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Monoids, specialized containers and a general map/reduce framework -- -- Monoids, specialized containers and a general map/reduce framework @package monoids @version 0.1.33 -- | A collection of orphan instance declarations for Monoids that should -- eventually be pushed back down to the source packages. -- -- Every package that uses these instances includes this package -- internally. -- -- Includes: -- -- -- -- This module is automatically included everywhere this functionality is -- required within this package. You should only have to import this -- module yourself if you want these instances for your own purposes. module Data.Monoid.Instances instance (Integral m) => Monoid (Ratio m) instance Monoid Integer instance Monoid Int instance (IsString a, IsString b, IsString c, IsString d, IsString e) => IsString (a, b, c, d, e) instance (IsString a, IsString b, IsString c, IsString d) => IsString (a, b, c, d) instance (IsString a, IsString b, IsString c) => IsString (a, b, c) instance (IsString a, IsString b) => IsString (a, b) instance (Stream s m t) => Monoid (ParsecT s u m a) instance (Measured v a) => Monoid (FingerTree v a) instance (MonadPlus m) => Monoid (StateT s m n) instance (MonadPlus m) => Monoid (StateT s m n) instance (MonadPlus m) => Monoid (ReaderT e m n) instance (MonadPlus m, Monoid w) => Monoid (RWST r w s m n) instance (MonadPlus m, Monoid w) => Monoid (RWST r w s m n) instance (MonadPlus m, Monoid w) => Monoid (WriterT w m n) instance (MonadPlus m, Monoid w) => Monoid (WriterT w m n) -- | A c-Reducer is a Monoid with a canonical -- mapping from c to the Monoid. This unit acts in many -- ways like return for a Monad but is limited to a single -- type. module Data.Monoid.Reducer -- | This type may be best read infix. A c Reducer m is a -- Monoid m that maps values of type c through -- unit to values of type m. A -- c-Reducer may also supply operations which tack-on -- another c to an existing Monoid m on the left -- or right. These specialized reductions may be more efficient in some -- scenarios and are used when appropriate by a Generator. The names -- cons and snoc work by analogy to the synonymous -- operations in the list monoid. -- -- This class deliberately avoids functional-dependencies, so that () can -- be a c-Reducer for all c, and so many common -- reducers can work over multiple types, for instance, First and Last -- may reduce both a and Maybe a. Since a -- Generator has a fixed element type, the input to the reducer is -- generally known and extracting from the monoid usually is sufficient -- to fix the result type. Combinators are available for most scenarios -- where this is not the case, and the few remaining cases can be handled -- by using an explicit type annotation. -- -- Minimal definition: unit or snoc class (Monoid m) => Reducer c m unit :: (Reducer c m) => c -> m snoc :: (Reducer c m) => m -> c -> m cons :: (Reducer c m) => c -> m -> m -- | Apply a Reducer to a Foldable container, after mapping -- the contents into a suitable form for reduction. foldMapReduce :: (Foldable f, Reducer e m) => (a -> e) -> f a -> m -- | Apply a Reducer to a Foldable mapping each element -- through unit foldReduce :: (Foldable f, Reducer e m) => f e -> m pureUnit :: (Applicative f, Reducer c n) => c -> f n returnUnit :: (Monad m, Reducer c n) => c -> m n data ReducedBy m s Reduction :: m -> ReducedBy m s getReduction :: ReducedBy m s -> m instance (Reflects s (a -> m), Monoid m) => Reducer a (ReducedBy m s) instance (Monoid m) => Monoid (ReducedBy m s) instance (Ord k) => Reducer (k, v) (Map k v) instance Reducer (Int, v) (IntMap v) instance (Ord a) => Reducer a (Set a) instance Reducer Int IntSet instance Reducer a (Seq a) instance (Stream s m t, Reducer c a) => Reducer c (ParsecT s u m a) instance (Measured v a) => Reducer a (FingerTree v a) instance Reducer a (Last a) instance Reducer (Maybe a) (Last a) instance Reducer a (First a) instance Reducer (Maybe a) (First a) instance (Num a) => Reducer a (Product a) instance (Num a) => Reducer a (Sum a) instance (Monoid a) => Reducer a (Dual a) instance Reducer (a -> a) (Endo a) instance Reducer Bool All instance Reducer Bool Any instance Reducer c () instance Reducer c [c] instance (Reducer c m, Reducer c n, Reducer c o, Reducer c p) => Reducer c (m, n, o, p) instance (Reducer c m, Reducer c n, Reducer c o) => Reducer c (m, n, o) instance (Reducer c m, Reducer c n) => Reducer c (m, n) module Data.Monoid.Reducer.Char -- | Provides a mechanism for the UTF8 Monoid to report invalid -- characters to one or more monoids. class (Reducer Char m) => CharReducer m fromChar :: (CharReducer m) => Char -> m invalidChar :: (CharReducer m) => [Word8] -> m instance CharReducer [Char] instance (CharReducer m, CharReducer m', CharReducer m'', CharReducer m''') => CharReducer (m, m', m'', m''') instance (CharReducer m, CharReducer m', CharReducer m'') => CharReducer (m, m', m'') instance (CharReducer m, CharReducer m') => CharReducer (m, m') -- | UTF8 encoded unicode characters can be parsed both forwards and -- backwards, since the start of each Char is clearly marked. This -- Monoid accumulates information about the characters represented -- and reduces that information using a CharReducer, which is just -- a Reducer Monoid that knows what it wants to do about an -- invalidChar -- a string of Word8 values that don't form -- a valid UTF8 character. -- -- As this monoid parses chars it just feeds them upstream to the -- underlying CharReducer. Efficient left-to-right and right-to-left -- traversals are supplied so that a lazy ByteString can be parsed -- efficiently by chunking it into strict chunks, and batching the -- traversals over each before stitching the edges together. -- -- Because this needs to be a Monoid and should return the exact -- same result regardless of forward or backwards parsing, it chooses to -- parse only canonical UTF8 unlike most Haskell UTF8 parsers, which will -- blissfully accept illegal alternative long encodings of a character. -- -- This actually fixes a potential class of security issues in some -- scenarios: -- -- -- http://prowebdevelopmentblog.com/content/big-overhaul-java-utf-8-charset -- -- NB: Due to naive use of a list to track the tail of an unfinished -- character this may exhibit O(n^2) behavior parsing backwards -- along an invalid sequence of a large number of bytes that all claim to -- be in the tail of a character. module Data.Monoid.Lexical.UTF8.Decoder data UTF8 m runUTF8 :: (CharReducer m) => UTF8 m -> m instance Pointed UTF8 instance Functor UTF8 instance (CharReducer m) => Reducer Word8 (UTF8 m) instance (CharReducer m) => Monoid (UTF8 m) module Data.Monoid.Reducer.With -- | If m is a c-Reducer, then m is (c -- WithReducer m)-Reducer This can be used to quickly -- select a Reducer for use as a FingerTree measure. newtype WithReducer c m WithReducer :: c -> WithReducer c m withoutReducer :: WithReducer c m -> c instance (Reducer c m) => Measured m (WithReducer c m) instance (Reducer c m) => Reducer (WithReducer c m) m module Data.Monoid.Union -- | A Container suitable for the Union Monoid class HasUnion f empty :: (HasUnion f) => f union :: (HasUnion f) => f -> f -> f -- | The Monoid (union,empty) newtype Union f Union :: f -> Union f getUnion :: Union f -> f -- | Polymorphic containers that we can supply an operation to handle -- unions with class (Functor f) => HasUnionWith f unionWith :: (HasUnionWith f) => (a -> a -> a) -> f a -> f a -> f a emptyWith :: (HasUnionWith f) => f a -- | The Monoid ('unionWith mappend',empty) for -- containers full of monoids. newtype UnionWith f m UnionWith :: f m -> UnionWith f m getUnionWith :: UnionWith f m -> f m instance (Eq (f m)) => Eq (UnionWith f m) instance (Ord (f m)) => Ord (UnionWith f m) instance (Show (f m)) => Show (UnionWith f m) instance (Read (f m)) => Read (UnionWith f m) instance (Functor f) => Functor (UnionWith f) instance (Pointed f) => Pointed (UnionWith f) instance (Monad f) => Monad (UnionWith f) instance (Eq f) => Eq (Union f) instance (Ord f) => Ord (Union f) instance (Show f) => Show (Union f) instance (Read f) => Read (Union f) instance (HasUnionWith f, Monoid m) => Reducer (f m) (UnionWith f m) instance (HasUnionWith f, Monoid m) => Monoid (UnionWith f m) instance (Ord k) => HasUnionWith (Map k) instance HasUnionWith IntMap instance Copointed Union instance Pointed Union instance Functor Union instance (HasUnion f) => Reducer f (Union f) instance (HasUnion f) => Monoid (Union f) instance HasUnion IntSet instance (Ord a) => HasUnion (Set a) instance (Eq a) => HasUnion [a] instance (Ord k) => HasUnion (Map k a) instance HasUnion (IntMap a) -- | A Generator c is a possibly-specialized container, -- which contains values of type Elem c, and which knows -- how to efficiently apply a Reducer to extract an answer. -- -- Since a Generator is not polymorphic in its contents, it is -- more specialized than Data.Foldable.Foldable, and a -- Reducer may supply efficient left-to-right and right-to-left -- reduction strategies that a Generator may avail itself of. module Data.Generator -- | minimal definition mapReduce or mapTo class Generator c where { type family Elem c :: *; { mapFrom f = mappend . mapReduce f mapTo f m = mappend m . mapReduce f mapReduce f = mapTo f mempty } } mapReduce :: (Generator c, Reducer e m) => (Elem c -> e) -> c -> m mapTo :: (Generator c, Reducer e m) => (Elem c -> e) -> m -> c -> m mapFrom :: (Generator c, Reducer e m) => (Elem c -> e) -> c -> m -> m -- | a Generator transformer that asks only for the keys of an -- indexed container newtype Keys c Keys :: c -> Keys c getKeys :: Keys c -> c -- | a Generator transformer that asks only for the values contained -- in an indexed container newtype Values c Values :: c -> Values c getValues :: Values c -> c -- | a Generator transformer that treats Word8 as Char -- This lets you use a ByteString as a Char source without going -- through a Monoid transformer like UTF8 newtype Char8 c Char8 :: c -> Char8 c getChar8 :: Char8 c -> c -- | Apply a Reducer directly to the elements of a Generator reduce :: (Generator c, Reducer (Elem c) m) => c -> m mapReduceWith :: (Generator c, Reducer e m) => (m -> n) -> (Elem c -> e) -> c -> n reduceWith :: (Generator c, Reducer (Elem c) m) => (m -> n) -> c -> n instance Generator (Char8 ByteString) instance Generator (Char8 ByteString) instance (Ix i) => Generator (Values (Array i e)) instance Generator (Values (Map k v)) instance Generator (Values (IntMap v)) instance (Ix i) => Generator (Keys (Array i e)) instance Generator (Keys (Map k v)) instance Generator (Keys (IntMap v)) instance (Ix i) => Generator (Array i e) instance Generator (Map k v) instance Generator (IntMap v) instance Generator (Set a) instance Generator IntSet instance Generator (Seq c) instance (Measured v e) => Generator (FingerTree v e) instance Generator [c] instance Generator Text instance Generator ByteString instance Generator ByteString -- | Incrementally determine locations in a source file through local -- information This allows for efficient recomputation of line #s and -- token locations while the file is being interactively updated by -- storing this as a supplemental measure on a FingerTree. -- -- The general idea is to use this as part of a measure in a FingerTree -- so you can use mappend to prepend a startOfFile with the -- file information. module Data.Monoid.Lexical.SourcePosition -- | Compute the location of the next standard 8-column aligned tab nextTab :: Int -> Int -- | A Monoid of partial information about locations in a source -- file. This is polymorphic in the kind of information you want to -- maintain about each source file. data SourcePosition file -- | An absolute position in a file is known, or an overriding #line -- directive has been seen Pos :: file -> !!SourceLine -> !!SourceColumn -> SourcePosition file -- | We've seen some carriage returns. Lines :: !!SourceLine -> !!SourceColumn -> SourcePosition file -- | We've only seen part of a line. Columns :: !!SourceColumn -> SourcePosition file -- | We have an unhandled tab to deal with. Tab :: !!SourceColumn -> !!SourceColumn -> SourcePosition file type SourceLine = Int type SourceColumn = Int -- | extract partial information about the current line number if possible sourceLine :: SourcePosition f -> Maybe SourceLine -- | extract partial information about the current column, even in the -- absence of knowledge of the source file sourceColumn :: SourcePosition f -> Maybe SourceColumn -- | lift information about a source file into a starting -- SourcePosition for that file startOfFile :: f -> SourcePosition f -- | extract the standard format for an absolute source position showSourcePosition :: SourcePosition String -> String instance (Read file) => Read (SourcePosition file) instance (Show file) => Show (SourcePosition file) instance (Eq file) => Eq (SourcePosition file) instance CharReducer (SourcePosition file) instance Reducer Char (SourcePosition file) instance Monoid (SourcePosition file) instance IsString (SourcePosition file) instance FunctorPlus SourcePosition instance FunctorZero SourcePosition instance Pointed SourcePosition instance Functor SourcePosition -- | A simple demonstration of tokenizing a Generator into distinct -- words and/or lines using a word-parsing Monoid that accumulates -- partial information about words and then builds up a token stream. module Data.Monoid.Lexical.Words -- | A CharReducer transformer that breaks a Char -- Generator into distinct words, feeding a Char -- Reducer each line in turn data Words m -- | Extract the matched words from the Words Monoid runWords :: Words m -> [m] -- | A CharReducer transformer that strips out any character matched -- by isSpace data Unspaced m -- | Utility function to extract words using accumulator, inside-word, and -- until-next-word monoids wordsFrom :: (Generator c, (Elem c) ~ Char, Reducer Char m, Reducer Char n, Reducer Char o) => m -> c -> [(m, n, o)] -- | A CharReducer transformer that breaks a Char -- Generator into distinct lines, feeding a Char -- Reducer each line in turn. data Lines m -- | Extract the matched lines from the Lines Monoid runLines :: Lines m -> [m] -- | A CharReducer transformer that strips out newlines data Unlined m -- | Utility function to extract lines using accumulator, inside-line, and -- until-next-line monoids linesFrom :: (Generator c, (Elem c) ~ Char, Reducer Char m, Reducer Char n, Reducer Char o) => m -> c -> [(m, n, o)] instance (Eq m) => Eq (Unlined m) instance (Ord m) => Ord (Unlined m) instance (Show m) => Show (Unlined m) instance (Read m) => Read (Unlined m) instance (Monoid m) => Monoid (Unlined m) instance (Eq m) => Eq (Unspaced m) instance (Ord m) => Ord (Unspaced m) instance (Show m) => Show (Unspaced m) instance (Read m) => Read (Unspaced m) instance (Monoid m) => Monoid (Unspaced m) instance (Show m) => Show (Lines m) instance (Read m) => Read (Lines m) instance (Monoid m) => Monoid (Lines m) instance Functor Lines instance (Show m) => Show (Words m) instance (Read m) => Read (Words m) instance (Reducer Char m) => IsString (Unlined m) instance Copointed Unlined instance Pointed Unlined instance Functor Unlined instance (CharReducer m) => CharReducer (Unlined m) instance (Reducer Char m) => Reducer Char (Unlined m) instance (Reducer Char m) => IsString (Unspaced m) instance Copointed Unspaced instance Pointed Unspaced instance Functor Unspaced instance (CharReducer m) => CharReducer (Unspaced m) instance (Reducer Char m) => Reducer Char (Unspaced m) instance (Reducer Char m) => IsString (Lines m) instance (CharReducer m) => CharReducer (Lines m) instance (Reducer Char m) => Reducer Char (Lines m) instance (Reducer Char m) => IsString (Words m) instance (CharReducer m) => CharReducer (Words m) instance Functor Words instance (Reducer Char m) => Reducer Char (Words m) instance (Monoid m) => Monoid (Words m) -- | A simple Monoid transformer that takes a Monoid m and -- produces a new m-Reducer named Self m -- -- This is useful when you have a generator that already contains -- monoidal values or someone supplies the map to the monoid in the form -- of a function rather than as a Reducer instance. You can just -- getSelf . reduce or getSelf . -- mapReduce f in those scenarios. These behaviors are -- encapsulated into the fold and foldMap combinators in -- Data.Monoid.Combinators respectively. module Data.Monoid.Self newtype Self m Self :: m -> Self m getSelf :: Self m -> m instance (Monoid m) => Monoid (Self m) instance Copointed Self instance Pointed Self instance Functor Self instance (Monoid m) => Reducer m (Self m) -- | Compression algorithms are all about exploiting redundancy. When -- applying an expensive Reducer to a redundant source, it may be -- better to extract the structural redundancy that is present. -- LZ78 is a compression algorithm that does so, without requiring -- the dictionary to be populated with all of the possible values of a -- data type unlike its later refinement LZW, and which has fewer -- comparison reqirements during encoding than its earlier counterpart -- LZ77. Since we aren't storing these as a bitstream the LZSS refinement -- of only encoding pointers once you cross the break-even point is a net -- loss. module Data.Generator.Compressive.LZ78 data LZ78 a -- | a type-constrained reduce operation decode :: LZ78 a -> [a] -- | contruct an LZ78-compressed Generator using a Map -- internally, requires an instance of Ord. encode :: (Ord a) => [a] -> LZ78 a -- | contruct an LZ78-compressed Generator using a list internally, -- requires an instance of Eq. encodeEq :: (Eq a) => [a] -> LZ78 a -- | QuickCheck property: decode . encode = id prop_decode_encode :: (Ord a) => [a] -> Bool -- | QuickCheck property: decode . encodeEq = id prop_decode_encodeEq :: (Eq a) => [a] -> Bool instance (Eq a) => Eq (LZ78 a) instance (Ord a) => Ord (LZ78 a) instance (Show a) => Show (LZ78 a) instance (Eq a) => Eq (Token a) instance (Ord a) => Ord (Token a) instance (Show a) => Show (Token a) instance (Read a) => Read (Token a) instance Foldable LZ78 instance Functor LZ78 instance Generator (LZ78 a) instance Functor Token -- | Transform any Char Reducer into an IsString -- instance so it can be used directly with overloaded string literals. module Data.Monoid.FromString data FromString m FromString :: m -> FromString m getFromString :: FromString m -> m instance Functor FromString instance Copointed FromString instance Pointed FromString instance (Reducer Char m) => IsString (FromString m) instance (Reducer Char m) => Reducer Char (FromString m) instance (Monoid m) => Monoid (FromString m) -- | Utilities for working with Monoids that conflict with names from the -- Prelude, Data.Foldable, Control.Monad or -- elsewhere. Intended to be imported qualified. -- -- 
--   import Data.Monoid.Combinators as Monoid 
--
module Data.Monoid.Combinators -- | A generalization of Data.List.repeat to an arbitrary Monoid. -- May fail to terminate for some values in some monoids. repeat :: (Reducer e m) => e -> m -- | 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 replicate :: (Monoid m, Integral n) => m -> n -> m -- | 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 prop_replicate_right_distributive :: (Eq m, Monoid m, Arbitrary m, Integral n) => m -> n -> n -> Bool -- | Compression algorithms are all about exploiting redundancy. When -- applying an expensive Reducer to a redundant source, it may be -- better to extract the structural redundancy that is present. Run -- length encoding can do so for long runs of identical inputs. module Data.Generator.Compressive.RLE -- | A Generator which supports efficient mapReduce -- operations over run-length encoded data. newtype RLE f a RLE :: f (Run a) -> RLE f a getRLE :: RLE f a -> f (Run a) -- | A single run with a strict length. data Run a Run :: a -> !!Int -> Run a decode :: (Foldable f) => RLE f a -> [a] encode :: (Generator c, Eq (Elem c)) => c -> RLE Seq (Elem c) -- | naive left to right encoder, which can handle infinite data encodeList :: (Eq a) => [a] -> RLE [] a prop_decode_encode :: (Generator c, Eq (Elem c)) => c -> Bool -- | QuickCheck property: decode . encode = id prop_decode_encodeList :: (Eq a) => [a] -> Bool instance (Eq a) => Reducer a (RLE Seq a) instance (Eq a) => Monoid (RLE Seq a) instance (Foldable f) => Generator (RLE f a) instance (Functor f) => Functor (RLE f) instance Pointed Run instance Functor Run module Data.Monoid.Categorical -- | The Monoid of the endomorphisms over some object in an -- arbitrary Category. data GEndo k a GEndo :: k a a -> GEndo k a getGEndo :: GEndo k a -> k a a -- | A Monoid is just a Category with one object. This fakes -- that with a GADT data CMonoid m n o -- | Extract the Monoid from its representation as a Category categoryToMonoid :: CMonoid m m m -> m -- | Convert a value in a Monoid into an arrow in a Category. monoidToCategory :: (Monoid m) => m -> CMonoid m m m instance (Monoid m) => Reducer (CMonoid m m m) m instance (Reducer c m) => Reducer c (CMonoid m m m) instance (Monoid m) => Monoid (CMonoid m m m) instance (Monoid m) => Category (CMonoid m) instance (Category k) => Monoid (GEndo k a) -- | More easily understood aliases for mappend and mempty -- -- 
--   import Data.Monoid.Additive
--
module Data.Monoid.Additive plus :: (Monoid m) => m -> m -> m zero :: (Monoid m) => m -- | Syntactic sugar for working with a Monoid that conflicts with -- names from the Prelude. -- -- 
--   import Prelude hiding ((+))
--   import Data.Monoid.Additive.Sugar
--
module Data.Monoid.Additive.Sugar (+) :: (Monoid m) => m -> m -> m -- | When dealing with a Ring or other structure, you often need a pair of -- Monoid instances that are closely related. Making a -- newtype for one is unsatisfying and yields an unnatural -- programming style. -- -- A Multiplicative is a Monoid that is intended for use in -- a scenario that can be extended to have another Monoid slot in -- for addition. This enables one to use common notation. -- -- Any Multiplicative can be turned into a Monoid using the -- Log wrapper. -- -- Any Monoid can be turned into a Multiplicative using the -- Exp wrapper. -- -- Instances are supplied for common Monads of Monoids, in a fashion -- which can be extended if the Monad is a MonadPlus to -- yield a RightSemiNearRing -- -- Instances are also supplied for common Applicatives of Monoids, in a -- fashion which can be extended if the Applicative is -- Alternative to yield a RightSemiNearRing module Data.Monoid.Multiplicative class Multiplicative m one :: (Multiplicative m) => m times :: (Multiplicative m) => m -> m -> m -- | Convert a Multiplicative into a Monoid. Mnemonic: -- Log a + Log b = Log (a * b) data Log m Log :: m -> Log m getLog :: Log m -> m -- | Convert a Monoid into a Multiplicative. Mnemonic: -- Exp a * Exp b = Exp (a + b) data Exp m Exp :: m -> Exp m getExp :: Exp m -> m instance (Integral m) => Multiplicative (Ratio m) instance Multiplicative Integer instance Multiplicative Int instance (Monoid m) => Multiplicative (Const m a) instance (Monoid n) => Multiplicative (ZipList n) instance (Stream s m t, Monoid n) => Multiplicative (ParsecT s u m n) instance (Monoid n) => Multiplicative (STM n) instance (Monoid n) => Multiplicative (ST s n) instance (Monoid n) => Multiplicative (ST s n) instance (Monoid n) => Multiplicative (IO n) instance (Monad m, Monoid w, Monoid n) => Multiplicative (WriterT w m n) instance (Monad m, Monoid w, Monoid n) => Multiplicative (WriterT w m n) instance (Monad m, Monoid n) => Multiplicative (ReaderT e m n) instance (Monad m, Monoid n) => Multiplicative (StateT s m n) instance (Monad m, Monoid n) => Multiplicative (StateT s m n) instance (Monad m, Monoid w, Monoid n) => Multiplicative (RWST r w s m n) instance (Monad m, Monoid w, Monoid n) => Multiplicative (RWST r w s m n) instance (Monad m, Monoid n) => Multiplicative (ContT r m n) instance (Monoid w, Monoid m) => Multiplicative (Writer w m) instance (Monoid w, Monoid m) => Multiplicative (Writer w m) instance (Monoid m) => Multiplicative (Reader e m) instance (Monoid m) => Multiplicative (State s m) instance (Monoid m) => Multiplicative (State s m) instance (Monoid w, Monoid m) => Multiplicative (RWS r w s m) instance (Monoid w, Monoid m) => Multiplicative (RWS r w s m) instance (Monoid m) => Multiplicative (Cont r m) instance (Monoid m) => Multiplicative (Identity m) instance (Monoid m) => Multiplicative (Maybe m) instance (Measured v m, Monoid m) => Multiplicative (FingerTree v m) instance (Monoid m) => Multiplicative (Seq m) instance (Monoid m) => Multiplicative [m] instance (Multiplicative m) => Multiplicative (FromString m) instance (Multiplicative m) => Multiplicative (Self m) instance (Monoid m) => Multiplicative (Exp m) instance (Multiplicative m) => Monoid (Log m) instance (Multiplicative m) => Multiplicative (ReducedBy m s) instance (Multiplicative m) => Multiplicative (Dual m) -- | Syntactic sugar for working with a Multiplicative monoids that -- conflicts with names from the Prelude. -- -- 
--   import Prelude hiding ((+),(*))
--   import Data.Monoid.Multiplicative.Sugar
--
module Data.Monoid.Multiplicative.Sugar (*) :: (Multiplicative r) => r -> r -> r -- | Defines left- and right- seminearrings. Every MonadPlus wrapped -- around a Monoid qualifies due to the distributivity of -- (>>=) over mplus. -- -- See -- http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers1/ module Data.Ring.Semi.Near -- | 0 annihilates times class (Multiplicative m, Monoid m) => Ringoid m -- | 
--   a * (b + c) = (a * b) + (a * c)
--
class (Ringoid m) => LeftSemiNearRing m -- | 
--   (a + b) * c = (a * c) + (b * c)
--
class (Ringoid m) => RightSemiNearRing m instance (MonadPlus m, Monoid w, Monoid n) => RightSemiNearRing (WriterT w m n) instance (MonadPlus m, Monoid w, Monoid n) => RightSemiNearRing (WriterT w m n) instance (MonadPlus m, Monoid w, Monoid n) => RightSemiNearRing (RWST r w s m n) instance (MonadPlus m, Monoid w, Monoid n) => RightSemiNearRing (RWST r w s m n) instance (MonadPlus m, Monoid n) => RightSemiNearRing (ReaderT e m n) instance (MonadPlus m, Monoid n) => RightSemiNearRing (StateT s m n) instance (MonadPlus m, Monoid n) => RightSemiNearRing (StateT s m n) instance (Stream s m t, Monoid a) => RightSemiNearRing (ParsecT s u m a) instance (Monoid m) => RightSemiNearRing (Seq m) instance (Monoid m) => RightSemiNearRing (Maybe m) instance (Monoid m) => RightSemiNearRing [m] instance (Measured v m, Monoid m) => RightSemiNearRing (FingerTree v m) instance (LeftSemiNearRing m) => RightSemiNearRing (Dual m) instance (RightSemiNearRing m) => RightSemiNearRing (ReducedBy m s) instance (RightSemiNearRing m) => RightSemiNearRing (FromString m) instance (RightSemiNearRing m) => RightSemiNearRing (Self m) instance (RightSemiNearRing m) => LeftSemiNearRing (Dual m) instance (LeftSemiNearRing m) => LeftSemiNearRing (ReducedBy m s) instance (LeftSemiNearRing m) => LeftSemiNearRing (FromString m) instance (LeftSemiNearRing m) => LeftSemiNearRing (Self m) instance (MonadPlus m, Monoid w, Monoid n) => Ringoid (WriterT w m n) instance (MonadPlus m, Monoid w, Monoid n) => Ringoid (WriterT w m n) instance (MonadPlus m, Monoid w, Monoid n) => Ringoid (RWST r w s m n) instance (MonadPlus m, Monoid w, Monoid n) => Ringoid (RWST r w s m n) instance (MonadPlus m, Monoid n) => Ringoid (ReaderT e m n) instance (MonadPlus m, Monoid n) => Ringoid (StateT s m n) instance (MonadPlus m, Monoid n) => Ringoid (StateT s m n) instance (Stream s m t, Monoid a) => Ringoid (ParsecT s u m a) instance (Monoid m) => Ringoid (Seq m) instance (Monoid m) => Ringoid (Maybe m) instance (Monoid m) => Ringoid [m] instance (Measured v m, Monoid m) => Ringoid (FingerTree v m) instance (Ringoid m) => Ringoid (Dual m) instance (Ringoid m) => Ringoid (ReducedBy m s) instance (Ringoid m) => Ringoid (FromString m) instance (Ringoid m) => Ringoid (Self m) module Data.Ring.Semi -- | A SemiRing is an instance of both Multiplicative and -- Monoid where times distributes over plus. class (RightSemiNearRing a, LeftSemiNearRing a) => SemiRing a instance (SemiRing r) => SemiRing (Dual r) instance (SemiRing r) => SemiRing (ReducedBy r s) instance (SemiRing r) => SemiRing (FromString r) instance (SemiRing r) => SemiRing (Self r) module Data.Monoid.Ord -- | The Monoid (max,minBound) newtype Max a Max :: a -> Max a getMax :: Max a -> a -- | The Monoid given by (min,maxBound) newtype Min a Min :: a -> Min a getMin :: Min a -> a -- | The Monoid (max,Nothing) over -- Maybe a where Nothing is the bottom element newtype MaxPriority a MaxPriority :: Maybe a -> MaxPriority a getMaxPriority :: MaxPriority a -> Maybe a minfinity :: MaxPriority a -- | The Monoid (min,Nothing) over -- Maybe a where Nothing is the top element newtype MinPriority a MinPriority :: Maybe a -> MinPriority a getMinPriority :: MinPriority a -> Maybe a infinity :: MinPriority a instance (Eq a) => Eq (MinPriority a) instance (Show a) => Show (MinPriority a) instance (Read a) => Read (MinPriority a) instance (Eq a) => Eq (MaxPriority a) instance (Ord a) => Ord (MaxPriority a) instance (Show a) => Show (MaxPriority a) instance (Read a) => Read (MaxPriority a) instance (Eq a) => Eq (Min a) instance (Ord a) => Ord (Min a) instance (Show a) => Show (Min a) instance (Read a) => Read (Min a) instance (Bounded a) => Bounded (Min a) instance (Eq a) => Eq (Max a) instance (Ord a) => Ord (Max a) instance (Show a) => Show (Max a) instance (Read a) => Read (Max a) instance (Bounded a) => Bounded (Max a) instance Pointed MinPriority instance Functor MinPriority instance (Ord a) => Reducer (Maybe a) (MinPriority a) instance (Ord a) => Monoid (MinPriority a) instance (Ord a) => Ord (MinPriority a) instance Pointed MaxPriority instance Functor MaxPriority instance (Ord a) => Reducer (Maybe a) (MaxPriority a) instance (Ord a) => Monoid (MaxPriority a) instance Copointed Min instance Pointed Min instance Functor Min instance (Ord a, Bounded a) => Reducer a (Min a) instance (Ord a, Bounded a) => Monoid (Min a) instance Copointed Max instance Pointed Max instance Functor Max instance (Ord a, Bounded a) => Reducer a (Max a) instance (Ord a, Bounded a) => Monoid (Max a) module Data.Ring.Semi.Kleene class (SemiRing r) => KleeneAlgebra r star :: (KleeneAlgebra r) => r -> r -- | Turn an instance of Ord into a SemiRing over max -- and min module Data.Ring.Semi.Ord -- | A SemiRing using a type's built-in Bounded instance. newtype Order a Order :: a -> Order a getOrder :: Order a -> a -- | A SemiRing which adds minBound and maxBound to a -- pre-existing type. data Priority a MinBound :: Priority a Priority :: a -> Priority a MaxBound :: Priority a instance (Eq a) => Eq (Priority a) instance (Read a) => Read (Priority a) instance (Show a) => Show (Priority a) instance (Eq a) => Eq (Order a) instance (Ord a) => Ord (Order a) instance (Read a) => Read (Order a) instance (Show a) => Show (Order a) instance (Bounded a) => Bounded (Order a) instance (Arbitrary a) => Arbitrary (Order a) instance (CoArbitrary a) => CoArbitrary (Order a) instance Pointed Priority instance Functor Priority instance (Ord a) => Reducer (MaxPriority a) (Priority a) instance (Ord a) => Reducer (MinPriority a) (Priority a) instance (Ord a) => Reducer a (Priority a) instance (Ord a) => SemiRing (Priority a) instance (Ord a) => RightSemiNearRing (Priority a) instance (Ord a) => LeftSemiNearRing (Priority a) instance (Ord a) => Ringoid (Priority a) instance (Ord a) => Multiplicative (Priority a) instance (Ord a) => Monoid (Priority a) instance (CoArbitrary a) => CoArbitrary (Priority a) instance (Arbitrary a) => Arbitrary (Priority a) instance (Ord a) => Ord (Priority a) instance Bounded (Priority a) instance Copointed Order instance Pointed Order instance Functor Order instance (Bounded a, Ord a) => Reducer a (Order a) instance (Bounded a, Ord a) => SemiRing (Order a) instance (Bounded a, Ord a) => LeftSemiNearRing (Order a) instance (Bounded a, Ord a) => RightSemiNearRing (Order a) instance (Bounded a, Ord a) => Ringoid (Order a) instance (Bounded a, Ord a) => Multiplicative (Order a) instance (Bounded a, Ord a) => Monoid (Order a) module Data.Ring.Semi.Tropical infinity :: Tropical a -- | The SemiRing (min,+) over a extended -- with infinity. When a has a Num instance with an -- addition that respects order, then this is transformed into a tropical -- semiring. It is assumed that 0 is the least element of a. -- -- -- http://hal.archives-ouvertes.fr/docs/00/11/37/79/PDF/Tropical.pdf newtype Tropical a Tropical :: Maybe a -> Tropical a getTropical :: Tropical a -> Maybe a instance (Eq a) => Eq (Tropical a) instance (Show a) => Show (Tropical a) instance (Read a) => Read (Tropical a) instance (Arbitrary a) => Arbitrary (Tropical a) instance (CoArbitrary a) => CoArbitrary (Tropical a) instance (Ord a, Num a) => SemiRing (Tropical a) instance (Ord a, Num a) => RightSemiNearRing (Tropical a) instance (Ord a, Num a) => LeftSemiNearRing (Tropical a) instance (Ord a, Num a) => Ringoid (Tropical a) instance (Num a) => Multiplicative (Tropical a) instance Pointed Tropical instance Functor Tropical instance (Ord a) => Reducer (MinPriority a) (Tropical a) instance (Ord a) => Reducer (Maybe a) (Tropical a) instance (Ord a) => Reducer a (Tropical a) instance (Ord a) => Monoid (Tropical a) instance (Ord a) => Ord (Tropical a) module Data.Ring.Semi.Near.Trie data Trie c m Trie :: m -> m -> UnionWith (Map c) (Trie c m) -> Trie c m total :: Trie c m -> m label :: Trie c m -> m children :: Trie c m -> UnionWith (Map c) (Trie c m) singleton :: (Ord c, Reducer c m) => c -> Trie c m empty :: (Ord c, Monoid m) => Trie c m null :: (Ord c) => Trie c m -> Bool instance (Eq c, Eq m) => Eq (Trie c m) instance (Show c, Show m) => Show (Trie c m) instance (Ord c, Reducer c m) => Reducer c (Trie c m) instance (Ord c, Monoid m) => Monoid (Trie c m) instance Functor (Trie c) -- | Syntactic sugar for working with rings that conflicts with names from -- the Prelude. -- -- 
--   import Prelude hiding ((-), (+), (*), negate, subtract)
--   import Data.Ring.Sugar
--
module Data.Ring.Sugar -- | Extends Monoid to support Group operations module Data.Group -- | Minimal complete definition: gnegate or minus class (Monoid a) => Group a gnegate :: (Group a) => a -> a minus :: (Group a) => a -> a -> a gsubtract :: (Group a) => a -> a -> a instance (Group a) => Group (ReducedBy a s) instance (Group a) => Group (FromString a) instance (Group a) => Group (Self a) instance (Group a) => Group (Dual a) instance (Fractional a) => Group (Product a) instance (Num a) => Group (Sum a) -- | Utilities for working with Groups that conflict with names from the -- Prelude. -- -- Intended to be imported qualified. -- -- 
--   import Data.Group.Combinators as Group (replicate)
--
module Data.Group.Combinators replicate :: (Group m, Integral n) => m -> n -> m prop_replicate_right_distributive :: (Eq g, Group g, Arbitrary g, Integral n) => g -> n -> n -> Bool module Data.Group.Multiplicative -- | Minimal definition over or grecip class (Multiplicative g) => MultiplicativeGroup g over :: (MultiplicativeGroup g) => g -> g -> g under :: (MultiplicativeGroup g) => g -> g -> g grecip :: (MultiplicativeGroup g) => g -> g instance (MultiplicativeGroup a) => MultiplicativeGroup (Dual a) instance (MultiplicativeGroup g) => MultiplicativeGroup (ReducedBy g s) instance (MultiplicativeGroup g) => MultiplicativeGroup (FromString g) instance (MultiplicativeGroup g) => MultiplicativeGroup (Self g) -- | Syntactic sugar for working with groups that conflicts with names from -- the Prelude. -- -- 
--   import Prelude hiding ((-), (+), negate, subtract)
--   import Data.Group.Sugar
--
module Data.Group.Sugar (-) :: (Group g) => g -> g -> g negate :: (Group g) => g -> g subtract :: (Group g) => g -> g -> g -- | Syntactic sugar for working with groups that conflicts with names from -- the Prelude. -- -- 
--   import Prelude hiding ((-), (+), (*), (/), negate, subtract, recip)
--   import Data.Group.Multiplicative.Sugar
--
module Data.Group.Multiplicative.Sugar (/) :: (MultiplicativeGroup g) => g -> g -> g (\\) :: (MultiplicativeGroup g) => g -> g -> g recip :: (MultiplicativeGroup g) => g -> g module Data.Ring class (Group a, SemiRing a) => Ring a instance (Ring r) => Ring (Dual r) instance (Ring r) => Ring (ReducedBy r s) instance (Ring r) => Ring (FromString r) instance (Ring r) => Ring (Self r) -- | A Boolean Ring over Bool. Note well that the -- mappend of this ring is symmetric difference and not -- disjunction like you might expect. To get that you should use use -- Ord from Data.Ring.Semi.Ord.Order on Bool to get -- the '&&'/'||'-based distributive-lattice SemiRing module Data.Ring.Boolean newtype BoolRing BoolRing :: Bool -> BoolRing getBoolRing :: BoolRing -> Bool instance Eq BoolRing instance Ord BoolRing instance Show BoolRing instance Read BoolRing instance Arbitrary BoolRing instance CoArbitrary BoolRing instance Reducer Bool BoolRing instance Ring BoolRing instance SemiRing BoolRing instance RightSemiNearRing BoolRing instance LeftSemiNearRing BoolRing instance Ringoid BoolRing instance Multiplicative BoolRing instance Group BoolRing instance Monoid BoolRing -- | A wrapper that lies for you and claims any instance of Num is a -- Ring. Who knows, for your type it might even be telling the -- truth! module Data.Ring.FromNum newtype FromNum a FromNum :: a -> FromNum a getFromNum :: FromNum a -> a instance (Eq a) => Eq (FromNum a) instance (Show a) => Show (FromNum a) instance (Num a) => Num (FromNum a) instance (Arbitrary a) => Arbitrary (FromNum a) instance (CoArbitrary a) => CoArbitrary (FromNum a) instance (Num a) => Reducer Integer (FromNum a) instance (Num a) => Ring (FromNum a) instance (Num a) => SemiRing (FromNum a) instance (Num a) => RightSemiNearRing (FromNum a) instance (Num a) => LeftSemiNearRing (FromNum a) instance (Num a) => Ringoid (FromNum a) instance (Num a) => Multiplicative (FromNum a) instance (Num a) => Group (FromNum a) instance (Num a) => Monoid (FromNum a) module Data.Ring.ModularArithmetic data Mod a s class Modular s a | s -> a modulus :: (Modular s a) => s -> a withIntegralModulus :: (Integral a) => a -> (forall s. (Modular s a) => w Mod s) -> w instance (Eq a) => Eq (Mod a s) instance (Show a) => Show (Mod a s) instance (Modular s a, Integral a) => Ring (Mod a s) instance (Modular s a, Integral a) => SemiRing (Mod a s) instance (Modular s a, Integral a) => RightSemiNearRing (Mod a s) instance (Modular s a, Integral a) => LeftSemiNearRing (Mod a s) instance (Modular s a, Integral a) => Ringoid (Mod a s) instance (Modular s a, Integral a) => Group (Mod a s) instance (Modular s a, Integral a) => Multiplicative (Mod a s) instance (Modular s a, Integral a) => Monoid (Mod a s) instance (Modular s a, Integral a) => Num (Mod a s) instance (ReflectedNum s, Num a) => Modular (ModulusNum s a) a -- | Left- and right- modules over rings, semirings, and Seminearrings. To -- avoid a proliferation of classes. These only require that there be an -- addition and multiplication operation for the Ring module Data.Ring.Module -- | 
--   (x * y) *. m = x * (y *. m)
--
class (Monoid r, Multiplicative r, Monoid m) => LeftModule r m (*.) :: (LeftModule r m) => r -> m -> m -- | 
--   (m .* x) * y = m .* (x * y)
--
class (Monoid r, Multiplicative r, Monoid m) => RightModule r m (.*) :: (RightModule r m) => m -> r -> m -- | 
--   (x *. m) .* y = x *. (m .* y)
--
class (LeftModule r m, RightModule r m) => Module r m instance (HasUnionWith f, Ord r, Eq r, RightSemiNearRing r) => Module r (UnionWith f r) instance (HasUnionWith f, Ord r, Eq r, RightSemiNearRing r) => RightModule r (UnionWith f r) instance (HasUnionWith f, Ord r, Eq r, RightSemiNearRing r) => LeftModule r (UnionWith f r) instance (Module r m, Module r n, Module r o, Module r p, Module r q) => Module r (m, n, o, p, q) instance (Module r m, Module r n, Module r o, Module r p) => Module r (m, n, o, p) instance (Module r m, Module r n, Module r o) => Module r (m, n, o) instance (Module r m, Module r n) => Module r (m, n) instance (RightModule r m, RightModule r n, RightModule r o, RightModule r p, RightModule r q) => RightModule r (m, n, o, p, q) instance (RightModule r m, RightModule r n, RightModule r o, RightModule r p) => RightModule r (m, n, o, p) instance (RightModule r m, RightModule r n, RightModule r o) => RightModule r (m, n, o) instance (RightModule r m, RightModule r n) => RightModule r (m, n) instance (LeftModule r m, LeftModule r n, LeftModule r o, LeftModule r p, LeftModule r q) => LeftModule r (m, n, o, p, q) instance (LeftModule r m, LeftModule r n, LeftModule r o, LeftModule r p) => LeftModule r (m, n, o, p) instance (LeftModule r m, LeftModule r n, LeftModule r o) => LeftModule r (m, n, o) instance (LeftModule r m, LeftModule r n) => LeftModule r (m, n) -- | Monoids for working with an Applicative Functor. module Data.Monoid.Applicative -- | A Traversal uses an glues together Applicative actions -- with (*>) in the manner of traverse_ from Data.Foldable. Any -- values returned by reduced actions are discarded. newtype Traversal f Traversal :: f () -> Traversal f getTraversal :: Traversal f -> f () -- | 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 -- RightSemiNearRing under these operations. newtype Alt f a Alt :: f a -> Alt f a getAlt :: Alt f a -> f a -- | 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 :: f m -> App f m getApp :: App f m -> f m -- | 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 instance (Eq (f m)) => Eq (App f m) instance (Ord (f m)) => Ord (App f m) instance (Show (f m)) => Show (App f m) instance (Read (f m)) => Read (App f m) instance (Functor f) => Functor (App f) instance (Pointed f) => Pointed (App f) instance (Applicative f) => Applicative (App f) instance (Alternative f) => Alternative (App f) instance (Copointed f) => Copointed (App f) instance (Eq (f a)) => Eq (Alt f a) instance (Ord (f a)) => Ord (Alt f a) instance (Show (f a)) => Show (Alt f a) instance (Read (f a)) => Read (Alt f a) instance (Functor f) => Functor (Alt f) instance (Applicative f) => Applicative (Alt f) instance (Alternative f) => Alternative (Alt f) instance (Copointed f) => Copointed (Alt f) instance (Module r m, Applicative f) => Module r (App f m) instance (RightModule r m, Applicative f) => RightModule r (App f m) instance (LeftModule r m, Applicative f) => LeftModule r (App f m) instance (Reducer c m, Applicative f) => Reducer c (App f m) instance (Group m, Applicative f) => Group (App f m) instance (Monoid m, Applicative f) => Monoid (App f m) instance (Alternative f, Monoid a) => RightSemiNearRing (Alt f a) instance (Alternative f, Monoid a) => Ringoid (Alt f a) instance (Alternative f) => Reducer (f a) (Alt f a) instance (Applicative f) => Pointed (Alt f) instance (Applicative f, Monoid a) => Multiplicative (Alt f a) instance (Alternative f) => Monoid (Alt f a) instance (Applicative f) => Reducer (f a) (Traversal f) instance (Applicative f) => Monoid (Traversal f) -- | Monoid instances for working with a Monad module Data.Monoid.Monad -- | An Action uses glues together Monad actions with -- (>>) in the manner of mapM_ from Data.Foldable. -- Any values returned by reduced actions are discarded. newtype Action m Action :: m () -> Action m getAction :: Action m -> m () -- | Efficiently avoid needlessly rebinding when using snoc on an -- action that already returns () A rewrite rule automatically applies -- this when possible snocAction :: (Reducer (m ()) (Action m)) => Action m -> m () -> Action m -- | 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 -- RightSemiNearRing under these operations. newtype MonadSum m a MonadSum :: m a -> MonadSum m a getMonadSum :: MonadSum m a -> 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 :: f m -> Mon f m getMon :: Mon f m -> f m instance (Eq (f m)) => Eq (Mon f m) instance (Ord (f m)) => Ord (Mon f m) instance (Show (f m)) => Show (Mon f m) instance (Read (f m)) => Read (Mon f m) instance (Functor f) => Functor (Mon f) instance (Pointed f) => Pointed (Mon f) instance (Monad f) => Monad (Mon f) instance (MonadPlus f) => MonadPlus (Mon f) instance (Eq (m a)) => Eq (MonadSum m a) instance (Ord (m a)) => Ord (MonadSum m a) instance (Show (m a)) => Show (MonadSum m a) instance (Read (m a)) => Read (MonadSum m a) instance (Monad m) => Monad (MonadSum m) instance (MonadPlus m) => MonadPlus (MonadSum m) instance (Module r m, Monad f) => Module r (Mon f m) instance (RightModule r m, Monad f) => RightModule r (Mon f m) instance (LeftModule r m, Monad f) => LeftModule r (Mon f m) instance (Reducer c m, Monad f) => Reducer c (Mon f m) instance (Group m, Monad f) => Group (Mon f m) instance (Monoid m, Monad f) => Monoid (Mon f m) instance (MonadPlus m, Monoid a) => RightSemiNearRing (MonadSum m a) instance (MonadPlus m, Monoid a) => Ringoid (MonadSum m a) instance (MonadPlus m) => Reducer (m a) (MonadSum m a) instance (Monad m) => Pointed (MonadSum m) instance (Monad m) => Applicative (MonadSum m) instance (Monad m) => Functor (MonadSum m) instance (Monad m, Monoid a) => Multiplicative (MonadSum m a) instance (MonadPlus m) => Monoid (MonadSum m a) instance (Monad m) => Reducer (m a) (Action m) instance (Monad m) => Monoid (Action m) -- | Utilities for working with Monoids that conflict with names from the -- Prelude, Data.Foldable, Control.Monad or -- elsewhere. Intended to be imported qualified. -- -- 
--   import Data.Generator.Combinators as Generator
--
module Data.Generator.Combinators -- | 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 () -- | Convenience function as found in Data.Foldable and -- Control.Monad -- -- 
--   flip mapM_
--
forM_ :: (Generator c, Monad m) => c -> (Elem c -> m b) -> m () -- | The sum of a collection of actions, generalizing concat -- -- 
--   reduceWith getMonadSum
--
msum :: (Generator c, MonadPlus m, (m a) ~ (Elem c)) => c -> m a -- | 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 () -- | Convenience function as found in Data.Foldable -- -- 
--   flip traverse_
--
for_ :: (Generator c, Applicative f) => c -> (Elem c -> f b) -> f () -- | The sum of a collection of actions, generalizing concat -- -- 
--   reduceWith getAlt
--
asum :: (Generator c, Alternative f, (f a) ~ (Elem c)) => c -> f a -- | Efficiently reduce a Generator that contains values of -- type Bool -- -- 
--   reduceWith getAll
--
and :: (Generator c, (Elem c) ~ Bool) => c -> Bool -- | Efficiently reduce a Generator that contains values of -- type Bool -- -- 
--   reduceWith getAny
--
or :: (Generator c, (Elem c) ~ Bool) => c -> Bool -- | 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 -- | 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 -- | 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 -- | 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 -- | Convert any Generator to a list of its contents. Specialization -- of reduce toList :: (Generator c) => c -> [Elem c] -- | Type specialization of foldMap above concatMap :: (Generator c) => (Elem c -> [b]) -> c -> [b] -- | Check to see if any member of the Generator matches the -- supplied value elem :: (Generator c, Eq (Elem c)) => Elem c -> c -> Bool -- | Efficiently mapReduce a subset of the elements in a -- Generator filter :: (Generator c, Reducer (Elem c) m) => (Elem c -> Bool) -> c -> m -- | Allows idiomatic specialization of filter by proving a function that -- will be used to transform the output filterWith :: (Generator c, Reducer (Elem c) m) => (m -> n) -> (Elem c -> Bool) -> c -> n -- | 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) -- | Efficiently sum over the members of any Generator -- -- 
--   reduceWith getSum
--
sum :: (Generator c, Num (Elem c)) => c -> Elem c -- | Efficiently take the product of every member of a Generator -- -- 
--   reduceWith getProduct
--
product :: (Generator c, Num (Elem c)) => c -> Elem c -- | 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 module Data.Generator.Free data Free a AnyGenerator :: c -> Free a instance Generator (Free a) instance Foldable Free instance MonadPlus Free instance Monad Free instance Pointed Free instance Functor Free instance Reducer a (Free a) instance Monoid (Free a) instance (Ord a) => Ord (Free a) instance (Eq a) => Eq (Free a) module Data.Set.Unboxed class US a where { data family USet a; } -- | O(n+m). See difference. (\\) :: (US a, Ord a) => USet a -> USet a -> USet a -- | O(1). Is this the empty set? null :: (US a) => USet a -> Bool -- | O(1). The number of elements in the set. size :: (US a) => USet a -> Int -- | O(log n). Is the element in the set? member :: (US a, Ord a) => a -> USet a -> Bool -- | O(log n). Is the element not in the set? notMember :: (US a, Ord a) => a -> USet a -> Bool -- | O(n+m). Is this a subset? (s1 isSubsetOf s2) -- tells whether s1 is a subset of s2. isSubsetOf :: (US a, Ord a) => USet a -> USet a -> Bool -- | O(n+m). Is this a proper subset? (ie. a subset but not equal). isProperSubsetOf :: (US a, Ord a) => USet a -> USet a -> Bool -- | O(1). The empty set. empty :: (US a) => USet a -- | O(1). Create a singleton set. singleton :: (US a) => a -> USet a -- | O(log n). Insert an element in a set. If the set already -- contains an element equal to the given value, it is replaced with the -- new value. insert :: (US a, Ord a) => a -> USet a -> USet a -- | O(log n). Delete an element from a set. delete :: (US a, Ord a) => a -> USet a -> USet a -- | O(n+m). The union of two sets, preferring the first set when -- equal elements are encountered. The implementation uses the efficient -- hedge-union algorithm. Hedge-union is more efficient on (bigset -- union smallset). union :: (US a, Ord a) => USet a -> USet a -> USet a -- | The union of a list of sets: (unions == foldl -- union empty). unions :: (US a, Ord a) => [USet a] -> USet a -- | O(n+m). Difference of two sets. The implementation uses an -- efficient hedge algorithm comparable with hedge-union. difference :: (US a, Ord a) => USet a -> USet a -> USet a -- | O(n+m). The intersection of two sets. Elements of the result -- come from the first set, so for example -- -- 
--   import qualified Data.Set as S
--   data AB = A | B deriving Show
--   instance Ord AB where compare _ _ = EQ
--   instance Eq AB where _ == _ = True
--   main = print (S.singleton A `S.intersection` S.singleton B,
--                 S.singleton B `S.intersection` S.singleton A)
--
-- -- prints (fromList [A],fromList [B]). intersection :: (US a, Ord a) => USet a -> USet a -> USet a -- | O(n). Filter all elements that satisfy the predicate. filter :: (US a, Ord a) => (a -> Bool) -> USet a -> USet a -- | O(n). Partition the set into two sets, one with all elements -- that satisfy the predicate and one with all elements that don't -- satisfy the predicate. See also split. partition :: (US a, Ord a) => (a -> Bool) -> USet a -> (USet a, USet a) -- | O(log n). The expression (split x set) is a -- pair (set1,set2) where set1 comprises the elements -- of set less than x and set2 comprises the -- elements of set greater than x. split :: (US a, Ord a) => a -> USet a -> (USet a, USet a) -- | O(log n). Performs a split but also returns whether the -- pivot element was found in the original set. splitMember :: (US a, Ord a) => a -> USet a -> (USet a, Bool, USet a) -- | O(n*log n). map f s is the set obtained by -- applying f to each element of s. -- -- It's worth noting that the size of the result may be smaller if, for -- some (x,y), x /= y && f x == f y map :: (US a, US b, Ord a, Ord b) => (a -> b) -> USet a -> USet b -- | O(n). The -- -- mapMonotonic f s == map f s, but works only -- when f is monotonic. The precondition is not checked. -- Semi-formally, we have: -- -- 
--   and [x < y ==> f x < f y | x <- ls, y <- ls] 
--                       ==> mapMonotonic f s == map f s
--       where ls = toList s
--
mapMonotonic :: (US a, US b) => (a -> b) -> USet a -> USet b -- | O(n). Fold over the elements of a set in an unspecified order. fold :: (US a) => (a -> b -> b) -> b -> USet a -> b -- | O(log n). The minimal element of a set. findMin :: (US a) => USet a -> a -- | O(log n). The maximal element of a set. findMax :: (US a) => USet a -> a -- | O(log n). Delete the minimal element. deleteMin :: (US a) => USet a -> USet a -- | O(log n). Delete the maximal element. deleteMax :: (US a) => USet a -> USet a -- | O(log n). Delete and find the minimal element. -- -- 
--   deleteFindMin set = (findMin set, deleteMin set)
--
deleteFindMin :: (US a) => USet a -> (a, USet a) -- | O(log n). Delete and find the maximal element. -- -- 
--   deleteFindMax set = (findMax set, deleteMax set)
--
deleteFindMax :: (US a) => USet a -> (a, USet a) -- | O(log n). Retrieves the maximal key of the set, and the set -- stripped of that element, or Nothing if passed an empty set. maxView :: (US a) => USet a -> Maybe (a, USet a) -- | O(log n). Retrieves the minimal key of the set, and the set -- stripped of that element, or Nothing if passed an empty set. minView :: (US a) => USet a -> Maybe (a, USet a) -- | O(n). The elements of a set. elems :: (US a) => USet a -> [a] -- | O(n). Convert the set to a list of elements. toList :: (US a) => USet a -> [a] -- | O(n*log n). Create a set from a list of elements. fromList :: (US a, Ord a) => [a] -> USet a -- | O(n). Convert the set to an ascending list of elements. toAscList :: (US a) => USet a -> [a] -- | O(n). Build a set from an ascending list in linear time. The -- precondition (input list is ascending) is not checked. fromAscList :: (US a, Eq a) => [a] -> USet a -- | O(n). Build a set from an ascending list of distinct elements -- in linear time. The precondition (input list is strictly ascending) -- is not checked. fromDistinctAscList :: (US a) => [a] -> USet a -- | O(n). Show the tree that implements the set. The tree is shown -- in a compressed, hanging format. showTree :: (US a, Show a) => USet a -> String -- | O(n). The expression (showTreeWith hang wide map) -- shows the tree that implements the set. If hang is -- True, a hanging tree is shown otherwise a rotated tree -- is shown. If wide is True, an extra wide version is -- shown. -- -- 
--   Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1..5]
--   4
--   +--2
--   |  +--1
--   |  +--3
--   +--5
--   
--   Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1..5]
--   4
--   |
--   +--2
--   |  |
--   |  +--1
--   |  |
--   |  +--3
--   |
--   +--5
--   
--   Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1..5]
--   +--5
--   |
--   4
--   |
--   |  +--3
--   |  |
--   +--2
--      |
--      +--1
--
showTreeWith :: (US a, Show a) => Bool -> Bool -> USet a -> String -- | O(n). Test if the internal set structure is valid. valid :: (US a, Ord a) => USet a -> Bool instance US Float instance US Double instance US Word64 instance US Word32 instance US Word16 instance US Word8 instance US Int64 instance US Int32 instance US Int16 instance US Int8 instance US Integer instance US Int instance US Char instance US (Boxed a) instance (US a, Read a, Ord a) => Read (USet a) instance (US a, Show a) => Show (USet a) instance (US a, Ord a) => Ord (USet a) instance (US a, Eq a) => Eq (USet a) instance (US a, Ord a) => Monoid (USet a) -- | Monoids for non-negative integers (Natural) and ints (Nat) -- -- The naturals form a module over any of our monoids. module Data.Ring.Semi.Natural data Natural natural :: Integer -> Natural instance Eq Natural instance Ord Natural instance (Multiplicative m) => Module Natural (Log m) instance (Multiplicative m) => RightModule Natural (Log m) instance (Multiplicative m) => LeftModule Natural (Log m) instance (CharReducer m) => Module Natural (UTF8 m) instance (CharReducer m) => RightModule Natural (UTF8 m) instance (CharReducer m) => LeftModule Natural (UTF8 m) instance Module Natural (SourcePosition f) instance RightModule Natural (SourcePosition f) instance LeftModule Natural (SourcePosition f) instance (MonadPlus f) => Module Natural (MonadSum f a) instance (MonadPlus f) => RightModule Natural (MonadSum f a) instance (MonadPlus f) => LeftModule Natural (MonadSum f a) instance (Monad f) => Module Natural (Action f) instance (Monad f) => RightModule Natural (Action f) instance (Monad f) => LeftModule Natural (Action f) instance (Alternative f) => Module Natural (Alt f a) instance (Alternative f) => RightModule Natural (Alt f a) instance (Alternative f) => LeftModule Natural (Alt f a) instance (Applicative f) => Module Natural (Traversal f) instance (Applicative f) => RightModule Natural (Traversal f) instance (Applicative f) => LeftModule Natural (Traversal f) instance (Monoid m) => Module Natural (CMonoid m m m) instance (Monoid m) => RightModule Natural (CMonoid m m m) instance (Monoid m) => LeftModule Natural (CMonoid m m m) instance (Category k) => Module Natural (GEndo k a) instance (Category k) => RightModule Natural (GEndo k a) instance (Category k) => LeftModule Natural (GEndo k a) instance (Eq a) => Module Natural (RLE Seq a) instance (Eq a) => RightModule Natural (RLE Seq a) instance (Eq a) => LeftModule Natural (RLE Seq a) instance Module Natural (Free a) instance RightModule Natural (Free a) instance LeftModule Natural (Free a) instance (Monoid m) => Module Natural (Self m) instance (Monoid m) => RightModule Natural (Self m) instance (Monoid m) => LeftModule Natural (Self m) instance (Monoid m) => Module Natural (FromString m) instance (Monoid m) => RightModule Natural (FromString m) instance (Monoid m) => LeftModule Natural (FromString m) instance (Monoid m) => Module Natural (Dual m) instance (Monoid m) => RightModule Natural (Dual m) instance (Monoid m) => LeftModule Natural (Dual m) instance Module Natural (Endo a) instance RightModule Natural (Endo a) instance LeftModule Natural (Endo a) instance (Num a) => Module Natural (Product a) instance (Num a) => RightModule Natural (Product a) instance (Num a) => LeftModule Natural (Product a) instance (Num a) => Module Natural (Sum a) instance (Num a) => RightModule Natural (Sum a) instance (Num a) => LeftModule Natural (Sum a) instance (Monoid m) => Module Natural (a -> m) instance (Monoid m) => RightModule Natural (a -> m) instance (Monoid m) => LeftModule Natural (a -> m) instance Module Natural [a] instance RightModule Natural [a] instance LeftModule Natural [a] instance Module Natural Ordering instance RightModule Natural Ordering instance LeftModule Natural Ordering instance Module Natural (Last a) instance RightModule Natural (Last a) instance LeftModule Natural (Last a) instance Module Natural (First a) instance RightModule Natural (First a) instance LeftModule Natural (First a) instance Module Natural All instance RightModule Natural All instance LeftModule Natural All instance Module Natural Any instance RightModule Natural Any instance LeftModule Natural Any instance Module Natural () instance RightModule Natural () instance LeftModule Natural () instance SemiRing Natural instance RightSemiNearRing Natural instance LeftSemiNearRing Natural instance Ringoid Natural instance Multiplicative Natural instance Monoid Natural instance Integral Natural instance Real Natural instance Enum Natural instance Num Natural instance Show Natural instance Read Natural module Data.Ring.Algebra -- | Algebra over a (near) (semi) ring. -- -- 
--   r *. (x * y) = (r *. x) * y = x * (r *. y)
--
-- -- 
--   (x * y) .* r = y * (x .* r) = (y .* r) * x
--
class (Module r m, Multiplicative m) => RAlgebra r m -- | Replacement for Data.BitSet extended to handle enumerations -- where fromEnum can return negative values, support efficient -- intersection and union and allow complementing of the set with respect -- to the bounds of the enumeration module Data.Ring.Semi.BitSet -- | Set operations optimized for tightly grouped sets or nearly universal -- sets with a close by group of elements missing. Stores itself like an -- arbitrary precision floating point number, tracking the least valued -- member of the set and an Integer comprised of the members. data BitSet a -- | O(1) The empty set. Permits O(1) null and size. empty :: (Enum a) => BitSet a -- | O(1) Construct a BitSet with a single element. Permits -- O(1) null and size singleton :: (Enum a) => a -> BitSet a -- | O(d) A BitSet containing every member of the enumeration -- of a. full :: (Enum a, Bounded a) => BitSet a -- | O(d). union :: (Enum a) => BitSet a -> BitSet a -> BitSet a -- | O(d) intersection :: (Enum a) => BitSet a -> BitSet a -> BitSet a -- | O(d) Complements a BitSet with respect to the bounds of -- a. Preserves order of null and size complement :: (Enum a, Bounded a) => BitSet a -> BitSet a -- | O(d) Insert a single element of type a into the -- BitSet. Preserves order of null and size insert :: (Enum a) => a -> BitSet a -> BitSet a -- | O(d) Delete a single item from the BitSet. Preserves -- order of null and size delete :: (Enum a) => a -> BitSet a -> BitSet a -- | O(d) Infix difference (\\) :: (Enum a) => BitSet a -> BitSet a -> BitSet a -- | O(d * n) Make a BitSet from a list of items. fromList :: (Enum a) => [a] -> BitSet a -- | O(d * n) Make a BitSet from a distinct ascending list of -- items fromDistinctAscList :: (Enum a) => [a] -> BitSet a -- | O(1) Test for membership in a BitSet member :: (Enum a) => a -> BitSet a -> Bool -- | O(1) amortized cost. Is the BitSet empty? May be faster -- than checking if size == 0. null :: BitSet a -> Bool -- | O(1) amortized cost. The number of elements in the bit set. size :: BitSet a -> Int -- | O(1) Check to see if we are represented as a complemented -- BitSet. isComplemented :: (Enum a) => BitSet a -> Bool -- | O(d) convert to an Integer representation. Discards negative -- elements toInteger :: BitSet a -> Integer instance Typeable1 BitSet instance Generator (BitSet a) instance (Bounded a, Enum a) => RAlgebra Natural (BitSet a) instance (Bounded a, Enum a) => Module (BitSet a) (BitSet a) instance (Bounded a, Enum a) => RightModule (BitSet a) (BitSet a) instance (Bounded a, Enum a) => LeftModule (BitSet a) (BitSet a) instance (Enum a) => Module Natural (BitSet a) instance (Enum a) => RightModule Natural (BitSet a) instance (Enum a) => LeftModule Natural (BitSet a) instance (Bounded a, Enum a) => SemiRing (BitSet a) instance (Bounded a, Enum a) => RightSemiNearRing (BitSet a) instance (Bounded a, Enum a) => LeftSemiNearRing (BitSet a) instance (Bounded a, Enum a) => Ringoid (BitSet a) instance (Bounded a, Enum a) => Multiplicative (BitSet a) instance (Enum a) => Reducer a (BitSet a) instance (Enum a) => Monoid (BitSet a) instance Foldable BitSet instance (Enum a, Bounded a) => Enum (BitSet a) instance (Enum a, Read a) => Read (BitSet a) instance (Show a) => Show (BitSet a) instance (Enum a, Bounded a) => Bounded (BitSet a) instance Eq (BitSet a) instance (Enum a, Data a) => Data (BitSet a) module Data.Ring.Module.AutomaticDifferentiation data D s r m d :: (Module r m, Ringoid m) => (forall s. D s r m -> D s r m) -> (r, m) lift :: (Module r m) => r -> D s r m instance (Show r, Show m) => Show (D s r m) instance (Read r, Read m) => Read (D s r m) instance (CoArbitrary r, CoArbitrary m) => CoArbitrary (D s r m) instance (Arbitrary r, Arbitrary m) => Arbitrary (D s r m) instance (Module r m, Reducer c r, Reducer c m) => Reducer c (D s r m) instance (Ring r, Module r m, Group m) => Ring (D s r m) instance (SemiRing r, Module r m) => SemiRing (D s r m) instance (RightSemiNearRing r, Module r m) => RightSemiNearRing (D s r m) instance (LeftSemiNearRing r, Module r m) => LeftSemiNearRing (D s r m) instance (Ringoid r, Module r m) => Ringoid (D s r m) instance (Fractional a) => Fractional (D s a a) instance (Num a) => Num (D s a a) instance (Group r, Module r m, Group m) => Group (D s r m) instance (Module r m) => Multiplicative (D s r m) instance (Module r m) => Monoid (D s r m) instance (Ord r) => Ord (D s r m) instance (Eq r) => Eq (D s r m) module Data.Field class (Ring a, MultiplicativeGroup a) => Field a instance (Field f) => Field (ReducedBy f s) instance (Field f) => Field (FromString f) instance (Field f) => Field (Self f) instance (Field f) => Field (Dual f) module Data.Field.VectorSpace class (Field f, Module f g) => VectorSpace f g