Blog post series: Alternative type constructors and HKT

[arielb1]

Syntax is a big issue with “full HKT.” allowing the Self parameter of a trait to be higher kinded also presents a lot issues with method resolution. This is some of the downside of going “that far” on this language feature.

Haskell-style HKT would be a big addition to the complexity budget - it would require adding some notion of “proper type constructor”, as well as requiring a rather complicated notion of kinds, and I am not sure there is a good killer app for that.

[cramertj]

I just wanted to pop in to add my personal reason for wanting HKT. Currently, it’s a massive pain (where not impossible) for collections to be generic over reference types. I want an easy way to make a single struct that can use (make its own) pure stack-based references or Rc/Arc where the user needs it. I think that something like MyStruct<RcFamily> serves this case quite nicely, although it does introduce more boilerplate than something like MyStruct<Rc<_>>.

I think there’s quite a bit of confusion over the family pattern, but I feel like that confusion could mostly be avoided through careful documentation that RcFamily corresponds roughly to a type function like Rc<_>.

[Diggsey]

So AIUI, the problem is that any type, eg. Vec<u32>, may belong to multiple families (VecFamily, OwningFamily<[u32]>, the latter being a meta-family that might allow conversion between Box<[T]> and any other owning type, like Vec<T>)

When we’re writing generic code, we already think in terms of these families, but we don’t think to write them explicitly because to us it seems obvious from the context what our intentions were. However, the compiler cannot figure that out from the context.

To assist with that, we add eg. the Collection trait, which corresponds to a context in which one might be using Vec<u32>. So far, the Collection trait and Vec types seem no more than what is necessary, but the need to define an additional VecFamily type seems superfluous.

One possibility would be to add some syntax-sugar for declaring families, eg.

impl<T> Collection<T> for Vec<T> as VecFamily {
    type Family = VecFamily;
}

The compiler would automatically declare a type VecFamily corresponding to this trait implementation - it would automatically implement an ATC on VecFamily with the same generic arguments (T) as the trait being implemented.

eg.

struct VecFamily;
impl VecFamily {
    type Member<T> = Vec<T>;
}

Each Member corresponds exactly to a single concrete type covered by the impl block. In a more complicated example, the family itself might be generic:

impl<T, 'a> Fooable<T> for Bar<T, 'a> as BarTypeFamily<'a> { }

->

struct BarTypeFamily<'a>;
impl<'a> BarTypeFamily<'a> {
    type Member<T> = Bar<T, 'a>
}

In all cases, the compiler can automatically figure out what the Family definition should look like, and conceptually, it’s just a way to name a particular trait implementation. It doesn’t depend on the trait even having a Family associated type.

[lfairy]

Regarding the third post:

In Haskell, at least, if I have a HKT, that means I can apply this type constructor to any type and get a result. But all collections in Rust tend to apply some bounds on that. For example, Vec<T> and List<T> both (implicitly) require that T: Sized. Or, if you have HashMap<K,V>, you might consider it to be a collection of pairs (K, V), except that it only works if K: Hash + Eq + Sized and V: Sized.

So, really, if we did want to support a syntax like Foo<_>, we would actually need some way of constraining this _.

Have constraint kinds / “associated bounds” been considered as a solution to this problem?

I think this is an elegant way of getting around the constrained type parameter issue, while keeping the HKT system easy to use.

[RalfJung]

(and, since these are floats and hence + is not actually commutative, that implies the sum may well be different)

On an entirely unrelated nitpicky note… Floating point addition is actually commutative (as is multiplication), it is just not associative. At least that’s what I remember, and Wikipedia agrees.

Coming to the actual topic, I have to agree with the sentiment here: All this “family” encoding feels like manually doing lots of work that really the compiler should be doing for me. However, maybe there’s a good way to have some nice syntactic sugar take care of all this and make it look beautiful? After all, closures in Rust are also just an encoding and manually writing it would be doing work that the compiler should do for me… but then, we have a closure syntax that actually does make the compiler do the work for me and provides the proper abstraction of working with closures.

[nikomatsakis]

