Trait higher_kinded_types::ForLifetime

pub trait ForLifetime: Sealed {
    type Of<'lt>;
}

The main trait of the crate. The one expressing : <'_>-genericity.

It is expected to be used as a bound on a <T> generic parameter, thereby resulting in a <T : ForLt> generic API, which, conceptually / sort to speak, is to be read as <T : <'_>>.

That is, a generic API whose generic parameter is, in and of itself, generic too!

• Such a “generic-generic API” is dubbed higher-kinded, which makes a type such as struct Example<T: <'_>> then be dubbed higher-kinded type, or HKT, for short.

  From there, the whole concept of expressing genericity over : <'_>-generic types can also be associated with the idea and concept of higher-kinded types, much like the name of this crate indicates.

  So, using this HKT terminology for something other than a type taking a : For-bounded generic type is, if we are to be pedantic¹ about the topic, an abuse of terminology (one which I’ll probably make throughout this documentation).

It cannot be manually implemented: the only types implementing this trait are the ones produced by the ForLt! macro.

HKT Usage

1. Make your API take a generic <T : ForLifetime> parameter (conceptually, a <T : Ofᐸᑊ_ᐳ> parameter).

   Congratulations, you now have a higher-kinded API: your API is not only generic, but it is also taking a parameter which is, in turn, generic.

2. Callers

   Call sites use the ForLt! macro to produce a type which they can and must turbofish to such APIs. For instance:

   • ForLt!(&str) for the pervasive reference case (which could also use the ForRef<str> type alias to avoid the macro),

     or ForLt!(Cow<'_, str>) for more complex lifetime-infected types;

   • ForLt!(u8) or other owned types work too: it is not mandatory, at the call-site, to be lifetime-infected, it is just possible (maximally flexible API). See ForFixed.

3. Callee/API author

   Make use of this nested genericity in your API!

   Feed, somewhere, a lifetime parameter to this T:

   T::Of<'some_lifetime_param>

   There are two situations where this is handy:

   • wanting to feed two different lifetimes to T:

     use ::higher_kinded_types::ForLifetime;
     
     struct Example<'a, 'b, T : ForLifetime> {
         a: T::Of<'a>,
         b: T::Of<'b>,
     }

   • wanting to “feed a lifetime later” / to feed a for<>-quantified lifetime to your impl ForLt type:

     use ::higher_kinded_types::ForLifetime as Ofᐸᑊ_ᐳ; // hopefully illustrative renaming.
     
     fn slice_sort_by_key<Item, Key : Ofᐸᑊ_ᐳ> (
         items: &'_ mut [Item],
         mut get_key: impl FnMut(&'_ Item) -> Key::Of<'_>,
     )

     Full example:

     Click to show

     use ::higher_kinded_types::ForLt;
     
     fn slice_sort_by_key<Item, Key : ForLt> (
         items: &'_ mut [Item],
         mut get_key: impl for<'it> FnMut(&'it Item) -> Key::Of<'it>,
     )
     where
         for<'it> Key::Of<'it> : Ord,
     {
         items.sort_by(|a: &'_ Item, b: &'_ Item| <Key::Of<'_>>::cmp(
             &get_key(a),
             &get_key(b),
         ))
     }
     
     // Demo:
     let clients: &mut [Client] = // …;
     
     slice_sort_by_key::<_, ForLt!(&str)>(clients, |c| &c.key); // ✅
     
     // Important: owned case works too!
     slice_sort_by_key::<_, ForLt!(u8)>(clients, |c| c.version); // ✅
     
     // But the classic `sort_by_key` stdlib API fails, since it does not use HKTs:
     clients.sort_by_key(|c| &c.key); // ❌ Error: cannot infer an appropriate lifetime for autoref due to conflicting requirements

Wait a moment; this is just a GAT! Why are you talking of HKTs?

Indeed, the definition of the ForLt trait is basically that of a trait featuring the simplest possible GAT:

trait Trait { // basic trait
    type Assoc<'lt>; // Associated Type which is itself Generic = GAT.
}

struct Struct<'a, 'b, T : Trait> {
    a: T::Assoc<'a>,
    b: T::Assoc<'b>,
}

Yes, the : <'_> signature pattern of HKTs, and GATs, from this point of view, are quite interchangeable:

• this whole crate is a demonstration of featuring : <'_> HKT idioms through a ForLt GAT trait (+ some extra for<>-quantifications);

