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

John Lato jwlato at gmail.com
Wed May 4 15:21:48 CEST 2011

On Wed, May 4, 2011 at 1:25 PM, Edward Kmett <ekmett at gmail.com> wrote:

> On Wed, May 4, 2011 at 7:40 AM, John Lato <jwlato at gmail.com> wrote:
>> From: Edward Kmett <ekmett at gmail.com>
>>> On Tue, May 3, 2011 at 3:43 PM, Yitzchak Gale <gale at sefer.org> wrote:
>>> > I'm sure there are countless other natural examples of semigroups
>>> > in the wild, and that the typical non-trivial ones will benefit
>>> > from an optimized sconcat.
>>> >
>>> Sold! (modulo the semantic considerations above)
>> Somewhat academic, but would there be a case for implementing sconcat in
>> terms of Foldable (or similar)?
> There is a Foldable1 in semigroupoids. I could move it into the semigroups
> package, but at the consequence that Data.Semigroup.Foldable wouldn't look
> like Data.Foldable API-wise, since the Semigroupoid package is what
> introduces Apply and Bind, giving you an Applicative sans pure and a Monad
> sans return, which are needed to make most of the analogues to the Foldable
> functions.
> So to do so, I'd need to move those into this package. This is not entirely
> implausible, if somewhat inconvenient from the perspective of keeping the
> semigroups package tiny. The default definition would wind up being
> something like:
> class Semigroup a where
>    (<>) :: a -> a -> a
>    sconcat :: Foldable1 f => f a -> a
>    sconcat = fold1
> class Foldable f => Foldable1 f where
>    fold1 :: Semigroup a => f a -> a
>    fold1 = foldMap1 id
>    foldMap1 :: Semigroup a => (b -> a) -> f b -> a
>    foldMap1 = ...
>    foldr1 :: ...
>    foldl1 :: ...
> choosing sconcat = fold1 by default seems pretty much optimal under those
> conditions, saying that if your Semigroup doesn't have an optimized fold,
> you might as well let the container figure out what to do instead.
> If we do that though, I'm hard pressed to find anything better to
> specialize to for most semigroups, which is what I was saying earlier to
> Yitzchak, and why I had omitted sconcat from the original API.
> I suppose you might exploit foldl, foldr, foldl' or foldr' instead to play
> a bit with how your traversal associates by default, or to use a different,
> more efficient intermediate state though.
> However, I am somewhat worried that with the type of the container
> abstracted that it probably won't receive the same love from the strictness
> analyzer though.
> One other annoying implementation consequence is that it would make the
> Data.Semigroup and Data.Semigroup.Foldable modules rather hopelessly
> entangled, so that I'd have to factor out the classes into a common
> Internals module, then re-export the appropriate fragments through separate
> modules. =/

Good points.  I was hoping for a reply like this, since I don't have a good
intuition for how Foldable would fit into the semigroups package.  I don't
have a strong opinion in either direction.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110504/c03ee75e/attachment.htm>

More information about the Haskell-Cafe mailing list