Multiplate Rust

multiplate.rs

//! this library is largely "incorrect" in the sense that projectors should be exitentials and not part of type arguments
// https://hackage.haskell.org/package/multiplate-0.0.3/docs/src/Data-Generics-Multiplate.html


use std::{marker::PhantomData};

pub trait Funct {
    type F<T>;
}

pub trait Functor<F : Funct = Self> {
    fn fmap<A,B>(func : impl Fn(A) -> B, funct : F::F<A>) -> F::F<B>;
}

pub trait Apply<F : Funct = Self> : Functor<F> {
    fn lift_a2<A,B,C>(func : impl Fn(A,B)->C, funct_a : F::F<A>, funct_b : F::F<B>)-> F::F<C>;
    
    fn apply<A,B>(f : F::F<impl Fn(A)->B>, funct : F::F<A>) -> F::F<B> {
        Self::lift_a2(|f_inner, a| f_inner(a), f, funct)
    }
}

pub trait Applicative<F : Funct = Self> : Apply<F> {
    fn pure<A>(a : A) -> F::F<A>;
}


pub trait Flatmap<F : Funct = Self> : Apply<F> {
    fn flatten<E>(ffa : F::F< F::F<E> >)->F::F<E> {
        Self::flatmap(|x|x, ffa)
    }
    fn flatmap<A,B>(f : impl Fn(A)->F::F<B>, fa : F::F<A>)->F::F<B> {
        Self::flatten(Self::fmap(f, fa))
    }

    fn tail_rec_m<A,B>(f : impl Fn(A)->F::F<core::ops::ControlFlow<B,A>>, fa : F::F<A>)->F::F<B>;
}

pub trait Monad<F : Funct = Self> : Flatmap<F> + Applicative<F> {}
impl<F, T> Monad<F> for T where F : Funct, T : Flatmap<F> + Applicative<F>{}


pub trait Magma<T = Self> {
    fn op(left : T, right : T ) -> T;
}

pub trait Semigroup<T = Self> : Magma<T> {}
pub trait Empty<T = Self> {
    fn empty()-> T;
}

pub trait CommutativeSemigroup<A = Self> : Semigroup<A>{}
impl<A,T> CommutativeSemigroup<A> for T where T : Semigroup<A> {}

pub trait Monoid<T = Self> : Semigroup<T> + Empty<T> {}
impl<T,U> Monoid<T> for U where U : Semigroup<T> + Empty<T> {}

pub trait CommutativeMonoid<T = Self> : Monoid<T> + CommutativeSemigroup<T> {}
impl<T,U> CommutativeMonoid<T> for U where U : Monoid<T> + CommutativeSemigroup<T>{}

pub trait EmptyK<F : Funct = Self>  {
    fn empty_k<A>() -> F::F<A>;
}
pub trait MagmaK<F : Funct = Self> {
    fn combine_k<A>(left : F::F<A>, right : F::F<A>)->F::F<A>;
}
pub trait SemigroupK<F : Funct = Self> : MagmaK<F> {}
pub trait NonEmptyAlternative<F : Funct = Self> : Applicative<F> + SemigroupK<F>{}
impl<F, T> NonEmptyAlternative<F> for T where F : Funct,  T : Applicative<F> + SemigroupK<F>{}


pub trait MonoidK<F : Funct = Self> : SemigroupK<F> + EmptyK<F> {}
impl<F, T> MonoidK<F> for T where F : Funct, T : SemigroupK<F> + MonoidK<F> {}

pub trait Alternative<F : Funct = Self> : NonEmptyAlternative<F> + MonoidK<F> {}




pub trait UnorderedFoldable<F :Funct = Self> {
    fn unordered_fold_map<A,B, C : CommutativeMonoid<B>>(f : impl Fn(A)->B, fa : F::F<A>)-> B;
}

pub trait Foldable<F : Funct = Self> : UnorderedFoldable<F> {
    fn fold_left<A,B>(f : impl Fn(B,A)->B, fa : F::F<A>, b : B)->B;
    fn fold_right<A,B>(f : impl Fn(B,A)->B, fa : F::F<A>, b : B)->B;
}

