-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Haskell 98 semigroups
--   
--   Haskell 98 semigroups
--   
--   In mathematics, a semigroup is an algebraic structure consisting of a
--   set together with an associative binary operation. A semigroup
--   generalizes a monoid in that there might not exist an identity
--   element. It also (originally) generalized a group (a monoid with all
--   inverses) to a type where every element did not have to have an
--   inverse, thus the name semigroup.
@package semigroups
@version 0.9


-- | A NonEmpty list forms a monad as per list, but always contains at
--   least one element.
module Data.List.NonEmpty
data NonEmpty a
(:|) :: a -> [a] -> NonEmpty a

-- | Map a function over a <a>NonEmpty</a> stream.
map :: (a -> b) -> NonEmpty a -> NonEmpty b

-- | 'intersperse x xs' alternates elements of the list with copies of
--   <tt>x</tt>.
--   
--   <pre>
--   intersperse 0 (1 :| [2,3]) == 1 :| [0,2,0,3]
--   </pre>
intersperse :: a -> NonEmpty a -> NonEmpty a

-- | <a>scanl</a> is similar to <a>foldl</a>, but returns a stream of
--   successive reduced values from the left:
--   
--   <pre>
--   scanl f z [x1, x2, ...] == z :| [z `f` x1, (z `f` x1) `f` x2, ...]
--   </pre>
--   
--   Note that
--   
--   <pre>
--   last (scanl f z xs) == foldl f z xs.
--   </pre>
scanl :: Foldable f => (b -> a -> b) -> b -> f a -> NonEmpty b

-- | <a>scanr</a> is the right-to-left dual of <a>scanl</a>. Note that
--   
--   <pre>
--   head (scanr f z xs) == foldr f z xs.
--   </pre>
scanr :: Foldable f => (a -> b -> b) -> b -> f a -> NonEmpty b

-- | <a>scanl1</a> is a variant of <a>scanl</a> that has no starting value
--   argument:
--   
--   <pre>
--   scanl1 f [x1, x2, ...] == x1 :| [x1 `f` x2, x1 `f` (x2 `f` x3), ...]
--   </pre>
scanl1 :: (a -> a -> a) -> NonEmpty a -> NonEmpty a

-- | <a>scanr1</a> is a variant of <a>scanr</a> that has no starting value
--   argument.
scanr1 :: (a -> a -> a) -> NonEmpty a -> NonEmpty a

-- | Extract the first element of the stream.
head :: NonEmpty a -> a

-- | Extract the possibly-empty tail of the stream.
tail :: NonEmpty a -> [a]

-- | Extract the last element of the stream.
last :: NonEmpty a -> a

-- | Extract everything except the last element of the stream.
init :: NonEmpty a -> [a]

-- | Prepend an element to the stream.
(<|) :: a -> NonEmpty a -> NonEmpty a

-- | Synonym for <a>&lt;|</a>.
cons :: a -> NonEmpty a -> NonEmpty a

-- | <a>uncons</a> produces the first element of the stream, and a stream
--   of the remaining elements, if any.
uncons :: NonEmpty a -> (a, Maybe (NonEmpty a))

-- | Sort a stream.
sort :: Ord a => NonEmpty a -> NonEmpty a

-- | <a>reverse</a> a finite NonEmpty stream.
reverse :: NonEmpty a -> NonEmpty a

-- | The <a>inits</a> function takes a stream <tt>xs</tt> and returns all
--   the finite prefixes of <tt>xs</tt>.
inits :: Foldable f => f a -> NonEmpty [a]

-- | The <a>tails</a> function takes a stream <tt>xs</tt> and returns all
--   the suffixes of <tt>xs</tt>.
tails :: Foldable f => f a -> NonEmpty [a]

-- | <tt><a>iterate</a> f x</tt> produces the infinite sequence of repeated
--   applications of <tt>f</tt> to <tt>x</tt>.
--   
--   <pre>
--   iterate f x = x :| [f x, f (f x), ..]
--   </pre>
iterate :: (a -> a) -> a -> NonEmpty a

-- | <tt><a>repeat</a> x</tt> returns a constant stream, where all elements
--   are equal to <tt>x</tt>.
repeat :: a -> NonEmpty a

-- | <tt><a>cycle</a> xs</tt> returns the infinite repetition of
--   <tt>xs</tt>:
--   
--   <pre>
--   cycle [1,2,3] = 1 :| [2,3,1,2,3,...]
--   </pre>
cycle :: NonEmpty a -> NonEmpty a

-- | <a>unfold</a> produces a new stream by repeatedly applying the
--   unfolding function to the seed value to produce an element of type
--   <tt>b</tt> and a new seed value. When the unfolding function returns
--   <a>Nothing</a> instead of a new seed value, the stream ends.
unfold :: (a -> (b, Maybe a)) -> a -> NonEmpty b

-- | <tt><a>insert</a> x xs</tt> inserts <tt>x</tt> into the last position
--   in <tt>xs</tt> where it is still less than or equal to the next
--   element. In particular, if the list is sorted beforehand, the result
--   will also be sorted.
insert :: (Foldable f, Ord a) => a -> f a -> NonEmpty a

-- | <tt><a>take</a> n xs</tt> returns the first <tt>n</tt> elements of
--   <tt>xs</tt>.
take :: Int -> NonEmpty a -> [a]

-- | <tt><a>drop</a> n xs</tt> drops the first <tt>n</tt> elements off the
--   front of the sequence <tt>xs</tt>.
drop :: Int -> NonEmpty a -> [a]

-- | <tt><a>splitAt</a> n xs</tt> returns a pair consisting of the prefix
--   of <tt>xs</tt> of length <tt>n</tt> and the remaining stream
--   immediately following this prefix.
--   
--   <pre>
--   'splitAt' n xs == ('take' n xs, 'drop' n xs)
--   xs == ys ++ zs where (ys, zs) = 'splitAt' n xs
--   </pre>
splitAt :: Int -> NonEmpty a -> ([a], [a])

-- | <tt><a>takeWhile</a> p xs</tt> returns the longest prefix of the
--   stream <tt>xs</tt> for which the predicate <tt>p</tt> holds.
takeWhile :: (a -> Bool) -> NonEmpty a -> [a]

-- | <tt><a>dropWhile</a> p xs</tt> returns the suffix remaining after
--   <tt><a>takeWhile</a> p xs</tt>.
dropWhile :: (a -> Bool) -> NonEmpty a -> [a]

-- | <tt><a>span</a> p xs</tt> returns the longest prefix of <tt>xs</tt>
--   that satisfies <tt>p</tt>, together with the remainder of the stream.
--   
--   <pre>
--   'span' p xs == ('takeWhile' p xs, 'dropWhile' p xs)
--   xs == ys ++ zs where (ys, zs) = 'span' p xs
--   </pre>
span :: (a -> Bool) -> NonEmpty a -> ([a], [a])

-- | The <tt><a>break</a> p</tt> function is equivalent to <tt><a>span</a>
--   (not . p)</tt>.
break :: (a -> Bool) -> NonEmpty a -> ([a], [a])

-- | <tt><a>filter</a> p xs</tt> removes any elements from <tt>xs</tt> that
--   do not satisfy <tt>p</tt>.
filter :: (a -> Bool) -> NonEmpty a -> [a]

-- | The <a>partition</a> function takes a predicate <tt>p</tt> and a
--   stream <tt>xs</tt>, and returns a pair of lists. The first list
--   corresponds to the elements of <tt>xs</tt> for which <tt>p</tt> holds;
--   the second corresponds to the elements of <tt>xs</tt> for which
--   <tt>p</tt> does not hold.
--   
--   <pre>
--   'partition' p xs = ('filter' p xs, 'filter' (not . p) xs)
--   </pre>
partition :: (a -> Bool) -> NonEmpty a -> ([a], [a])

