On 16/12/2011, Gregory Crosswhite wrote:

On Dec 17, 2011, at 12:35 PM, Matthew Farkas-Dyck wrote:

...

(1) If we do (4), then the documentation ought to be adequate as-is.

I see your point that if we do (4) then some and many are no longer problematic for Maybe and [], and thus we don't need warnings for those types. However, nonetheless we will *still* need *big warnings* *for the sake of others who write Alternative instances* for new types to make sure that these instances do not fall into the same trap as Maybe and []. That is, we want to let future authors of instances know about the conditions under which they will need to write their own versions of some and maybe in order to make sure that these methods have sensible behavior.

Finally, if we adopt (4) then we will need to change the documentation to remove "least" from "least solutions of the equations" since the phrase will no longer be correct. Better still, we could replace the phrase entirely with something like "least *converging* solutions of the equations". (*)

Ah, true. Sorry.

In addition to this, we also really need some additional documentation explaining what the point of some and many are, since few people have any clue about them. :-)

Myself, I think it's quite clear by the axioms given, but I certainly shan't grouch about more/better documentation.

Cheers, Greg

(*) P.S:

Dear people who are better at this kind of technical language than I:

I am fully aware of the fact that the phrase "least converging solutions of the equations [...]" is sloppy wording at best and absolutely wrong at worst, but hopefully you should at least understand what I am *trying* to get at. Thus, I would welcome either your feedback on what it is that I am supposed to be thinking and saying, or an explanation about why the idea I am trying to conceive and convey is so intrinsically poorly formed that I am best off just giving up on it. ;-)

Actually, now that I think of it, they are not, in general, the least converging solutions -- in the case of a parser, for example, (some (pure x)) would nevertheless diverge (I think). Perhaps "least sane solutions" (^_^) Cheers, Matthew Farkas-Dyck

On Sun, Dec 18, 2011 at 20:42, Richard O'Keefe wrote:

No. Not by a country mile. It's better than "non-existent". It's better than "misleading". But it's not even on the same *continent* as "adequate".

+1 -- brandon s allbery allbery.b@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms

On 19/12/2011, at 3:44 PM, Gregory Crosswhite wrote:

So what do you all think about my own suggestion for the documentation?

It is an improvement. Documentation for a library module needs to start by telling people what it is for. For a particular function, someone needs to know very quickly "is this what I am looking for? is this the kind of thing I _should_ have been looking for?" One important thing about the Monoid instance for Maybe is that There is more than one way to turn Maybe into a Monoid. One way treats Maybe a as a truncated [a] and does not depend on any properties of a, it takes mappend (Just x) _ = Just x The other requires a itself to be a Monoid, and lift's a's operations to Maybe a: mappend (Just x) (Just y) = mappend x y The latter, more interesting, case is the one implemented here. (In the same way, bounded integers like Int can be viewed as Monoids in at least 4 ways, only two of which are predefined in Data.Monoid. mempty = minBound mappend = max mempty = maxBound mappend = min are the other two. In fact these apply to anything that is Bounded and Ord.) The point is not that your proposed documentation doesn't say that, but it doesn't say that the MonadPlus reading is a *LEGITIMATE* way to view Maybe as a Monoid, which happens not to have been the one chosen; also that this possibility that the Monoid instance you WANT might not be the one you GET is to me the first thing you need to understand about it. Yes, there is a blanket warning about this, but it specifically mentions Num. Whenever it is possible for a reasonable person to want a Monoid instance and get one that is not the instance s/he wanted, it's worth highlighting in the docs.

On Dec 19, 2011, at 1:01 PM, Richard O'Keefe wrote:

Documentation for a library module needs to start by telling people what it is for. For a particular function, someone needs to know very quickly "is this what I am looking for? is this the kind of thing I _should_ have been looking for?"

