Seamless Higher-Kinded Types in Rust

Overview

Seamless Higher-Kinded Types in Rust

This is actual working code:

pub trait Functor<A> : HKT1 {
    fn map<B, F: FnMut(A) -> B>(self, f: F) -> Self::With<B>;
}

pub trait Applicative<A> : Functor<A> {
    fn pure(a: A) -> Self;
    fn apply<B, F: FnMut(A) -> B>(self, ff: Self::With<F>) -> Self::With<B>;
}

pub trait Monad<A> : Applicative<A> {
    fn ret(a: A) -> Self;
    fn flatmap<B, F: FnMut(A) -> Self::With<B>>(self, f: F) -> Self::With<B>;
}

Here are some implementations for Vec:

implHKT1!(Vec);         // the magic part!

impl<A> Functor<A> for Vec<A> {
    fn map<B, F: FnMut(A) -> B>(self, f: F) -> Self::With<B> {
        self.into_iter().map(f).collect()
    }
}

impl<A> Applicative<A> for Vec<A> {
    fn pure(a: A) -> Self {
        vec![a]
    }

    fn apply<B, F: FnMut(A) -> B>(self, ff: Self::With<F>) -> Self::With<B> {
        ff.into_iter().zip(self.into_iter()).map(
            |(mut f, x)| f(x)
        ).collect()
    }
}

impl<A> Monad<A> for Vec<A> {
    fn ret(a: A) -> Self {
        vec![a]
    }

    fn flatmap<B, F: FnMut(A) -> Self::With<B>>(self, mut f: F) -> Self::With<B> {
        self.into_iter().flat_map(|x| f(x).into_iter()).collect()
    }
}

Let's try our flatmap:

assert_eq!(
    vec![1, 2, 3].flatmap(|x| vec![x, x*x, x*x*x]),
    vec![1, 1, 1, 2, 4, 8, 3, 9, 27]
);

Here's an example with 2 type parameters:

trait Mixuppable<T1, U1> : HKT2 {
    fn mixup<T2, U2>(self, other: Self::With<T2, U2>) -> Self::With<T1, U2>;
}

struct Point<T, U> {
    x: T,
    y: U
}

struct _NotPoint<T, U> {
    a: T,
    b: U
}

implHKT2!(Point);

impl<T1, U1> Mixuppable<T1, U1> for Point<T1, U1> {
    // // ERROR: expected struct `Point`, found struct `_NotPoint`
    // fn mixup<T2, U2>(self, other: Point<T2, U2>) -> _NotPoint<T1, U2> {
    //     todo!()
    // }
    
    fn mixup<T2, U2>(self, other: Point<T2, U2>) -> Point<T1, U2> {
        Point { x: self.x, y: other.y }
    }
}

Can we still claim that Rust doesn't support HKTs, in practice?

Under the hood [obsolete]

The implementation of implHKT1 is trivial:

pub unsafe trait HKT1 {
    type With<W1>;
}

#[macro_export]
macro_rules! implHKT1 {
    ($TypeIdent:ident) => {
        unsafe impl<T1> HKT1 for $TypeIdent<T1> {
            type With<S1> = $TypeIdent<S1>;
        }
    };
}

Notice the use of the unsafe keyword.

The unsafe keyword indicates that HKT1 has invariants that the compiler can't verify, which is exactly what's happening here!

If users try to implement HKT1 on their own, they will get an error. Then it's their responsibility to do the right thing and use the macro instead of just marking their implementation as unsafe.

A little detail: to avoid redefinitions, I call the macros for external types (e.g. Vec and Option) once and for all in ext_hkts_impls.rs.

Under the hood v2

It seems Rust community hates my use of unsafe since I'm extending its meaning beyond what they deem acceptable. I think the pros outweighed the cons, but, luckily, there's a better solution (and possibly others) that avoids the unsafe hack and it's even safer:

pub trait HKT1 {
    type HKTInner1;
    type With<W1>:
        HKT1<HKTInner1 = W1> +
        HKT1<With<Self::HKTInner1> = Self> +
        HKT1<With<W1> = Self::With<W1>>;
}

This was suggested by u/Chadshinshin32 in this comment on reddit.

Let's consider a more general case and let's try to show (informally) its correctness:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
        HKT2<HKTInner1 = W1, HKTInner2 = W2> +
        HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self> +
        HKT2<With<W1, W2> = Self::With<W1, W2>>;
}

Let's start with no bounds on With and then add them back one at a time, updating our as-general-as-possible implementation so that it doesn't violate them:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
        //    HKT2<HKTInner1 = W1, HKTInner2 = W2>
        //  + HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self>
        //  + HKT2<With<W1, W2> = Self::With<W1, W2>>
         ;
}

