Skip to content

Instantly share code, notes, and snippets.

@snoyberg
Created December 2, 2020 15:05
Show Gist options
  • Save snoyberg/91ae892199bc8a6687d3798343a9ee54 to your computer and use it in GitHub Desktop.
Save snoyberg/91ae892199bc8a6687d3798343a9ee54 to your computer and use it in GitHub Desktop.
Playing with GATs, transformers, and more
#![feature(generic_associated_types)]
#[allow(dead_code)]
trait Functor {
type Unwrapped;
type Wrapped<B>: Functor;
fn map<F, B>(self, f: F) -> Self::Wrapped<B>
where
F: FnMut(Self::Unwrapped) -> B;
}
impl<A> Functor for Option<A> {
type Unwrapped = A;
type Wrapped<B> = Option<B>;
fn map<F: FnMut(A) -> B, B>(self, mut f: F) -> Option<B> {
match self {
Some(x) => Some(f(x)),
None => None,
}
}
}
impl<A> Functor for Vec<A> {
type Unwrapped = A;
type Wrapped<B> = Vec<B>;
fn map<F: FnMut(A) -> B, B>(self, f: F) -> Vec<B> {
self.into_iter().map(f).collect()
}
}
trait Pointed: Functor {
fn wrap<T>(t: T) -> Self::Wrapped<T>;
}
impl<A> Pointed for Option<A> {
fn wrap<T>(t: T) -> Option<T> {
Some(t)
}
}
impl<A> Pointed for Vec<A> {
fn wrap<T>(t: T) -> Vec<T> {
vec![t]
}
}
trait Applicative: Pointed {
/*
fn apply<A, B>(self, a: Self::Wrapped<A>) -> Self::Wrapped<B>
where
Self::Unwrapped: FnOnce(A) -> B
{
self.lift_a2(|f, a| f(a), a)
}
*/
//type WrappedApplicative<B>: Applicative;
/*
fn rewrap_applicative<T>(w: Self::Wrapped<T>) -> Self::Wrapped<T>;
fn pure<T>(t: T) -> Self::Wrapped<T> {
rewrap_applicative(Self::wrap(t))
}
*/
fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, f: F) -> Self::Wrapped<C>
where
F: FnMut(Self::Unwrapped, B) -> C;
}
/* FIXME didn't work
fn lift_a2<F, A, B, C>(f: F, a: A, b: A::WrappedApplicative<B>) -> A::WrappedApplicative<C>
where
F: FnOnce(A::Unwrapped, B) -> C,
A: Applicative
{
a.map(|a| { move |b| f(a, b) }).apply(b)
}
*/
impl<A> Applicative for Option<A> {
//type WrappedApplicative<B> = Option<B>;
/*
fn rewrap_applicative<T>(w: Self::Wrapped<T>) -> Self::Wrapped<T> {
w
}
*/
fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, mut f: F) -> Self::Wrapped<C>
where
F: FnMut(Self::Unwrapped, B) -> C
{
let a = self?;
let b = b?;
Some(f(a, b))
}
/*
fn apply<B, C>(self, b: Self::Wrapped<B>) -> Self::Wrapped<C>
where
Self::Unwrapped: FnOnce(B) -> C
{
let f = self?;
let b = b?;
Some(f(b))
}
*/
}
/*
impl<A: Clone> Applicative for Vec<A> {
fn lift_a2<F, B, C>(self, f: F, b: Self::Wrapped<B>) -> Self::Wrapped<C>
where
F: FnOnce(Self::Unwrapped, B) -> C
{
let mut result = Vec::new();
for a in self {
for b in &b {
result.push(f(a.clone(), b.clone()));
}
}
result
}
}
*/
trait Monad : Applicative {
fn bind<B, F>(self, f: F) -> Self::Wrapped<B>
where
F: FnMut(Self::Unwrapped) -> Self::Wrapped<B>;
}
impl<A> Monad for Option<A> {
fn bind<B, F>(self, f: F) -> Option<B>
where
F: FnMut(A) -> Option<B>,
{
self.and_then(f)
}
}
struct Identity<T>(T);
impl<T> Functor for Identity<T> {
type Unwrapped = T;
type Wrapped<A> = Identity<A>;
fn map<F, B>(self, mut f: F) -> Identity<B>
where
F: FnMut(T) -> B
{
Identity(f(self.0))
}
}
impl<A> Pointed for Identity<A> {
fn wrap<T>(t: T) -> Identity<T> {
Identity(t)
}
}
impl<T> Applicative for Identity<T> {
/*
type WrappedApplicative<B> = Identity<B>;
fn rewrap_applicative<A>(w: Self::Wrapped<A>) -> Self::WrappedApplicative<A> {
w
}
*/
fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, mut f: F) -> Self::Wrapped<C>
where
F: FnMut(Self::Unwrapped, B) -> C
{
Identity(f(self.0, b.0))
}
/*
fn apply<A, B>(self, a: Identity<A>) -> Identity<B>
where
Self::Unwrapped: FnOnce(A) -> B
{
Identity((self.0)(a.0))
}
*/
}
impl<T> Monad for Identity<T> {
fn bind<B, F>(self, mut f: F) -> Identity<B>
where
F: FnMut(T) -> Identity<B>
{
f(self.0)
}
}
struct IdentityT<M>(M);
impl<M: Functor> Functor for IdentityT<M> {
type Unwrapped = M::Unwrapped;
type Wrapped<A> = IdentityT<M::Wrapped<A>>;
fn map<F, B>(self, f: F) -> Self::Wrapped<B>
where
F: FnMut(M::Unwrapped) -> B
{
IdentityT(self.0.map(f))
}
}
impl<M: Pointed> Pointed for IdentityT<M> {
fn wrap<T>(t: T) -> IdentityT<M::Wrapped<T>> {
IdentityT(M::wrap(t))
}
}
impl<M: Applicative> Applicative for IdentityT<M> {
/*
type WrappedApplicative<A> = IdentityT<M::WrappedApplicative<A>>;
fn rewrap_applicative<T>(w: Self::Wrapped<T>) -> Self::WrappedApplicative<T> {
IdentityT(M::rewrap_applicative(w.0))
}
*/
fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, f: F) -> Self::Wrapped<C>
where
F: FnMut(Self::Unwrapped, B) -> C
{
IdentityT(self.0.lift_a2(b.0, f))
}
/*
fn apply<A, B>(self, a: IdentityT<M::Wrapped<A>>) -> IdentityT<M::Wrapped<B>>
where
M::Unwrapped: FnOnce(A) -> B
{
IdentityT(self.0.apply(a.0))
}
*/
}
impl<M: Monad> Monad for IdentityT<M> {
fn bind<B, F>(self, mut f: F) -> Self::Wrapped<B>
where
F: FnMut(Self::Unwrapped) -> Self::Wrapped<B>
{
IdentityT(self.0.bind(|x| f(x).0))
}
}
trait MonadTrans {
type Base: Monad;
fn lift(base: Self::Base) -> Self;
}
impl<M: Monad> MonadTrans for IdentityT<M> {
type Base = M;
fn lift(base: M) -> Self {
IdentityT(base)
}
}
fn main() {
let x = Some(1).bind(|x| Some(x * 2));
println!("{:?}", x);
println!("Age is {:?}", age());
}
#[allow(dead_code)]
#[derive(Debug, PartialEq)]
enum MyOption<A> {
Some(A),
None,
}
#[allow(dead_code)]
impl<A> MyOption<A> {
fn map<F: FnOnce(A) -> B, B>(self, f: F) -> MyOption<B> {
match self {
MyOption::Some(a) => MyOption::Some(f(a)),
MyOption::None => MyOption::None,
}
}
}
#[test]
fn test_option_map() {
assert_eq!(Some(5).map(|x| x + 1), Some(6));
assert_eq!(None.map(|x: i32| x + 1), None);
}
#[test]
fn test_myoption_map() {
assert_eq!(MyOption::Some(5).map(|x| x + 1), MyOption::Some(6));
assert_eq!(MyOption::None.map(|x: i32| x + 1), MyOption::None);
}
#[allow(dead_code)]
#[derive(Debug, PartialEq)]
enum MyResult<A, E> {
Ok(A),
Err(E),
}
#[allow(dead_code)]
impl<A, E> MyResult<A, E> {
fn map<F: FnOnce(A) -> B, B>(self, f: F) -> MyResult<B, E> {
match self {
MyResult::Ok(a) => MyResult::Ok(f(a)),
MyResult::Err(e) => MyResult::Err(e),
}
}
}
#[test]
fn test_result_map() {
assert_eq!(MyResult::Ok(5).map(|x| x + 1), MyResult::Ok::<i32, ()>(6));
assert_eq!(MyResult::Err("hello").map(|x: i32| x + 1), MyResult::Err("hello"));
}
#[allow(dead_code)]
#[derive(PartialEq, Debug)]
enum Validation<A, E> {
Ok(A),
Err(E),
}
#[allow(dead_code)]
impl<A, E> Validation<A, E> {
fn map<F: FnOnce(A) -> B, B>(self, f: F) -> Validation<B, E> {
match self {
Validation::Ok(a) => Validation::Ok(f(a)),
Validation::Err(e) => Validation::Err(e),
}
}
}
trait Semigroup {
fn append(self, rhs: Self) -> Self;
}
impl Semigroup for String {
fn append(mut self, rhs: Self) -> Self {
self += &rhs;
self
}
}
impl<T> Semigroup for Vec<T> {
fn append(mut self, mut rhs: Self) -> Self {
Vec::append(&mut self, &mut rhs);
self
}
}
impl Semigroup for () {
fn append(self, (): ()) -> () {}
}
impl<A, E> Functor for Validation<A, E> {
type Unwrapped = A;
type Wrapped<B> = Validation<B, E>;
fn map<F: FnOnce(A) -> B, B>(self, f: F) -> Validation<B, E> {
match self {
Validation::Ok(a) => Validation::Ok(f(a)),
Validation::Err(e) => Validation::Err(e),
}
}
}
impl<A, E> Pointed for Validation<A, E> {
fn wrap<T>(t: T) -> Validation<T, E> {
Validation::Ok(t)
}
}
impl<A, E: Semigroup> Applicative for Validation<A, E> {
/*
type WrappedApplicative<B> = Validation<B, E>;
fn rewrap_applicative<T>(w: Self::Wrapped<T>) -> Self::WrappedApplicative<T> {
w
}
*/
fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, f: F) -> Self::Wrapped<C>
where
F: FnOnce(Self::Unwrapped, B) -> C
{
match (self, b) {
(Validation::Ok(a), Validation::Ok(b)) => Validation::Ok(f(a, b)),
(Validation::Err(e), Validation::Ok(_)) => Validation::Err(e),
(Validation::Ok(_), Validation::Err(e)) => Validation::Err(e),
(Validation::Err(e1), Validation::Err(e2)) => Validation::Err(e1.append(e2)),
}
}
/*
fn apply<A, B>(self, a: Validation<A, E>) -> Self::Wrapped<B>
where
Self::Unwrapped: FnOnce(A) -> B
{
match (self, a) {
(Validation::Ok(f), Validation::Ok(a)) => Validation::Ok(f(a)),
(Validation::Err(e), Validation::Ok(_)) => Validation::Err(e),
(Validation::Ok(_), Validation::Err(e)) => Validation::Err(e),
(Validation::Err(e1), Validation::Err(e2)) => Validation::Err(e1.append(e2)),
}
}
*/
}
#[test]
fn test_validation_ok() {
let a: Validation<i32, ()> = Validation::Ok(5);
let b: Validation<i32, ()> = Validation::Ok(10);
assert_eq!(a.lift_a2(b, |x, y| x + y), Validation::Ok(15));
}
#[test]
fn test_validation_err() {
let a: Validation<i32, Vec<&str>> = Validation::Err(vec!["error1", "error2"]);
let b: Validation<i32, Vec<&str>> = Validation::Err(vec!["error3"]);
assert_eq!(a.lift_a2(b, |x, y| x + y), Validation::Err(vec!["error1", "error2", "error3"]));
}
fn traverse<F, M, A, B, I>(iter: I, f: F) -> M::Wrapped<Vec<B>>
where
F: FnMut(A) -> M,
M: Applicative<Unwrapped = B>,
I: IntoIterator<Item = A>,
M::Wrapped<Vec<B>>: Applicative<Unwrapped = Vec<B>>,
{
let mut iter = iter.into_iter().map(f);
let mut result: M::Wrapped<Vec<B>> = match iter.next() {
Some(b) => b.map(|x| vec![x]),
None => return M::wrap(Vec::new()),
};
for m in iter {
result = result.lift_a2(m, |vec, b| {
vec.push(b);
vec
});
}
result
}
/// Monomorphic functor trait
trait MonoFunctor {
type Unwrapped; // value "contained inside"
fn map<F>(self, f: F) -> Self
where
F: FnMut(Self::Unwrapped) -> Self::Unwrapped;
}
impl<A> MonoFunctor for Option<A> {
type Unwrapped = A;
fn map<F: FnMut(A) -> A>(self, mut f: F) -> Option<A> {
match self {
Some(a) => Some(f(a)),
None => None,
}
}
}
/*
trait HktFunctor {
fn map<A, B, F: FnMut(A) -> B>(self: Self<A>, f: F) -> Self<B>;
impl HktFunctor for Option {
fn map<A, B, F: FnMut(A) -> B>(self: Option<A>, f: F) -> Option<B> {
match self {
Some(a) => Some(f(a)),
None => None,
}
}
}
*/
impl<A, E> Functor for Result<A, E> {
type Unwrapped = A;
type Wrapped<B> = Result<B, E>;
fn map<F: FnMut(A) -> B, B>(self, mut f: F) -> Result<B, E> {
match self {
Ok(a) => Ok(f(a)),
Err(e) => Err(e),
}
}
}
impl<A> Functor for MyOption<A> {
type Unwrapped = A;
type Wrapped<B> = Result<B, String>; // wut?
fn map<F: FnMut(A) -> B, B>(self, mut f: F) -> Result<B, String> {
match self {
MyOption::Some(a) => Ok(f(a)),
MyOption::None => Err("Well this is weird, isn't it?".to_owned()),
}
}
}
/*
Womp womp
fn join<MOuter, MInner, A>(outer: MOuter) -> MOuter::Wrapped<A>
where
MOuter: Monad<Unwrapped = MInner>,
MInner: Monad<Unwrapped = A, Wrapped = MOuter::Wrapped<A>>,
{
outer.bind(|inner| inner)
}
#[test]
fn test_join() {
assert_eq!(Some(Some(true)), true);
}
*/
fn birth_year() -> Result<i32, String> {
Err("No birth year".to_string())
}
fn current_year() -> Result<i32, String> {
Err("No current year".to_string())
}
fn age() -> Result<i32, String> {
current_year().lift_a2(birth_year(), |cy, by| cy - by)
}
impl<A, E> Pointed for Result<A, E> {
fn wrap<T>(t: T) -> Result<T, E> {
Ok(t)
}
}
impl<A, E> Applicative for Result<A, E> {
fn lift_a2<F, B, C>(self, b: Self::Wrapped<B>, f: F) -> Self::Wrapped<C>
where
F: FnOnce(Self::Unwrapped, B) -> C
{
match (self, b) {
(Ok(a), Ok(b)) => Ok(f(a, b)),
(Err(e), _) => Err(e),
(_, Err(e)) => Err(e),
}
}
/*
fn apply<A, B>(self, a: Validation<A, E>) -> Self::Wrapped<B>
where
Self::Unwrapped: FnOnce(A) -> B
{
match (self, a) {
(Validation::Ok(f), Validation::Ok(a)) => Validation::Ok(f(a)),
(Validation::Err(e), Validation::Ok(_)) => Validation::Err(e),
(Validation::Ok(_), Validation::Err(e)) => Validation::Err(e),
(Validation::Err(e1), Validation::Err(e2)) => Validation::Err(e1.append(e2)),
}
}
*/
}
@mschuwalow
Copy link