for<'a> &'a Self has that annoying side effect of requiring Self: 'static, which makes it much less useful.

One of the posts I want to write in this series – though really it’s an independent thing – are some thoughts on improving HRTB. Limitations like these can be overcome, I think.

[nikomatsakis]

On an entirely unrelated nitpicky note… Floating point addition is actually commutative (as is multiplication), it is just not associative. At least that’s what I remember, and Wikipedia agrees

D’oh, I meant to double check that.

[nikomatsakis]

So on the topic of whether families are “doing work the compiler should be doing for me”: I am certainly sympathetic, but also not. I am not quite sure how to order my thoughts yet on this topic, and I hope to get at it in more detail in a future post, but I’ll take a stab here. Anyway, here are some thoughts from reading the latest comments

On the question of HKT vs ATC

First, I second @nrc and @withoutboats in saying that I really want to get a better handle on the use cases for HKT independent of associated-type constructors. As @withoutboats and @Manishearth said, it seems like ATC is basically a no brainer: it’s a natural syntax, it fills a gap in the language.

In fact, when you consider that every method has a unique (unwritable, atm) type, we already have ATC. That is, if I have something like this:

trait Foo {
    fn bar<'a, T>(...);
}

The type of Foo::bar includes the 'a and T that you supply to a particular instantiation (at least, some of the time – sometimes the type of bar is higher-ranked; c.f. the distinction between early- and late-bound regions; I am still puzzling a bit over the connection between higher-ranked and higher-kinded =)

Whether families are a poor man’s HKT or what

On the one hand, the “family pattern” is definitely emulating HKT to some extent. On the other hand, it’s also more expressive than conventional HKT: for example, it can accommodate bounds. As I noted in the post, basically no types in Rust actually satisfy a kind like (type -> type), since most of them require something more like type: Sized -> type.

Having to add things like I<_> into the language is already adding complexity – and it hasn’t even addressed the need for bounds! Presumably we’d wind up writing things like for<K: Hash> I<K> or something at some point. We won’t want to repeat these things everywhere, so we’ll need to invent ways to factor out these signatures into independent declarations – at which point we are basically reinventing families. So it’s not clear to me that HKT is really going to be a win syntactically.

How often do we really want “true HKT” anyway?

But there is a separate question. Let’s assume that that we either don’t add HKT (in which case we use families) or we invent some syntax for HKT that expresses bounds – how often will we find ourselves wanting to abstract over type constructors anyway? In particular, how often will we want to abstract over a type constructor where you don’t have a specific instance around? (I’ll just use families in my examples, since they have a concrete syntax.)

That is, how often do you want to write functions or types that are generic over Vec but which do not have an argument or return type like Vec<T> (Vec for some specific T)? (After all, if you do, you then don’t really want a family, you just want a way to go from one kind of collection to another instance in that same family, which is less modeling overhead.)

But there’s another question that I’m also wrestling with. Collections are actually a really bad case for HKT, because they vary so wildly in the bounds that they impose. e.g., if I want to write some code that works for any set, the conditions to make a valid set will be different for hashsets and btreesets. It’ll be hard to accommodate this even in families. Consider this very simple attempt:

trait SetFamily {
    type Member<K>;
}

This is clearly wrong, since it imposes no conditions on K. So maybe we write:

trait SetFamily {
    type Member<K: Hash + Ord>;
}

Now both HashSet and BTreeSet can implement it, but it’s actually too strong for both of them! It’s hard to see what’s the right balance here, unless we let you abstract over trait bounds (and I’m not ready to go there).

I’m not sure what the answer is here! One pattern I was toying with was something like this, which actually doesn’t use either ATC or HKT, just HRTB that apply to types:

/// If you have `Foo: Set<T>`, then the type `Foo`  can act as a set of `U`.
trait Set<T> { /* methods for some paricular set */ }

/// If you have `Foo: SetApply<T, U>`, then not only is `Foo` a set of `U`,
/// but `<Foo as SetApply<T, U>::Member` is a set of `U` in the same "family".
trait SetConvert<T, U>: Set<T> {
    type Member: Set<U>;
}