pub trait Traverse<T : Funct = Self> : Functor<T> + Foldable<T> {
    fn traverse<A, B, F : Funct, App : Applicative<F>>(f : impl Fn(A)->F::F<B>, t : T::F<A>) -> F::F<T::F<B>>;
}

trait Num<T = Self> {
  fn plus(left : T, right : T)->T;
  fn mul( left : T, right : T)->T;
  fn negate(x : T)->T;
  fn from_integer(x : u64)->T;
  fn signum(x : T)->T;
  fn abs(x : T)->T;
}













// WHERE MULTIPLATE "STARTS"


pub trait NaturalTranformation<F : Funct, G : Funct>{
    fn natural_tranformation<A>(f : F::F<A>)->G::F<A>;
}
pub trait Projector<P : Funct,A> {
    fn project<F : Funct>(&self, p_f : P::F<F>) -> impl Fn(A) -> F::F<A>;
}
pub trait Multiplate<P : Funct = Self> {
    fn multiplate<G : Funct, A : Applicative<G>>(plate : P::F<G>) -> P::F<G>;
    fn mk_plate<A, G: Funct, Proj : Projector<P, A> >
    (p : impl Fn(Proj, A)->G::F<A>) -> P::F<G>;
}

fn apply_natural_transform
< P    : Funct
, F    : Funct
, G    : Funct
, Mult : Multiplate<P>
, NatT : NaturalTranformation<F,G>
, A
, Proj : Projector<P, A>
> (plate : P::F<F>)-> P::F<G>
where <P as Funct>::F<F> : Clone
{
    Mult::mk_plate(move |proj : Proj, a| NatT::natural_tranformation(Projector::<P,A>::project(&proj,plate.clone())(a)))
}


fn pure_plate
< P    : Funct
, G    : Funct
, Mult : Multiplate<P>
, Alt  : Alternative<G>
, Proj : Projector<P,()>
>() -> P::F<G> 
{ Mult::mk_plate(|_ : Proj,_| Alt::empty_k() ) }


fn kleisli_pipe< M : Funct, Mon : Monad<M>, A, B, C> (f : impl Fn(A)->M::F<B>,  g : impl Fn(B)->M::F<C>, ) -> impl Fn(A)->M::F<C> {
    move |a| Mon::flatmap(&g, f(a))
}
fn kleisli_compose< M : Funct, Mon : Monad<M>, A, B, C> ( f : impl Fn(B)->M::F<C>, g : impl Fn(A)->M::F<B> ) -> impl Fn(A)->M::F<C> {
    kleisli_pipe::<M,Mon,_,_,_>(g, f)
}


fn kleisli_compose_plate
< P    : Funct
, M    : Funct
, Mult : Multiplate<P>
, Mon  : Monad<M>
, A
, Proj : Projector<P, A>
>(left : P::F<M>, right : P::F<M>) -> P::F<M> 
where P::F<M> : Clone
{
    Mult::mk_plate(|proj : Proj, a| 
        kleisli_compose::<M,Mon,_,_,_>(
            proj.project(left.clone()),
            proj.project(right.clone())
        )(a)
    )
}



fn compose_plate_right_id
< P    : Funct
, F    : Funct
, Mult : Multiplate<P>
, A
, Proj : Projector<P,A>
>(p_f : P::F<F>, id : P::F<Identity>) -> P::F<F>
where P::F<F>        : Clone, 
      P::F<Identity> : Clone
{
    Mult::mk_plate(move |proj : Proj, a : A| 
        proj.project
            (p_f.clone())
            (proj.project(id.clone())(a)) 
    )
}


fn compose_plate_left_id
< P    : Funct
, F    : Funct
, Mult : Multiplate<P>
, F_   : Functor<F>
, A
, Proj : Projector<P,A>
>(p_f : P::F<F>, id : P::F<Identity>) -> P::F<F>
where P::F<F>        : Clone, 
      P::F<Identity> : Clone
{
    Mult::mk_plate(move |proj : Proj, a : A| 
        F_::fmap
        ( proj.project(id.clone())
        , proj.project(p_f.clone())(a)
        )
    )
}



