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 <ekm...@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 <ekm...@gmail.com> wrote: > >> On Tue, May 3, 2011 at 3:43 PM, Yitzchak Gale <g...@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 >> > >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
