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

Henning Thielemann schlepptop at henning-thielemann.de
Sat May 14 21:38:16 CEST 2011

Yitzchak Gale schrieb:

> When using it in practice, it would be very useful
> to have an analogue to the mconcat method of
> Monoid. It has the obvious default implementation,
> but allows for an optimized implementation for
> specific instances. That turns out to be something
> that comes up all the time (at least for me) in
> real life.

Btw. has someone an idea how to design 'mconcat' for pair types?

I mean, it is certainly sensible to define:

instance (Monoid a, Monoid b) => Monoid (a,b) where
  mappend (a0,b0) (a1,b1) = (mappend a0 a1, mappend b0 b1)
  mconcat pairs = (mconcat (map fst pairs), mconcat (map snd pairs))

but the mconcat definition would be inefficient for the type (Sum a, Sum
b). E.g. if I evaluate the first sum in (mconcat pairs) first and the
second sum last, then 'pairs' must be stored until we evaluate the
second sum. Without the Monoid instance I would certainly compute both
sums simultaneously in one left fold. Since a left fold can be expressed
in terms of a right fold, it would certainly work to map left-fold-types
like Sum to an Endo type, but this leads us to functional dependent
types or type functions.

More information about the Haskell-Cafe mailing list