-- | The <a>group</a> function takes a stream and returns a list of streams
--   such that flattening the resulting list is equal to the argument.
--   Moreover, each stream in the resulting list contains only equal
--   elements. For example, in list notation:
--   
--   <pre>
--   'group' $ 'cycle' "Mississippi" = "M" : "i" : "ss" : "i" : "ss" : "i" : "pp" : "i" : "M" : "i" : ...
--   </pre>
group :: (Foldable f, Eq a) => f a -> [NonEmpty a]

-- | <a>groupBy</a> operates like <a>group</a>, but uses the provided
--   equality predicate instead of <a>==</a>.
groupBy :: Foldable f => (a -> a -> Bool) -> f a -> [NonEmpty a]

-- | <a>group1</a> operates like <a>group</a>, but uses the knowledge that
--   its input is non-empty to produce guaranteed non-empty output.
group1 :: Eq a => NonEmpty a -> NonEmpty (NonEmpty a)

-- | <a>groupBy1</a> is to <a>group1</a> as <a>groupBy</a> is to
--   <a>group</a>.
groupBy1 :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty (NonEmpty a)

-- | The <tt>isPrefix</tt> function returns <tt>True</tt> if the first
--   argument is a prefix of the second.
isPrefixOf :: Eq a => [a] -> NonEmpty a -> Bool

-- | <tt>xs !! n</tt> returns the element of the stream <tt>xs</tt> at
--   index <tt>n</tt>. Note that the head of the stream has index 0.
--   
--   <i>Beware</i>: a negative or out-of-bounds index will cause an error.
(!!) :: NonEmpty a -> Int -> a

-- | The <a>zip</a> function takes two streams and returns a stream of
--   corresponding pairs.
zip :: NonEmpty a -> NonEmpty b -> NonEmpty (a, b)

-- | The <a>zipWith</a> function generalizes <a>zip</a>. Rather than
--   tupling the elements, the elements are combined using the function
--   passed as the first argument.
zipWith :: (a -> b -> c) -> NonEmpty a -> NonEmpty b -> NonEmpty c

-- | The <a>unzip</a> function is the inverse of the <a>zip</a> function.
unzip :: Functor f => f (a, b) -> (f a, f b)

-- | The <a>words</a> function breaks a stream of characters into a stream
--   of words, which were delimited by white space.
--   
--   <i>Beware</i>: if the input contains no words (i.e. is entirely
--   whitespace), this will cause an error.
words :: NonEmpty Char -> NonEmpty String

-- | The <a>unwords</a> function is an inverse operation to <a>words</a>.
--   It joins words with separating spaces.
--   
--   <i>Beware</i>: the input <tt>("" :| [])</tt> will cause an error.
unwords :: NonEmpty String -> NonEmpty Char

-- | The <a>lines</a> function breaks a stream of characters into a stream
--   of strings at newline characters. The resulting strings do not contain
--   newlines.
lines :: NonEmpty Char -> NonEmpty String

-- | The <a>unlines</a> function is an inverse operation to <a>lines</a>.
--   It joins lines, after appending a terminating newline to each.
unlines :: NonEmpty String -> NonEmpty Char

-- | Converts a normal list to a <a>NonEmpty</a> stream.
--   
--   Raises an error if given an empty list.
fromList :: [a] -> NonEmpty a

-- | Convert a stream to a normal list efficiently.
toList :: NonEmpty a -> [a]

-- | <a>nonEmpty</a> efficiently turns a normal list into a <a>NonEmpty</a>
--   stream, producing <a>Nothing</a> if the input is empty.
nonEmpty :: [a] -> Maybe (NonEmpty a)
xor :: NonEmpty Bool -> Bool
instance Typeable1 NonEmpty
instance Eq a => Eq (NonEmpty a)
instance Ord a => Ord (NonEmpty a)
instance Show a => Show (NonEmpty a)
instance Read a => Read (NonEmpty a)
instance Data a => Data (NonEmpty a)
instance Foldable NonEmpty
instance Traversable NonEmpty
instance Monad NonEmpty
instance Applicative NonEmpty
instance Functor NonEmpty


