Important traits which don't need HKTs

View all comments

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.)

Start with the issue body and the linked Combine proposal in RFC pull request 203, then review the referenced Haskell monoid-subclasses and mono-traversable packages. A useful outcome would require a settled proposal for which traits to add, their ownership and mutability behavior, and naming; no implementation files or tests are identified.