Really nice post!
I have been playing around with a similar idea here https://github.com/mschuwalow/ratz/blob/main/src/hkt.rs, just using a different encoding.

It can avoid the problem of 'forgetting' the specific type that we have by defining the instances not on specific type, but on a phantom type representing the type constructor itself. Then we can establish the link between this phantom type and all members using traits.

pub trait Hkt {
    type Member<T>: Mirror<T = T, Family = Self>;
}

pub trait Mirror {
    type T;
    type Family: Hkt;
    fn as_member(self) -> <Self::Family as Hkt>::Member<Self::T>;
}

For example it looks like this for Option:

impl<T> Mirror for Option<T> {
    type Family = OptionFamily;
    type T = T;

    fn as_member(self) -> <Self::Family as Hkt>::Member<Self::T> {
        self
    }
}
pub struct OptionFamily;
impl Hkt for OptionFamily {
    type Member<T> = Option<T>;
}

This seems to be able to express traverse / join / etc without any problems and looks reasonably clean:

pub trait Traversable: Covariant {
    fn traverse<App: Applicative, A, B: Clone, F: Fn(A) -> App::Member<B>>(
        fa: Self::Member<A>,
        f: F,
    ) -> App::Member<Self::Member<B>>;
}

This has one caveat that the compiler seems to have problems to infer the type of the 'Hkt' given a member, but there are workarounds for this.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment