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

[John Lato]

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.

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