-- | In mathematics, a semigroup is an algebraic structure consisting of a
--   set together with an associative binary operation. A semigroup
--   generalizes a monoid in that there might not exist an identity
--   element. It also (originally) generalized a group (a monoid with all
--   inverses) to a type where every element did not have to have an
--   inverse, thus the name semigroup.
--   
--   The use of <tt>(&lt;&gt;)</tt> in this module conflicts with an
--   operator with the same name that is being exported by Data.Monoid.
--   However, this package re-exports (most of) the contents of
--   Data.Monoid, so to use semigroups and monoids in the same package just
--   
--   <pre>
--   import Data.Semigroup
--   </pre>
module Data.Semigroup
class Semigroup a where sconcat (a :| as) = go a as where go b (c : cs) = b <> go c cs go b [] = b times1p y0 x0 = f x0 (1 + y0) where f x y | even y = f (x <> x) (y `quot` 2) | y == 1 = x | otherwise = g (x <> x) (unsafePred y `quot` 2) x g x y z | even y = g (x <> x) (y `quot` 2) z | y == 1 = x <> z | otherwise = g (x <> x) (unsafePred y `quot` 2) (x <> z)
(<>) :: Semigroup a => a -> a -> a
sconcat :: Semigroup a => NonEmpty a -> a
times1p :: (Semigroup a, Whole n) => n -> a -> a
newtype Min a
Min :: a -> Min a
getMin :: Min a -> a
newtype Max a
Max :: a -> Max a
getMax :: Max a -> a

-- | Use <tt><a>Option</a> (<a>First</a> a)</tt> -- to get the behavior of
--   <a>First</a>
newtype First a
First :: a -> First a
getFirst :: First a -> a

-- | Use <tt><a>Option</a> (<a>Last</a> a)</tt> -- to get the behavior of
--   <a>Last</a>
newtype Last a
Last :: a -> Last a
getLast :: Last a -> a

-- | Provide a Semigroup for an arbitrary Monoid.
newtype WrappedMonoid m
WrapMonoid :: m -> WrappedMonoid m
unwrapMonoid :: WrappedMonoid m -> m

-- | The class of monoids (types with an associative binary operation that
--   has an identity). Instances should satisfy the following laws:
--   
--   <ul>
--   <li><pre>mappend mempty x = x</pre></li>
--   <li><pre>mappend x mempty = x</pre></li>
--   <li><pre>mappend x (mappend y z) = mappend (mappend x y) z</pre></li>
--   <li><pre>mconcat = <a>foldr</a> mappend mempty</pre></li>
--   </ul>
--   
--   The method names refer to the monoid of lists under concatenation, but
--   there are many other instances.
--   
--   Minimal complete definition: <a>mempty</a> and <a>mappend</a>.
--   
--   Some types can be viewed as a monoid in more than one way, e.g. both
--   addition and multiplication on numbers. In such cases we often define
--   <tt>newtype</tt>s and make those instances of <a>Monoid</a>, e.g.
--   <a>Sum</a> and <a>Product</a>.
class Monoid a
mempty :: Monoid a => a
mappend :: Monoid a => a -> a -> a
mconcat :: Monoid a => [a] -> a

-- | The dual of a monoid, obtained by swapping the arguments of
--   <a>mappend</a>.
newtype Dual a :: * -> *
Dual :: a -> Dual a
getDual :: Dual a -> a

-- | The monoid of endomorphisms under composition.
newtype Endo a :: * -> *
Endo :: (a -> a) -> Endo a
appEndo :: Endo a -> a -> a

-- | Boolean monoid under conjunction.
newtype All :: *
All :: Bool -> All
getAll :: All -> Bool

-- | Boolean monoid under disjunction.
newtype Any :: *
Any :: Bool -> Any
getAny :: Any -> Bool

-- | Monoid under addition.
newtype Sum a :: * -> *
Sum :: a -> Sum a
getSum :: Sum a -> a

-- | Monoid under multiplication.
newtype Product a :: * -> *
Product :: a -> Product a
getProduct :: Product a -> a

