On Wed, May 4, 2011 at 1:25 PM, Edward Kmett <ekm...@gmail.com> wrote:
> On Wed, May 4, 2011 at 7:40 AM, John Lato <jwl...@gmail.com> wrote: > >> From: Edward Kmett <ekm...@gmail.com> >>> >>> >>> On Tue, May 3, 2011 at 3:43 PM, Yitzchak Gale <g...@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
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
