On Wed, May 4, 2011 at 7:40 AM, John Lato <jwlato@gmail.com> wrote:
From: Edward Kmett <ekmett@gmail.com>
> 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