edmundsmith

Method for Emulating Higher-Kinded Types in Rust

Intro

I've been fiddling about with an idea lately, looking at how higher-kinded types can be represented in such a way that we can reason with them in Rust here and now, without having to wait a couple years for what would be a significant change to the language and compiler.

There have been multiple discussions on introducing higher-ranked polymorphism into Rust, using Haskell-style Higher-Kinded Types (HKTs) or Scala-looking Generalised Associated Types (GATs). The benefit of higher-ranked polymorphism is to allow higher-level, richer abstractions and pattern expression than just the rank-1 polymorphism we have today.

As an example, currently we can express this type:

pyricau

import android.util.Log;
import com.squareup.leakcanary.AnalysisResult;
import com.squareup.leakcanary.DisplayLeakService;
import com.squareup.leakcanary.HeapDump;
import retrofit.RestAdapter;
import retrofit.RetrofitError;
import retrofit.http.Multipart;
import retrofit.http.POST;
import retrofit.http.Part;
import retrofit.mime.TypedFile;

codedot

x ∈ Λ;                                                                          Лямбда-выражения строятся из переменных
M, N ∈ Λ ⇒ λx.M ∈ Λ ∧ M N ∈ Λ;                                                  с помощью абстракций и аппликаций;
(M) = M, M N P = (M N) P.                                                       причем аппликация лево-ассоциативна.

x[x := P] = P;                                                                  Подстановка заменяет вхождения переменной на другое выражение,
y[x := P] = y;                                                                  но только если переменная совпадает,
(λx.M)[x := P] = λx.M;                                                          при этом связанные переменные не подлежат подстановке;
(λy.M)[x := P] = λy.M[x := P];                                                  операция подстановки через абстракции
(M N)[x := P] = M[x := P] N[x := P].                                            и аппликации проходит выражение рекуррентно.