hey,

your package requires bytestring (>=0.9 && <0.10.4) and bytestring-builder(>=0.10.4 && <1) in case of enabled bytestring-builder flag and bytestring-builder requires bytestring (>=0.9 && <0.10.2 || >=0.10.4), thus it's not possible to use bytestring >=0.10.4 along with your package. If bytestring-builder supports it, I think you can, too.

https://hackage.haskell.org/package/semigroups-0.18/changelog says only about 0.17.0.1

The instance Semigroup [a] uses the default implementation of times1p for replicating lists. I wonder, is there any advantage compared to the "standard" implementation

    times1p n x = let rep 0 = x
                      rep i = x ++ rep (i - 1)
                  in rep n

? Both have O(n) time overhead. But if the resulting list is consumed lazily, the default implementation of times1p has O(n * length x) memory overhead, while the "standard" variant has O(length x).

(Also head (times1p n x) takes O(1) time for the "standard" implementation but O(ln n) for the current default one. But I don't think this is important, since replicating a list to only read its head is probably something that never happens.)

diff --git a/semigroups.cabal b/semigroups.cabal
index 37daad7..566470d 100644
--- a/semigroups.cabal
+++ b/semigroups.cabal
@@ -178,7 +178,7 @@ library
       build-depends: unordered-containers >= 0.2  && < 0.3
 
     if flag(transformers)
-      build-depends: transformers        >= 0.2 && < 0.6
+      build-depends: transformers        >= 0.2 && < 0.7
                    , transformers-compat >= 0.5 && < 1
 

Seems to compile fine. (The up/downside is that it will make more install plans for older GHCs)

In a way you can decide that transformers-0.6 and pre GHC-8 are not a good idea and practically prevent that by not relaxing this bound.

Therefore I'm not relaxing it myself.

template-haskell-2.15 (GHC 8.8) will debut a Lift instance for NonEmpty. We should backport it in this library as well (behind a template-haskell Cabal flag).

Would you guys be interested in a PR adding a Semigroup for modular arithmetic?

Something like this:

data Mod (k :: Nat) (f :: * -> *) (a :: *) = Mod (f a)

instance (KnownNat k, Semigroup (f a), Applicative f,  Integral a) => Semigroup (Mod k f a) where
  (<>) (Mod fx) (Mod fy) = Mod $
    mod <$> (fx <> fy) <*> (pure $ fromIntegral $ natVal $ Proxy @k)

In the introduction comment, https://github.com/ekmett/semigroups/blob/master/Data/Semigroup.hs#L18
(<>) should be escaped as (\<\>) or @(\<\>)@

We should replace times1p. The naming convention of it doesn't adapt well to Data.Monoid and standardization.

If we added stimes instead which would be allowed to fail on 0 or less, then we can add mtimes to Monoid, which can delegate to stimes on 1+ by default and mempty on 0. This avoids the minor addition/subtraction dance we have to play if we want such a combinator today, and makes the naming much more homogeneous.

Is there a reason a Monoid instance isn't supplied? standard list concatenation seems to work fine with the laws.

Now that the SMP has completed, it's time to face an annoying issue: the Data.Semigroup module backported in this library is perniciously different from the one provided in base. In particular, the Semigroup class defined in this library has a default implementation for (<>) in terms of mappend:

The Semigroup in base, however, does not. This is a subtle difference, but one that has bitten in practice. See for instance, hedgehogqa/haskell-hedgehog#141.

If we want to make the two libraries uniform, it seems like we ought to rip out this default implementation. However, that might break other libraries that currently rely this default implementation. I would argue that the pain would be worth it (especially since folks are going to have to do this anyway to upgrade to GHC 8.4), but it would require a breaking change in semigroups itself.

As Data.List.nub preserves non-emptiness, I think it would be very useful to have a Data.List.NonEmpty.nub function.

I attempted to use ArgMin but got the following error:

No instance for (Bounded (Arg Number LocalTime))

And sure enough there is no Bounded instance for Arg which Min requires.

Nothing that another orphan instance won't work around.

Example here. I'm guessing that GHC couldn't derive Generic1 properly until after GHC 7.4.

In semigroup documentation:

-- | Use @'Option' ('First' a)@ to get the behavior of 'Data.Monoid.First' from @Data.Monoid@.

In my code:

stats1 :: TempTime -> Option (First LocalTime)
stats1 tt@(Arg temp time) = Option (First time)

Error message:

Couldn't match expected type ‘Maybe (First LocalTime)’
            with actual type ‘First LocalTime’
In the first argument of ‘Option’, namely ‘(First time)’
In the expression: Option (First time)

Is there a more thorough example of how to use this feature?

Thanks, Mark

I'm guessing that the merge in #68 is responsible for this build error in postgresql-simple for GHC 7.8.

Curiously, the postgresql-simple build for GHC 7.6 went off without a hitch.

@RyanGlScott

I'm considering sending a PR myself, but since this is a bit laborious I'd like to know first if this would be a welcome addition.

My need comes from trying to fulfill Prims laws when dealing with serialization/deserialization of Maps with Text keys. The empty key is the offender and wouldn't like to support this case anyway since it doesn't make sense to allow it at all.

I could also take care of ByteString and the corresponding Lazy variants at the same time.

It was pointed out in https://ghc.haskell.org/trac/ghc/ticket/14439

that there's a redundant pred even though y is known to be odd:

  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)
        | y == 1 = x
        | otherwise = g (x <> x) (pred 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) (pred y `quot` 2) (x <> z)
  {-# INLINE stimes #-}

@ekmett do you agree, or is there some subtle reason for why you made y even before dividing by two?

Need a better name for the fromList version?

Data.List.NonEmpty.singleton :: a -> NonEmpty a
Data.List.NonEmpty.singletonWithList :: a -> [a] -> NonEmpty a

There are five instance Enum a => Enum (XYZ a) instances in semigroups.hs and all of them have

succ (XYZ a) = XYZ (succ a)
pred (XYZ a) = XYZ (succ a)

which looks like a typo to me.

I think that it would be good to add foldl1 to NonEmpty, especially because we can actually write a safe version of it:

nonEmptyFoldl1 :: (a -> a -> a) -> NonEmpty a -> a
nonEmptyFoldl1 g (a :| as) = List.foldl g a as

The same can be done for foldr1. Although at this point in time, it may make more sense to add this to base-4.9 instead of semigroups.

Text 1.0.0.0 is now released. Please modify the dependency. Quick release would be appreciated.

I was having an error more-or-less identical to this: z0w0/helm#49

Their fix, appropriately modified for semigroups, worked for me: z0w0/helm#50

Data.{Map, Set, HashMap, HashSet, etc} have (<>) as a union-y operation But they're also a semigroup under intersection, and it'd be nice to offer a generic way to select an intersection-y instance. Note that, for finite containers, there's not a sensible identity element for intersections, so this can't also be a Monoid.

Sketch of what that would look like:

class Intersectable s where
  intersection :: s -> s -> s

instance (Ord k) => Intersectable (Data.Map.Map k v) where
  intersection = Data.Map.intersection

--etc

newtype Intersection s = Intersection { getIntersection :: s }
  deriving (Show, Read) --etc

instance (Intersectable s) => Semigroup (Intersection s) where
  Intersection a <> Intersection b = Intersection (intersection a b)

Names are subject to bikeshedding, of course. Data.List exports intersect and containers/unordered-containers use intersection so I suggest preferring intersection on the assumption that containters and unordered-containers are generally imported qualified.

Whether to specify which side the elements in the result come from is a question: either always left (containers and unordered-containers do that) or caveat emptor are the options here.

https://hackage.haskell.org/package/semigroups-0.15.3/reports/1/log ; maybe it’s due to the .cabal file containing unicode.

I'd like to see a wrapper for Either whose Semigroup/Monoid instances would work like the standard Either instance, except Lefts would be combined using the underlying semigroup operation.

I can prepare a patch if needed.

Some issues to discuss:

• naming. WithLeftZeros sounds too verbose.
• I think wrapping left zeros in Left, not Right, is more intuitive because of both the pun and the intuition from the Applicative instance. But that'd be inconsistent with the provided Either instance
• because of short-cicuiting, it is unlikely that strictness analysis will tell to evaluate underlying <> eagerly, which can lead to memory leaks. Should there be a strict and non-strict versions of the wrapper? Or perhaps only add the strict one? I understand it's unconventional, but it'll probably do the right thing most of the time, and such behavior is easier to override than the opposite

Same as ekmett/nats#1

(more context: https://prime.haskell.org/wiki/Libraries/Proposals/SemigroupMonoid)

This involves several sub-items:

• make semigroups conditionally hide Data.Semigroup and Data.List.NonEmpty
• add base < 4.9 upper bound to released semigroups versions on Hackage to mark semigroups as incompatible w/ GHC8's base

as well as (conditionally) move instances and add base < 4.9 where needed to

• bytestring
• containers
• deepseq
• tagged
• text
• hashable
• unordered-containers

After this, for GHC>=8, semigroups will only provide Data.Semigroup.Generic

Sum and Prod already have Num instances, which I find handy. It would be nice to have them for Min and Max as well.

Found your package, looks very nice!
I am considering to use it in the Agda code base, there is just one little thing:

I just wondered why non empty lists are just called NonEmpty instead of NonEmptyList or NEList? What about other non-empty collection types? It seems fine when importing Data.List.NonEmpty but the connection to lists is lost as I cannot rename identifiers during import. It would actually have made more sense to call it just List, then

import qualified Data.List.NonEmpty as NE

myList :: NE.List Int

would read ok.
Importing the module as List would look nice, but it conflicts with Data.List.

import Data.List as List
import qualified Data.List.NonEmpty as List

myList :: List.NonEmpty Int

Two issues:

1. Give suggestions how to import Data.List.NonEmpty in the haddock.
2. Rename NonEmpty to NonEmptyList and add type NonEmpty = NonEmptyList for backwards compatibility.

Item 2. is my suggestion to solve the dilemma about NonEmpty being to general and non-telling, but you might have a better solution.

Seems like there should be functions for appending a list to a NonEmpty.

[a] -> NonEmpty a -> NonEmpty a

and

NonEmpty a -> [a] -> NonEmpty a

without going through Maybe.

http://hackage.haskell.org/package/semigroups-0.18.2 has docs for Data.Semigroup.Generic but not for anything else. I don't know if this project uploads it's own docs?

https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8696

@ekmett @RyanGlScott what are your thoughts on this? Other than annoying operational bits, I think the module would fit right in in base.

Existential crisis ensues.

Interested in putting any of these into the package?

• length ∷ NonEmpty a → Int
• transpose ∷ NonEmpty (NonEmpty a) → NonEmpty (NonEmpty a)
• sortWith :: Ord o => (a -> o) -> NonEmpty a -> NonEmpty a

More obscure

• splitAt1 ∷ NonEmpty a → (a, [a])
• fromPair :: (a,a) -> NonEmpty a
• neighboringJusts :: [Maybe a] -> [NonEmpty a]

I can't find a reason why there aren't semigroup instances for these structures?

I just got a build failure on Travis with the message:

[1 of 3] Compiling Data.List.NonEmpty ( src-ghc7/Data/List/NonEmpty.hs, dist/build/Data/List/NonEmpty.o )
[2 of 3] Compiling Data.Semigroup   ( src-ghc7/Data/Semigroup.hs, dist/build/Data/Semigroup.o )
src-ghc7/Data/Semigroup.hs:799:10:
    Duplicate instance declarations:
      instance Semigroup ByteString.Builder
        -- Defined at src-ghc7/Data/Semigroup.hs:799:10
      instance Semigroup ByteString.Builder
        -- Defined at src-ghc7/Data/Semigroup.hs:811:10

This seems to be caused by binary unexpectedly reexporting the same Builder type.

Hi Edward,

A fresh cabal install semigroups fails with:

Data/Semigroup.hs:54:10:
    Ambiguous occurrence `<>'
    It could refer to either `Data.Semigroup.<>',
                             defined at Data/Semigroup.hs:57:3
                          or `Monoid.<>',
                             imported from `Data.Monoid' at Data/Semigroup.hs:35:1-47

But cloning the repository and building from there works fine. Could you upload an updated version to Hackage please?

Thanks,

Martijn.

I was thinking about adding generics support to semigroup, similar to what's defined in
http://hackage.haskell.org/package/generic-deriving-1.6.2/docs/Generics-Deriving-Monoid.html

Would this be considered?
Thanks

I don't about you guys but I often need to add NFData and Storable instances myself for the monoids like Sum, Product, All, etc for using them with Data.Vector.Storable and writing strict folds! Would this be the right package to add this? Is there some reason Storable instances are not defined?

@RyanGlScott

When compiling semigroups-0.18.2 on GHC 7.6.3 w/ bytestring-0.10.2.0 I run into the following compile failure:

Preprocessing library for semigroups-0.18.2..
Building library for semigroups-0.18.2..

src-ghc7/Data/Semigroup.hs:146:8:
    Could not find module `Data.ByteString.Short'
    It is a member of the hidden package `bytestring-0.10.8.1'.
    Perhaps you need to add `bytestring' to the build-depends in your .cabal file.
    Use -v to see a list of the files searched for.

after some investigation I found the culprit: 2d9fe67 introduced

 -# if MIN_VERSION_bytestring(0,10,4)
 +# if MIN_VERSION_bytestring(0,10,4) || defined(MIN_VERSION_bytestring_builder)
  import Data.ByteString.Short
  # endif
  #endif

 -# if MIN_VERSION_bytestring(0,10,4)
 +# if MIN_VERSION_bytestring(0,10,4) || defined(MIN_VERSION_bytestring_builder)
  instance Semigroup ShortByteString where
    (<>) = mappend
  # endif

But defined(MIN_VERSION_bytestring_builder) is not a sufficient condition for the existence of Data.ByteString.Short; MIN_VERSION_bytestring(0,10,4) however is.

The documentation for cycle says that

cycle [1,2,3] = 1 :| [2,3,1,2,3,...]

But the argument should be NonEmpty, so it should read

cycle (1 :| [2,3]) = 1 :| [2,3,1,2,3,...]

Just as Foldables are naturally defined using Monoids with

class Foldable t where
  foldMap :: (Monoid m) => (a -> m) -> t a -> m
    -- ...

non-empty foldable collections could be naturally defined using Semigroups like

class Foldable t => Foldable1 t where
  foldMap1 :: (Semigroup m) => (a -> m) -> t a -> m

If Semigroup ever gets into base as a super-class of Monoid, I'd be nice to move foldr1 and foldl1 from Foldable into Foldable1 (although this probably won't happen because it'd break code that already uses foldr1 on lists etc.).

unless there's a reason for leaving them out, the functions

all p = Data.List.all p . toList
any p = Data.List.any p . toList

would be convenient to have...