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

[Edward Kmett]

I felt I should probably mention that ultimately what was done is I moved
NonEmpty all the way down into semigroups and chose

> sconcat :: NonEmpty a -> a

at it was the closest analogue to the current mconcat behavior.

So, request accomodated. ;)

-Edward

On Tue, May 3, 2011 at 7:23 PM, Edward Kmett <ekmett at gmail.com> wrote:

> Another option (upon reflection) would be to just transplant the NonEmpty
> type from
>
>
> http://hackage.haskell.org/packages/archive/streams/0.6.1.1/doc/html/Data-Stream-NonEmpty.html
>
> data NonEmpty a = a :| [a]
>
>
> <http://hackage.haskell.org/packages/archive/streams/0.6.1.1/doc/html/Data-Stream-NonEmpty.html>into
> the semigroups package, which would give you the 'canonical non empty list'
> you seem to want.
>
> and then add the more pleasing and natural generalization
>
> sconcat:: NonEmpty a -> a
>
> to the Semigroup class
>
> All I would need is to strip out the use of PatternGuards in a couple of
> locations.
>
> I would have to sprinkle a lot of instances through other packages on the
> way up the package tree
>
> NonEmpty isn't the most natural inductive version (Data.Stream.Future has
> that distinction), but it does implement efficiently and it can cheaply
> interconvert to [a].
>
> -Edward
>
>
> On Tue, May 3, 2011 at 6:49 PM, Edward Kmett <ekmett at gmail.com> wrote:
>
>> On Tue, May 3, 2011 at 3:43 PM, Yitzchak Gale <gale at sefer.org> wrote:
>>
>>> Edward Kmett wrote:
>>> > sconcat :: [a] -> a -> a
>>> > with either the semantics you supplied or something like
>>> > sconcat = appEndo . mconcat . map diff
>>>
>>>
>>
>>
>>> The sconcat we have been discussing is
>>>
>>> sconcat = flip $ appEndo . getDual . mconcat . map (Dual . Endo . flip
>>> (<>))
>>
>>
>> Holger's basically had this form, but I think Tetley's version is more
>> useful, because it provides for the scenario you describe below where there
>> is no value of the semigroup's type that you can merge with.
>>
>>
>>> > But it was somewhat unsatisfying, in part because of the need for a
>>> seed
>>> > element.
>>>
>>> Only because, as you said, there is no standard non-empty list type.
>>
>>
>> I have a streams package which provides a number of non-empty list types,
>> but it is fairly high up my module hierarchy, as it requires a number of
>> compiler extensions, and other classes, and so isn't available to the class
>> down here in the semigroups package.
>>
>>
>>> > Another unsatisfying detail is no definition is in any way shape or
>>> form
>>> > canonical when folding over a list.
>>>
>>> While our definition doesn't look any better than the others
>>> when expressed in terms of those combinators, it certainly
>>> seems to be the most natural when defined directly
>>> as Holger did. It's also the direct analogue of mconcat when
>>> viewed as the same type with lists replaced by non-empty
>>> lists. I'm sure that's the definition most users will expect.
>>> But I would be happy with whichever you supply.
>>>
>>> > ...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
>>>
>>> I'm currently doing some recognition algorithms on heterogeneous
>>> collections of graphical elements on a 2D canvas. Many types of
>>> elements have a location and a rectangular extent. You can often
>>> combine them, but there is no unit element because even an
>>> empty element needs to have a specific location. It would be very
>>> slow to combine a list of them incrementally; instead, you find
>>> the minimum and maximum X and Y coordinates, and combine
>>> the content using a fast algorithm.
>>>
>>
>> This is a pretty good example. Even if in this case it is mostly saving
>> you the boxing and unboxing of the intermediate rectangles
>>
>>  You still probably want something closer to Stephen Tetley's version,
>> otherwise you're going to have to magic up just that kind of empty rectangle
>> that you don't want to give though!
>>
>>  In fact you probably want something even stronger, that way you can
>> signal the empty list result 'out of band' of the values you can fit in the
>> Semigroup. This would avoid specifying an alternative directly, and his case
>> can be derived with
>>
>> sconcat :: Semigroup a => [a] -> Maybe a
>> sconcat [] = Nothing
>> sconcat (a:as) = Just (go a as)
>>    where
>>       go a (b:bs) = gs (a<>b) bs
>>       go a [] = a
>>
>> and effectively avoids fiddling with the empty case throughout the list.
>>
>> Then Stephen's version would look like
>>
>> tetley :: Semigroup a => a -> [a] -> a
>> tetley alt = maybe alt id . sconcat
>>
>> Alternately Option could be used instead of Maybe to keep the package's
>> API more self-contained, but I don't particularly care one way or the other.
>>
>> (I originally used Monoid instances by augmenting types with
>>> locationless empty elements. But that made a mess of my code
>>> and introduced a myriad of bugs and potential crashes. These
>>> are definitely semigroups, not monoids.)
>>>
>>
>>
>>> 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)
>>
>> -Edward
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110530/e0a9af8c/attachment.htm>