fn append_plate
< P : Funct
, O : Monoid
, Mult : Multiplate<P>
, A
, Proj : Projector<P,A>
>( left : P::F<Constant<O>>, right : P::F<Constant<O>>) -> P::F<Constant<O>>
where P::F<Constant<O>> : Clone,
      A                 : Clone
{
    Mult::mk_plate(move |proj : Proj, a : A|
        Constant::<O>::lift_a2(
            |x, _|x,
            proj.project(left.clone())(a.clone()),
            proj.project(right.clone())(a.clone())
        )
    )
}


fn m_children
< P    : Funct
, O    : Monoid
, Mult : Multiplate<P>
>() -> impl Fn(P::F<Constant<O>>) -> P::F<Constant<O>> {
    Mult::multiplate::<Constant<O>,Constant<O>>
}

#[allow(unconditional_recursion)]
fn preorder_fold
< P : Funct
, O : Monoid
, Mult : Multiplate<P>
, A
, Proj : Projector<P, A>
>(f : P::F<Constant<O>>) -> P::F<Constant<O>>
where P::F<Constant<O>> : Clone,
      A                 : Clone,
{
    append_plate::<P, O, Mult, A, Proj>(
        f.clone(),
        Mult::multiplate::<Constant<O>,Constant<O>>(preorder_fold::<P, O, Mult, A, Proj>(f)),
    )
}

#[allow(unconditional_recursion)]
fn postorder_fold
< P : Funct
, O : Monoid
, Mult : Multiplate<P>
, A
, Proj : Projector<P, A>
>(f : P::F<Constant<O>>) -> P::F<Constant<O>>
where P::F<Constant<O>> : Clone,
      A                 : Clone,
{
    append_plate::<P, O, Mult, A, Proj>(
        Mult::multiplate::<Constant<O>,Constant<O>>(preorder_fold::<P, O, Mult, A, Proj>(f.clone())),
        f,
    )
}

fn map_children<P : Funct, Mult : Multiplate<P>>() -> impl Fn(P::F<Identity>) -> P::F<Identity> {
    Mult::multiplate::<Identity,Identity>
}
fn map_family<P : Funct, Mult : Multiplate<P>, A, Proj : Projector<P, A>>() -> impl Fn(P::F<Identity>) -> P::F<Identity>
where
    P::F<Identity> : Clone
{
    map_family_m::<P, Identity, Mult, Identity, A, Proj>
}

fn map_children_m
< P    : Funct
, M    : Funct
, Mult : Multiplate<P>
, Mon  : Monad<M>
>() -> impl Fn(P::F<M>) -> P::F<M>
{
    Mult::multiplate::<M,Mon>
}

fn map_family_m
< P    : Funct
, M    : Funct
, Mult : Multiplate<P>
, Mon  : Monad<M>
, A
, Proj : Projector<P,A>
>(f : P::F<M>) -> P::F<M>
where 
    P::F<M> : Clone
{
    kleisli_compose_plate::<P, M, Mult, Mon, A, Proj>(
        f.clone(),
        Mult::multiplate::<M, Mon>(map_family_m::<P, M, Mult, Mon, A, Proj>(f))
    )
}


fn eval_family
< P    : Funct
, M    : Funct
, Mult : Multiplate<P>
, A
, Proj : Projector<P,A>
>(f : P::F::<Option<()>>) -> P::F<Identity> 
where P::F<Option<()>> : Clone,
      P::F<Identity> : Clone,
      P::F<OptionT1<Identity>> : Clone,
      A :Clone
{
    struct OptionToOptionTIdentity;
    impl NaturalTranformation<Option<()>, OptionT1<Identity>> for OptionToOptionTIdentity{
        fn natural_tranformation<A>(f : <Option<()> as Funct>::F<A>)-><OptionT1<Identity> as Funct>::F<A> {
            OptionT(f)
        }
    }
    eval_family_m::<P,Identity,Mult,Identity,A,Proj>(
            apply_natural_transform::<P, Option<()>,OptionT1<Identity>, Mult,OptionToOptionTIdentity,A, Proj>(f)
    )
}


