Most coveted Rust features

[shelby3]

@arielb1

@shelby3

A solution is use category theory Functor.map instead of iterators, which also solves the memory leak problems at a high-level. Use a more functional programming model, instead of a C/C++ imperative style model. A functional model can enable much more efficient deforestation of chained modular operations (although lazy evaluation is typically required), which can't be achieved modularly with an imperative style.

That is, of course, not an option in Rust. Laziness leads to very unpredictable memory consumption, which we really do not want. Plus, functors require higher-kinded types already, and if we had HKT, we would have working iterators.

Functional composition of operations over collections can be performed without laziness (and pure function memoization), but loses the runtime deforestion optimization which consumes more memory and is slower. There are other potential methods of performing deforestation. All of those can and should be allowed, because programmers want the flexibility to choose the best paradigm model for each scenario.

Let's review why functors require higher-kinded types. Seems you are requiring something like the following (apologies if the Rust syntax isn't correct):

trait Functor {
   type T;
   fn map<A>(&self, T -> A) -> Self<T=A>;
}

We might contemplate to do instead the following which is not higher-kinded:

trait Functor {
   type T;
   fn map<A>(&self, T -> A) -> &Functor<T=A>;
}

So in other words, the trait object would maintain the runtime knowledge about what the implementing Self type is, which is not checked at compile time.

However, you are correct on this point, because the type signature of the alternative is not constrained to a functor.map operation, because there is no requirement that the return value have the same Self type. For example, the implementation could employ monoid.append to return a Functor which has a different Self type, e.g. convert from a Vec<T> to List<A>, which would violate the invariants of the category theory for a functor.

So thus you have pointed out an example of where we must have higher-kinded types.

I think we have shown that higher-kinded types are required when either we must restrict a trait type to a parametrization of the Self type for reasons of conformance to invariants (e.g. category theory for functors) or because we wish to forsake some generality in order to get more optimization (e.g. not using a trait object for an iterator, but where it is possible to get similar optimization using functors but these require higher-kinded types also and we might gain some other higher-level functional composition abstraction and control over resource management to avoid the low-level imperative approach).