-- | Option is effectively <a>Maybe</a> with a better instance of
--   <a>Monoid</a>, built off of an underlying <a>Semigroup</a> instead of
--   an underlying <a>Monoid</a>. Ideally, this type would not exist at all
--   and we would just fix the <a>Monoid</a> intance of <a>Maybe</a>
newtype Option a
Option :: Maybe a -> Option a
getOption :: Option a -> Maybe a
option :: b -> (a -> b) -> Option a -> b

-- | This lets you use a difference list of a Semigroup as a Monoid.
diff :: Semigroup m => m -> Endo m

-- | A generalization of <a>cycle</a> to an arbitrary <a>Semigroup</a>. May
--   fail to terminate for some values in some semigroups.
cycle1 :: Semigroup m => m -> m
instance Typeable1 Min
instance Typeable1 Max
instance Typeable1 First
instance Typeable1 Last
instance Typeable1 WrappedMonoid
instance Typeable1 Option
instance Eq a => Eq (Min a)
instance Ord a => Ord (Min a)
instance Bounded a => Bounded (Min a)
instance Show a => Show (Min a)
instance Read a => Read (Min a)
instance Data a => Data (Min a)
instance Eq a => Eq (Max a)
instance Ord a => Ord (Max a)
instance Bounded a => Bounded (Max a)
instance Show a => Show (Max a)
instance Read a => Read (Max a)
instance Data a => Data (Max a)
instance Eq a => Eq (First a)
instance Ord a => Ord (First a)
instance Bounded a => Bounded (First a)
instance Show a => Show (First a)
instance Read a => Read (First a)
instance Data a => Data (First a)
instance Eq a => Eq (Last a)
instance Ord a => Ord (Last a)
instance Bounded a => Bounded (Last a)
instance Show a => Show (Last a)
instance Read a => Read (Last a)
instance Data a => Data (Last a)
instance Eq m => Eq (WrappedMonoid m)
instance Ord m => Ord (WrappedMonoid m)
instance Bounded m => Bounded (WrappedMonoid m)
instance Show m => Show (WrappedMonoid m)
instance Read m => Read (WrappedMonoid m)
instance Data m => Data (WrappedMonoid m)
instance Eq a => Eq (Option a)
instance Ord a => Ord (Option a)
instance Show a => Show (Option a)
instance Read a => Read (Option a)
instance Data a => Data (Option a)
instance Ord k => Semigroup (Map k v)
instance Semigroup (IntMap v)
instance Ord a => Semigroup (Set a)
instance Semigroup IntSet
instance Semigroup (Seq a)
instance Semigroup a => Monoid (Option a)
instance Semigroup a => Semigroup (Option a)
instance Traversable Option
instance Foldable Option
instance MonadFix Option
instance MonadPlus Option
instance Alternative Option
instance Monad Option
instance Applicative Option
instance Functor Option
instance Monoid m => Monoid (WrappedMonoid m)
instance Monoid m => Semigroup (WrappedMonoid m)
instance Semigroup (Last a)
instance Semigroup (First a)
instance (Ord a, Bounded a) => Monoid (Max a)
instance Ord a => Semigroup (Max a)
instance (Ord a, Bounded a) => Monoid (Min a)
instance Ord a => Semigroup (Min a)
instance Semigroup (NonEmpty a)
instance Semigroup (Last a)
instance Semigroup (First a)
instance Num a => Semigroup (Product a)
instance Num a => Semigroup (Sum a)
instance Semigroup Any
instance Semigroup All
instance Semigroup (Endo a)
instance Semigroup a => Semigroup (Dual a)
instance Semigroup Ordering
instance (Semigroup a, Semigroup b, Semigroup c, Semigroup d, Semigroup e) => Semigroup (a, b, c, d, e)
instance (Semigroup a, Semigroup b, Semigroup c, Semigroup d) => Semigroup (a, b, c, d)
instance (Semigroup a, Semigroup b, Semigroup c) => Semigroup (a, b, c)
instance (Semigroup a, Semigroup b) => Semigroup (a, b)
instance Semigroup (Either a b)
instance Semigroup a => Semigroup (Maybe a)
instance Semigroup [a]
instance Semigroup b => Semigroup (a -> b)
instance Semigroup ()
