feature request: `Compose` trait for strings and functions

[apoelstra]

As @huonw mentions in #14482, mathematical convention is that addition is commutative. The stdlib already follows mathematical convention in some cases (for example, Zero requires Add and is expected to be the additive identity; ditto for One and Mul).

Currently everything in the stdlib which implements Add implements add as a commutative operator, except for strings. Therefore I propose:

• Introduce a Compose trait with a compose function that sugars to the ++ operator.
• Implement this on String for concatenation, and Fn traits for composition (edit this actually doesn't make sense for functions that aren't A->B and B->C, never mind). This replaces add for String.
• Add "must be commutative" to the documentation for Add.
  This will help in writing generic code, since it is an (often unstated) assumption in many algorithms that + is a commutative operator. It'll also make analysis easier since programmers won't have to memorize that + means something different in rust than it does everywhere else.

It might also be worthwhile to add an empty() constructor to Compose to make it a monoid trait. Though as reem points out on IRC, Compose+Default is probably preferable as it is more explicit.

Edit: Perhaps this should be on discourse, but it's a very minor (though breaking) change that cleans up the API and doesn't remove any functionality, and doesn't have any room for bikeshedding that I see. Sorry if I'm wrong on this point.

[reem]

Not sure if this would be a good place to bring this up, but a good, generic replacement for Haskell's . would be really nice. Even this (which is basically Semigroup) doesn't apply to function composition, it would be good to have.

Of note, this does work for functions of A -> A or <B: Compose> A -> B.

[CloudiDust]

@apoelstra @reem

Personally I think this request is RFC-worthy and a function composition operator can be considered once unboxed closures are stabilized. (Though I am not sure if Rust needs a dedicated operator for that, as Haskell's “multi-arity” functions are all effectively unary, but Rust's are not.)

I don't like unifying both string concatenation and function composition under the same Compose trait. They are not the same thing after all. Especially, what does it mean to "compose" two strings?

I propose that we add two traits, Concat, which desugars to ++, and Compose, which desugars to +.. (Haskell special-cases ., while I'm fine with that, I don't expect Rust to do the same.)

[apoelstra]

@CloudiDust Strings are monoids under concatenation with identity ε; functions T->T are monoids under composition with identity id. They are algebraically the same operation. But I will submit an RFC since there is evidently some discussion to be had.

[pnkfelix]

Adding a new operator sugar is absolutely something that needs to go through the RFC process.

Here's the link: rfc process

[pnkfelix]

(closing as this needs to go through rfc process)

[pnkfelix]

see rust-lang/rfcs#203

[CloudiDust]

@apoelstra, I see, and I now suggest that we use Accumulate/accumulate as the trait/method name. Or Accum/accum if shorter names are desired.

Accumulate is better because both function composition and string concatenation can be described as an "accumulating" operation.

I get the inspiration from the Wikipedia article on monoid, especially the section "Monoids in computer science".