Re: HasCallStack constraint for maximum in Prelude?

> Mind you there's a conflict between the suggested `foldMap'`
> implementation for Bounded elements and efficient implementations
> with ordered Foldable collections (Map, IntMap, Set, ...).
> 
> The latter, just return quickly return the least or greatest element
> without paying a linear cost to perform the proposed fold.

... which is why functions like sum, product, maximum and minimum have
become Foldable class methods, to be overridden whenever it is more
efficient. 
I fail to see how your boundedMinimum reduces time complexity. It is
still a general fold in the non-empty case. 

I wonder, though, how sustainable it is to bloat the Foldable interface
with special cases of foldMap that can be overridden. What special
monoid structures do exist that warrant a specialized fold
implementation? We have 

(1) commutative monoids, such as Sum and Product,
(2) semilattices, where (x<>) is idempotent for every x,
(3) Short-circuiting monoids such as First and Last, 
    where either (x<>) or (<>x) is constant for x /= mempty.

Evidently, for cases (2) and (3) there are examples where the short-
circuiting behavior of the monoid itself can be leveraged to short-
circuit foldMap. Does anyone know of a real-world example where sum and
product are overridden? All instances Hoogle turns up are O(n). 

I can't cast that into a type signature right now, but I feel all of
null, sum, product, maximum, minimum
can be unified given a suitable sub-class that relates the particular
Foldable f to the contraint (Ord, Num etc.) present in the head of the
function. 

Olaf

_______________________________________________
Haskell-Cafe mailing list -- [email protected]
To (un)subscribe, modify options or view archives go to:
Only members subscribed via the mailman list are allowed to post.