fn eval_family_m
< P    : Funct
, M    : Funct
, Mult : Multiplate<P>
, Mon  : Monad<M>
, A
, Proj : Projector<P, A>
>(p_f : P::F::<OptionT1<M>>) -> P::F<M>
where
    P::F<OptionT1<M>> : Clone,
    P::F<M>           : Clone,
    A                 : Clone,
{
    map_family_m::<P,M,Mult,Mon,A,Proj>(Mult::mk_plate(|proj : Proj, a : A|{
        Mon::flatmap(
            |x : Option<_>| 
                x.map_or(
                    Mon::pure(a.clone()), 
                    |g| proj.project::<M>(eval_family_m::<P,M,Mult,Mon,A,Proj>(p_f.clone()))(g)
                ),
            (| OptionT(x)| x)(proj.project(p_f.clone())(a.clone())), 
        )
    }))
}



fn always
< P    : Funct
, Mult : Multiplate<P>
, A
, Proj : Projector<P, A>
>( p_f : P::F<Option<()>> ) -> P::F<Identity> 
where
    P::F<Option<()>>         : Clone,
    P::F<OptionT1<Identity>> : Clone,
    A                        : Clone,   
{
    struct NT;
    impl NaturalTranformation<Option<()>, OptionT1<Identity>> for NT {
        fn natural_tranformation<A>(f : <Option<()> as Funct>::F<A>)-><OptionT1<Identity> as Funct>::F<A> {
            OptionT(f)
        }
    }
    always_m::<P,Identity,Mult,Identity,A,Proj>(
        apply_natural_transform::<P, Option<()>, OptionT1<Identity>, Mult, NT, A, Proj>(p_f)
    )
}


fn always_m
< P    : Funct
, F    : Funct
, Mult : Multiplate<P>
, Func : Functor<F>
, A
, Proj : Projector<P,A>
>(p_f : P::F<OptionT1<F>>) -> P::F<F>
where
    P::F<OptionT1<F>> : Clone,
    A : Clone
{
    Mult::mk_plate(|proj : Proj, a : A| 
        Func::fmap(
            | m : Option<A>| m.unwrap_or(a.clone()),
            (| OptionT(x)| x)(proj.project(p_f.clone())(a.clone())), 
        )
    )
}





fn traverse_for
< P : Funct
, Mult : Multiplate<P>
, A
, Proj : Projector<P, A>
>(proj : &Proj, id : P::F<Identity>, a : A) -> A {
    proj.project(id)(a)
}

fn traverse_m_for
< P    : Funct
, M    : Funct
, Mult : Multiplate<M>
, Mon  : Monad<M>
, A
, Proj : Projector<P, A>
>(proj : Proj, p_f : P::F<M>)->impl Fn(A)->M::F<A>
where
    P::F<M> : Clone
{
    move |a| proj.project(p_f.clone())(a)
}


fn fold_for
< P    : Funct
, Mult : Multiplate<P>
, O
, A
, Proj : Projector<P,A>
>( proj : Proj, p_c : P::F<Constant<O>>, a : A) -> O {
    (|Constant(c, _)|c)(proj.project(p_c)(a))
}

fn unwrap_for
< P    : Funct
, Mult : Multiplate<P>
, O
, A
, Proj : Projector<P,A>
, B
>(unwrapper : impl Fn(O)->B,  proj : Proj, p_c : P::F<Constant<O>>, a : A) -> B
{
    unwrapper(fold_for::<_,Mult,_,_,Proj>(proj, p_c, a))

}

fn sum_for
< P    : Funct
, Mult : Multiplate<P>
, N    : Num
, A
, Proj : Projector<P,A>
>(proj : Proj, p_c_s : P::F<Constant<Sum<N>>>, a : A) -> N {
    unwrap_for::<_,Mult,_,_,Proj,_>(|Sum(n)|n, proj, p_c_s, a)
}

