An implementation of the Functor/Applicative/Monad trait family using carrier types.

monad.rs

#![allow(incomplete_features)]
#![feature(generic_associated_types)]
use std::marker::PhantomData;

macro_rules! do_notation {
    (| $ty:ty | pure $e:expr) => {
        <$ty>::pure($e)
    };
    (| $ty:ty | $e:expr) => {
        $e
    };
    (| $ty:ty | let $p:pat = $e:expr; $($t:tt)*) => {
        { let $p = $e; do_notation!{ |$ty| $($t)* } }
    };
    (| $ty:ty | $p:pat in $e:expr; $($t:tt)*) => {
        <$ty>::bind(|$p| do_notation!{ |$ty|  $($t)* }, $e)
    };
    (| $ty:ty | $e:expr; $($t:tt)*) => {
        <$ty>::bind(|_| do_notation!{ |$ty| $($t)* }, $e)
    };
}

fn main() {
    let option_ex = do_notation! { |OptionCarrier|
        x in Some(1);
        let y = 2;
        pure x + y
    };
    println!("{:?}", option_ex);

    let vec_ex = do_notation! { |VecCarrier|
        z in vec!{0,8};
        y in vec!{0,4};
        x in vec!{0,2};
        w in vec!{0,1};
        pure w + x + y + z
    };
    println!("{:?}", vec_ex);

    fn first<T>(t: T, s: &str) -> (T, String) {
        (t, String::from(s))
    }

    let first_ex = do_notation! { |First<String>|
        x in first(1, "x");
        first((), " + ");
        y in first(2, "y");
        pure x + y
    };
    println!("{:?}", first_ex);

    fn second<T>(t: T, s: &str) -> (String, T) {
        (String::from(s), t)
    }

    let second_ex = do_notation! { |Second<String>|
        x in second(1, "x");
        second((), " + ");
        y in second(2, "y");
        second(x + y, "!")
    };
    println!("{:?}", second_ex);
}

// use carrier types for the traits so we can make assertions about generic types
trait Functor {
    type Obj<T>;

    fn fmap<F, A, B>(f: F, t: Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> B;
}

trait Applicative: Functor {
    fn pure<A>(a: A) -> Self::Obj<A>;

    fn ap<F, A, B>(u: Self::Obj<F>, v: Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> B;
}

trait Monad: Applicative {
    fn bind<F, A, B>(f: F, t: Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> Self::Obj<B>;
}

struct OptionCarrier;

impl Functor for OptionCarrier {
    type Obj<T> = Option<T>;

    fn fmap<F, A, B>(f: F, t: Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> B,
    {
        t.map(f)
    }
}

impl Applicative for OptionCarrier {
    fn pure<A>(a: A) -> Self::Obj<A> {
        Some(a)
    }

    fn ap<F, A, B>(u: Self::Obj<F>, v: Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> B,
    {
        u.zip(v).map(|(f, a)| f(a))
    }
}

impl Monad for OptionCarrier {
    fn bind<F, A, B>(f: F, t: Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> Self::Obj<B>,
    {
        t.and_then(f)
    }
}

struct VecCarrier;

impl Functor for VecCarrier {
    type Obj<T> = Vec<T>;

    fn fmap<F, A, B>(f: F, t: Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> B,
    {
        t.into_iter().map(f).collect()
    }
}

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

    fn ap<F, A, B>(u: Self::Obj<F>, v: Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> B,
    {
        u.into_iter()
            .zip(v.into_iter())
            .map(|(f, a)| f(a))
            .collect()
    }
}

impl Monad for VecCarrier {
    fn bind<F, A, B>(f: F, t: Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> Self::Obj<B>,
    {
        t.into_iter().map(f).flatten().collect()
    }
}

trait Monoid {
    fn mempty() -> Self;
    fn mappend(self, other: Self) -> Self;
}

impl Monoid for String {
    fn mempty() -> Self {
        String::from("")
    }
    fn mappend(self, other: Self) -> Self {
        self + &other
    }
}

struct First<C>(PhantomData<C>);

impl<C> Functor for First<C> {
    type Obj<T> = (T, C);

    fn fmap<F, A, B>(f: F, (a, c): Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> B,
    {
        (f(a), c)
    }
}

impl<C> Applicative for First<C>
where
    C: Monoid,
{
    fn pure<A>(a: A) -> Self::Obj<A> {
        (a, C::mempty())
    }

    fn ap<F, A, B>((f, lhs): Self::Obj<F>, (a, rhs): Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> B,
    {
        (f(a), lhs.mappend(rhs))
    }
}

impl<C> Monad for First<C>
where
    C: Monoid,
{
    fn bind<F, A, B>(f: F, (a, lhs): Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> Self::Obj<B>,
    {
        let (b, rhs) = f(a);
        (b, lhs.mappend(rhs))
    }
}

struct Second<C>(PhantomData<C>);
impl<C> Functor for Second<C> {
    type Obj<T> = (C, T);

    fn fmap<F, A, B>(f: F, (c, a): Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> B,
    {
        (c, f(a))
    }
}

impl<C> Applicative for Second<C>
where
    C: Monoid,
{
    fn pure<A>(a: A) -> Self::Obj<A> {
        (C::mempty(), a)
    }

    fn ap<F, A, B>((lhs, f): Self::Obj<F>, (rhs, a): Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> B,
    {
        (lhs.mappend(rhs), f(a))
    }
}

impl<C> Monad for Second<C>
where
    C: Monoid,
{
    fn bind<F, A, B>(f: F, (lhs, a): Self::Obj<A>) -> Self::Obj<B>
    where
        F: Fn(A) -> Self::Obj<B>,
    {
        let (rhs, b) = f(a);
        (lhs.mappend(rhs), b)
    }
}