packages feed

semigroups 0.16.2.2 → 0.17

raw patch · 5 files changed

+231/−49 lines, 5 filesdep +tagged

Dependencies added: tagged

Files

CHANGELOG.markdown view
@@ -1,3 +1,11 @@+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.
README.markdown view
@@ -1,7 +1,7 @@ semigroups ========== -[![Build Status](https://secure.travis-ci.org/ekmett/semigroups.png?branch=master)](http://travis-ci.org/ekmett/semigroups)+[![Hackage](https://img.shields.io/hackage/v/semigroups.svg)](https://hackage.haskell.org/package/semigroups) [![Build Status](https://secure.travis-ci.org/ekmett/semigroups.png?branch=master)](http://travis-ci.org/ekmett/semigroups)  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`
semigroups.cabal view
@@ -1,6 +1,6 @@ name:          semigroups category:      Algebra, Data, Data Structures, Math-version:       0.16.2.2+version:       0.17 license:       BSD3 cabal-version: >= 1.10 license-file:  LICENSE@@ -56,6 +56,14 @@   default: True   manual: True +flag tagged+  description:+    You can disable the use of the `tagged` package using `-f-tagged`.+    .+    Disabling this is an unsupported configuration, but it may be useful for accelerating builds in sandboxes for expert users.+  default: True+  manual: True+ flag text   description:     You can disable the use of the `text` package using `-f-text`.@@ -100,6 +108,9 @@    if flag(deepseq)     build-depends: deepseq >= 1.1 && < 1.5++  if flag(tagged)+    build-depends: tagged >= 0.4.4 && < 1    if flag(text)     build-depends: text >= 0.10 && < 2
src/Data/List/NonEmpty.hs view
@@ -52,7 +52,7 @@    , scanr1      -- :: (a -> a -> a) -> NonEmpty a -> NonEmpty a    , transpose   -- :: NonEmpty (NonEmpty a) -> NonEmpty (NonEmpty a)    , sortBy      -- :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a-   , sortOn      -- :: Ord o => (a -> o) -> NonEmpty a -> NonEmpty a+   , sortWith      -- :: Ord o => (a -> o) -> NonEmpty a -> NonEmpty a    -- * Basic functions    , length      -- :: NonEmpty a -> Int    , head        -- :: NonEmpty a -> a@@ -85,8 +85,12 @@    , 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]+   , groupWith     -- :: (Foldable f, Eq b) => (a -> b) -> f a -> [NonEmpty a]+   , groupAllWith  -- :: (Foldable f, Ord b) => (a -> b) -> f a -> [NonEmpty a]    , group1      -- :: Eq a => NonEmpty a -> NonEmpty (NonEmpty a)    , groupBy1    -- :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty (NonEmpty a)+   , groupWith1     -- :: (Foldable f, Eq b) => (a -> b) -> f a -> NonEmpty (NonEmpty a)+   , groupAllWith1  -- :: (Foldable f, Ord b) => (a -> b) -> f a -> NonEmpty (NonEmpty a)    -- * Sublist predicates    , isPrefixOf  -- :: Foldable f => f a -> NonEmpty a -> Bool    -- * \"Set\" operations@@ -148,6 +152,7 @@ import Data.Traversable #endif import qualified Data.Foldable as Foldable+import Data.Function (on)  #ifdef MIN_VERSION_hashable import Data.Hashable@@ -510,6 +515,18 @@     go eq (x : xs) = (x :| ys) : groupBy eq zs       where (ys, zs) = List.span (eq x) xs +-- | 'groupWith' operates like 'group', but uses the provided projection when+-- comparing for equality+groupWith :: (Foldable f, Eq b) => (a -> b) -> f a -> [NonEmpty a]+groupWith f = groupBy ((==) `on` f)+{-# INLINE groupWith #-}++-- | 'groupAllWith' operates like 'groupWith', but sorts the list first so that each+-- equivalence class has, at most, one list in the output+groupAllWith :: (Ord b) => (a -> b) -> [a] -> [NonEmpty a]+groupAllWith f = groupWith f . List.sortBy (compare `on` f)+{-# INLINE groupAllWith #-}+ -- | '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)@@ -522,6 +539,16 @@   where (ys, zs) = List.span (eq x) xs {-# INLINE groupBy1 #-} +-- | 'groupWith1' is to 'group1' as 'groupWith' is to 'group'+groupWith1 :: (Eq b) => (a -> b) -> NonEmpty a -> NonEmpty (NonEmpty a)+groupWith1 f = groupBy1 ((==) `on` f)+{-# INLINE groupWith1 #-}++-- | 'groupAllWith1' is to 'groupWith1' as 'groupAllWith' is to 'groupWith'+groupAllWith1 :: (Ord b) => (a -> b) -> NonEmpty a -> NonEmpty (NonEmpty a)+groupAllWith1 f = groupWith1 f . sortWith f+{-# INLINE groupAllWith1 #-}+ -- | The 'isPrefix' function returns @True@ if the first argument is -- a prefix of the second. isPrefixOf :: Eq a => [a] -> NonEmpty a -> Bool@@ -614,8 +641,8 @@ sortBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a sortBy f = lift (List.sortBy f) --- | 'sortOn' for 'NonEmpty', behaves the same as:+-- | 'sortWith' for 'NonEmpty', behaves the same as: -- -- > sortBy . comparing-sortOn :: Ord o => (a -> o) -> NonEmpty a -> NonEmpty a-sortOn = sortBy . comparing+sortWith :: Ord o => (a -> o) -> NonEmpty a -> NonEmpty a+sortWith = sortBy . comparing
src/Data/Semigroup.hs view
@@ -22,6 +22,10 @@ {-# LANGUAGE FlexibleContexts #-} #endif +#if __GLASGOW_HASKELL__ >= 706+{-# LANGUAGE PolyKinds #-}+#endif+ #if __GLASGOW_HASKELL__ >= 708 #define USE_COERCE {-# LANGUAGE ScopedTypeVariables #-}@@ -58,13 +62,16 @@ ---------------------------------------------------------------------------- module Data.Semigroup (     Semigroup(..)+  , stimesMonoid+  , stimesIdempotent+  , stimesIdempotentMonoid+  , mtimesDefault   -- * Semigroups   , Min(..)   , Max(..)   , First(..)   , Last(..)   , WrappedMonoid(..)-  , timesN   -- * Re-exported monoids from Data.Monoid   , Monoid(..)   , Dual(..)@@ -89,6 +96,7 @@  #if MIN_VERSION_base(4,8,0) import Data.Bifunctor+import Data.Void #else import Data.Monoid (Monoid(..)) import Data.Foldable@@ -96,13 +104,15 @@ #endif  import Data.Monoid (Dual(..),Endo(..),All(..),Any(..),Sum(..),Product(..))+#if MIN_VERSION_base(4,8,0)+import Data.Monoid (Alt(..))+#endif  import Control.Applicative import Control.Monad import Control.Monad.Fix import qualified Data.Monoid as Monoid import Data.List.NonEmpty-import Numeric.Natural  #ifdef MIN_VERSION_deepseq import Control.DeepSeq (NFData(..))@@ -131,6 +141,14 @@ # endif #endif +#if MIN_VERSION_base(4,7,0) || defined(MIN_VERSION_tagged)+import Data.Proxy+#endif++#ifdef MIN_VERSION_tagged+import Data.Tagged+#endif+ #ifdef MIN_VERSION_text import qualified Data.Text as Strict import qualified Data.Text.Lazy as Lazy@@ -187,19 +205,19 @@     go b (c:cs) = b <> go c cs     go b []     = b -  -- | Repeat a value (n + 1) times.+  -- | Repeat a value @n@ times.   ---  -- @-  -- 'times1p' n a = a '<>' a '<>' ... '<>' a  -- using '<>' n times-  -- @+  -- Given that this works on a 'Semigroup' it is allowed to fail if you request 0 or fewer+  -- repetitions, and the default definition will do so.   ---  -- The default definition uses peasant multiplication, exploiting associativity to only-  -- require /O(log n)/ uses of @\<\>@.+  -- By making this a member of the class, idempotent semigroups and monoids can upgrade this to execute in+  -- /O(1)/ by picking @stimes = stimesIdempotent@ or @stimes = stimesIdempotentMonoid@ respectively.   ---  -- See also 'timesN'.--  times1p :: Natural -> a -> a-  times1p y0 x0 = f x0 (1 Prelude.+ y0)+  -- @since 0.18+  stimes :: Integral b => b -> a -> a+  stimes y0 x0+    | y0 <= 0   = error "stimes: positive multiplier expected"+    | otherwise = f x0 y0     where       f x y         | even y = f (x <> x) (y `quot` 2)@@ -209,7 +227,7 @@         | even y = g (x <> x) (y `quot` 2) z         | y == 1 = x <> z         | otherwise = g (x <> x) (pred y `quot` 2) (x <> z)-  {-# INLINE times1p #-}+  {-# INLINE stimes #-}  -- | A generalization of 'Data.List.cycle' to an arbitrary 'Semigroup'. -- May fail to terminate for some values in some semigroups.@@ -219,51 +237,61 @@ instance Semigroup () where   _ <> _ = ()   sconcat _ = ()-  times1p _ _ = ()+  stimes _ _ = ()  instance Semigroup b => Semigroup (a -> b) where   f <> g = \a -> f a <> g a-  times1p n f e = times1p n (f e)+  stimes n f e = stimes n (f e)  instance Semigroup [a] where   (<>) = (++)-  times1p n x = rep n where-    rep 0 = x-    rep i = x ++ rep (i - 1)+  stimes n x+    | n < 0 = error "stimes: [], negative multiplier"+    | otherwise = rep n+    where+      rep 0 = []+      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)+  stimes _ Nothing  = Nothing+  stimes n (Just a) = case compare n 0 of+    LT -> error "stimes: Maybe, negative multiplier"+    EQ -> Nothing+    GT -> Just (stimes n a)  instance Semigroup (Either a b) where   Left _ <> b = b   a      <> _ = a+  stimes = stimesIdempotent  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)+  stimes n (a,b) = (stimes n a, stimes 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)+  stimes n (a,b,c) = (stimes n a, stimes n b, stimes 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)+  stimes n (a,b,c,d) = (stimes n a, stimes n b, stimes n c, stimes 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)+  stimes n (a,b,c,d,e) = (stimes n a, stimes n b, stimes n c, stimes n d, stimes n e)  instance Semigroup Ordering where   LT <> _ = LT   EQ <> y = y   GT <> _ = GT+  stimes = stimesIdempotentMonoid  instance Semigroup a => Semigroup (Dual a) where   Dual a <> Dual b = Dual (b <> a)-  times1p n (Dual a) = Dual (times1p n a)+  stimes n (Dual a) = Dual (stimes n a)  instance Semigroup (Endo a) where #ifdef USE_COERCE@@ -271,6 +299,7 @@ #else   Endo f <> Endo g = Endo (f . g) #endif+  stimes = stimesMonoid  instance Semigroup All where #ifdef USE_COERCE@@ -278,22 +307,26 @@ #else   All a <> All b = All (a && b) #endif-  times1p _ a = a +  stimes = stimesIdempotentMonoid+ instance Semigroup Any where #ifdef USE_COERCE   (<>) = coerce (||) #else   Any a <> Any b = Any (a || b) #endif-  times1p _ a = a +  stimes = stimesIdempotentMonoid++ instance Num a => Semigroup (Sum a) where #ifdef USE_COERCE   (<>) = coerce ((+) :: a -> a -> a) #else   Sum a <> Sum b = Sum (a + b) #endif+  stimes n (Sum a) = Sum (fromIntegral n * a)  instance Num a => Semigroup (Product a) where #ifdef USE_COERCE@@ -301,26 +334,84 @@ #else   Product a <> Product b = Product (a * b) #endif+  stimes n (Product a) = Product (a ^ n) +-- | This is a valid definition of 'stimes' for a 'Monoid'.+-- +-- Unlike the default definition of 'stimes', it is defined for 0+-- and so it should be preferred where possible.+stimesMonoid :: (Integral b, Monoid a) => b -> a -> a+stimesMonoid n x0 = case compare n 0 of+  LT -> error "stimesMonoid: negative multiplier"+  EQ -> mempty+  GT -> f x0 n+    where+      f x y+        | even y = f (x `mappend` x) (y `quot` 2)+        | y == 1 = x+        | otherwise = g (x `mappend` x) (pred y  `quot` 2) x+      g x y z+        | even y = g (x `mappend` x) (y `quot` 2) z+        | y == 1 = x `mappend` z+        | otherwise = g (x `mappend` x) (pred y `quot` 2) (x `mappend` z)++-- | This is a valid definition of 'stimes' for an idempotent 'Monoid'.+--+-- When @mappend x x = x@, this definition should be preferred, because it+-- works in /O(1)/ rather than /O(log n)/+stimesIdempotentMonoid :: (Integral b, Monoid a) => b -> a -> a+stimesIdempotentMonoid n x = case compare n 0 of+  LT -> error "stimesIdempotentMonoid: negative multiplier"+  EQ -> mempty+  GT -> x+{-# INLINE stimesIdempotentMonoid #-}++-- | This is a valid definition of 'stimes' for an idempotent 'Semigroup'.+--+-- When @x <> x = x@, this definition should be preferred, because it+-- works in /O(1)/ rather than /O(log n)/.+stimesIdempotent :: Integral b => b -> a -> a+stimesIdempotent n x +  | n <= 0 = error "stimesIdempotent: positive multiplier expected"+  | otherwise = x+{-# INLINE stimesIdempotent #-}+ instance Semigroup a => Semigroup (Const a b) where #ifdef USE_COERCE   (<>) = coerce ((<>) :: a -> a -> a) #else   Const a <> Const b = Const (a <> b) #endif+  stimes n (Const a) = Const (stimes n a)  #if MIN_VERSION_base(3,0,0) instance Semigroup (Monoid.First a) where   Monoid.First Nothing <> b = b   a                    <> _ = a-  times1p _ a = a+  stimes = stimesIdempotentMonoid  instance Semigroup (Monoid.Last a) where   a <> Monoid.Last Nothing = a   _ <> b                   = b-  times1p _ a = a+  stimes = stimesIdempotentMonoid #endif +#if MIN_VERSION_base(4,8,0)+instance Alternative f => Semigroup (Alt f a) where+# ifdef USE_COERCE+  (<>) = coerce ((<|>) :: f a -> f a -> f a)+# else+  Alt a <> Alt b = Alt (a <|> b)+# endif+  stimes = stimesMonoid+#endif++#if MIN_VERSION_base(4,8,0)+instance Semigroup Void where+  a <> _ = a+  stimes = stimesIdempotent+#endif+ instance Semigroup (NonEmpty a) where   (a :| as) <> ~(b :| bs) = a :| (as ++ b : bs) @@ -367,7 +458,7 @@ #else   Min a <> Min b = Min (a `min` b) #endif-  times1p _ a = a+  stimes = stimesIdempotent  instance (Ord a, Bounded a) => Monoid (Min a) where   mempty = maxBound@@ -401,6 +492,15 @@   rnf (Min a) = rnf a #endif +instance Num a => Num (Min a) where+  (Min a) + (Min b) = Min (a + b)+  (Min a) * (Min b) = Min (a * b)+  (Min a) - (Min b) = Min (a - b)+  negate (Min a) = Min (negate a)+  abs    (Min a) = Min (abs a)+  signum (Min a) = Min (signum a)+  fromInteger    = Min . fromInteger+ newtype Max a = Max { getMax :: a } deriving   ( Eq, Ord, Show, Read #ifdef LANGUAGE_DeriveDataTypeable@@ -443,7 +543,7 @@ #else   Max a <> Max b = Max (a `max` b) #endif-  times1p _ a = a+  stimes = stimesIdempotent  instance (Ord a, Bounded a) => Monoid (Max a) where   mempty = minBound@@ -477,6 +577,16 @@   rnf (Max a) = rnf a #endif +instance Num a => Num (Max a) where+  (Max a) + (Max b) = Max (a + b)+  (Max a) * (Max b) = Max (a * b)+  (Max a) - (Max b) = Max (a - b)+  negate (Max a) = Max (negate a)+  abs    (Max a) = Max (abs a)+  signum (Max a) = Max (signum a)+  fromInteger    = Max . fromInteger++ -- | 'Arg' isn't itself a 'Semigroup' in its own right, but it can be placed inside 'Min' and 'Max' -- to compute an arg min or arg max. data Arg a b = Arg a b deriving@@ -575,7 +685,7 @@  instance Semigroup (First a) where   a <> _ = a-  times1p _ a = a+  stimes = stimesIdempotent  instance Functor First where   fmap f (First x) = First (f x)@@ -644,7 +754,7 @@  instance Semigroup (Last a) where   _ <> b = b-  times1p _ a = a+  stimes = stimesIdempotent  instance Functor Last where   fmap f (Last x) = Last (f x)@@ -709,10 +819,11 @@ #ifdef MIN_VERSION_unordered_containers instance (Hashable k, Eq k) => Semigroup (Lazy.HashMap k a) where   (<>) = mappend+  stimes = stimesIdempotentMonoid  instance (Hashable a, Eq a) => Semigroup (HashSet a) where   (<>) = mappend-  times1p _ a = a+  stimes = stimesIdempotentMonoid #endif  -- | Provide a Semigroup for an arbitrary Monoid.@@ -771,14 +882,17 @@  -- | Repeat a value @n@ times. ----- > timesN n a = a <> a <> ... <> a  -- using <> (n-1) times+-- > mtimesDefault n a = a <> a <> ... <> a  -- using <> (n-1) times ----- Implemented using 'times1p'.-timesN :: Monoid a => Natural -> a -> a-timesN n x | n == 0    = mempty-           | otherwise = unwrapMonoid . times1p (pred n) . WrapMonoid $ x-{-# INLINE timesN #-}-+-- Implemented using 'stimes' and 'mempty'.+--+-- This is a suitable definition for an 'mtimes' member of 'Monoid'.+--+-- @since 0.18+mtimesDefault :: (Integral b, Monoid a) => b -> a -> a+mtimesDefault n x+  | n == 0    = mempty+  | otherwise = unwrapMonoid (stimes n (WrapMonoid x))  -- | 'Option' is effectively 'Maybe' with a better instance of 'Monoid', built off of an underlying 'Semigroup' -- instead of an underlying 'Monoid'.@@ -858,6 +972,11 @@ #else   Option a <> Option b = Option (a <> b) #endif+  stimes _ (Option Nothing) = Option Nothing+  stimes n (Option (Just a)) = case compare n 0 of+    LT -> error "stimes: Option, negative multiplier"+    EQ -> Option Nothing+    GT -> Option (Just (stimes n a))  instance Semigroup a => Monoid (Option a) where   mempty = Option Nothing@@ -873,17 +992,34 @@  instance Semigroup IntSet where   (<>) = mappend-  times1p _ a = a+  stimes = stimesIdempotentMonoid  instance Ord a => Semigroup (Set a) where   (<>) = mappend-  times1p _ a = a+  stimes = stimesIdempotentMonoid  instance Semigroup (IntMap v) where   (<>) = mappend-  times1p _ a = a+  stimes = stimesIdempotentMonoid  instance Ord k => Semigroup (Map k v) where   (<>) = mappend-  times1p _ a = a+  stimes = stimesIdempotentMonoid #endif++#if MIN_VERSION_base(4,7,0) || defined(MIN_VERSION_tagged)+instance Semigroup (Proxy s) where+  _ <> _ = Proxy+  sconcat _ = Proxy+  stimes _ _ = Proxy+#endif++#ifdef MIN_VERSION_tagged+instance Semigroup a => Semigroup (Tagged s a) where+# ifdef USE_COERCE+  (<>) = coerce ((<>) :: a -> a -> a)+# else+  Tagged a <> Tagged b = Tagged (a <> b)+# endif+#endif+  stimes n (Tagged a) = Tagged (stimes n a)