fn product_for
< P    : Funct
, Mult : Multiplate<P>
, N    : Num
, A
, Proj : Projector<P,A>
>(proj : Proj, p_c_s : P::F<Constant<Product<N>>>, a : A) -> N {
    unwrap_for::<_,Mult,_,_,Proj,_>(|Product(n)|n, proj, p_c_s, a)
}

fn all_for
< P    : Funct
, Mult : Multiplate<P>
, A
, Proj : Projector<P,A>
>(proj : Proj, p_c_s : P::F<Constant<All>>, a : A) -> bool {
    unwrap_for::<_,Mult,_,_,Proj,_>(|All(n)|n, proj, p_c_s, a)
}

fn any_for
< P    : Funct
, Mult : Multiplate<P>
, A
, Proj : Projector<P,A>
>(proj : Proj, p_c_s : P::F<Constant<All>>, a : A) -> bool {
    unwrap_for::<_,Mult,_,_,Proj,_>(|All(n)|n, proj, p_c_s, a)
}

fn first_for
< P    : Funct
, Mult : Multiplate<P>
, A
, Proj : Projector<P,A>
, B
>(proj : Proj, p_c_s : P::F<Constant<First<B>>>, a : A) -> Option<B> {
    unwrap_for::<_,Mult,_,_,Proj,_>(|First(n)|n, proj, p_c_s, a)
}

fn last_for
< P    : Funct
, Mult : Multiplate<P>
, A
, Proj : Projector<P,A>
, B
>(proj : Proj, p_c_s : P::F<Constant<Last<B>>>, a : A) -> Option<B> {
    unwrap_for::<_,Mult,_,_,Proj,_>(|Last(n)|n, proj, p_c_s, a)
}























// impls


#[derive(Debug,Clone, Copy)]
pub struct Identity;
impl Funct for Identity {
    type F<T> = T;
}
impl Functor for Identity {
    fn fmap<A,B>(func : impl Fn(A) -> B, funct : <Self as Funct>::F<A>) -> <Self as Funct>::F<B> {
        func(funct)
    }
}
impl Apply for Identity {
    fn lift_a2<A,B,C>(func : impl Fn(A,B)->C, funct_a : <Self as Funct>::F<A>, funct_b : <Self as Funct>::F<B>)-> <Self as Funct>::F<C> {
        func(funct_a, funct_b)
    }
    fn apply<A,B>(f : <Self as Funct>::F<impl Fn(A)->B>, funct : <Self as Funct>::F<A>) -> <Self as Funct>::F<B> {
        f(funct)
    }
}
impl Applicative for Identity { fn pure<A>(a : A) -> <Self as Funct>::F<A> { a } }
impl Flatmap for Identity {
    fn flatmap<A,B>(f : impl Fn(A)-><Self as Funct>::F<B>, fa : <Self as Funct>::F<A>)-><Self as Funct>::F<B> {
        f(fa)
    }
    fn tail_rec_m<A,B>(f : impl Fn(A)-><Self as Funct>::F<core::ops::ControlFlow<B,A>>, fa : <Self as Funct>::F<A>)-><Self as Funct>::F<B> {
        let mut state = f(fa);
        loop {
            state = match state {
                std::ops::ControlFlow::Continue(c) => f(c),
                std::ops::ControlFlow::Break(b) => return b,
            }
        }
    }
}
impl UnorderedFoldable for Identity {
    fn unordered_fold_map<A,B, C : CommutativeMonoid<B>>(f : impl Fn(A)->B, fa : <Self as Funct>::F<A>)-> B {
        f(fa)
    }
}
impl Foldable for Identity {
    fn fold_left<A,B>(f : impl Fn(B,A)->B, fa : <Self as Funct>::F<A>, b : B)->B {
        f(b,fa)
    }

    fn fold_right<A,B>(f : impl Fn(B,A)->B, fa : <Self as Funct>::F<A>, b : B)->B {
        f(b,fa)
    }
}

