[Haskell-cafe] Please add a method for optimized concat to the Semigroup class

[Edward Kmett]

On Tue, May 3, 2011 at 7:12 AM, Yitzchak Gale <gale at sefer.org> wrote:

> Hi Edward,
>
> Thanks much for the very useful semigroups
> package.
>
> When using it in practice, it would be very useful
> to have an analogue to the mconcat method of
> Monoid. It has the obvious default implementation,
> but allows for an optimized implementation for
> specific instances. That turns out to be something
> that comes up all the time (at least for me) in
> real life.
>
> Thanks,
> Yitz
>


I had considered an

sconcat :: [a] -> a -> a

with either the semantics you supplied or something like

sconcat = appEndo . mconcat . map diff

But it was somewhat unsatisfying, in part because of the need for a seed
element.

Another unsatisfying detail is no definition is in any way shape or form
canonical when folding over a list.

There are at least 3 definitions that make sense. The nice inductive Endo
definition above (which differs in semantics from the one you proposed),
something like what you propose, with its funny base case, and the option of
placing something like the unit I placed in Endo on the other side. Finally,
I wasn't able to get any such specialized sconcat to actually speed anything
up. =/

I'm more than happy to revisit this decision, as it isn't particularly
onerous to add an sconcat definition to Semigroup, but I've yet to see it
pay off and it is somewhat disturbing to me that the type doesn't
automatically offer up its meaning.

As the Prelude has a general dearth of suitable container types that contain
a guarantee of at least one element, my focus was instead upon the use of
Foldable1 and Traversable1 from the semigroupoids package. This provides an
optimization path, similar to those of Foldable and Traversable by
optimizing the non-empty-by-construction *container* for its use of a
semigroup, rather than optimizing the semigroup for its use of by one
particularly inappropriate container.

http://hackage.haskell.org/packages/archive/semigroupoids/1.1.2/doc/html/Data-Semigroup-Foldable.html
http://hackage.haskell.org/packages/archive/semigroupoids/1.1.2/doc/html/Data-Semigroup-Traversable.html

These offer up a wealth of combinators for manipulating Semigroups over
suitable containers. Again, I'm more than happy to add it if only for
symmetry with Data.Monoid, but I'd be much happier doing so with a
compelling example where it actually sped things up, and if there was
actually a better motivated inductive definition.

-Edward
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110503/4e41d57e/attachment.htm>