semigroups 0.9.2 → 0.20.1
raw patch · 8 files changed
Files
- .travis.yml +0/−8
- CHANGELOG.markdown +189/−0
- LICENSE +1/−5
- README.markdown +4/−3
- semigroups.cabal +23/−28
- src/Data/List/NonEmpty.hs +0/−506
- src/Data/Semigroup.hs +0/−374
- src/Data/Semigroup/Generic.hs +115/−0
− .travis.yml
@@ -1,8 +0,0 @@-language: haskell-notifications:- irc:- channels:- - "irc.freenode.org#haskell-lens"- skip_join: true- template:- - "\x0313semigroups\x03/\x0306%{branch}\x03 \x0314%{commit}\x03 %{build_url} %{message}"
+ CHANGELOG.markdown view
@@ -0,0 +1,189 @@+0.20.1 [2026.01.10]+-------------------+* Drop support for pre-8.0 versions of GHC.++0.20 [2021.11.15]+-----------------+* Support `hashable-1.4`. The `Hashable1` instances added in 0.19.2+ are removed for all types except `NonEmpty`, in accordance with the+ corresponding changes from `hashable-1.4`.++0.19.2 [2021.08.30]+-------------------+* Backport `Hashable1` instances for `NonEmpty`, `Min`, `Max`, `First`, `Last`,+ `WrappedMonoid`, and `Option`.++0.19.1 [2019.08.27]+-------------------+* Add `GenericSemigroupMonoid`, an adapter newtype suitable for `DerivingVia`,+ to `Data.Semigroup.Generic`.+* Work around a bug related to the backported `Generic(1)` instances in this+ package (that could only be triggered on GHC 7.2 or 7.4) in which the+ hand-written `Datatype`, `Constructor`, and `Selector` instances for internal+ data types could overlap with GHC-generated instances.++0.19 [2019.05.10]+-----------------+* The `(<>)` method of the backported `Semigroup` class no longer has a default+ implementation in terms of `mappend`. This mirrors the `Data.Semigroup` API+ that was introduced in `base-4.9`. This is a breaking change for any+ `Semigroup` instances that are defined in tandem with versions of `base`+ older than 4.9.+* Make the backported `Hashable Arg` instance reflect its respective variants+ in the `hashable` package. In `hashable-1.3`, the `Hashable Arg` instance+ only hashes the first argument, lest equal values have different hashes.+* Backport the `Lift (NonEmpty a)` instance introduced in+ `template-haskell-2.15.0.0`.+* `Data.List.NonEmpty` is now unconditionally `Trustworthy`.++0.18.5 [2018.07.02]+-------------------+* Use a more efficient `sconcat` for the `Semigroup` instances for strict and+ lazy `ByteString`.++0.18.4 [2018.01.29]+-------------------+* Backport `Semigroup` instances for `Data.Ord.Down` and strict `ST`, which were+ added in `base-4.11`.++0.18.3+------+* Add `Semigroup` instance for `IO`, as well as for `Event` and `Lifetime` from+ `GHC.Event`+* Add `Eq1`, `Ord1`, `Read1`, and `Show1` instances for `NonEmpty`+* Define `Generic` and `Generic1` instances back to GHC 7.2, and expose the+ `Data.Semigroup.Generic` module on GHC 7.2++0.18.2+------+* Depend on the `bytestring-builder` package to ensure `Semigroup` instances for bytestring `Builder` and `ShortByteString` are always defined+* Allow building with `binary-0.8.3` and later++0.18.1+------+* Add the missing instance for `Data.Binary.Builder.Builder`.++0.18.0.1+--------+* Added support for `base-4.9`++0.18+--------+* Removed the partial functions `words`, `unwords`, `lines`, `unlines`++0.17.0.1+--------+* Fixed the `@since` annotations++0.17+----+* Added `groupWith`, `groupAllWith`, `groupWith1`, `groupAllWith1`+* Renamed `sortOn` to `sortWith` to match the "Comprehensive comprehensions" paper and `TransformListComp` extension.+* Add `Semigroup` instances for `Alt`, `Void`, `Proxy` and `Tagged`+* Add `Num` instances for `Min` and `Max`+* Removed `times1p` in favor of `stimes`.++0.16.2.2+--------+* Cleaned up imports to remove warnings on GHC 7.10.++0.16.2.1+--------+* Restored the ability to build on GHC < 7.6. (`Generic1` deriving was only added in GHC 7.6)++0.16.2+------+* Added `genericMappend` and supporting `GSemigroup` class for generically deriving Semigroup instances.+* Added `Arg a b` which only compares for equality/order on its first argument, which can be used to compute `argmin` and `argmax`.+* Add `Bifunctor` `Arg` instance to avoid orphans for GHC 7.10+.+* Added missing `Data.Monoid.Generic` module to source control.++0.16.1+------+* Added `Semigroup` instances for various Builder constructions in `text` and `bytestring` where available.+* Added `MonadFix` and `MonadPlus` instances for `NonEmpty`.++0.16.0.1+--------+* Bumped `deepseq` version bound for GHC 7.10 compatibility.++0.16+----+* `times1p` and `timesN` are now reduced to accepting only a `Natural` argument. `Whole` doesn't exist in GHC 7.10's Numeric.Natural, and `nats` version 1 has removed support for the class.++0.15.4+------+* Use `Data.Coerce.coerce` on GHC 7.8+ to reduce the number of eta-expansions in the resulting core.+* Avoid conflict with pending `Foldable.length` in base.++0.15.3+------+* `instance NFData a => NFData (NonEmpty a)`+* Added `NFData` instances for the types in Data.Semigroup++0.15.2+------+* Fixed a Trustworthiness problem for GHC 7.8+++0.15.1+------+* Nathan van Doorn fixed a number of embarrassing bugs in the `Enum` instances.++0.15+----+* `instance IsList NonEmpty`++0.14+----+* Allow for manual removal of dependencies to support advanced sandbox users who explicitly want to avoid compiling certain dependencies+ they know they aren't using.++ We will fix bugs caused by any combination of these package flags, but the API of the package should be considered the default build+ configuration with all of the package dependency flags enabled.++* Will now build as full-fledged `Safe` Haskell if you configure with -f-hashable.++* Added some missing `Generic`/`Generic`/`Hashable` instances++0.13.0.1+--------+* `Generic` support requires `ghc-prim` on GHC 7.4.++0.13+----+* Added instances for 'Generic', 'Foldable', 'Traversable', 'Enum', 'Functor', 'Hashable', 'Applicative', 'Monad' and 'MonadFix'++0.12.2+------+* Vastly widened the dependency bound on `text` and `bytestring`.++0.12.1+-------+* Updated to support the new version of `text`.+* Added `transpose`, `sortBy` and `sortWith`.++0.12+----+* Added an instance for `Const r`.+* Added `some1`++0.11+----+* Added the missing instance for `HashSet`.++0.10+----+* Added support for `unordered-containers`, `bytestring` and `text`.++0.9.2+-----+* Added a `DefaultSignature` for `(<>)` in terms of `mappend`.+++0.9.1+-----+* Added `timesN`.++0.9+---+* Moved `Numeric.Natural` to a separate `nats` package.
LICENSE view
@@ -1,4 +1,4 @@-Copyright 2011 Edward Kmett+Copyright 2011-2015 Edward Kmett All rights reserved. @@ -12,10 +12,6 @@ 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.--3. Neither the name of the author nor the names of his contributors- may be used to endorse or promote products derived from this software- without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
README.markdown view
@@ -1,12 +1,13 @@ semigroups ========== -[](http://travis-ci.org/ekmett/semigroups)+[](https://hackage.haskell.org/package/semigroups) [](https://github.com/ekmett/semigroups/actions?query=workflow%3AHaskell-CI) +Haskellers are usually familiar with monoids. A monoid has an appending operation `<>` or `mappend` and an identity element `mempty`. A Semigroup has an append `<>`, but does not require an `mempty` element. A Monoid can be made a Semigroup with just `instance Semigroup MyMonoid` -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.+More formally, 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. -Semigroups appear all over the place, except in the Haskell Prelude, so they are packaged here.+`Data.Semigroup` and `Data.List.NonEmpty` were added to `base` as of 4.9.0.0. This package now offers some tools for deriving semigroups with generics. Contact Information -------------------
semigroups.cabal view
@@ -1,6 +1,6 @@ name: semigroups category: Algebra, Data, Data Structures, Math-version: 0.9.2+version: 0.20.1 license: BSD3 cabal-version: >= 1.10 license-file: LICENSE@@ -9,42 +9,37 @@ stability: provisional homepage: http://github.com/ekmett/semigroups/ bug-reports: http://github.com/ekmett/semigroups/issues-copyright: Copyright (C) 2011 Edward A. Kmett-synopsis: Haskell 98 semigroups+copyright: Copyright (C) 2011-2015 Edward A. Kmett+synopsis: Anything that associates description:- 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. build-type: Simple-extra-source-files: .travis.yml README.markdown+extra-source-files: README.markdown CHANGELOG.markdown+tested-with:+ GHC == 9.14.1+ GHC == 9.12.2+ GHC == 9.10.3+ GHC == 9.8.4+ GHC == 9.6.7+ GHC == 9.4.8+ GHC == 9.2.8+ GHC == 9.0.2+ GHC == 8.10.7+ GHC == 8.8.4+ GHC == 8.6.5+ GHC == 8.4.4+ GHC == 8.2.2+ GHC == 8.0.2 source-repository head type: git- location: git://github.com/ekmett/semigroups.git--flag base2- default: False- manual: False+ location: https://github.com/ekmett/semigroups.git library default-language: Haskell98- other-extensions: CPP-- if !impl(hugs)- other-extensions: DeriveDataTypeable- cpp-options: -DLANGUAGE_DeriveDataTypeable-- if flag(base2)- build-depends: base == 2.*- else- build-depends:- base >= 3 && < 5,- containers >= 0.3 && < 0.6,- nats >= 0.1- hs-source-dirs: src- ghc-options: -Wall+ ghc-options: -Wall + build-depends: base >= 4.9 && < 5 exposed-modules:- Data.Semigroup- Data.List.NonEmpty+ Data.Semigroup.Generic
− src/Data/List/NonEmpty.hs
@@ -1,506 +0,0 @@-{-# LANGUAGE CPP #-}-#ifdef LANGUAGE_DeriveDataTypeable-{-# LANGUAGE DeriveDataTypeable #-}-#endif--------------------------------------------------------------------------------- |--- Module : Data.List.NonEmpty--- Copyright : (C) 2011 Edward Kmett,--- (C) 2010 Tony Morris, Oliver Taylor, Eelis van der Weegen--- License : BSD-style (see the file LICENSE)------ Maintainer : Edward Kmett <ekmett@gmail.com>--- Stability : provisional--- Portability : portable------ A NonEmpty list forms a monad as per list, but always contains at least--- one element.-------------------------------------------------------------------------------module Data.List.NonEmpty (- -- * The type of non-empty streams- NonEmpty(..)- -- * Non-empty stream transformations- , map -- :: (a -> b) -> NonEmpty a -> NonEmpty b- , intersperse -- :: a -> NonEmpty a -> NonEmpty a- , scanl -- :: Foldable f => (b -> a -> b) -> b -> f a -> NonEmpty b- , scanr -- :: Foldable f => (a -> b -> b) -> b -> f a -> NonEmpty b- , scanl1 -- :: (a -> a -> a) -> NonEmpty a -> NonEmpty a- , scanr1 -- :: (a -> a -> a) -> NonEmpty a -> NonEmpty a- --, transpose -- :: NonEmpty (NonEmpty a) -> NonEmpty (NonEmpty a)- -- * Basic functions- , head -- :: NonEmpty a -> a- , tail -- :: NonEmpty a -> [a]- , last -- :: NonEmpty a -> a- , init -- :: NonEmpty a -> [a]- , (<|), cons -- :: a -> NonEmpty a -> NonEmpty a- , uncons -- :: NonEmpty a -> (a, Maybe (NonEmpty a))- , sort -- :: NonEmpty a -> NonEmpty a- , reverse -- :: NonEmpty a -> NonEmpty a- , inits -- :: Foldable f => f a -> NonEmpty a- , tails -- :: Foldable f => f a -> NonEmpty a- -- * Building streams- , iterate -- :: (a -> a) -> a -> NonEmpty a- , repeat -- :: a -> NonEmpty a- , cycle -- :: NonEmpty a -> NonEmpty a- , unfold -- :: (a -> (b, Maybe a) -> a -> NonEmpty b- , insert -- :: (Foldable f, Ord a) => a -> f a -> NonEmpty a- -- * Extracting sublists- , take -- :: Int -> NonEmpty a -> [a]- , drop -- :: Int -> NonEmpty a -> [a]- , splitAt -- :: Int -> NonEmpty a -> ([a], [a])- , takeWhile -- :: Int -> NonEmpty a -> [a]- , dropWhile -- :: Int -> NonEmpty a -> [a]- , span -- :: Int -> NonEmpty a -> ([a],[a])- , break -- :: Int -> NonEmpty a -> ([a],[a])- , filter -- :: (a -> Bool) -> NonEmpty a -> [a]- , partition -- :: (a -> Bool) -> NonEmpty a -> ([a],[a])- , group -- :: Foldable f => Eq a => f a -> [NonEmpty a]- , groupBy -- :: Foldable f => (a -> a -> Bool) -> f a -> [NonEmpty a]- , group1 -- :: Eq a => NonEmpty a -> NonEmpty (NonEmpty a)- , groupBy1 -- :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty (NonEmpty a)- -- * Sublist predicates- , isPrefixOf -- :: Foldable f => f a -> NonEmpty a -> Bool- -- * Indexing streams- , (!!) -- :: NonEmpty a -> Int -> a- -- * Zipping and unzipping streams- , zip -- :: NonEmpty a -> NonEmpty b -> NonEmpty (a,b)- , zipWith -- :: (a -> b -> c) -> NonEmpty a -> NonEmpty b -> NonEmpty c- , unzip -- :: NonEmpty (a, b) -> (NonEmpty a, NonEmpty b)- -- * Functions on streams of characters- , words -- :: NonEmpty Char -> NonEmpty String- , unwords -- :: NonEmpty String -> NonEmpty Char- , lines -- :: NonEmpty Char -> NonEmpty String- , unlines -- :: NonEmpty String -> NonEmpty Char- -- * Converting to and from a list- , fromList -- :: [a] -> NonEmpty a- , toList -- :: NonEmpty a -> [a]- , nonEmpty -- :: [a] -> Maybe (NonEmpty a)- , xor -- :: NonEmpty a -> Bool- ) where---import Prelude hiding- ( head, tail, map, reverse- , scanl, scanl1, scanr, scanr1- , iterate, take, drop, takeWhile- , dropWhile, repeat, cycle, filter- , (!!), zip, unzip, zipWith, words- , unwords, lines, unlines, break, span- , splitAt, foldr, foldl, last, init- )--import Control.Applicative--- import Control.Comonad-import Control.Monad--- import Data.Functor.Alt-import Data.Foldable hiding (toList)-import qualified Data.Foldable as Foldable-import qualified Data.List as List-import Data.Monoid (mappend)-import Data.Traversable--- import Data.Semigroup hiding (Last)--- import Data.Semigroup.Foldable--- import Data.Semigroup.Traversable--#ifdef LANGUAGE_DeriveDataTypeable-import Data.Data-#endif--infixr 5 :|, <|--data NonEmpty a = a :| [a] deriving- ( Eq, Ord, Show, Read-#ifdef LANGUAGE_DeriveDataTypeable- , Data, Typeable-#endif- )--xor :: NonEmpty Bool -> Bool-xor (x :| xs) = foldr xor' x xs- where xor' True y = not y- xor' False y = y---- | 'unfold' produces a new stream by repeatedly applying the unfolding--- function to the seed value to produce an element of type @b@ and a new--- seed value. When the unfolding function returns 'Nothing' instead of--- a new seed value, the stream ends.-unfold :: (a -> (b, Maybe a)) -> a -> NonEmpty b-unfold f a = case f a of- (b, Nothing) -> b :| []- (b, Just c) -> b <| unfold f c---- | 'nonEmpty' efficiently turns a normal list into a 'NonEmpty' stream,--- producing 'Nothing' if the input is empty.-nonEmpty :: [a] -> Maybe (NonEmpty a)-nonEmpty [] = Nothing-nonEmpty (a:as) = Just (a :| as)-{-# INLINE nonEmpty #-}---- | 'uncons' produces the first element of the stream, and a stream of the--- remaining elements, if any.-uncons :: NonEmpty a -> (a, Maybe (NonEmpty a))-uncons ~(a :| as) = (a, nonEmpty as)-{-# INLINE uncons #-}--instance Functor NonEmpty where- fmap f ~(a :| as) = f a :| fmap f as-#if MIN_VERSION_base(4,2,0)- b <$ ~(_ :| as) = b :| (b <$ as)-#endif--{--instance Extend NonEmpty where- extend f w@ ~(_ :| aas) = f w :| case aas of- [] -> []- (a:as) -> toList (extend f (a :| as))--instance Comonad NonEmpty where- extract ~(a :| _) = a--instance Apply NonEmpty where- (<.>) = ap--instance Alt NonEmpty where- (a :| as) <!> ~(b :| bs) = a :| (as ++ b : bs)--}--instance Applicative NonEmpty where- pure a = a :| []- (<*>) = ap--instance Monad NonEmpty where- return a = a :| []- ~(a :| as) >>= f = b :| (bs ++ bs')- where b :| bs = f a- bs' = as >>= toList . f--instance Traversable NonEmpty where- traverse f ~(a :| as) = (:|) <$> f a <*> traverse f as--{--instance Traversable1 NonEmpty where- traverse1 f (a :| []) = (:|[]) <$> f a- traverse1 f (a :| (b: bs)) = (\a' (b':| bs') -> a' :| b': bs') <$> f a <.> traverse1 f (b :| bs)--}--instance Foldable NonEmpty where- foldr f z ~(a :| as) = f a (foldr f z as)- foldl f z ~(a :| as) = foldl f (f z a) as- foldl1 f ~(a :| as) = foldl f a as- foldMap f ~(a :| as) = f a `mappend` foldMap f as- fold ~(m :| ms) = m `mappend` fold ms--{--instance Foldable1 NonEmpty where- foldMap1 f (a :| []) = f a- foldMap1 f (a :| b : bs) = f a <> foldMap1 f (b :| bs)--instance Semigroup (NonEmpty a) where- (<>) = (<!>)--}---- | Extract the first element of the stream.-head :: NonEmpty a -> a-head ~(a :| _) = a-{-# INLINE head #-}---- | Extract the possibly-empty tail of the stream.-tail :: NonEmpty a -> [a]-tail ~(_ :| as) = as-{-# INLINE tail #-}---- | Extract the last element of the stream.-last :: NonEmpty a -> a-last ~(a :| as) = List.last (a : as)-{-# INLINE last #-}---- | Extract everything except the last element of the stream.-init :: NonEmpty a -> [a]-init ~(a :| as) = List.init (a : as)-{-# INLINE init #-}---- | Prepend an element to the stream.-(<|) :: a -> NonEmpty a -> NonEmpty a-a <| ~(b :| bs) = a :| b : bs-{-# INLINE (<|) #-}---- | Synonym for '<|'.-cons :: a -> NonEmpty a -> NonEmpty a-cons = (<|)-{-# INLINE cons #-}---- | Sort a stream.-sort :: Ord a => NonEmpty a -> NonEmpty a-sort = lift List.sort-{-# INLINE sort #-}---- | Converts a normal list to a 'NonEmpty' stream.------ Raises an error if given an empty list.-fromList :: [a] -> NonEmpty a-fromList (a:as) = a :| as-fromList [] = error "NonEmpty.fromList: empty list"-{-# INLINE fromList #-}---- | Convert a stream to a normal list efficiently.-toList :: NonEmpty a -> [a]-toList ~(a :| as) = a : as-{-# INLINE toList #-}---- | Lift list operations to work on a 'NonEmpty' stream.------ /Beware/: If the provided function returns an empty list,--- this will raise an error.-lift :: Foldable f => ([a] -> [b]) -> f a -> NonEmpty b-lift f = fromList . f . Foldable.toList-{-# INLINE lift #-}---- | Map a function over a 'NonEmpty' stream.-map :: (a -> b) -> NonEmpty a -> NonEmpty b-map f ~(a :| as) = f a :| fmap f as-{-# INLINE map #-}---- | The 'inits' function takes a stream @xs@ and returns all the--- finite prefixes of @xs@.-inits :: Foldable f => f a -> NonEmpty [a]-inits = fromList . List.inits . Foldable.toList-{-# INLINE inits #-}---- | The 'tails' function takes a stream @xs@ and returns all the--- suffixes of @xs@.-tails :: Foldable f => f a -> NonEmpty [a]-tails = fromList . List.tails . Foldable.toList-{-# INLINE tails #-}---- | @'insert' x xs@ inserts @x@ into the last position in @xs@ 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-insert a = fromList . List.insert a . Foldable.toList-{-# INLINE insert #-}---- | 'scanl' is similar to 'foldl', but returns a stream of successive--- reduced values from the left:------ > scanl f z [x1, x2, ...] == z :| [z `f` x1, (z `f` x1) `f` x2, ...]------ Note that------ > last (scanl f z xs) == foldl f z xs.-scanl :: Foldable f => (b -> a -> b) -> b -> f a -> NonEmpty b-scanl f z = fromList . List.scanl f z . Foldable.toList-{-# INLINE scanl #-}---- | 'scanr' is the right-to-left dual of 'scanl'.--- Note that------ > head (scanr f z xs) == foldr f z xs.-scanr :: Foldable f => (a -> b -> b) -> b -> f a -> NonEmpty b-scanr f z = fromList . List.scanr f z . Foldable.toList-{-# INLINE scanr #-}---- | 'scanl1' is a variant of 'scanl' that has no starting value argument:------ > scanl1 f [x1, x2, ...] == x1 :| [x1 `f` x2, x1 `f` (x2 `f` x3), ...]-scanl1 :: (a -> a -> a) -> NonEmpty a -> NonEmpty a-scanl1 f ~(a :| as) = fromList (List.scanl f a as)-{-# INLINE scanl1 #-}---- | 'scanr1' is a variant of 'scanr' that has no starting value argument.-scanr1 :: (a -> a -> a) -> NonEmpty a -> NonEmpty a-scanr1 f ~(a :| as) = fromList (List.scanr1 f (a:as))-{-# INLINE scanr1 #-}---- | 'intersperse x xs' alternates elements of the list with copies of @x@.------ > intersperse 0 (1 :| [2,3]) == 1 :| [0,2,0,3]-intersperse :: a -> NonEmpty a -> NonEmpty a-intersperse a ~(b :| bs) = b :| case bs of- [] -> []- _ -> a : List.intersperse a bs-{-# INLINE intersperse #-}---- | @'iterate' f x@ produces the infinite sequence--- of repeated applications of @f@ to @x@.------ > iterate f x = x :| [f x, f (f x), ..]-iterate :: (a -> a) -> a -> NonEmpty a-iterate f a = a :| List.iterate f (f a)-{-# INLINE iterate #-}---- | @'cycle' xs@ returns the infinite repetition of @xs@:------ > cycle [1,2,3] = 1 :| [2,3,1,2,3,...]-cycle :: NonEmpty a -> NonEmpty a-cycle = fromList . List.cycle . toList-{-# INLINE cycle #-}---- | 'reverse' a finite NonEmpty stream.-reverse :: NonEmpty a -> NonEmpty a-reverse = lift List.reverse-{-# INLINE reverse #-}---- | @'repeat' x@ returns a constant stream, where all elements are--- equal to @x@.-repeat :: a -> NonEmpty a-repeat a = a :| List.repeat a-{-# INLINE repeat #-}---- | @'take' n xs@ returns the first @n@ elements of @xs@.-take :: Int -> NonEmpty a -> [a]-take n = List.take n . toList-{-# INLINE take #-}---- | @'drop' n xs@ drops the first @n@ elements off the front of--- the sequence @xs@.-drop :: Int -> NonEmpty a -> [a]-drop n = List.drop n . toList-{-# INLINE drop #-}---- | @'splitAt' n xs@ returns a pair consisting of the prefix of @xs@--- of length @n@ and the remaining stream immediately following this prefix.------ > 'splitAt' n xs == ('take' n xs, 'drop' n xs)--- > xs == ys ++ zs where (ys, zs) = 'splitAt' n xs-splitAt :: Int -> NonEmpty a -> ([a],[a])-splitAt n = List.splitAt n . toList-{-# INLINE splitAt #-}---- | @'takeWhile' p xs@ returns the longest prefix of the stream--- @xs@ for which the predicate @p@ holds.-takeWhile :: (a -> Bool) -> NonEmpty a -> [a]-takeWhile p = List.takeWhile p . toList-{-# INLINE takeWhile #-}---- | @'dropWhile' p xs@ returns the suffix remaining after--- @'takeWhile' p xs@.-dropWhile :: (a -> Bool) -> NonEmpty a -> [a]-dropWhile p = List.dropWhile p . toList-{-# INLINE dropWhile #-}---- | @'span' p xs@ returns the longest prefix of @xs@ that satisfies--- @p@, together with the remainder of the stream.------ > 'span' p xs == ('takeWhile' p xs, 'dropWhile' p xs)--- > xs == ys ++ zs where (ys, zs) = 'span' p xs-span :: (a -> Bool) -> NonEmpty a -> ([a], [a])-span p = List.span p . toList-{-# INLINE span #-}---- | The @'break' p@ function is equivalent to @'span' (not . p)@.-break :: (a -> Bool) -> NonEmpty a -> ([a], [a])-break p = span (not . p)-{-# INLINE break #-}---- | @'filter' p xs@ removes any elements from @xs@ that do not satisfy @p@.-filter :: (a -> Bool) -> NonEmpty a -> [a]-filter p = List.filter p . toList-{-# INLINE filter #-}---- | The 'partition' function takes a predicate @p@ and a stream--- @xs@, and returns a pair of lists. The first list corresponds to the--- elements of @xs@ for which @p@ holds; the second corresponds to the--- elements of @xs@ for which @p@ does not hold.------ > 'partition' p xs = ('filter' p xs, 'filter' (not . p) xs)-partition :: (a -> Bool) -> NonEmpty a -> ([a], [a])-partition p = List.partition p . toList-{-# INLINE partition #-}---- | The 'group' 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:------ > 'group' $ 'cycle' "Mississippi" = "M" : "i" : "ss" : "i" : "ss" : "i" : "pp" : "i" : "M" : "i" : ...-group :: (Foldable f, Eq a) => f a -> [NonEmpty a]-group = groupBy (==)-{-# INLINE group #-}---- | 'groupBy' operates like 'group', but uses the provided equality--- predicate instead of `==`.-groupBy :: Foldable f => (a -> a -> Bool) -> f a -> [NonEmpty a]-groupBy eq0 = go eq0 . Foldable.toList- where- go _ [] = []- go eq (x : xs) = (x :| ys) : groupBy eq zs- where (ys, zs) = List.span (eq x) xs---- | 'group1' operates like 'group', but uses the knowledge that its--- input is non-empty to produce guaranteed non-empty output.-group1 :: Eq a => NonEmpty a -> NonEmpty (NonEmpty a)-group1 = groupBy1 (==)-{-# INLINE group1 #-}---- | 'groupBy1' is to 'group1' as 'groupBy' is to 'group'.-groupBy1 :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty (NonEmpty a)-groupBy1 eq (x :| xs) = (x :| ys) :| groupBy eq zs- where (ys, zs) = List.span (eq x) xs-{-# INLINE groupBy1 #-}---- | The 'isPrefix' function returns @True@ if the first argument is--- a prefix of the second.-isPrefixOf :: Eq a => [a] -> NonEmpty a -> Bool-isPrefixOf [] _ = True-isPrefixOf (y:ys) (x :| xs) = (y == x) && List.isPrefixOf ys xs-{-# INLINE isPrefixOf #-}---- | @xs !! n@ returns the element of the stream @xs@ at index--- @n@. Note that the head of the stream has index 0.------ /Beware/: a negative or out-of-bounds index will cause an error.-(!!) :: NonEmpty a -> Int -> a-(!!) ~(x :| xs) n- | n == 0 = x- | n > 0 = xs List.!! (n - 1)- | otherwise = error "NonEmpty.!! negative argument"-{-# INLINE (!!) #-}---- | The 'zip' function takes two streams and returns a stream of--- corresponding pairs.-zip :: NonEmpty a -> NonEmpty b -> NonEmpty (a,b)-zip ~(x :| xs) ~(y :| ys) = (x, y) :| List.zip xs ys-{-# INLINE zip #-}---- | The 'zipWith' function generalizes 'zip'. 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-zipWith f ~(x :| xs) ~(y :| ys) = f x y :| List.zipWith f xs ys-{-# INLINE zipWith #-}---- | The 'unzip' function is the inverse of the 'zip' function.-unzip :: Functor f => f (a,b) -> (f a, f b)-unzip xs = (fst <$> xs, snd <$> xs)-{-# INLINE unzip #-}---- | The 'words' function breaks a stream of characters into a--- stream of words, which were delimited by white space.------ /Beware/: if the input contains no words (i.e. is entirely--- whitespace), this will cause an error.-words :: NonEmpty Char -> NonEmpty String-words = lift List.words-{-# INLINE words #-}---- | The 'unwords' function is an inverse operation to 'words'. It--- joins words with separating spaces.------ /Beware/: the input @(\"\" :| [])@ will cause an error.-unwords :: NonEmpty String -> NonEmpty Char-unwords = lift List.unwords-{-# INLINE unwords #-}---- | The 'lines' 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-lines = lift List.lines-{-# INLINE lines #-}---- | The 'unlines' function is an inverse operation to 'lines'. It--- joins lines, after appending a terminating newline to each.-unlines :: NonEmpty String -> NonEmpty Char-unlines = lift List.unlines-{-# INLINE unlines #-}
− src/Data/Semigroup.hs
@@ -1,374 +0,0 @@-{-# LANGUAGE CPP #-}-#ifdef LANGUAGE_DeriveDataTypeable-{-# LANGUAGE DeriveDataTypeable #-}-#endif-#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 702-{-# LANGUAGE DefaultSignatures #-}-#endif--------------------------------------------------------------------------------- |--- Module : Data.Semigroup--- Copyright : (C) 2011 Edward Kmett,--- License : BSD-style (see the file LICENSE)------ Maintainer : Edward Kmett <ekmett@gmail.com>--- Stability : provisional--- Portability : portable------ 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 @(\<\>)@ 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------ > import Data.Semigroup---------------------------------------------------------------------------------module Data.Semigroup (- Semigroup(..)- -- * Semigroups- , Min(..)- , Max(..)- , First(..)- , Last(..)- , WrappedMonoid(..)- , timesN- -- * Re-exported monoids from Data.Monoid- , Monoid(..)- , Dual(..)- , Endo(..)- , All(..)- , Any(..)- , Sum(..)- , Product(..)- -- * A better monoid for Maybe- , Option(..)- , option- -- * Difference lists of a semigroup- , diff- , cycle1- ) where--import Prelude hiding (foldr1)-import Data.Monoid (Monoid(..),Dual(..),Endo(..),All(..),Any(..),Sum(..),Product(..),Endo(..))-import Control.Applicative-import Control.Monad-import Control.Monad.Fix-import qualified Data.Monoid as Monoid-import Data.Foldable-import Data.Traversable-import Data.List.NonEmpty--import Numeric.Natural.Internal-import Data.Sequence (Seq, (><))-import Data.Set (Set)-import Data.IntSet (IntSet)-import Data.Map (Map)-import Data.IntMap (IntMap)--#ifdef LANGUAGE_DeriveDataTypeable-import Data.Data-#endif--infixr 6 <>--class Semigroup a where- -- | An associative operation.- --- -- > (a <> b) <> c = a <> (b <> c)- --- -- If @a@ is also a 'Monoid' we further require- --- -- > (<>) = mappend- (<>) :: a -> a -> a-#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 702- default (<>) :: Monoid a => a -> a -> a- (<>) = mappend-#endif-- -- | Reduce a non-empty list with @\<\>@- --- -- The default definition should be sufficient, but this can be overridden for efficiency.- --- sconcat :: NonEmpty a -> a- sconcat (a :| as) = go a as where- go b (c:cs) = b <> go c cs- go b [] = b-- -- | Repeat a value (n + 1) times.- --- -- > times1p n a = a <> a <> ... <> a -- using <> n times- --- -- The default definition uses peasant multiplication, exploiting associativity to only- -- require /O(log n)/ uses of @\<\>@.- --- -- See also 'times'.-- times1p :: Whole n => n -> a -> a- times1p y0 x0 = f x0 (1 Prelude.+ 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)- {-# INLINE times1p #-}---- | A generalization of 'Data.List.cycle' to an arbitrary 'Semigroup'.--- May fail to terminate for some values in some semigroups.-cycle1 :: Semigroup m => m -> m-cycle1 xs = xs' where xs' = xs <> xs'--instance Semigroup () where- _ <> _ = ()- sconcat _ = ()- times1p _ _ = ()--instance Semigroup b => Semigroup (a -> b) where- f <> g = \a -> f a <> g a- times1p n f e = times1p n (f e)--instance Semigroup [a] where- (<>) = (++)- times1p n x = rep n where- rep 0 = x- rep i = x ++ rep (i - 1)--instance Semigroup a => Semigroup (Maybe a) where- Nothing <> b = b- a <> Nothing = a- Just a <> Just b = Just (a <> b)--instance Semigroup (Either a b) where- Left _ <> b = b- a <> _ = a--instance (Semigroup a, Semigroup b) => Semigroup (a, b) where- (a,b) <> (a',b') = (a<>a',b<>b')- times1p n (a,b) = (times1p n a, times1p n b)--instance (Semigroup a, Semigroup b, Semigroup c) => Semigroup (a, b, c) where- (a,b,c) <> (a',b',c') = (a<>a',b<>b',c<>c')- times1p n (a,b,c) = (times1p n a, times1p n b, times1p n c)--instance (Semigroup a, Semigroup b, Semigroup c, Semigroup d) => Semigroup (a, b, c, d) where- (a,b,c,d) <> (a',b',c',d') = (a<>a',b<>b',c<>c',d<>d')- times1p n (a,b,c,d) = (times1p n a, times1p n b, times1p n c, times1p n d)--instance (Semigroup a, Semigroup b, Semigroup c, Semigroup d, Semigroup e) => Semigroup (a, b, c, d, e) where- (a,b,c,d,e) <> (a',b',c',d',e') = (a<>a',b<>b',c<>c',d<>d',e<>e')- times1p n (a,b,c,d,e) = (times1p n a, times1p n b, times1p n c, times1p n d, times1p n e)--instance Semigroup Ordering where- LT <> _ = LT- EQ <> y = y- GT <> _ = GT--instance Semigroup a => Semigroup (Dual a) where- Dual a <> Dual b = Dual (b <> a)- times1p n (Dual a) = Dual (times1p n a)--instance Semigroup (Endo a) where- Endo f <> Endo g = Endo (f . g)--instance Semigroup All where- All a <> All b = All (a && b)- times1p _ a = a--instance Semigroup Any where- Any a <> Any b = Any (a || b)- times1p _ a = a--instance Num a => Semigroup (Sum a) where- Sum a <> Sum b = Sum (a + b)--instance Num a => Semigroup (Product a) where- Product a <> Product b = Product (a * b)--#if MIN_VERSION_base(3,0,0)-instance Semigroup (Monoid.First a) where- Monoid.First Nothing <> b = b- a <> _ = a- times1p _ a = a--instance Semigroup (Monoid.Last a) where- a <> Monoid.Last Nothing = a- _ <> b = b- times1p _ a = a-#endif--instance Semigroup (NonEmpty a) where- (a :| as) <> ~(b :| bs) = a :| (as ++ b : bs)--newtype Min a = Min { getMin :: a } deriving- ( Eq, Ord, Bounded, Show, Read-#ifdef LANGUAGE_DeriveDataTypeable- , Data, Typeable-#endif- )--instance Ord a => Semigroup (Min a) where- Min a <> Min b = Min (a `min` b)- times1p _ a = a--instance (Ord a, Bounded a) => Monoid (Min a) where- mempty = maxBound- mappend = (<>)--newtype Max a = Max { getMax :: a } deriving- ( Eq, Ord, Bounded, Show, Read-#ifdef LANGUAGE_DeriveDataTypeable- , Data, Typeable-#endif- )--instance Ord a => Semigroup (Max a) where- Max a <> Max b = Max (a `max` b)- times1p _ a = a--instance (Ord a, Bounded a) => Monoid (Max a) where- mempty = minBound- mappend = (<>)---- | Use @'Option' ('First' a)@ -- to get the behavior of 'Data.Monoid.First'-newtype First a = First { getFirst :: a } deriving- ( Eq, Ord, Bounded, Show, Read-#ifdef LANGUAGE_DeriveDataTypeable- , Data- , Typeable-#endif- )--instance Semigroup (First a) where- a <> _ = a- times1p _ a = a---- | Use @'Option' ('Last' a)@ -- to get the behavior of 'Data.Monoid.Last'-newtype Last a = Last { getLast :: a } deriving- ( Eq, Ord, Bounded, Show, Read-#ifdef LANGUAGE_DeriveDataTypeable- , Data, Typeable-#endif- )--instance Semigroup (Last a) where- _ <> b = b- times1p _ a = a---- (==)/XNOR on Bool forms a 'Semigroup', but has no good name----- | Provide a Semigroup for an arbitrary Monoid.-newtype WrappedMonoid m = WrapMonoid- { unwrapMonoid :: m } deriving- ( Eq, Ord, Bounded, Show, Read-#ifdef LANGUAGE_DeriveDataTypeable- , Data, Typeable-#endif- )--instance Monoid m => Semigroup (WrappedMonoid m) where- WrapMonoid a <> WrapMonoid b = WrapMonoid (a `mappend` b)--instance Monoid m => Monoid (WrappedMonoid m) where- mempty = WrapMonoid mempty- WrapMonoid a `mappend` WrapMonoid b = WrapMonoid (a `mappend` b)---- | Repeat a value @n@ times.------ > times n a = a <> a <> ... <> a -- using <> (n-1) times------ Implemented using 'times1p'.-timesN :: (Whole n, Monoid a) => n -> a -> a-timesN n x | n == 0 = mempty- | otherwise = unwrapMonoid . times1p (unsafePred n) . WrapMonoid $ x-{-# INLINE timesN #-}----- | Option is effectively 'Maybe' with a better instance of 'Monoid', built off of an underlying 'Semigroup'--- instead of an underlying 'Monoid'. Ideally, this type would not exist at all and we would just fix the 'Monoid' intance of 'Maybe'-newtype Option a = Option- { getOption :: Maybe a } deriving- ( Eq, Ord, Show, Read-#ifdef LANGUAGE_DeriveDataTypeable- , Data, Typeable-#endif- )--instance Functor Option where- fmap f (Option a) = Option (fmap f a)--instance Applicative Option where- pure a = Option (Just a)- Option a <*> Option b = Option (a <*> b)--instance Monad Option where- return = pure-- Option (Just a) >>= k = k a- _ >>= _ = Option Nothing-- Option Nothing >> _ = Option Nothing- _ >> b = b--instance Alternative Option where- empty = Option Nothing- Option Nothing <|> b = b- a <|> _ = a--instance MonadPlus Option where- mzero = empty- mplus = (<|>)--instance MonadFix Option where- mfix f = Option (mfix (getOption . f))--instance Foldable Option where- foldMap f (Option (Just m)) = f m- foldMap _ (Option Nothing) = mempty--instance Traversable Option where- traverse f (Option (Just a)) = Option . Just <$> f a- traverse _ (Option Nothing) = pure (Option Nothing)--option :: b -> (a -> b) -> Option a -> b-option n j (Option m) = maybe n j m--instance Semigroup a => Semigroup (Option a) where- Option a <> Option b = Option (a <> b)--instance Semigroup a => Monoid (Option a) where- mempty = empty- Option a `mappend` Option b = Option (a <> b)---- | This lets you use a difference list of a Semigroup as a Monoid.-diff :: Semigroup m => m -> Endo m-diff = Endo . (<>)--instance Semigroup (Seq a) where- (<>) = (><)--instance Semigroup IntSet where- (<>) = mappend- times1p _ a = a--instance Ord a => Semigroup (Set a) where- (<>) = mappend- times1p _ a = a--instance Semigroup (IntMap v) where- (<>) = mappend- times1p _ a = a--instance Ord k => Semigroup (Map k v) where- (<>) = mappend- times1p _ a = a
+ src/Data/Semigroup/Generic.hs view
@@ -0,0 +1,115 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE Safe #-}+{-# LANGUAGE TypeOperators #-}+{-# LANGUAGE UndecidableInstances #-}+-----------------------------------------------------------------------------+-- |+-- Module : Data.Semigroup.Generic+-- Copyright : (C) 2014-2015 Edward Kmett, Eric Mertens+-- License : BSD-style (see the file LICENSE)+--+-- Maintainer : Edward Kmett <ekmett@gmail.com>+-- Stability : provisional+-- Portability : portable+--+-- This module provides generic deriving tools for monoids and semigroups for+-- product-like structures.+--+----------------------------------------------------------------------------+module Data.Semigroup.Generic+ ( -- * Generic method implementations+ gmappend, gmempty++ -- * Adapter newtype+ , GenericSemigroupMonoid(..)++ -- * Internal classes+ , GSemigroup, GMonoid+ ) where++#if !(MIN_VERSION_base(4,11,0))+import Data.Semigroup (Semigroup(..))+#endif+import GHC.Generics++-- | Generically generate a 'Semigroup' ('<>') operation for any type+-- implementing 'Generic'. This operation will append two values+-- by point-wise appending their component fields. It is only defined+-- for product types.+--+-- @+-- 'gmappend' a ('gmappend' b c) = 'gmappend' ('gmappend' a b) c+-- @+gmappend :: (Generic a, GSemigroup (Rep a)) => a -> a -> a+gmappend x y = to (gmappend' (from x) (from y))++class GSemigroup f where+ gmappend' :: f p -> f p -> f p++instance GSemigroup U1 where+ gmappend' _ _ = U1++instance GSemigroup V1 where+ gmappend' x y = x `seq` y `seq` error "GSemigroup.V1: gmappend'"++instance Semigroup a => GSemigroup (K1 i a) where+ gmappend' (K1 x) (K1 y) = K1 (x <> y)++instance GSemigroup f => GSemigroup (M1 i c f) where+ gmappend' (M1 x) (M1 y) = M1 (gmappend' x y)++instance (GSemigroup f, GSemigroup g) => GSemigroup (f :*: g) where+ gmappend' (x1 :*: x2) (y1 :*: y2) = gmappend' x1 y1 :*: gmappend' x2 y2++-- | Generically generate a 'Monoid' 'mempty' for any product-like type+-- implementing 'Generic'.+--+-- It is only defined for product types.+--+-- @+-- 'gmappend' 'gmempty' a = a = 'gmappend' a 'gmempty'+-- @++gmempty :: (Generic a, GMonoid (Rep a)) => a+gmempty = to gmempty'++class GSemigroup f => GMonoid f where+ gmempty' :: f p++instance GMonoid U1 where+ gmempty' = U1++instance (Semigroup a, Monoid a) => GMonoid (K1 i a) where+ gmempty' = K1 mempty++instance GMonoid f => GMonoid (M1 i c f) where+ gmempty' = M1 gmempty'++instance (GMonoid f, GMonoid g) => GMonoid (f :*: g) where+ gmempty' = gmempty' :*: gmempty'++-- | An adapter newtype, suitable for @DerivingVia@. Its 'Semigroup' and+-- 'Monoid' instances leverage the 'Generic'-based defaults defined by+-- 'gmappend' and 'gmempty'. Here is an example of how to use it:+--+-- @+-- {-# LANGUAGE DerivingVia #-}+-- import "Data.Semigroup.Generic"+--+-- data Pair a = MkPair a a+-- deriving ('Semigroup', 'Monoid') via ('GenericSemigroupMonoid' (Pair a))+-- @+--+-- @since 0.19.1+newtype GenericSemigroupMonoid a =+ GenericSemigroupMonoid { getGenericSemigroupMonoid :: a }++instance (Generic a, GSemigroup (Rep a)) => Semigroup (GenericSemigroupMonoid a) where+ GenericSemigroupMonoid x <> GenericSemigroupMonoid y =+ GenericSemigroupMonoid (gmappend x y)+instance (Generic a, GMonoid (Rep a)) => Monoid (GenericSemigroupMonoid a) where+ mempty = GenericSemigroupMonoid gmempty+#if !(MIN_VERSION_base(4,11,0))+ mappend = (<>)+#endif