pub trait Unplug {
    type Gen;
    type A;
}

pub trait Plug<A> {
    type Out: Unplug<A = A>;
}

pub trait Functor: Unplug + Plug<<Self as Unplug>::A> {
    fn map<B, F>(self, f: F) -> <Self as Plug<B>>::Out
    where
        Self: Plug<B>,
        F: FnMut(<Self as Unplug>::A) -> B;
}

pub trait Applicative: Functor {
    fn pure(s: <Self as Unplug>::A) -> Self;
    fn app<B, F>(self, f: <Self as Plug<F>>::Out) -> <Self as Plug<B>>::Out
    where
        F: FnOnce(<Self as Unplug>::A) -> B,
        Self: Plug<F> + Plug<B>;
}

pub trait Monad: Applicative {
    fn bind<F, B>(self, f: F) -> <Self as Plug<B>>::Out
    where
        Self: Plug<F> + Plug<B>,
        F: FnMut(<Self as Unplug>::A) -> <Self as Plug<B>>::Out;
}

impl<A> Unplug for Option<A> {
    type Gen = Option<A>;
    type A = A;
}

impl<A, B> Plug<B> for Option<A> {
    type Out = Option<B>;
}

impl<A> Functor for Option<A> {
    fn map<B, F>(self, f: F) -> <Self as Plug<B>>::Out
    where
        F: FnMut(<Self as Unplug>::A) -> B,
    {
        self.map(f)
    }
}

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

    fn app<B, F>(self, fs: <Self as Plug<F>>::Out) -> <Self as Plug<B>>::Out
    where
        F: FnOnce(<Self as Unplug>::A) -> B,
    {
        self.map(fs?)
    }
}

impl<A: Clone> Monad for Option<A> {
    fn bind<F, B>(self, f: F) -> <Self as Plug<B>>::Out
    where
        F: FnMut(<Self as Unplug>::A) -> <Self as Plug<B>>::Out,
    {
        self.and_then(f)
    }
}

impl<A> Unplug for Vec<A> {
    type Gen = Vec<A>;
    type A = A;
}

impl<A, B> Plug<B> for Vec<A> {
    type Out = Vec<B>;
}

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

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

    fn app<B, F>(self, fs: <Self as Plug<F>>::Out) -> <Self as Plug<B>>::Out
    where
        F: FnOnce(<Self as Unplug>::A) -> B,
    {
        self.into_iter().zip(fs).map(|(x, f)| f(x)).collect()
    }
}

impl<A: Clone> Monad for Vec<A> {
    fn bind<F, B>(self, f: F) -> <Self as Plug<B>>::Out
    where
        F: FnMut(<Self as Unplug>::A) -> <Self as Plug<B>>::Out,
    {
        self.into_iter().flat_map(f).collect()
    }
}

pub fn functor_test<F: Functor, A, B, C>(
    functor: F,
    fun: impl Fn(A) -> B,
    fun2: impl Fn(B) -> C,
) -> <F as Plug<C>>::Out
where
    F: Plug<A> + Plug<B> + Plug<C> + Unplug<A = A>,
{
    functor.map(|x| fun2(fun(x)))
}

#[test]
fn test_f() {
    let x = Functor::map(Some(3), |x| x + 1);

    assert_eq!(x, Some(4));

    let x = None::<i32>.map(|x| x + 1);

    assert_eq!(x, None);

    let x = functor_test(Some(3), |x| x + 1, |x| x * 2);

    assert_eq!(x, Some(8));

    let x = functor_test(None::<i32>, |x| x + 1, |x| x * 2);

    assert_eq!(x, None);

    assert_eq!(None::<i32>.bind(|x| x.checked_add(1)), None);
}