struct A;
struct B;
struct C;

impl<T, U> HKT2 for OK1<T, U> {
    type HKTInner1 = A;
    type HKTInner2 = B;
    type With<W1, W2> = C;
}

Now let's add back the first bound:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
           HKT2<HKTInner1 = W1, HKTInner2 = W2>
        //  + HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self>
        //  + HKT2<With<W1, W2> = Self::With<W1, W2>>
         ;
}

struct A;
struct B;
struct OK1<T, U> { x: (T, U) }
struct OK2<T, U> { x: (T, U) }
struct OK3<T, U> { x: (T, U) }
struct OK4<T, U> { x: (T, U) }

impl<T, U> HKT2 for OK1<T, U> {
    type HKTInner1 = A;
    type HKTInner2 = B;
    type With<W1, W2> = OK2<W1, W2>;
}

impl<T, U> HKT2 for OK2<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK3<W1, W2>;
}

impl<T, U> HKT2 for OK3<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK4<W1, W2>;
}

impl<T, U> HKT2 for OK4<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK3<W1, W2>;
}

(In what follows, I'll say OKx as short for "the implementation of HKT2 for OKx".)

We can create as long a WITH-chain as we want, but we need to "close" it at a certain point. I closed it by making OK4 refer back to OK3. Notice how OK1 is the only HKT2 still with arbitrary HKTInner1 and HKTInner2.

Now let's consider the second bound. Let's focus on OK1. The bound requires that OK2<W1, W2> is an HKT2<With<A, B> = Self>, i.e. that OK2<W1, W2>::With<A, B> = OK1<T, U>, which implies that OK2 must refer back to OK1, and that A = T, B = U:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
           HKT2<HKTInner1 = W1, HKTInner2 = W2>
         + HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self>
        //  + HKT2<With<W1, W2> = Self::With<W1, W2>>
         ;
}

struct OK1<T, U> { x: (T, U) }
struct OK2<T, U> { x: (T, U) }

impl<T, U> HKT2 for OK1<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK2<W1, W2>;
}

impl<T, U> HKT2 for OK2<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK1<W1, W2>;
}

Focusing on OK1, we can see that the last bound requires that OK2<W1, W2>::With<W1, W2> = OK2<W1, W2>, which means that OK2 must refer to OK2 instead of OK1:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
           HKT2<HKTInner1 = W1, HKTInner2 = W2>
         + HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self>
         + HKT2<With<W1, W2> = Self::With<W1, W2>>
         ;
}

struct OK1<T, U> { x: (T, U) }
struct OK2<T, U> { x: (T, U) }

impl<T, U> HKT2 for OK1<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK2<W1, W2>;
}

impl<T, U> HKT2 for OK2<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK2<W1, W2>;        // changed from OK1 to OK2
}

We can't do this, though, as this violates the second bound. Basically, we have:

  • (Bound 2) OK2<W1, W2>::With<T, U> = OK1<T, U>
  • (Bound 3) OK2<W1, W2>::With<W1, W2> = OK2<W1, W2>

For all T and U, by choosing W1 = T and W2 = U, we get OK1<T, U> = OK2<T, U>, that is, OK1 = OK2:

pub trait HKT2 {
    type HKTInner1;
    type HKTInner2;
    type With<W1, W2>:
           HKT2<HKTInner1 = W1, HKTInner2 = W2>
         + HKT2<With<Self::HKTInner1, Self::HKTInner2> = Self>
         + HKT2<With<W1, W2> = Self::With<W1, W2>>
         ;
}

struct OK1<T, U> { x: (T, U) }

impl<T, U> HKT2 for OK1<T, U> {
    type HKTInner1 = T;
    type HKTInner2 = U;
    type With<W1, W2> = OK1<W1, W2>;
}

This is the only allowed implementation!


This is just a POC, so feel free to add derive macros, modify names to avoid name collisions, and so on... I've just read The Book and been programming in Rust for a couple of days (to code this POC!), so I'm not familiar with Rust ecosystem and its conventions.

That's all! Happy coding!

You might also like...
Leetcode Solutions in Rust, Advent of Code Solutions in Rust and more

RUST GYM Rust Solutions Leetcode Solutions in Rust AdventOfCode Solutions in Rust This project demostrates how to create Data Structures and to implem

Simple autoclicker written in Rust, to learn the Rust language.

RClicker is an autoclicker written in Rust, written to learn more about the Rust programming language. RClicker was was written by me to learn more ab

