Add specialized sconcat implementation for Data.Semigroup.First

[cbrt-x]

The default implementation of sconcat is strict in its spine.
This means that even though in the instance of First a we have the lazy x <> _ = x, sconcat $ First () :| undefined outputs First {getFirst = *** Exception: Prelude.undefined....

I think this should be changed, by having a non-default implementation of sconcat as

sconcat (x :| _) = x

This will also have performance benefits when the spine takes time to compute.

This is 'breaking' in the sense that a program that might previously have errored would work fine now. No program that previously worked would not work with this change unless the strictness in the spine triggered a side-effect, which would only be possible with unsafePerformIO I believe.

This would make this instance more in line with other Semigroup instances like () which also provides a custom sconcat implementation for laziness.

[mixphix]

Do you have a merge request?

[tomjaguarpaw]

The default implementation of sconcat is strict in its spine.

It's not strict in the spine, it's just strict in the first : of (the second component of) the NonEmpty. This works fine, for example:

sconcat (First () :| (First () : undefined))

That's because the default implementation of sconcat is:

        sconcat :: NonEmpty a -> a
        sconcat (a :| as) = go a as where
          go b (c:cs) = b <> go c cs
          go b []     = b

You can't do better than forcing : in general, because you need to know whether there will be another element coming -- you don't have mempty! But yes, it seems pretty plausible that for First we should have a specialised implementation.

It should be

        sconcat :: NonEmpty a -> a
        sconcat (a :| as) = go a as where
          go b ccs = case css of
            c : cs -> go c cs
            []     = b

[parsonsmatt]

There are two Firsts - one in Data.Monoid which is newtype First a = First (Maybe a) and one in Data.Semigroup, which is newtype First a = First a.

For the Semigroup.First type, I think the specialized implementation of sconcat (a :| _) = a makes sense.

For the Monoid.First type, I think the implementation can be improved too.

instance Semigroup (Monoid.First a) where
  sconcat (Monoid.First ma :| rest) = 
    case ma of
      Nothing -> mconcat rest
      Just a -> Monoid.First (Just a)

This allows the implementation to avoid forcing the list if the first value is present, and only inspect the rest of the list if the first element is Nothing.

[cbrt-x]

Do you have a merge request?

Not yet but I would be happy to implement these

[cbrt-x]

I have opened a merge request at !11983
As far as I understand I now need to wait for the approval (or disapproval) of the CLC (?)

[mixphix]

LGTM!

[treeowl]

This is yet another example of what I see as an unnatural definition of NonEmpty in the context of a lazy language. For this type, we don't have that problem:

data NE a
  = End a
  | a :< NE a

neConcat :: Semigroup a => NE a -> a
neConcat (End a) = a
neConcat (a :< as) = a <> neConcat as

[Bodigrim]

@tomjaguarpaw @parsonsmatt are you happy with the MR? https://gitlab.haskell.org/ghc/ghc/-/merge_requests/11983/diffs

[tomjaguarpaw]

Yes, fine.

[parsonsmatt]

Looks great to me!

[Bodigrim]

Seems we are good to go for a vote then.

Dear CLC members, let's vote on the proposal to write specialised implementations of sconcat for Data.Semigroup.First and Data.Monoid.First as implemented at https://gitlab.haskell.org/ghc/ghc/-/merge_requests/11983/diffs. The default implementations are surprisingly strict, forcing list's spine past the first element even if it was sufficient to determine the outcome.

@tomjaguarpaw @parsonsmatt @angerman @hasufell @mixphix @velveteer

---

+1 from me, this is a neat improvement.

[tomjaguarpaw]

+1

[angerman]

+1 🤞 no one relies on the oddities of the current behavior.

[velveteer]

+1