#generic #traits #standard #hkt #experimental #framework #iterator

generic-std

Experimental HKT framework and generic traits for the standard library

1 unstable release

0.1.0 Aug 22, 2020

#8 in #hkt

MIT license

18KB
358 lines

Standard generic traits.

Why

Did you ever need a generic Sequence trait? Ever wanted a data structure that was generic over either Rc or Arc? An iterator that returns borrowed data?

These are not usually thought to be possible in stable Rust due to lack of native support for higher-kinded types (HKTs). HKTs is a feature that would allow us to reason about, say, Vec without fully defining it with type arguments (Vec<T>). The classic example that is usually thought impossible is the streaming (or borrowing) iterator, where next() returns an item wih a lifetime bound by the iterator itself:

trait StreamingIterator {
  type Item = &str;
  fn next<'a>(&'a mut self) -> Option<&'a str> {
    unimplemented!()
  }
}

This does not compile because the reference &str must be declared with a lifetime, but we only have the lifetime for self in next() itself and not in the associated type declaration. Unlike type aliases, associated types (type in a trait) cannot have type arguments. That is, the following is not valid:

trait StreamingIterator {
  type Item<'a> = &'a str;
  fn next<'a>(&'a mut self) -> Option<&'a str> {
    unimplemented!()
  }
}

This is called an associated type constructor. For more information, see the RFC and Nicholas' ATC post series.

However, it is possible to emulate this behaviour in stable Rust with more boilerplate. See the StreamingIterator trait.

How

This library implements multiple generic traits for std types using a variation of Edmund Smith's method to emulate higher-kinded types. See the plug module for details.

Limitations

HKT for types seems to be complete using the plug method. That is, any functionality you could get with native HKT support for types, you can get with this method. Ergonomy is not great though, even if it works.

There are limitations regarding HKT lifetimes due to the fact that is impossible to put bounds on HRTB lifetimes. That is, something like for<'a: 'b> is inexpressible. As a result some traits and impls may have more restrictive lifetime bounds than necessary.

Current Status

This crate is highly experimental and many traits have limited functionality.

No runtime deps