functional 0.0.5

//#![feature(zero_one)]
use std::rc::Rc;
use std::sync::Arc;

/// Equality trait
/// It is widely used in complex type traits to declare equalty between any types
/// Equals<T> is implemented for T
/// No others implementations alowed
pub unsafe trait Equals<T> {
    fn eqcast(self) -> T;
}
unsafe impl<T> Equals<T> for T {
    fn eqcast(self) -> T { self }
}

/// Generic types can implement this trait
/// providing an ability to extract first generic parameter.
pub trait Generic1 {
    type Type;
}

/// Generic types can implement this trait
/// providing an ability to change first generic parameter.
/// Associated `Type` must have same HKT.
/// There are few laws:
/// `<<X As Rebind1<T>::Type as Generic1>::Type == T`
/// `<X As Rebind1<<X as Generic1>::Type>::Type == X`
pub trait Rebind1<Y> : Generic1 {
    type Type;
}

/// Generic types with at least two parameters can implement this trait
/// providing an ability to extract second generic parameter.
pub trait Generic2: Generic1 {
    type Type;
}

/// Generic types with at least two parameters can implement this trait
/// providing an ability to change second generic parameter.
/// Associated `Type` must have same HKT.
/// There are few laws:
/// `<<X As Rebind2<T>::Type as Generic2>::Type == T`
/// `<X As Rebind2<<X as Generic2>::Type>::Type == X`
pub trait Rebind2<Y> : Generic2 {
    type Type;
}


/// Basic functional trait
pub trait Functor : Generic1 {
    /// Apply function to value(s) in the functor producing new functor with same type
    fn fmap<Y, F: Fn(<Self as Generic1>::Type)->Y>(self, f: F) -> <Self as Rebind1<Y>>::Type where Self: Rebind1<Y>;
}

/// Monad trait.
/// Can you explain monads... in five words?
pub trait Monad: Functor {
    /// Wrap ordinary value into monadic value
    fn unit(value: <Self as Generic1>::Type) -> Self;

    /// Bind monadic value to the monadic action
    /// `m.bind(f)` is equvalent of `m.fmap(f).join()`
    fn bind<U, F: Fn(<Self as Generic1>::Type) -> <Self as Rebind1<U>>::Type>(self, f: F) -> <Self as Rebind1<U>>::Type where Self: Rebind1<U>;

    /// Join two level of monad into one `M<M<T>> => M<T>`
    /// `m.join()` is equivalent of `m.bind(|x|x)`
    fn join<U>(self) -> <Self as Rebind1<U>>::Type where <Self as Generic1>::Type: Equals<<Self as Rebind1<U>>::Type>, Self: Rebind1<U> + Sized { self.bind(|x|x.eqcast()) }
}


// Algebra

/// Define binary operation as type
pub trait BinaryOperation<T> {
    fn apply(lhs: T, rhs: T) -> T;
}

/// Declare binary operation as associative
pub trait AssociativeOperation<T> : BinaryOperation<T> {}

/// Basic algebraic structure/
/// Combines binary operation with type
pub trait Magma<T: BinaryOperation<Self>>: Sized {}
impl<T, Op> Magma<Op> for T where Op: BinaryOperation<T> {}

/// Combines asscotiative operation with type
pub trait Semigroup<T: AssociativeOperation<Self>> : Magma<T> {}
impl<T, Op> Semigroup<Op> for T where Op: AssociativeOperation<T> {}


/// Monoid is Semigroup with neutral element for is's operation
pub trait Monoid<T: AssociativeOperation<Self>> : Semigroup<T> {
    /// Get the neutral element
    /// if `T: Monoid<Op>` and `r: T` then `Op::apply(T::one(), r) == r`
    fn one() -> Self;
}




// ---------------
// Implementations
// ---------------


/// Implementation of Generic1 and Rebind1 for HKTs with 1 parameter
///
/// # Examples
///
/// ```
/// struct A<T>;
/// generic1(A);
/// ```
macro_rules! generic1 {
    ($x:ident) => {
        impl<T> Generic1 for $x<T> {
            type Type = T;
        }
        impl<T, Y> Rebind1<Y> for $x<T> where $x<T>: Generic1<Type=T> {
            type Type = $x<Y>;
        }
    };
}

/// Implementation of Generic1/2 and Rebind1/2 for HKTs with 2 parameter
///
/// # Examples
///
/// ```
/// struct A<T, Y>;
/// generic2(A);
/// ```
macro_rules! generic2 {
    ($x:ident) => {
        impl<T0, T1> Generic1 for $x<T0, T1> {
            type Type = T0;
        }
        impl<T0, T1, Y> Rebind1<Y> for $x<T0, T1> where $x<T0, T1>: Generic1<Type=T0>, $x<T0, T1>: Generic2<Type=T1> {
            type Type = $x<Y, T1>;
        }
        impl<T0, T1> Generic2 for $x<T0, T1> where $x<T0, T1>: Generic1<Type=T0> {
            type Type = T1;
        }
        impl<T0, T1, Y> Rebind2<Y> for $x<T0, T1> where $x<T0, T1>: Generic1<Type=T0>, $x<T0, T1>: Generic2<Type=T1> {
            type Type = $x<T0, Y>;
        }
    };
}


generic1!(Option);
generic2!(Result);
generic1!(Vec);
// TODO: Add more HKTs for std




