Knights & Knaves solved with the list monad in C++

knights_knaves.cpp

#include <iostream>
#include <iterator>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

//------------------------------------------------------------------------------
// The "many-worlds" method of solving problems with the list monad
// See Bartosz Milewski's 4-part article:
// http://bartoszmilewski.com/2015/05/11/using-monads-in-c-to-solve-constraints-1-the-list-monad/

//------------------------------------------------------------------------------
// A few functions to treat vectors as monads

template <typename VA, typename F>
auto mbind(VA&& va, F&& f) -> decltype(f(va[0]))
{
  using VB = decltype(f(va[0]));
  VB vb;
  for (auto&& i : std::forward<VA>(va))
  {
    VB vf = f(std::forward<decltype(i)>(i));
    vb.insert(vb.end(),
              make_move_iterator(vf.begin()),
              make_move_iterator(vf.end()));
  }
  return vb;
}

template <typename V, typename F>
auto mthen(V&& v, F&& f) -> decltype(f())
{
  using B = decay_t<decltype(f()[0])>;
  if (std::forward<V>(v).empty()) return vector<B>{};
  return std::forward<F>(f)();
}

vector<int> guard(bool b)
{
  if (b) return vector<int>{0};
  return vector<int>{};
}

//------------------------------------------------------------------------------
// Raymond Smullyan's Knights and Knaves
// http://en.wikipedia.org/wiki/Knights_and_Knaves

enum class Person
{
  KNIGHT,
  KNAVE
};

bool says(Person p, bool prop)
{
  return (p == Person::KNAVE) ? !prop : prop;
}

bool implies(bool x, bool y)
{
  return !x || y;
}

//------------------------------------------------------------------------------
// A few "knights and knaves" problems, simply expressed

vector<Person> unknown = { Person::KNIGHT, Person::KNAVE };

vector<Person> iAmAKnight()
{
  vector<Person> a = unknown;
  return mbind(a, [&] (Person p) {
  return mthen(guard(says(p, (p == Person::KNIGHT))),
               [&] () { return vector<Person>{p}; });
  });
}

vector<Person> iAmAKnave()
{
  vector<Person> a = unknown;
  return mbind(a, [&] (Person p) {
  return mthen(guard(says(p, (p == Person::KNAVE))),
               [&] () { return vector<Person>{p}; });
  });
}

vector<Person> aSaysHeNeverClaimsToBeAKnave()
{
  vector<Person> a = unknown;
  return mbind(a, [&] (Person p) {
  return mthen(guard(says(p, (!says (p, (p == Person::KNAVE))))),
               [&] () { return vector<Person>{p}; });
  });
}

vector<pair<Person, Person>> aSaysBCallsMeAKnave()
{
  vector<Person> a = unknown;
  vector<Person> b = unknown;
  return mbind(a, [&] (Person pa) {
  return mbind(b, [&] (Person pb) {
  return mthen(guard(says(pa, (says (pb, (pa == Person::KNAVE))))),
               [&] () { return vector<pair<Person, Person>>{{pa, pb}}; });
  }); });
}

vector<pair<Person, Person>> aSaysIfBIsAKnaveThenSoAmI()
{
  vector<Person> a = unknown;
  vector<Person> b = unknown;
  return mbind(a, [&] (Person pa) {
  return mbind(b, [&] (Person pb) {
  return mthen(guard(says(pa, implies(pb == Person::KNAVE, pa == Person::KNAVE))),
               [&] () { return vector<pair<Person, Person>>{{pa, pb}}; });
  }); });
}

vector<pair<Person, Person>> aSaysWeAreBothKnaves()
{
  vector<Person> a = unknown;
  vector<Person> b = unknown;
  return mbind(a, [&] (Person pa) {
  return mbind(b, [&] (Person pb) {
  return mthen(guard(says(pa, (pa == Person::KNAVE && pb == Person::KNAVE))),
               [&] () { return vector<pair<Person, Person>>{{pa, pb}}; });
  }); });
}

vector<pair<Person, Person>> aSaysSameBSaysDifferent()
{
  vector<Person> a = unknown;
  vector<Person> b = unknown;
  return mbind(a, [&] (Person pa) {
  return mbind(b, [&] (Person pb) {
  return mthen(guard(says(pa, (pa == pb)) && says(pb, (pa != pb))),
               [&] () { return vector<pair<Person, Person>>{{pa, pb}}; });
  }); });
}

vector<tuple<Person, Person, Person>> abcProblem()
{
  vector<Person> a = unknown;
  vector<Person> b = unknown;
  vector<Person> c = unknown;
  return mbind(a, [&] (Person pa) {
  return mbind(b, [&] (Person pb) {
  return mbind(c, [&] (Person pc) {
  return mthen(guard(says(pb, says(pa, pa == Person::KNAVE))
                     && says(pc, (pb == Person::KNAVE))),
               [&] () { return vector<tuple<Person, Person, Person>>{ make_tuple(pa, pb, pc) }; });
    }); }); });
}

//------------------------------------------------------------------------------
// Outputting the answers

template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A,B>& p)
{
  return os << '(' << p.first << ',' << p.second << ')';
}


template <typename A, typename B, typename C>
ostream& operator<<(ostream& os, const tuple<A,B,C>& p)
{
  return os << '(' << get<0>(p) << ',' << get<1>(p) << ',' << get<2>(p) << ')';
}


template <typename A>
ostream& operator<<(ostream& os, const vector<A>& v)
{
  os << '[';
  auto it = v.cbegin();
  if (it != v.cend()) os << *it++;
  for (; it != v.cend(); ++it)
    os << ',' << *it;
  return os << ']';
}

ostream& operator<<(ostream& os, const Person& p)
{
  return os << (p == Person::KNIGHT ? "Knight" : "Knave");
}

int main()
{
  cout << "iAmAKnight: " << iAmAKnight() << endl;
  cout << "iAmAKnave: " << iAmAKnave() << endl;
  cout << "aSaysHeNeverClaimsToBeAKnave: " << aSaysHeNeverClaimsToBeAKnave() << endl;
  cout << "aSaysBCallsMeAKnave: " << aSaysBCallsMeAKnave() << endl;
  cout << "aSaysIfBIsAKnaveThenSoAmI: " << aSaysIfBIsAKnaveThenSoAmI() << endl;
  cout << "aSaysWeAreBothKnaves: " << aSaysWeAreBothKnaves() << endl;
  cout << "aSaysSameBSaysDifferent: " << aSaysSameBSaysDifferent() << endl;
  cout << "abcProblem: " << abcProblem() << endl;

  return 0;
}