Important traits which don't need HKTs

[glaebhoerl]

While we're waiting for HKTs, there are a lot of useful traits which don't need them, and which we should think about adding, especially if we do have associated types.

The most obvious ones are Semigroup and Monoid. There is an existing proposal concerning a semigroup trait, under the name Combine (full disclosure: which I suggested), albeit also tied to a new operator overload.

Other prior art from Haskell:

Many (theoretically well-founded) monomorphic type classes for things which are "like lists" or "like strings" exist in the monoid-subclasses package. (See also the GitHub page, which has more information and important links.)

The mono-traversable package has monomorphic versions of the Functor/Foldable/Traversable hierarchy, which is valuable in that they can also be used with monomorphic containers (think String, Bitv), so there is demand for these even though Haskell does also have HKTs. There are also some classes (marked experimental) which are seemingly similar to the ones from monoid-subclasses, but using associated types.

The point is that we will probably want traits like these even if we do grow HKTs, so there's no real reason to wait (apart from having more important things on our plate).

For the most part we should be able to just copy many of these ideas, but there are some things we need to, or should want to, put extra thought into:

• Issues related to ownership (move semantics, borrowing). Haskell doesn't have to worry about where to take things by reference and where by value; we do.
• Mutability. While we probably do want the same methods as the Haskell classes for non-destructive manipulation, we probably also want ones which do in-place updates in addition to them.
• Naming. We might want to lean in the direction of more approachable, "intuition-capturing", rather than more precise, mathematical names (Functor -> Map/Mappable, Semigroup -> Combine, and so on), but coming up with these, especially for everything, is hard. We also have to think about how to distinguish monomorphic versions from future HKT-using ones. (The mono-traversable package uses Mono and o prefixes, of which, in my opinion, the former is not bad, and the latter is quite awful.)

(List is not necessarily exhaustive.)

[nrc]

+1000 to having "intuition-capturing" names, the Haskell-style naming is really off putting to most programmers.

I'm generally pretty luke-warm on these kind of abstractions. I think they are a good way to inform design choices, rather than practical tools for a programming language. It is much too easy to stray into 'abstraction astronaut' territory and write concise but unreadable code this way (in an analogous way to overusing OO design patterns in Java-like languages). OTOH, there are probably some useful things we can extract (e.g., a Mappable trait, perhaps).

[Gankra]

I'm skeptical of introducing many more advanced mathematical notions to std. #369 was just opened to remove a lot of our generic numeric stuff. Can you provide some concrete examples of Rust code that would be improved/enabled by generic programming over Functors and Semigroups?

