Blog post series: Alternative type constructors and HKT

[steven099]

I think that

self.cell.next = Some(Box::new(cell));

should be

self.cell = Some(Box::new(cell));

As for the type lambda issue, the problem with allowing arbitrary type lambdas is with inference. If I have

trait<*> HKT { ... }
struct Pair<A, B>(A, B);

impl<T> HKT for<U> Pair<T, U> { ... }
impl<T> HKT for<U> Pair<U, T> { ... }

fn function<T: HKT, U>(t: T<U>) { ... }

...

function(Pair(3, "three"));

how do you infer which impl to use?

[gnzlbg]

and you can accidentally describe types which are non-terminating programs.

Is this bad? I mean, Rust has already better features for doing meta-programming than ATC, so while type shenanigans will obviously play with this because it’s FUN, a recursion limit should be enough to catch these accidental errors at compile-time for most users.

[nikomatsakis]

But Rust’s type system has been Turing complete for ages (and it gets easier with specialization); you just have to use different encodings, typically involving associated types.

While true, this is not especially relevant. It’s certainly true that one can build complex things that the will cause associated type resolution to never terminate (or, more accurately, overflow). The problem, which I’ll get into in detail in the third post of the series, has more to do with inference and the limitations around it. That is, if you want to support HKT (and not just ATC, which can easily model HKT but is not the same thing), then you need to worry about higher-order unification. Basically equality constraints like ?T<?U> = Rc<i32>. You want to avoid the case where those constraints are never – or very rarely – solvable, and you can only do that by restricting the kinds of “functions” that ?T can be.

Now, it’s not that ATC doesn’t encounter the problem at all. In fact, in the second post (which I just posted), we already encounter the problem when we are modeling HKT using families. But it plays out differently and more explicitly, and can be solved by using the right design pattern to steer type inference. In contrast, when you have a normal HKT system, the user is not able to control type inference in the same way. (Or at least I don’t see how you could, happy to be enlightened!)

[nikomatsakis]

Next post is up, covering the ‘family trait pattern’. This allows you to model HKT using ATC.

[nikomatsakis]

I think this restriction would be unfortunate

I’m not sure if it’s tenable, to be honest. I also don’t know that I ever care to have “true” HKT. For reasons I’ll elaborate on in the 3rd post, it’s not clear to me that it’s a good fit for Rust, and it doesn’t add any expressiveness (as you can see in the current post =).

[nikomatsakis]

Just imagine it was the iterator that results from into_iterator instead (I should patch up the post; didn’t have time today).

Actually, rewriting to use into_iterator isn’t as interesting, since you don’t need the lifetime at all then of course. Ah well I guess the “narrative flow” of the blog post just has to be altered. Spoils a nice surprise, but doesn’t change the basic facts at play. =)

[BruceIV]

Is the second CollectionFamily trait actually necessary, or could it just be collapsed into an associated type constructor on the Collection trait?

trait Collection<T> {
    // ...
    type SelfCollection<S>: Collection<S>;
}

impl Collection<T> for Vec<T> {
    // ...
    type SelfCollection<S> = Vec<S>;
}

[nikomatsakis]

Is the second CollectionFamily trait actually necessary, or could it just be collapsed into an associated type constructor on the Collection trait?

It is not necessary. I wanted to separate out the idea of a “family of collections” as a distinct concept, since it maps well to HKT, but maybe it would have been simpler to start with an Other<U> sort of thing.

Interestingly, I suspect we would want neither of these in practice – at least not for collections. This is because collections often place bounds on their members (e.g., that they must be hashable). So something like you proposed:

trait Collection<T> {
    // ...
    type SelfCollection<S>: Collection<S>;
}

couldn’t be implemented by HashSet<K>, because it would need type SelfCollection<S: Hash>. The same is true for collection families. I will get into this a bit more in the upcoming posts…

[cuviper]

fn floatify_family<F>(ints: &F::Collection<i32>) -> F::Collection<f32>
    where F: CollectionFamily

Typo - I think those should be F::Member.

I was also wondering why you need a separate trait. And if things like S: Hash are an issue either way, is there any advantage at all for a family trait? Or did you just like how it compares to HKT?

trait Collection<T> {
    // ...
    type SelfCollection<S>: Collection<S>;
}

It seems to me that once you have this self-referential ATC, then you could basically go ahead and use that as desugaring for fn floatify_hkt<I>(ints: &I<i32>) -> I<f32>. That is, using I in HKT style desugars into some implicit I::Self<T> ATC.

[nikomatsakis]

I was also wondering why you need a separate trait. And if things like S: Hash are an issue either way, is there any advantage at all for a family trait? Or did you just like how it compares to HKT?

Probably it wouldn’t make sense for collection (if, indeed, anything would). I think it came to mind mostly because of the direct mapping to HKT.

I think there are a few things where a “family-like” trait might make sense. One thing might be to group together a bunch of related types.

Another is if you want to let people customize how you work internally, but you don’t expose those types at the interface. i.e., instead of taking or returning a collection, you are just using it internally, and you want people to be able to choose whether you use a Vec or a List (for some reason…)

Or maybe something like:

trait SharedBoxFamily {
    type Member<T>: Clone + Deref<Target=T>;
}

struct RcFamily;
impl SharedBoxFamily for RcFamily {
     type Member<T> = Rc<T>;
}

struct ArcFamily;
impl SharedBoxFamily for ArcFamily {
     type Shared<T> = Arc<T>;
}

Then I can have a tree that is parameterized over a SharedBoxFamily:

struct MyTree<F: SharedBoxFamily> {
    node: F::Member<MyTreeData<F>>
}

struct MyTreeData<F: SharedBoxFamily> {
    data: usize,
    left: Option<MyTree<F>>,
    right: Option<MyTree<F>>,
}

type RcTree = MyTree<RcFamily>;
type ArcTree = MyTree<ArcFamily>;

If you didn’t have a family trait here, those type aliases would be:

type RcTree = MyTree<Rc<()>>;
type ArcTree = MyTree<Arc<()>>;

where the () in Rc<()> is just a “dummy type” that we don’t really use.

[bluss]

The family pattern also looks like a warning sign — ”this is what the boilerplate will be everywhere if there is no real HKT”.

[kornel]

This is too complex for me.

I’m already finding Rust requiring too much too specific declarations. I’m already irritated that lots of things look like <This>, but have subtly different meaning depending on their position. The proposal adds yet another syntactically subtly different variant of declaring types/lifetimes/generics

impl … { 
    fn iterate<'iter>(&'iter self) -> ListIter<'iter, T> {
        self.iter()
    }
    
    type Iter = ListIter<'iter, T>;
    //                   ^^^^^ oh, wait, this is not in scope!
}

I’d love if you could make that “oh wait” part work instead. Make it in scope (i.e. let Rust figure out that it matches fn iterate<'iter> and that is what I’ve meant).

[troplin]

Next post is up, covering the ‘family trait pattern’. This allows you to model HKT using ATC.

I’m a bit torn about this.

On one side, this is actually HKT but just in one very specific place (Associated types). That means that wherever you want HKT, you have to bend everything until you can use an associated type.

OTOH, ATCs seem a really natural extension. The syntax is kind of obvious because there already exist non-associated type aliases.

[troplin]

I’d love if you could make that “oh wait” part work instead. Make it in scope (i.e. let Rust figure out that it matches fn iterate<'iter> and that is what I’ve meant).

How would this work? If you write generic code, you just see the generic signature:

fn iterate(&self) -> Self::Iter;

How would you know about 'iter?

[cgag]

Missing word here: “can’t actually infer the of the family”.

I’m confused as to why you can’t infer List<32> when the caller annotated it with ListFamily. I’ll keep reading but I want to take notes as I go: it seems like you know you need a Family, you were told it’s a ListFamily, and the only way to get a collection from ListFamily is with List.

I was also confused by the issue steven99 pointed out with the linked list prepend impl.

[kornel]

fn iterate(&self) -> Self::Iter;

How would you know about 'iter?

Can it be inferred/elided?

Alternatively, can the compiler say exactly what I should write here? (rather than fail with a generic error like "can’t infer lifetime for Iter").

[troplin]

Can it be inferred/elided?

Let’s for one moment forget about associated types.

struct S1;
struct S2<'a>;

impl S1 {
    fn function_1(&self) -> S1 { ... }
    fn function_2<'a>(&'a self) -> S2<'a> { ... }
}

function_1 and function_2 quite different as the second one keeps the self borrowed, while the first one does not.

The same way, the following traits are different:

trait Collection1<T> {
    fn iterate(&self) -> Self::Iter;
    type Iter: Iterator<Item=T>;
}

trait Collection2<T> {
    fn iterate<'iter>(&'iter self) -> Self::Iter<'iter>;
    type Iter<'iter>: Iterator<Item=T>;
}

The trait methods themselves have different signatures. The impls are actually completely irrelevant to this.

[kornel]

The same way, the following traits are different:

…

I see they’d be different if Iterator didn’t have a lifetime argument. But as far as I understand, because of the lifetime they’re only different in a way that one works, and the other doesn’t:

trait Collection1<T> {
    fn iterate(&self) -> Self::Iter;
    type Iter: Iterator<'missing_lifetime_error, Item=T>;
}

trait Collection2<T> {
    fn iterate<'iter>(&'iter self) -> Self::Iter<'iter>;
    type Iter<'iter>: Iterator<'iter, Item=T>;
}

So could Collection2 be made to work without explicit <'iter> in so many places? Some sort of lifetime elision/inference?

[AaronFriel]

Where you write

Linking collections and families

To make inference work, then, we really need a “backlink” from Collection to CollectionFamily. This lets us go from a specific collection type to its family:

I believe this is just injectivity. You want “trait families” to be injective, which would create an “automatic” back-link without having to place an additional “back link” in your type. You probably want injectivity by default, I’m not sure where you would not want it to be injective.

Am I wrong here? Is there ever a case, in Rust’s type system, you wouldn’t want the default to be injective?

[AaronFriel]

I would agree with the above, however, that the syntax seems exceptionally, uhm, clumsy compared to languages that do have HKTs.

This For<T> and bending everything to go through associated types and associated type constructors seems like a kludge.