fun_types.rs

use std::marker::PhantomData;

// monad trait

trait Monad{
	type App<T>;

	fn pure<T>(x: T) -> Self::App<T>;

	fn bind<T, U>(x: Self::App<T>, f: impl Fn(T) -> Self::App<U>) -> Self::App<U>;
}

// do-notation

macro_rules! mdo{
    // binds: let &a = b;
    ($t:ty | let! $i:ident = $e:expr; $($k:tt)*) => { <$t>::bind($e, |$i| mdo!( $t | $($k)* ) ) };
    // non-monadic let
    ($t:ty | let $i:ident = $e:expr; $($k:tt)*) => { { let $i = $e; mdo!( $t | $($k)* ) } };
    // wrapping and non-wrapping returns
    ($t:ty | pure $e:expr) => { <$t>::pure($e) };
    ($t:ty | exact $e:expr) => { ($e) };
}

// concrete monads

struct Identity;
impl Monad for Identity{
	type App<T> = T;

	fn pure<T>(x: T) -> T {
		x
	}

	fn bind<T, U>(x: T, f: impl Fn(T) -> U) -> U {
		f(x)
	}
}

struct Vecs;
impl Monad for Vecs{
	type App<T> = Vec<T>;

	fn pure<T>(x: T) -> Vec<T>{
		vec![x]
	}

	fn bind<T, U>(xs: Vec<T>, f: impl Fn(T) -> Vec<U>) -> Vec<U>{
		let mut tmp: Vec<U> = vec![];
		for x in xs{
			tmp.extend(f(x));
		}
		tmp
	}
}

// monad transformer trait

trait MonadTrans{
	type Trans<M: Monad>: Monad;

	fn lift<M: Monad, T>(x: M::App<T>) -> <Self::Trans<M> as Monad>::App<T>;
}

// concrete monad transformers

struct MaybeT<M: Monad>{ _ty: PhantomData<M> }
impl<M: Monad> Monad for MaybeT<M>{
	type App<T> = M::App<Option<T>>;

	fn pure<T>(x: T) -> M::App<Option<T>> {
		M::pure(Some(x))
	}

	fn bind<T, U>(x: M::App<Option<T>>, f: impl Fn(T) -> M::App<Option<U>>) -> M::App<Option<U>> {
		mdo!{ M |
            let! v = x;
            exact match v {
                Some(vv) => f(vv),
                None => M::pure(None)
            }
        }
	}
}

struct MaybeTS;
impl MonadTrans for MaybeTS{
	type Trans<M: Monad> = MaybeT<M>;

	fn lift<M: Monad, T>(x: M::App<T>) -> M::App<Option<T>> {
		mdo!{ M |
			let! v = x;
			pure Some(v)
		}
	}
}