(I don't question that these things are great in Haskell, but Haskell is A Very Different Language)

[reem]

Personally I would really like to have these traits and have them implemented for many standard library types. I agree that in Rust it is usually not really needed or useful to program generically over a semigroup in an application, but it is very useful in a library which could provide packets of common behavior in terms of these very general traits which could be used in an application even when applied to concrete types.

[japaric]

Personally I would really like to have these traits and have them implemented for many standard library types.

There is no need for these traits to be in the standard library tough, they could be defined in some crate foo, implemented for any "standard library type" in that crate, and then your library can link to foo and get all the abstractions you need. (The exception being that the if trait is glued to some compiler magic (like an operator), then yes, it needs to be in stdlib.)

(FWIW, I agree with the rest of your post)

[reem]

Well, the issue with that is there are certainly types for which these traits may need to access the internals of types and that can't be done outside the module those types are created in.

[blaenk]

I'm definitely for this; no need to wait until we have HKT if certain traits wouldn't even require them.

but coming up with these, especially for everything, is hard

I personally don't mind the mathematical names because they are specific, which is why coming up with alternative, more practical names is difficult. I'm open to having more practical names though, when we can find more practical names that are also equivalent.

So I don't think it should be all-or-nothing practical names. If we can't find a practical name for a particular trait, we shouldn't shoe-horn in some 'practical' name where the only difference is that it "sounds more familiar" but still doesn't inform on anything about the trait's use. We can make up for this by providing solid, practical documentation for the trait.

[reem]

@blaenk While I also like the specificity of names like Monoid and Semigroup, there is something to be said for approachability. Haskell gets a terribly bad rep for names like the above, and we could potentially dodge that bullet.

[blaenk]

Yeah, that's what I'm saying though. I'm aware of that effect on approachability, so I'm open to more practical names.

I'm just saying that I don't think we should commit to an all-or-nothing practical naming scheme. If a clearly better name can't be devised for a particular trait, such that its purpose/use remains ambiguous to someone not familiar with the underlying type, then I say we should stay with the specific name.

I think mandating "practical names" for every one of these traits would probably put us into bikeshedding gridlock, impeding the actual implementations of the traits. Instead we should focus on implementing them, then coming up with better names if we can find them.

Maybe we can have opt-in specific name type alias imports, but that's probably overkill.

[glaebhoerl]

For one specific example, if we want to have separate Semigroup and also Monoid inheriting from it (which I think we do - at least the Haskellers eventually realized that they want this after originally having had just Monoid), then Combine is I think a pretty good name for Semigroup, but then what do we call Monoid? Compared to semigroups, it adds an identity or unit element. CombineWithUnit? Doesn't exactly roll off the tongue...

(And while I agree that we shouldn't force "practical" names when we can't come up with any, having some traits follow one and others another naming convention in a seemingly haphazard way is also not most awesome. But it may still be the least worst thing.)

But yes, figuring out how to best formulate them should probably precede both figuring out the best names, and deciding which ones we should include in std.

[jsanders]

I second @gankro's request for real rust code that would be improved or newly allowed by the presence of these traits. Seeing code examples might also help illuminate practical names, eg. what patterns does a Monoid enable that a Semigroup doesn't? Do these examples already exist somewhere that we can just get links to?

[lucidd]

I don't think the problem with the approachability comes from the naming. Just renaming things doesn't
make it easier to understand the concepts behind them, but it makes it impossible to search for. If i search for Monoid or Semigroup i get wikipedia and lots of sites and blog posts for Haskell, F# or scalaz explaining what those are and why i would use them. I think this i much more useful than renaming it for marketing purposes.

[blaenk]

I have to agree with @lucidd. More and more I'm leaning towards keeping the same names. I'm still open to more practical names, but I would definitely prefer to keep their actual names.

Haskell was for the most part alone as far as I know—or at least now part of a few languages which it's permeating into—which used the specific names. It presumably did this because the concepts are inherently very general and abstract, and there wasn't precedent for naming them aside from math. Naturally these names were/are pretty weird for people not already familiar with them, but I think this will change as more and more languages are exposed to them and absorb them.

These names are what they are, barring technicalities. It seems counter-productive to me to come up with names that perhaps don't convey their use and meaning any better than the actual name, and in so doing we perpetuate the situation where people aren't familiar with the real names. Just imagine if other languages pop up that do the same thing, but chose different names. Now we have names that perhaps aren't any better than the actual name, and they're different between languages, which makes things more confusing in my opinion. Sure, we have no control over what other languages choose to do, but I think Rust has the opportunity to champion these traits as practical to use in a practical language like Rust, and thereby make them perhaps more accessible (understandable) to more people.

If we're not necessarily building the std completely using these traits (afaik?), then they won't be deeply entrenched in the language so that learning Rust would necessitate having to learn them as well. Then there's even less of a reason to bend over backwards IMO to give them friendlier names, since they're more likely to be used by people who already know what they're looking for.

TL;DR: Call it what it is.

1. Keep their actual names.
   • Help champion them for being practical to use in a practical language like Rust.
   • Stand in solidarity alongside Haskell (and other languages which are adopting them as well) to help disseminate the terminology and their underlying concepts.
2. Provide solid documentation for each of them.
   • Each of these traits should have very solid and approachable documentation with "real world," practical code examples.

[glaebhoerl]

It seems counter-productive to me to come up with names that perhaps don't convey their use and meaning any better than the actual name, and in so doing we perpetuate the situation where people aren't familiar with the real names.

This is something of a straw man argument on two fronts. First, obviously it doesn't make sense to choose names which are both "unofficial" and aren't any better at conveying an intuition. The point would be to achieve the latter wherever we can. If we can't, we should of course reconsider. Second, it's not as if this means that people would be left totally in the dark about the mathematical connections: the correspondence should be mentioned prominently in the documentation. ("This corresponds to the mathematical concept of a semigroup.")

And the naming scheme we should follow is simply the one which Rust already uses: name the trait after the (most important) method. The associative semigroup/monoid operation in Haskell is called mappend, which is clearly not a very good name. I don't know if math itself has any name for it apart from "the semigroup/monoid operation" and symbolic operators. I think combine would be a good name, and then the trait can also be named Combine. And similarly in other cases. (Difficulties arise when supertraits are involved, as "CombineWithUnit" above.)

[aturon]

This is interesting ground to explore, but as a general principle this is not the kind of thing we would toss into libstd right off the bat. Now that Cargo is available (and it will soon have a central repository of crates), our strong preference is for new efforts like this to begin in the Cargo ecosystem, and gradually migrate into libstd as they prove themselves (and as the need for standardization becomes clear).

[blaenk]

First, obviously it doesn't make sense to choose names which are both "unofficial" and aren't any better at conveying an intuition. The point would be to achieve the latter wherever we can. If we can't, we should of course reconsider.

Of course, this is what I suggested, but I don't think it's as obvious as you make it out to be. It certainly doesn't seem settled or accepted yet, and given Rust's history for stringent consistency, I was approaching it from the perspective of forcing all "practical" names.

You yourself expressed uncertainty about this approach:

And while I agree that we shouldn't force "practical" names when we can't come up with any, having some traits follow one and others another naming convention in a seemingly haphazard way is also not most awesome. But it may still be the least worst thing.

As for the following:

Second, it's not as if this means that people would be left totally in the dark about the mathematical connections: the correspondence should be mentioned prominently in the documentation. ("This corresponds to the mathematical concept of a semigroup.")

I agree that this is how it should be done if we do it this way, but I definitely don't think that an offhanded comment likely to be ignored or forgotten by many people is the same as seeing the name throughout code, reinforcing the connection.

That said, I'm still open to judicious use of practical names, as I originally proposed, but I wanted to provide alternative arguments to motivate the discussion.

[ghost]

We should call things what they are, even if they don't mean much to the uninitiated. Isn't that why we have Guides for?

[brendanzab]

I am definitely in favor of exploring this.

We might want to lean in the direction of more approachable, "intuition-capturing", rather than more precise, mathematical names...

I would go with the standard names. Switching up with non-standard names just muddies the waters even more. Plus it would be an endless bikeshed... :(

This is interesting ground to explore, but as a general principle this is not the kind of thing we would toss into libstd right off the bat. - @aturon

Agreed. I would advocate keeping this issue open, but for @glaebhoerl to start whipping together a crate (glaebhoerl/control?) as part of the proposal. Then it will be easier for us to evaluate.

I would also recommend doing some commented out traits/impls for the things that require HKT so that we can start to get a feeling for what types might be able to take advantage of these things. (Are boxed types functors? I think @kmcallister needed that for his HTML lib).

[glaebhoerl]

Apparently @darinmorrison already wrote a library for semigroups.

(Edit: See also for more interesting prior art.)

[ghost]

@glaebhoerl I'm planning on extending that and building a monoid library and some other algebraic bits on top of it soon. I'm not sure if they'll fit what folks may have had in mind here but feedback is certainly welcome.

[thehydroimpulse]

Agree with @bjz. The standard names are known across languages and are fairly easy to learn about them. If we come up with Rust specific names, it would lead to a muddier field with utter confusion.

People with knowledge in this area will come by and see things like Combine and not know what the heck it is. And now they have to convolute their knowledge with multiple names for the same thing, Whereas if they see things like Semigroup or Applicative, they'll be able to jump right in without a problem.

[skeet70]

Came across kinder, thought it might be of interest to you if you hadn't seen it already.