Higher-kinded types: the difference between giving up, and moving forward

language design
1

http://typelevel.org/blog/2016/08/21/hkts-moving-forward.html

A very good read about the motivation and utility of HKTs, as implemented in Scala.

5 Likes
2

This is a good overview of the utility of higher kinded polymorphism in languages like Scala and Haskell. I think however the most important insight when considering this feature in regard to Rust is the contrast between what this blog post points out and what is true about Rust.

All flatMaps are the same

In Rust, this isn't true! Let's look at the flat_maps on Option, Result, Iterator, and Future:

// Option
fn and_then<U, F>(self, f: F) -> Option<U> where F: FnOnce(T) -> Option<U>;
// Result
fn and_then<U, F>(self, op: F) -> Result<U, E> where F: FnOnce(T) -> Result<U, E>;
// Iterator
fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F>
    where F: FnMut(Self::Item) -> U,
          U: IntoIterator;
// Future
fn and_then<F, B>(self, f: F) -> AndThen<Self, B, F>
    where F: FnOnce(Self::Item) -> B,
          B: IntoFuture<Error=Self::Error>,
          Self: Sized;

These are not the same type signature at all (except for Option and Result). I am at a loss as to how these could usefully abstracted. I worry that Rust's low level aspects makes its types too 'leaky' about memory layout and state for higher kinded polymorphism to be all that useful.

13 Likes
3

There also a matter of understanding your language. I think most programmers are able (or have the time and focus) to understand a language as Python, but the more complexity you add to your language, the less casual programmers will want to use it. This isn’t enough to rule out HKTs for Rust, but it’s a cost worth keeping in mind.

Edit: for lot of people “giving up” is generally a negative thing, so this is a bad title for the article, because tries to mix a gut feeling where you should use technical considerations and balance. “Going forward” too has costs and disadvantages.

5 Likes
4

The critical thing to note here is that Option<T> and Result<T, E> are types, while Iterator and Future are traits, which explains why it would work straightforwardly for Option and Result but why it doesn't appear to work for Iterator and Future. If the return types on Iterator::flat_map and Future::and_then were written using the proposed -> impl Trait syntax (i.e. I return some unspecified type that implements this trait), they would look like -> impl Iterator<Item=U::Item> and -> impl Future<Item=B::Item>, respectively. If -> impl Trait was usable in traits, then I guess we'd need higher-kinded traits too in order to provide a maximally generic flat_map? The fact that types and traits are distinct in Rust makes this kinda tricky.

However, my experience shows that higher-kinded polymorphism will be more useful for type constructors taking lifetime arguments, rather than type arguments. I have answered three questions on Stack Overflow where somebody tried to write generic code that didn't work because they needed type constructors parameterized on a lifetime argument. Here they are:

So if Rust implements higher-kinded types, it should minimally support type constructors with lifetime parameters; type constructors with type parameters would be a bonus.

10 Likes
5

Yes, the fact that Iterator and Future are traits is a fundamental part of why these functions have different signatures. But what you suggest after that is not feasible, as far as I know - even if the specific FlatMap struct were obscured by impl Iterator<Item=U::Item>, you can’t validly abstract between that and Option, because impl Iterator<Item=U::Item> and the receiver type of any Iterator impl have different type constructors.

The second part of your comment I agree with wholeheartedly. Dancing with lifetimes is where higher kindedness and higher rank both become very obviously important. Thanks for posting those StackOverflow links, they’re all use cases that ideally Rust would support.

1 Like
6

Sometimes I’m kind of worried that HKT will forever be low priority. Yes, we won’t be able to copy others’ interface hierarchy’s abstractions verbatum, but @FraGag’s points show a way forward. And we won’t be able to even try abstracting this stuff until HKT lands.

4 Likes
7

While HKT alone probably won't solve the issue with the high-level abstractions like Functor or Monad, it has other uses that are arguably much more relevant for Rust and not nearly as much in other languages.

A big source of code duplication comes from the inability to abstract over mutability, ownership, and containers:

  • It's very difficult to write a function agnostic to mutability, so that's why you see foo(&self) -> &X and foo_mut(&mut self) -> &mut self all over the place.
  • More generally, it's hard to write functions that are agnostic in ownership: &T, &mut T, Box<T>, Rc<T>, Arc<T>. This issue shows up in GitHub - Kimundi/owning-ref-rs: A library for creating references that carry their owner with them.
  • And even more generally, it's hard to write data types that are container-agnostic, e.g. enum Wrapper<F> { U32(F<u32>), String(F<String>), ... }.

All of these require HKT for their full expressiveness (plus some syntactic sugar, perhaps). There's kludgy ways to work around these problems, but ultimately the lack of for<T> (equivalent in power to HKTs) causes all kinds of trait constraints to eventually bubble up to the end user, including any that might be private implementation details.

(The inability to abstract over lifetimes through HKT is not nearly as severe of a problem because for<'a> already exists and works, modulo bugs and ergonomics.)

6 Likes
8

As the author of rental, I have to say I strongly agree with this. I’ve done a lot of thinking lately about what the core motivation behind self-referential structs, and by extension rental, really is. In nearly every use case of it I’ve seen, the goal is to change the ownership semantic between two types.

Since rust currently does not allow this to be abstracted, an API must choose up front which ownership semantic it imposes. Choosing borrowing is the most performant, but imposes design limitations that may be incompatible with your planned use. The only way to circumvent this currently is to erase the lifetime relationship with something like owning-ref or rental. If there were a mechanism by which this could be chosen as a type parameter, there would be no need to bludgeon the type system to achieve it.

Naturally it still requires APIs to choose to provide that abstraction, but it would at least be possible at all, and ecosystem pressure could drive adoption.

4 Likes
9

For this case, a type parameter X: Borrow<T> (or X: BorrowMut<T> if you need to mutate the value) should work fine. If you don't actually need ownership, but want to let the user transfer ownership to you because it's more convenient for them, Borrow and BorrowMut let you do this. T also implements Borrow<T>, so Borrow is a bit more flexible than AsRef in this regard. And since you wanted to accept a reference in the first place, then the T type is not an implementation detail, because it would have been part of the public API, so switching to Borrow generally doesn't reveal anything new. Unless you're doing dirty tricks like Chars does (you construct it from a &str, but it stores a slice::Iter<'a, u8>).

10

But, for example, this all falls apart when you use UniCase, since AFAICT, Borrow can’t be implemented for UniCase<String>.

11

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.