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

[Edward Kmett]

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/20110503/3c76242a/attachment.htm>