impl<T: Hash, U: Hash> SetConvert<U> for HashSet<T> { ... }
impl<T: Ord, U: Ord> SetConvert<U> for BTreeSet<T> { ... }

(Probably I would actually use an associated type for the T in these examples, but whatever.)

Anyway, the key idea here is that we have pulled the new element type for the set (U) out into the trait. This is useful because it means that we can let the functions that are consuming the set specify the limits they wish to impose on their keys:

/// If you give specific types, this is most flexible for your caller:
/// they can pick any set type that can accommodate those two types.
fn floatify<S>(s: S) -> S::Member
    where S: SetConvert<i32, f32>

/// Or I can pick bounds. Here I say that you can use any kind of set,
/// as long as it can work with `Ord` types.
fn floatify<S>(s: S) -> S::Member
    where S: for<U: Ord> SetConvert<i32, U>

/// Or I can pick bounds. Here I say that you can use any kind of set,
/// as long as it can work with hash + ord types.
fn floatify<S>(s: S) -> S::Member
    where S: for<U: Hash+Ord> SetConvert<i32, U>

This seems to very much mirror the problems that HKT faces around collection types in general, no?

[fitzgen]

Hi everyone! I just want to double check that I am correctly following along with how ATCs would work.

Say I wanted to generalize Option::map and Result::map with a Functor trait. Using ATC and family traits, am I correct that this would look like the following?

pub trait FunctorFamily {
    type Member<T>: Functor<T>;
}

pub trait Functor<T> {
    type Family: FunctorFamily;

    fn map<F, U>(self, f: F) -> Self::Family::Member<U>
        where Self: Self::Family::Member<T>,
              F: FnOnce(T) -> U;
}

pub enum OptionFamily { }

impl FunctorFamily for OptionFamily {
    type Member<T>: Option<T>;
}

impl<T> Functor<T> for Option<T> {
    type Family: OptionFamily;

    fn map<F, U>(self, f: F) -> Self::Family::Member<U>
        where Self: Self::Family::Member<T>,
              F: FnOnce(T) -> U
    {
        match self {
            Some(t) => Some(f(t))
            None => None,
        }
    }
}

Alternatively, we could collapse the family into the Functor trait itself, right?

pub trait Functor {
    type Context<V>;

    fn map<F, T, U>(self, f: F) -> Context<U>
        where Self: Self::Context<T>,
              F: FnOnce(T) -> U;
}

impl<T> Functor for Option<T> {
    type Context<V> = Option<V>;

    fn map<F, U>(self, f: F) -> Self::Context<U>
        where Self: Self::Context<T>,
              F: FnOnce(T) -> U
    {
        match self {
            Some(t) => Some(f(t))
            None => None,
        }
    }
}

Is this also correct?

Thanks!

[withoutboats]

That definition is interesting. There are a few problems:

• The function should probably be FnMut.
• The trait/impl definitions differ in where the T variable is introduced. You seem to need the trait to be defined Functor<T>. This is why the family solution is more closely equivalent to “HKT” - a FunctorFamily is equivalent to the Functor type class in Haskell, whereas this is not.
• You have a trait bound where you actually want a type equality bound Self = Self::Context<T>. This bound is very interesting because it applies an equality constraint to the self type; I don’t think this is supported right now & I’m not sure what problem it presents.

This seems to be the “right” definition of the single trait form:

pub trait Functor<T> where Self = Self::Context<T> {
    type Context<V>;

    fn map<F, U>(self, f: F) -> Self::Context<U> where F: FnMut(T) -> U;
}

[fitzgen]

Thanks for your response! Very elucidating

You have a trait bound where you actually want a type equality bound Self = Self::Context<T>.

Ah, of course, that makes perfect sense.

it applies an equality constraint to the self type

If Functor::map were a static method, we could avoid this, but then it doesn’t match Option::map and Result::map.

[withoutboats]

If Functor::map were a static method, we could avoid this, but then it doesn’t match Option::map and Result::map.

Yep. This touches on some of the problems with traits which want a higher kinded self parameter.

[Ericson2314]

