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

[Edward Kmett]

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. =/

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