#include <functional>
#include <vector>
#include <iostream>

template< template<class> class M >
class Monad{
public:
    template<class A>
    static M<A> Return(A a);

    template<class A, class B>
    static M<B> Bind(M<A> a, std::function<M<B>(A)> f);
};

template<class A>
class Unit{};

template<>
class Monad<Unit> {
public:
    template<class A>
    static Unit<A> Return(A a){
      return Unit<A>();
    }

    template<class A, class B>
    static Unit<B> Bind(Unit<A> a, std::function<Unit<B>(A)> f){
      return Unit<B>();
    }
};

template<class A>
struct Id{
  A a;
};

template<>
class Monad<Id> {
public:
    template<class A>
    static Id<A> Return(A a){
      return {a};
    }

    template<class A, class B>
    static Id<B> Bind(Id<A> a, std::function<Id<B>(A)> f){
      return f(a.a);
    }
};

template<class A>
struct Maybe{
  A* a;
};

template<>
class Monad<Maybe> {
public:
    template<class A>
    static Maybe<A> Return(A a){
      return {new A(a)};
    }

    template<class A, class B>
    static Maybe<B> Bind(Id<A> a, std::function<Maybe<B>(A)> f){
      if ( a.a ){
        return f(*a.a);
      }
      return {nullptr};
    }
};


template<class T>
using List = std::vector<T>;

template<>
class Monad<List> {
public:
    template<class A>
    static List<A> Return(A a){
      return {a};
    }

    template<class A, class B>
    static List<B> Bind(List<A> a, std::function<List<B>(A)> f){
      List<B> out;
      for ( auto& x : a ){
        List<B> b = f(x);
        for ( auto& y : b ){
          out.push_back(y);
        }
      }
      return out;
    }
};


List<int> WithLists(){
  using M = Monad<List>;

  List<int> xs = {1, 2, 3};
  List<int> ys = {5, 6, 7};

  return M::Bind<int,int>(xs, [&](int x){
    return M::Bind<int,int>(ys, [&](int y){
      return M::Return(x * y);
    });
  });
}



int main(){
  List<int> xs = WithLists();
  std::cout << "[";
  for ( auto& x : xs ){
    std::cout << x << " ";
  }
  std::cout << "]\n";

  return 0;
}