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

using namespace std;

template <template <class, class...> class f>
struct functor {
  template<typename a, typename b>
  static f<b>* map(function<b(a)> ab, const f<a>* fa);
};

template <template <class, class...> class f>
struct applicative {
  template<typename a>
  static f<a>* pure(a aval);

  template <typename a, typename b>
  static f<b>* ap(const f<function<b(a)>>* fab, const f<a>* fa);
};

template <template <class, class...> class f>
struct monad {
  template<typename a, typename b>
  static f<b>* bind(function<f<b>(a)> afb, const f<a>* fa);
};

template <typename a>
struct semigroup {
  static a* combine(a* x, a* y);
};

template <typename a>
struct monoid {
  static a* empty();
};

template<>
struct functor<vector> {
  template<typename a, typename b>
  static vector<b>* map(function<b(a)> ab, const vector<a>* va) {
    vector<b>* vb = new vector<b>(va->size());
    for (unsigned i = 0; i < va->size(); ++i) {
      (*vb)[i] = ab((*va)[i]);
    }
    return vb;
  }
};

template <>
struct applicative<vector> {
  template<typename a>
  static vector<a>* pure(const a aval) {
    vector<a>* va = new vector<a>(1);
    (*va)[0] = aval;
    return va;
  };

  template <typename a, typename b>
  static vector<b>* ap(const vector<function<b(a)>>* vab, const vector<a>* va) {
    vector<b>* vb = new vector<b>(va->size() * vab->size());
    unsigned i = 0;
    for (auto ait = va->begin(); ait < va->end(); ++ait) {
      for (auto abit = vab->begin(); abit < vab->end(); ++abit) {
        (*vb)[i++] = (*abit)(*ait);
      }
    }
    return vb;
  };
};

template <>
struct monad<vector> {
  template<typename a, typename b>
  static vector<b>* bind(const vector<a>* va, function<vector<b>*(a)> avb) {
    vector<b>* res = new vector<b>();
    for (auto ait = va->begin(); ait < va->end(); ++ait) {
      const vector<b>* vb = avb(*ait);
      res->insert(res->end(), vb->begin(), vb->end());
      // While deleting seems dangerous, we might argue that part of the contract
      // of bind is that intermediate structures are subject to deletion as
      // a means of avoiding leaking memory since the caller likely won't be
      // able to take care of this.
      delete vb;
    }
    return res;
  }
};

template <typename a>
struct semigroup<vector<a>> {
  static vector<a>* combine(vector<a>* x, vector<a>* y) {
    vector<a>* res = new vector<a>(x->size() + y->size());
    unsigned i = 0;
    for (auto it = x->begin(); it < x->end(); ++it) {
      (*res)[i++] = *it;
    }
    for (auto it = y->begin(); it < y->end(); ++it) {
      (*res)[i++] = *it;
    }
    return res;
  }
};

template <typename a>
struct monoid<vector<a>> {
  static vector<a>* empty() {
    return new vector<a>(0);
  }
};

template <typename a>
void render_vec(ostream& os, vector<a>* vs) {
  for (auto it = vs->begin(); it < vs->end(); ++it) {
    if (it > vs->begin()) cout << ", ";
    cout << *it;
  }
}

int main(int argc, char** argv) {
  vector<int> vi { 1, 2, 3, 4 };
  vector<string>* vs = functor<vector>::map<int, string>(
    [](int i) { return to_string(i*2); }, &vi
  );
  cout << "functor::map       => ";
  render_vec(cout, vs);
  cout << '\n';
  delete vs;

  cout << "applicative::pure  => ";
  vs = applicative<vector>::pure<string>("hi");
  render_vec(cout, vs);
  cout << '\n';
  delete vs;

  cout << "applicative::ap    => ";
  vector<function<string(int)>> vis
    { ([](int i) { return to_string(i);   })
    , ([](int i) { return to_string(i*2); })
    , ([](int i) { return to_string(i*3); })
    , ([](int i) { return to_string(i*4); })
    };
  vs = applicative<vector>::ap<int, string>(&vis, &vi);
  render_vec(cout, vs);
  cout << '\n';
  delete vs;

  cout << "monad::bind        => ";
  vs = monad<vector>::bind<int, string>(
    &vi,
    [](int n) {
      vector<string>* res = new vector<string>(n);
      for (unsigned i = 1; i <= (unsigned)n; ++i) {
        (*res)[i-1] = to_string(i);
      }
      return res;
    }
  );
  render_vec(cout, vs);
  cout << '\n';
  delete vs;

  cout << "monoid::empty\n";
  cout << "semigroup::combine => ";
  vector<string>* vs0 = monoid<vector<string>>::empty();
  vector<string>  vs1 { "hi", "there" };
  vector<string>* vs2 = semigroup<vector<string>>::combine(vs0, &vs1);
  render_vec(cout, vs2);
  cout << '\n';
  delete vs0;
  delete vs2;

  return 0;
}