unless we let you abstract over trait bounds (and I’m not ready to go there).

Say we conflate bounds with the kind of types that implement them, so we have awkward subkinds, but don’t need abstracted bounds? This also solves the syntax problem where T: Trait + <type, lifetime> -> type + Trait is ok (+ intersects kinds).

More broadly, don’t we run into the same Hash problems with ATC families? So its a little unfair to blame HKT for this? I want a good collection hierarchy, and am willing to “pay” a lot for it. If that means PolyKinds + subkinds, with either ATC or HKT, so be it.

[nikomatsakis]

You have a trait bound where you actually want a type equality bound Self = Self::Context<T>. This bound is very interesting because it applies an equality constraint to the self type; I don’t think this is supported right now & I’m not sure what problem it presents.

Yeah – so I’ve been slowly building up some ideas around this (and other parts of the trait system). I think we likely can eventually support such equality constraints, but it definitely adds another orthogonal wrench into things. =)

(The basic name for this problem is congruence closure, and there are good algorithms for solving it, but combining them properly with other kinds of inference is something I’ve not fully put together in my brain.)

[nikomatsakis]

More broadly, don’t we run into the same Hash problems with ATC families? So its a little unfair to blame HKT for this? I want a good collection hierarchy, and am willing to “pay” a lot for it. If that means PolyKinds + subkinds, with either ATC or HKT, so be it.

I tried to avoid blaming HKT for that. I do not blame HKT. But what I think is that, in order to deal with that problem, you will wind up with various declarations and traits and so forth that start to look a lot like families, such that the extra cost of using ATC (rather than HKT) is small.

[nikomatsakis]

I just posted a new post: This post considers what it might mean if we had both ATC and HKT in the language: in particular, whether those two concepts can be unified, and at what cost.

[sgrif]

Can you elaborate on why the “must use all parameters exactly once in the first position” rule is needed and/or good? It would kill several of the use cases that I would want to use ATCs for. For example, wanting to be able to write:

impl Identifiable for User {
    type Id<'a> = &'a Uuid;

    fn id<'a>(&'a self) -> Self::Id<'a> {
        &self.id
    }
}

as well as

impl Identifiable for JoinTable {
    type Id<'a> = (&'a Uuid, &'a Uuid);

    fn id<'a>(&'a self) -> Self::Id<'a> {
        (&self.parent1_id, &self.parent2_id)
   }
}

and also

impl Identifiable for Post {
    type Id<'a> = i32;

    fn id<'a>(&'a self) -> Self::Id<'a> {
        self.id
    }
}

The rule would disallow the second and third impls both of which would be extremely useful to write.

[nikomatsakis]

Can you elaborate on why the “must use all parameters exactly once in the first position” rule is needed and/or good?

I don’t contend that it is good.

However, it – or perhaps some other constraint – would be needed if we wanted to ensure that <T as Iterable>::Iter was a “higher-kinded thing”. What this means is that one would be able to do something like this:

fn foo<C: Iterable>(x: T<'a>) -> T<'b> {
    bar::<C::Iter>(...)
//        ^^^^^^^ here, even though we don't know what C is,
//        we know that C::Iter has kind `lifetime -> type`
}

fn bar<T<'_>>(...) {
//       ^^ my notation that means T has kind (lifetime -> type)
    ...
}

The key point here is that at times we will have to infer what the value of T is. And if you want this to work, you need some constraints over what kind of “type lambdas” we can support. I talked about this in more detail in the third post in the “decidability and inference” section.

[nikomatsakis]

However, it – or perhaps some other constraint – would be needed if we wanted to ensure that <T as Iterable>::Iter was a “higher-kinded thing”.

What I was trying to say in my conclusion, just to be clear, is that I personally don’t believe that having the notion of a “higher-kinded type” as part of the type system is worthwhile. I feel the family system has advantages and is “good enough”. But I still think it’s worth elaborating out more use cases and feeling our way through this, I don’t claim this to be a final conclusion.

[chpio]

all four blog posts as ebook (epub)

edit: i don’t get why Calibre is able to show the TOC, but my ebook reader is not.