Rust programs written entirely in Rust

mustang Programs written entirely in Rust Mustang is a system for building programs built entirely in Rust, meaning they do not depend on any part of

Rust 核心库和标准库的源码级中文翻译,可作为 IDE 工具的智能提示 (Rust core library and standard library translation. can be used as IntelliSense for IDE tools)

Rust 标准库中文版 这是翻译 Rust 库 的地方, 相关源代码来自于 https://github.com/rust-lang/rust。 如果您不会说英语,那么拥有使用中文的文档至关重要,即使您会说英语,使用母语也仍然能让您感到愉快。Rust 标准库是高质量的,不管是新手还是老手,都可以从中

A library for extracting #[no_mangle] pub extern "C" functions (https://docs.rust-embedded.org/book/interoperability/rust-with-c.html#no_mangle)

A library for extracting #[no_mangle] pub extern "C" functions In order to expose a function with C binary interface for interoperability with other p

clone of grep cli written in Rust. From Chapter 12 of the Rust Programming Language book

minigrep is a clone of the grep cli in rust Minigrep will find a query string in a file. To test it out, clone the project and run cargo run body poem

Rust-blog - Educational blog posts for Rust beginners

pretzelhammer's Rust blog 🦀 I write educational content for Rust beginners and Rust advanced beginners. My posts are listed below in reverse chronolo

The ray tracer challenge in rust - Repository to follow my development of
The ray tracer challenge in rust - Repository to follow my development of "The Raytracer Challenge" book by Jamis Buck in the language Rust

The Ray Tracer Challenge This repository contains all the code written, while step by implementing Ray Tracer, based on the book "The Ray Tracer Chall

Learn-rust-the-hard-way - "Learn C The Hard Way" by Zed Shaw Converted to Rust

Learn Rust The Hard Way This is an implementation of Zed Shaw's Learn X The Hard Way for the Rust Programming Language. Installing Rust TODO: Instruct

Owner
Massimiliano Tomassoli
Massimiliano Tomassoli
TodoX is a sophisticated Rust-based application designed to facilitate seamless todo management.

Rust Todo List App is a command-line tool written in Rust that allows users to manage their tasks efficiently. Whether you need to add, mark as done, edit, or clear tasks from your todo list, this app provides essential functionalities to streamline your task management process. Additionally, I have integrated sqlite3 using the rusqlite crate. The database stores the data and will persist indefinitely until you manually delete it.

Harikesh Ranjan Sinha 3 Apr 4, 2024
Higher-level toolkit for MSDF text rendering

MSDF Toolkit Higher-level toolkit for MSDF text rendering About MSDF - an abbreviation of Multi-channel Signed Distance Field. In short, an efficient

null 2 Aug 19, 2022
A library for transcoding between bytes in Astro Notation Format and Native Rust data types.

Rust Astro Notation A library for transcoding between hexadecimal strings in Astro Notation Format and Native Rust data types. Usage In your Cargo.tom

Stelar Software 1 Feb 4, 2022
Idiomatic Rust implementations for various Windows string types (like UNICODE_STRING)

nt-string by Colin Finck <[email protected]> Provides idiomatic Rust implementations for various Windows string types: NtUnicodeString (with NtUnicode

Colin Finck 5 Jun 4, 2023
Efficiently store Rust idiomatic bytes related types in Avro encoding.

Serde Avro Bytes Avro is a binary encoding format which provides a "bytes" type optimized to store &[u8] data like. Unfortunately the apache_avro enco

Akanoa 3 Mar 30, 2024
A typemap for a set of known types optionally without heap allocation, and supporting iterating by traits

fixed_typemap docs.rs GitHub Sponsors Implements typemaps that support a lot of extra funcctionality using procedural macros. docs.rs has a lot more t

Austin Hicks 2 Dec 27, 2021
An implementation of a predicative polymorphic language with bidirectional type inference and algebraic data types

Vinilla Lang Vanilla is a pure functional programming language based on System F, a classic but powerful type system. Merits Simple as it is, Vanilla

Zehao Chen 73 Aug 4, 2022
Custom deserialization for fields that can be specified as multiple types.

serde-this-or-that Custom deserialization for fields that can be specified as multiple types. This crate works with Cargo with a Cargo.toml like: [dep

Ritvik Nag 7 Aug 25, 2022
Create custom ID types that are guaranteed to be valid `RecordID` in SurrealDB

surreal-id The surreal-id crate offers a standardized way to create and validate IDs in your application for usage with SurrealDB. Using the NewId tra

Liam Woodleigh-Hardinge 4 Oct 5, 2023