Niko, in your 3rd blog entry, you describe HKT versus ATCs as having their own tradeoffs and expressiveness potential. Specifically you describe the bounds requirements of hashsets and the non-genericity of bitsets. This reminds me of a similar problem that’s already been solved before in Rust: having a hierarchy of traits to model increasing amounts of “power”. The closure hierarchy of FnOnce, FnMut, and Fn is elegant and has proven to be very useful in Rust because people choose how much flexibility they need based on the problem at hand. For bitsets and Collections vs. HKTCollections, we find the same kind of choice. Let me proceed with some arbitrary definitions: the largest group of types we want to have methods for are things that are “Collections” over some (single) type. These can return iterators, add to their collection, create new empty collections, etc. A subset of these collection types are “Containers”, collections that are capable of holding many different kinds of types and are not bound to any particular one. These have the ability to map over them functor style, implement your floatify function in your second blog post, and most importantly do not require excessive type annotations to constrain the polymorphism/inference.
So if we think of HKTs as being a small improvement to ACTs, we can come up with this hierarchy:
// Collection trait
trait Collection<T> {
// create an empty collection of this type:
fn empty() -> Self;
// add `value` to this collection in some way:
fn add(&mut self, value: T);
// iterate over this collection:
fn iterate(&'a self) -> Self::Iter<'a>;
// the type of an iterator for this collection (e.g., `ListIter`)
type Iter<'a>: Iterator<Item=T>;
}
// "A collection that can contain many different types"
// I take some liberty here with the syntax
trait Container where Self<_>, for<T> Self<T> : Collection<T> {
...
}
impl Collection<usize> for BitSet { ... }
impl<T> Collection<T> for Vec<T> { ... }
impl Container for Vec { ... }
Etc.
Orthogonal consideration: you mentioned hashsets. Two people also mentioned constraint kinds / “associated bounds” as a solution. This seems like a pretty big leap in complexity but is certainly as intuitive as associated types are. In fact, because of Rust’s handy “default values for associated types”, this complexity is totally transparent to users until they need or want the power. Again, I take liberties with the syntax here:
trait Container<trait C = Id> where
Self<_>, for<T: C> Self<T> : Collection<T> {
...
}
impl<T: Hash> Collection<T> for HashSet<T> { ... }
impl Container<Hash> for HashSet { ... }
Where Id is a new built in trait auto-implemented for everything and means nothing (similar to the Id wrapper type as commonly used in Haskell). In essence: if you don’t specify a trait, there is no trait requirement (I would expect this pattern a lot). That particular pattern is also backwards compatible.
I think this is very elegant!