/// &X/Box<X>/YourCoolSmartPtr<X> shouldn't implement Generc1<X> cause they behave exactly as X
/// Instead they should implement Generic1<T> if X implements Generic1<T> etc
impl<'a, X, T> Generic1 for &'a X where X: Generic1<Type=T> {
    type Type = T;
}
impl<'a, X, Y, T> Rebind1<Y> for &'a X where X: Rebind1<Y, Type=T> {
    type Type = T;
}
impl<'a, X, T> Generic2 for &'a X where X: Generic2<Type=T> {
    type Type = T;
}
impl<'a, X, Y, T> Rebind2<Y> for &'a X where X: Rebind2<Y, Type=T> {
    type Type = T;
}
macro_rules! generic_refs {
    ($x:ident) => {
        impl<X, T> Generic1 for $x<X> where X: Generic1<Type=T> {
            type Type = T;
        }
        impl<X, Y, T> Rebind1<Y> for $x<X> where X: Rebind1<Y, Type=T> {
            type Type = T;
        }
        impl<X, T> Generic2 for $x<X> where X: Generic2<Type=T> {
            type Type = T;
        }
        impl<X, Y, T> Rebind2<Y> for $x<X> where X: Rebind2<Y, Type=T> {
            type Type = T;
        }
    };
}
generic_refs!(Box);
generic_refs!(Rc);
generic_refs!(Arc);


// ---------------
impl<T> Functor for Option<T> {
    fn fmap<Y, F: Fn(<Option<T> as Generic1>::Type)->Y>(self, f: F) -> <Option<T> as Rebind1<Y>>::Type {
        match self {
            Some(value) => Some(f(value)),
            None => None
        }
    }
}

impl<T> Monad for Option<T> {
    fn unit(value: T) -> Option<T> { Some(value) }
    fn bind<U, F: Fn(<Option<T> as Generic1>::Type) -> <Option<T> as Rebind1<U>>::Type>(self, f: F) -> <Option<T> as Rebind1<U>>::Type {
        match self {
            Some(value) => f(value),
            None => None
        }
    }
    fn join<U>(self) -> <Option<T> as Rebind1<U>>::Type where <Option<T> as Generic1>::Type: Equals<<Option<T> as Rebind1<U>>::Type> {
        match self {
            Some(value) => value.eqcast(),
            None => None
        }
    }
}


// ---------------

impl<T, E> Functor for Result<T, E> {
    fn fmap<Y, F: Fn(<Result<T, E> as Generic1>::Type)->Y>(self, f: F) -> <Result<T, E> as Rebind1<Y>>::Type {
        match self {
            Ok(value) => Ok(f(value)),
            Err(e) => Err(e)
        }
    }
}
impl<T> Functor for Vec<T> {
    fn fmap<Y, F: Fn(<Vec<T> as Generic1>::Type)->Y>(self, f: F) -> <Vec<T> as Rebind1<Y>>::Type { self.into_iter().map(f).collect() }
}



// ---------------


/// One of the basic binary operation type
/// It's autoimplemeted for all types which implement std::ops::Add<Self, Output=Self>
pub struct Add;
impl<T: std::ops::Add<Output=T>> BinaryOperation<T> for Add {
    fn apply(lhs: T, rhs: T) -> T { lhs + rhs }
}

impl AssociativeOperation<isize> for Add {}
impl AssociativeOperation<i8> for Add {}
impl AssociativeOperation<i16> for Add {}
impl AssociativeOperation<i32> for Add {}
impl AssociativeOperation<i64> for Add {}
impl AssociativeOperation<u16> for Add {}
impl AssociativeOperation<u32> for Add {}
impl AssociativeOperation<u64> for Add {}
/*
requires #![feature(zero_one)]
impl<T: std::num::Zero> Monoid<Add> for T where Add: AssociativeOperation<T> {
    fn one() -> T { <T as std::num::Zero>::zero() }
}
*/

/// One of the basic binary operation type
/// It's autoimplemeted for all types which implement std::ops::Mul<Self, Output=Self>
pub struct Mul;
impl<T: std::ops::Mul<Output=T>> BinaryOperation<T> for Mul {
    fn apply(lhs: T, rhs: T) -> T { lhs * rhs }
}

impl AssociativeOperation<isize> for Mul {}
impl AssociativeOperation<i8> for Mul {}
impl AssociativeOperation<i16> for Mul {}
impl AssociativeOperation<i32> for Mul {}
impl AssociativeOperation<i64> for Mul {}
impl AssociativeOperation<usize> for Mul {}
impl AssociativeOperation<u8> for Mul {}
impl AssociativeOperation<u16> for Mul {}
impl AssociativeOperation<u32> for Mul {}
impl AssociativeOperation<u64> for Mul {}

/*
requires #![feature(zero_one)]
impl<T: std::num::One> Monoid<Mul> for T where Mul: AssociativeOperation<T> {
    fn one() -> T { <T as std::num::One>::one() }
}
*/

/// Concatination operation for sequenses
pub struct Concat;
impl<U, T: IntoIterator<Item=U> + std::iter::FromIterator<U>> BinaryOperation<T> for Concat {
    fn apply(lhs: T, rhs: T) -> T { lhs.into_iter().chain(rhs.into_iter()).collect() }
}
impl<U, T: IntoIterator<Item=U> + std::iter::FromIterator<U>> AssociativeOperation<T> for Concat {}
impl<U, T> Monoid<Concat> for T where T: std::iter::FromIterator<U> + IntoIterator<Item=U> {
    fn one() -> T {
        <T as std::iter::FromIterator<U>>::from_iter(std::iter::empty())
    }
}



#[test]
fn it_works() {
    let x = Some(1);
    let f1 = |x|Some(x*2);
    let f2 = |x|Some(x*2);
    assert!(x.fmap(f1).join() == x.bind(f2));

    let x = Some(Some(1));
    assert!(x.bind(|x|x) == x.join());
}