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 (<>)) (avoiding the use of Dual.diff.Dual so that we don't need to define dualUnDual or some such messiness) > 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. > 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. (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. Thanks, Yitz _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