As I said before, some of this information really belongs in the Monoid typeclass itself, so here is my attempt at adding more information in this vein to the Monoid typeclass: ================================================================ The Monoid typeclass provides a standard interface for specifying how pairs of values of a given type can be combined to form new values of that type, as well well as an identity value for that type that when combined with any value x produces x. The Monoid class typically appears in higher-order functions that produce a list of values that need to be summarized into a single result, such as in Data.Foldable.foldMap function or the Writer monad. Formally, an instance of Monoid provides a binary associative operator with an identity element; to do this one must specify (at a minimum) the methods mempty and mappend such that they obey following properties: (*) mempty is the identity: mempty `mappend` x = x `mappend` mempty = x (*) mappend is associative: x `mappend` (y `mappend` z) = (x `mappend` y) `mappend` z Although not strictly necessary, for reasons of performance the Monoid typeclass also includes the method mconcat which combines all the elements in a list, i.e. it is a method which obeys the property (*) mconcat = foldr mappend mempty The above is the default definition of mconcat if no other is supplied, but for some times users may wish to override it when it can be performed more efficiently. Regardless, the minimal complete definition for an instance of the Monoid typeclass is mempty and mappend. For many types there are multiple equally sensible ways to combine pairs of values; for example, for the Int type one could use either addition or multiplication. In such cases where there is no single "natural" way to combine values, we often (though not always) define newtype wrappers for these types so that we can make it explicit which operation we are using. In the case of the Int type, for example, we define the Sum and Product newtypes and make these instances of Monoid using the corresponding mathematical operator. ================================================================ This additional information unfortunately makes the documentation more verbose, but the hope was to try to explain as much as possible the "whys" and "whens" of the Monoid class (to a non-mathematician audience) in addition to the "whats", since as you point out often the most important part of the documentation is where it explains why something exists and when you would need it. Cheers, Greg

On Dec 19, 2011, at 3:49 PM, Richard O'Keefe wrote:

On 19/12/2011, at 5:46 PM, Gregory Crosswhite wrote: [improved Monoid documentation]

Thank you. :-)

I would go so far as to point out that "mappend is a generalisation of Data.List.sum, Data.List.product, Data.List.and, and Data.List.or, where the initial value and combining rule are implied by the type.

Inspired by the idea behind your suggestion, I modified the documentation as follows: ======================================================== The Monoid typeclass provides a standard interface for specifying how pairs of values of a given type can be combined to form new values of that type, as well as an identity value for that type that when combined with any value x produces x. The Monoid class typically appears in higher-order functions that produce a list of values that need to be summarized into a single result, such as in Data.Foldable.foldMap function or the Writer monad. Formally, an instance of Monoid provides a binary associative operator with an identity element; to do this one must specify (at a minimum) the methods mempty and mappend such that they obey following properties: (*) mempty is the identity: mempty `mappend` x = x `mappend` mempty = x (*) mappend is associative: x `mappend` (y `mappend` z) = (x `mappend` y) `mappend` z Note that this structure is very generic; it includes addition with the identity element 0 (i.e. mappend = (+), mempty = 0), multiplication with the identity element 1 (i.e. mappend = (*), mempty = 1), list concatenation with the identity element [] (i.e. mappend = (++), mempty = []), logical and with the identity element True (i.e., mappend = (&&), mempty = True), logical or with the identity element False (i.e., mappend = (||), mempty = False), etc. Unfortunately, sometimes this very generality results in there being multiple equally sensible ways to define a Monoid instance for a type. For example, for numeric values addition and multiplication work equally well, and for boolean values logical and and logical or work equally well. In such cases, it is a good idea to define newtype wrappers for these types so that we can make it explicit which operation we are using. In the case of the Int type, for example, we define the Sum and Product newtypes and make these instances of Monoid using the corresponding mathematical operator; see also Any, All, First, and Last for other examples of this. Although not strictly necessary, for reasons of performance the Monoid typeclass also includes the method mconcat which combines all the elements in a list, i.e. it is a method which obeys the property (*) mconcat = foldr mappend mempty The above is the default definition of mconcat if no other is supplied, but for some times users may wish to override it when it can be performed more efficiently. Regardless, the minimal complete definition for an instance of the Monoid typeclass is mempty and mappend. ========================================================

...

This additional information unfortunately makes the documentation more verbose,

One man's "more verbose" is another man's "less cryptic".

Don't get me wrong, I completely agree with you that adding more words for the sake of making a subject less cryptic is a net win. :-) There are two dangers that lurk, however. First, there needs to be lots of that makes it easy for people to skim through and pick out the specific information that they want to find out about, and in particular the information that is most important/most urgently needed needs to be placed first so that it is the first thing that reader sees. Second, if you take too long to explain a point then you risk having your reader get fatigued so that all that effort you put in to make things clear just ends up getting going in one eye and out the other. :-)

I really don't like the emphasis on Num, as if it was a bizarre feature of Num that there's more than one Monoid reading for it. This is a *common* property of data types. For example, Sets can be seen as monoids with empty and union; and Sets with a universe can also be seen as monoids with universe and intersection.

In the revised version above, added Booleans as another example.

The more I think about it, the less idea I have _what_ to expect for _any_ instance of Monoid.

This is an inherent weakness of typeclasses, and why languages like Agda use record systems where instance declarations are records that you can either pass in explicitly or import explicitly to use implicitly within a particular scope. I think, though, that for many types, though, there really is a sort of "most intuitive"/"most natural" Monoid operation. For lists and sequences, for example, I think that the most intuitive operation is concatenation, rather than say taking the intersection of the elements of the two arguments. Likewise when you are accumulating over a bunch of sets of values you are probably more likely to be wanting the union of all the values you have seen so far than the intersection. Of course, such notions are ill-formed. :-) Cheers, Greg

On Sun, Dec 18, 2011 at 6:44 PM, Gregory Crosswhite wrote:

On Dec 19, 2011, at 12:39 PM, Brandon Allbery wrote:

On Sun, Dec 18, 2011 at 20:42, Richard O'Keefe wrote:

...

No. Not by a country mile. It's better than "non-existent". It's better than "misleading". But it's not even on the same *continent* as "adequate".

+1

So what do you all think about my own suggestion for the documentation? The following is the same as what I've posted before, but with some tweaks such as swapping the last two paragraphs.

============================================================

The Monoid instance for Maybe has the property that, for all x and y, (Just x) wins when combined (on either side) with Nothing values, and when (Just x) is combined with (Just y) then the result is (Just (x `mappend` y)).

Note that the behavior of the Monoid instance of Maybe is *different* from the behavior of the MonadPlus and Alternative instance of Maybe. For the latter two typeclasses, the behavior is that when (Just x) is combined with (Just y) the x and y values themselves are not combined but rather y is discarded so (Just x) simply wins; put another way, for all x and z, we have that (Just x) `mappend` z is *always* equal to (Just x), regardless of whether z is equal to Nothing or whether it is equal to (Just y) for some y. For this reason, unlike the instance for Monoid, the instances for these MonadPlus and Alternative place no additional constraints on the type lifted into Maybe.

Incidentally, for the more mathematically inclined, you may think of this as being equivalent to the standard practice of turning an arbitrary semigroup into a monoid by simply adding a new element to the semigroup to serve as the identity element, where in this case the identity element is the Nothing value of Maybe; unfortunately, since the base libraries do not come with a Semigroup typeclass, this process is expressed in code as lifting from the Monoid typeclass.

============================================================

I welcome any feedback that you all have to offer. If some iteration of the above is considered an improvement, then I would be happy to submit a patch using whatever process someone is kind enough to point me towards. :-)

The "incidental" comment is significantly more clear than an English description. As somebody else has said in these threads, the problem is that syntactically equivalent but semantically distinct types have been collapsed into Maybe. That complicates the reading of the source code, since it is much harder to figure out which interpretation is intended, and so which theorems we get from the types. In other words, they are not free theorems (since those are true in any interpretation). We have to work for them. I would rather see commutative diagrams (or what amounts to the same, usage examples) that describe the behavior than a "plain English" description.