Proposal: Max and Min for Monoid

Edward Kmett ekmett at gmail.com
Thu Sep 23 15:08:48 EDT 2010


I was trying to avoid offering up color swatches for the bikeshed, but here
are my thoughts:

The use-cases that most often arise are that you either want to:

1.) take the Min or Max of a common Bounded type. These have a nice
analogues in Sum and Product in Data.Monoid now.

2.) take the Min or Max of an unbounded Type, and therefore need to have a
unit added. These have nice analogues in First and Last in the Data.Monoid
now, and reflect the practice of using the equivalent of Maybe to transform
something that is notionally a Semigroup into a Monoid. This is common for
things like priority queues. In fact, using a fingertree as a fair priority
queue is really easy with this monoid. In Data.Monoid.Ord from the monoids
package these are "MinPriority" and "MaxPriority" for that reason. Note that
by adding just a minimum or maximum element these aren't strong enough to be
Bounded, and this is the minimum requirement to really be able to implement
a priority queue with any Ord'ered value as the priority, while handling the
empty queue case gracefully.

On the other hand, composing AddBounds introduces another element on the
other side, which serves as an annihilator when composed with Min and Max.
This is fine for some applications, but I don't believe it subsumes
MinPriority and MaxPriority.

AddBounds is a useful type, but I don't think injecting MinPriority
a/MaxPriority a into the larger Max (AddBounds a) and Min (AddBounds a) is
the right solution.

By that same 'the type is too large' token, I don't like just providing
MinPriority/MaxPriority, since Min and Max are perfectly usable and much
more efficient monoids with a smaller domain.

So in my perfect world the patch would include
Min/Max/MinPriority/MaxPriority and another proposal could find a nice place
to shoehorn AddBounds. ;)

-Edward Kmett

On Thu, Sep 23, 2010 at 2:25 PM, Conal Elliott <conal at conal.net> wrote:

> I encountered exactly this issue in my use of the Max & Min monoids in
> Reactive.  I wanted to allow already-bounded types to use their own minBound
> for Max and maxBound for Min, and also allow unbounded types to be used.
> So, rather than entangling bound addition with Max & Min, I defined
> AddBounds type wrapper, which is *orthogonal* to Max & Min.  If your type is
> already Bounded, then use my simple Max & Min wrappers directly.  If not (as
> in Reactive's use), compose Max or Min with AddBounds.
>
> I'm sorry I didn't think to mention this useful composition the Max & Min
> trac ticket.
>
>    - Conal
>
>
> On Thu, Sep 23, 2010 at 10:47 AM, Gregory Collins <greg at gregorycollins.net
> > wrote:
>
>> Felipe Lessa <felipe.lessa at gmail.com> writes:
>> > On Thu, Sep 23, 2010 at 12:58 PM, Jake McArthur <
>> jake.mcarthur at gmail.com> wrote:
>> >
>> >>>    -- | Ordered monoid under 'max'.
>> >>>    newtype Max a = Max { getMax :: a }
>> >>>            deriving (Eq, Ord, Read, Show, Bounded)
>> >>>
>> >>>    instance (Ord a, Bounded a) => Monoid (Max a) where
>> >>>            mempty = Max minBound
>> >>>            Max a `mappend` Max b = Max (a `max` b)
>> >
>> > Why should we prefer this monoid over
>> >
>> >> data Max a = Minimum | Max a
>> >>              deriving (Eq, Ord, Read, Show)
>> >>
>> >> instance Ord a => Monoid (Max a) where
>> >>   mempty = Minimum
>> >>   Minimum `mappend` x   = x
>> >>   x `mappend` Minimum   = x
>> >>   Max a `mappend` Max b = Max (a `max` b)
>>
>> You're right, the original wouldn't fly because there are unbounded
>> types (like Integer) that you'd like to be able to use with Max/Min.
>>
>> Rather than your proposal I would suggest that Max/Min mirror
>> the existing First/Last, namely:
>>
>>    newtype Max a = Max { getMax :: Maybe a }
>>       deriving (Eq, Ord, Read, Show)
>>
>>    instance (Ord a) => Monoid (Max a) where
>>         mempty  = Max Nothing
>>        mappend = max
>>
>> G
>> --
>> Gregory Collins <greg at gregorycollins.net>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://www.haskell.org/mailman/listinfo/libraries
>>
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100923/bebafc61/attachment-0001.html


More information about the Libraries mailing list