impl Traverse for Identity {
    fn traverse<A, B, F : Funct, App : Applicative<F>>(f : impl Fn(A)->F::F<B>, t : <Self as Funct>::F<A>) -> F::F<<Self as Funct>::F<B>> {
        f(t)
    }
}

#[derive(Debug,PartialEq, Eq, PartialOrd, Ord)]
pub struct Constant<A,B=()>(A, PhantomData<B>);
impl<A : Clone, B> Clone for Constant<A,B> {fn clone(&self) -> Self { Constant(self.0.clone(), PhantomData::<B>) }}
impl<A : Copy, B> Copy for Constant<A,B> {}

impl<A,B> Funct for Constant<A,B> {
    type F<T> = Constant<A, T>;
}
impl<T,U> Functor for Constant<T,U> {
    fn fmap<A,B>(_func : impl Fn(A) -> B, funct : <Self as Funct>::F<A>) -> <Self as Funct>::F<B> {
      Constant(funct.0, PhantomData::<B>)
    }
}

impl<T : Semigroup,U> Apply for Constant<T,U> {
    fn lift_a2<A,B,C>(_func : impl Fn(A,B)->C, funct_a : <Self as Funct>::F<A>, funct_b : <Self as Funct>::F<B>)-> <Self as Funct>::F<C> {
        Constant(T::op(funct_a.0,funct_b.0), PhantomData::<C>)
    }
}
impl<T : Empty, U> Empty for Constant<T,U> {
    fn empty()-> Self {
        Constant(T::empty(), PhantomData::<U>)
    }
}
impl<T : Monoid, U> Applicative for Constant<T,U> {
    fn pure<A>(_a : A) -> <Self as Funct>::F<A> {
        Constant(T::empty(),PhantomData::<A>)
    }
}

impl<T,U> UnorderedFoldable for Constant<T,U> {
    fn unordered_fold_map<A,B, C : CommutativeMonoid<B>>(_f : impl Fn(A)->B, _fa : <Self as Funct>::F<A>)-> B {
        C::empty()
    }
}
impl<T,U> Foldable for Constant<T,U> {
    fn fold_left<A,B>(_f : impl Fn(B,A)->B, _fa : <Self as Funct>::F<A>, b : B)->B {
        b
    }
    fn fold_right<A,B>(_f : impl Fn(B,A)->B, _fa : <Self as Funct>::F<A>, b : B)->B {
        b
    }
}
impl<T,U> Traverse for Constant<T,U> {
    fn traverse<A, B, F : Funct, App : Applicative<F>>(_f : impl Fn(A)->F::F<B>, t : <Self as Funct>::F<A>) -> F::F<<Self as Funct>::F<B>> {
        App::pure(Constant(t.0, PhantomData::<B>))
    }
}




impl<A> Funct for Option<A> {
    type F<T> = Option<T>;
}
impl<T> Functor for Option<T> {
    fn fmap<A,B>(func : impl Fn(A) -> B, funct : <Self as Funct>::F<A>) -> <Self as Funct>::F<B> {
        funct.map(func)
    }
}
impl<T> Apply for Option<T> {
    fn lift_a2<A,B,C>(func : impl Fn(A,B)->C, funct_a : <Self as Funct>::F<A>, funct_b : <Self as Funct>::F<B>)-> <Self as Funct>::F<C> {
        match (funct_a, funct_b) {
            (Some(l), Some(r)) => Some(func(l,r)),
            _ => None,
        }
    }
}
impl<T> Flatmap for Option<T> {
    fn flatmap<A,B>(f : impl Fn(A)-><Self as Funct>::F<B>, fa : <Self as Funct>::F<A>)-><Self as Funct>::F<B> {
        fa.and_then(f)
    }

