Your Family Tree

This code would work just fine, but it has some interesting properties that we may not have expected. In particular, floatify can convert any collection of integers into any collection of floats, but those collections can be of totally different types. For example, I could convert from a List to a Vec like so:

fn foo(x: &List) -> f32 { let y: Vec = floatify(x); // ^^^^^^^^ notice the type annotation y.iterate.sum }

This is more flexible, which is good, but also has some downsides. For example, that same flexibility can make type inference harder. To see what I mean, imagine that I wanted to remove the Vec type annotation from the variable y, like so:

fn foo(x: &List) -> f32 { let y = floatify(x); // ^ error: type not constrained! y.iterate.sum }

This would not compile, because we don’t have enough information to figure out the type of y! In particular, we know that y is a “collection of f32 values”, but we don’t know what kind of collection. It is a Vec or List? Obviously it makes a difference to the semantics of our code, since vectors add items onto the end, and lists add things onto the beginning, so the order of iterator is going to be different (and, since these are floats and hence + is not actually commutative, that implies the sum may well be different). So the compiler doesn’t want to just guess.

So maybe we’d like to say that floatify takes and returns a collection of the same type. It turns out we can’t do that with just the Collection trait we’ve seen so far. Essentially, the signature that we would want is maybe something like this (ignoring the where clauses for now):

fn floatify_hkt(ints: &I) -> I // ^^^^^^ wait up, what is `I` here?

But woah, what is this I thing here? It’s not a type parameter in the normal sense, since it doesn’t represent a type like Vec or List. Instead it represents a kind of “partial type”, like Vec or List, where the the element type is not yet specified. Or, as type theorists like to call it, a “higher-kinded type” (HKT). I’ll get into why it’s called that, and more about how such a thing might work, in the next post. For this post, I want to focus on an alternative solution, one that doesn’t require HKT at all.

Introducing type families

So let’s assume that type parameters still just represent plain old types – in that case, is it possible to write a version of floatify that returns a collection of the same “sort” as its input?

It turns out you can do it, but you need an extra trait. We already saw the Collection trait before; we’d want to add a second trait, let’s call it CollectionFamily, that lets us go from a “collection family” (e.g., Vec) to a specific collection (e.g., Vec):

trait CollectionFamily { type Member: Collection; }

A “collection family” corresponds to a ‘family’ of collections, like Vec or List. We’re also going to need then some dummy types to use for implementing this trait:

struct VecFamily; impl CollectionFamily for VecFamily { type Member = Vec; } struct ListFamily; impl CollectionFamily for ListFamily { type Member = List; }

Note: While writing this post I realized that Haskell also has a feature called “associated type families”. Those are certainly related to the things I am talking about here, but I am not trying to model that Haskell feature, and my use of the term “family” is independent.

Families and inference

OK, so now we have the idea of a “collection family”. You might think then that we can now rewrite floatify like so:

fn floatify_family(ints: &F::Collection) -> F::Collection where F: CollectionFamily { let mut floats = F::Coll::empty; for &f in c.iterate { floats.add(f as f32); } floats }

Whereas before the type parameters represented specific collection types, now we take a type parameter F that represents an entire family of collection types. Then we can can use F::Collection to name “the collection in the family F whose item type is i32”.

This type signature for floatify_family works, but let’s see what happens now for our caller:

fn foo(x: &List) -> f32 { let y = floatify_family::(x); // ^^^^^^^^^^ wait, what? y.iterate.sum }

It turns out that there is good and bad news. The good news is that, once we know the family, we can indeed infer the type of y. The bad news is that, at least with the setup we have so far, we can’t actually infer the type of the family! That is, the floatify_family:: annotation turns out to be required! To see why, let’s look again at the signature of floatify_family

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