• in a world with HKTs and : <'_> as a first-class construct, GATs could then just be HKT Associated Types (HATs instead of GATs 🤠).

  //! pseudo-code!
  trait LendingIterator {
      type Item: <'_>;
  
      fn next(&mut self) -> Self::Item<'_>;
  }

  • Real code:

    Click to show

    use ::higher_kinded_types::ForLt;
    
    trait LendingIterator {
        /// Look ma, "no" GATs!
        type Item: ForLt;
    
        fn next(&mut self) -> <Self::Item as ForLt>::Of<'_>;
    }

In a way, the similarity between these two paradigms is akin to that of closure vs. object in more classic programming: you can always pick some canonical object interface, say:

trait Closure<Args> {
    type Ret;

    fn call(&self, _: Args) -> Self::Ret;
}

and then use Closure<Args, Ret = …> where we currently use Fn(Args…) -> Output: that is, the canonical Fn… traits can easily be polyfilled with any arbitrary trait of our choice featuring the same functional API (same method signature).

or, vice versa, never define custom traits or interfaces, and always use closures:

trait Display = Fn(&mut fmt::Formatter<'_>) -> fmt::Result;
// etc.

• The astute reader may notice that we lose the nominal typing aspect of our current traits, which is what lets us, for instance, distinguish between Display and Debug, even if both traits, structurally, are equivalent / have exactly the same function signature.

  • In general, Rust traits go way beyond the sheer API of their methods. They can be used as (sometimes unsafe) marker traits, or other API promises, etc.

So, closures are just one specific interface/trait shape, which we could use pervasively everywhere, if we did not mind the loss of “nominal typing” (the trait name).

But they’re actually more: closures would not be near as useful as they are if we did not have closure expressions!

In fact, closure expressions are so handy that nowadays we have a bunch of impl Trait constructors that take the raw/bare API/signature as a closure, and then wrap it within the “name” of the trait:

• Iterator: from FnMut() -> Option<Item> using iter::from_fn()
• Future: from FnMut(&mut Context<'_>) -> Poll<Output> using future::poll_fn();
• Stream: from FnMut(Acc) -> impl Future<Output = (Item, Acc)> using stream::unfold()

And that same difference applies to arbitrary GATs vs. ForLt: the ability to produce ad-hoc / on-demand impl ForLt types / ForLt type “expressions”, thanks to the ForLt! macro, is what makes ForLt convenient and flexible, vs. the overly cumbersome aspect of manually using custom GATs.

Indeed, compare:

trait ForLt {
    type Assoc<'lt>;
}

enum StrRef {}

impl ForLt for StrRef {
    type Assoc<'lt> = &'lt str;
}

to:

type StrRef = ForLt!(<'lt> = &'lt str);

Conclusion

So, to summarize, this ForLt = “: <'_>” HKT pattern is just:

• some GAT API having been canonical-ized,

  • much like how, in the realm of closures, the Fn(Args…) -> R was picked (vs. any other signature-equivalent Closure<Args, Ret = R> trait);

• which can be “inhabited” on demand / in an ad-hoc fashion thanks to the ForLt!(<'input> = Output…) macro,

  • much like how, in the realm of closures, it is done with the |input…| output… closure expressions.

In other words:

: <'_> and HKTs are to GATs what closures are to traits.

(it’s the Fn(Lifetime) -> Type of the type realm).

---

Finally, another observation which I find interesting, is that:

type A = ForLt!(<'r> = &'r str);
// vs.
type B        <'r> = &'r str;

is an annoying limitation of Rust, which happens to feature a similar distinction that certain past languages have had between values, and functions, wherein they were treated separately (rather than as first-class citizens, i.e., like the other values).

In Rust, type B<'r> = &'r str; suffers from this same kind of limitation, only in the type realm this time: type B<'r> = is a special construct, which yields a “type” constructor. That is, it yields some syntax, B, to which we can feed a lifetime 'lt, by writing B<'lt>, so as to end up with a type.

But B, in and of itself, is not a type, even if we often call it a “generic type” by abuse of terminology.

Which is why it cannot be fed, alone, to some type-generic API that would want to be the one feeding the lifetime parameter: it does not play well with “generic generics”!

In this example, the only true “generic type”, that is, the type which is, itself, lifetime-generic, is A.

This is where ForLt! and HKTs, thus, shine.

---

1. For Haskell enthusiasts, this : For-bounded-ness could be called “Arrow-Kinded”, as in, it matches the … -> * kind.
   
   Then, an Arrow-Kinded type which has, inside the …, yet another Arrow-Kinded type, is what is called a Higher-Kinded Type:
   

   • “Arrow-Kinded Type”: … -> *, such as ForLt!(<'a> = &'a str) : ForLt.
   • Higher-Kinded Type: (… -> *) -> *, such as struct Example<T : ForLt>.
    ↩