    fn tail_rec_m<A,B>(f : impl Fn(A)-><Self as Funct>::F<core::ops::ControlFlow<B,A>>, fa : <Self as Funct>::F<A>)-><Self as Funct>::F<B> {
        let mut state = fa.and_then(&f);
        loop {
            state = match state {
                Some(std::ops::ControlFlow::Break(b))    => return Some(b),
                Some(std::ops::ControlFlow::Continue(c)) => f(c),
                None                                     => return None,
            }
        }
    }
}
impl<T> Applicative for Option<T> {
    fn pure<A>(a : A) -> <Self as Funct>::F<A> {
        Some(a)
    }
}



#[derive(Debug,Clone, Copy)]
pub struct OptionT0;
impl Funct for OptionT0 {
    type F<M> = OptionT1<M>;
}
pub struct OptionT1<M>(PhantomData<M>);
impl<M> Clone for OptionT1<M> { fn clone(&self) -> Self { OptionT1(PhantomData) } }
impl<M> Copy  for OptionT1<M> {}
impl<M : Funct> Funct for OptionT1<M> {
    type F<T> = OptionT<M,T>;
}

pub struct OptionT<M : Funct, A>(M::F<Option<A>>);
impl<M : Funct,A> Funct for OptionT<M,A> {
    type F<T> = OptionT<M, T>;
}


#[derive(Debug, Clone, Copy, PartialEq, PartialOrd, Eq, Ord)]
pub struct Sum<T>(T);

impl<U> Funct for Sum<U> {type F<T> = Sum<T>;}
impl<U> Functor for Sum<U> {
    fn fmap<A,B>(func : impl Fn(A) -> B, funct : <Self as Funct>::F<A>) -> <Self as Funct>::F<B> {
        Sum(func(funct.0))        
    }
}

impl<U : Num> Magma for Sum<U> 
where 
{ fn op(left : Self, right : Self ) -> Self {  Sum(U::plus(left.0, right.0))  } }
impl<U : Num> Semigroup for Sum<U> {}
impl<U : Num> Empty for Sum<U> {
    fn empty()-> Self {
        Sum(U::from_integer(0))       
    }
}

#[derive(Debug, Clone, Copy, PartialEq, PartialOrd, Eq, Ord)]
pub struct Product<T>(T);

impl<U> Funct for Product<U> {type F<T> = Product<T>;}
impl<U> Functor for Product<U> {
    fn fmap<A,B>(func : impl Fn(A) -> B, funct : <Self as Funct>::F<A>) -> <Self as Funct>::F<B> {
        Product(func(funct.0))        
    }
}

impl<U : Num> Magma for Product<U> 
where 
{ fn op(left : Self, right : Self ) -> Self {  Product(U::mul(left.0, right.0))  } }
impl<U : Num> Semigroup for Product<U> {}
impl<U : Num> Empty for Product<U> {
    fn empty()-> Self {
        Product(U::from_integer(1))       
    }
}





struct All(bool);

impl Magma for All {
    fn op(left : Self, right : Self ) -> Self {
        All(left.0 && right.0)
    }
}
impl Semigroup for All{}
impl Empty for All{
    fn empty()-> Self {
        All(true)
    }
}

struct Any_(bool);

impl Magma for Any_ {
    fn op(left : Self, right : Self ) -> Self {
        Any_(left.0 || right.0)
    }
}
impl Semigroup for Any_{}
impl Empty for Any_ {
    fn empty()-> Self {
        Any_(false)
    }
}




pub struct First<T>(Option<T>);
impl<U> Magma for First<U> {
    fn op(left : Self, right : Self ) -> Self {
        match [&left.0,&right.0] {

            [Some(_),_] => left,
            _           => right,
        }
    }
}
impl<U> Semigroup for First<U> {}
impl<U> Empty for First<U>{
    fn empty()-> Self {
        First(None)
    }
}

pub struct Last<T>(Option<T>);
impl<U> Magma for Last<U> {
    fn op(left : Self, right : Self ) -> Self {
        match [&left.0,&right.0] {

            [_,Some(_)] => right,
            _           => left,
        }
    }
}
impl<U> Semigroup for Last<U> {}
impl<U> Empty for Last<U>{
    fn empty()-> Self {
        Last(None)
    }
}