#include <functional>
#include <memory>
#include <string>
#include <iostream>

using std::placeholders::_1;

//
// Maybe data type definition
//

template <typename a>
struct Maybe
{
	std::shared_ptr<a> value;
	
	// Evaluate the monadic action and yield its value
	const a& operator() () const
	{
		return *value;
	}
};

// Construct a Nothing value, denoting failure
template <typename a>
Maybe<a> Nothing ()
{
	return Maybe<a>(); // null pointer, empty value / failed computation
}

// Construct a Just value, denoting a successful computation
template <typename a>
Maybe<a> Just (const a& x)
{
	Maybe<a> maybe;
	maybe.value.reset(new a(x));
	return maybe;
}

// Return true if the Maybe value is Nothing, false if it is Just a value.
template <typename a>
bool is_nothing (const Maybe<a>& x)
{
	return x.value.get() == nullptr;
}

//
// Monad operations
//

template <typename a>
Maybe<a> ret (const a& x) // I am calling the function `ret` because `return` is a special keyword in C++
{
	return Just(x);
}

template <typename a, typename b>
Maybe<b> mbind (const Maybe<a>& x, const std::function<Maybe<b>(const a&)>& f)
{
	return is_nothing(x) ? Nothing<b>() : f(x());
}

//
// Example program
//

// g++ type deduction is failing when passing functions directly to mbind,
// so we wrap them in a MaybeF<int> to solve this issue
template <typename T>
using MaybeF = std::function<Maybe<int>(const int&)>;

Maybe<int> divide (int x, int y)
{
	if (y == 0)
		return Nothing<int>();
	else
		return Just(x/y);
}

Maybe<int> inc (int x)
{
	return Just(x+1);
}

// Compute (1/x) + 1
Maybe<int> compute (int x)
{
	MaybeF<int> inc(::inc);
	std::function<Maybe<int>(const int&)> div_by_x = std::bind(divide, _1, x);
	return mbind(mbind(ret(1), div_by_x), inc);
}

template <typename T>
std::string show (const Maybe<T>& x)
{
	if (is_nothing(x)) return "Nothing";
	else return std::string("Just ") + std::to_string(x());
}

int main ()
{
	MaybeF<int> inc(::inc);
	
	Maybe<int> x;
	Maybe<int> y = Just(3);
	
	std::cout << "x: " << show(x) << std::endl;
	std::cout << "y: " << show(y) << std::endl;
	
	Maybe<int> a = mbind(ret(2), inc);
	std::cout << "2 + 1 = " << show(a) << std::endl;
	
	Maybe<int> b = mbind(mbind(ret(2), inc), inc);
	std::cout << "2 + 1 + 1 = " << show(b) << std::endl;
	
	std::function<Maybe<int>(const int&)> div2 = std::bind(divide, _1, 2);
	Maybe<int> c = mbind(ret(4), div2);
	std::cout << "4/2 = " << show(c) << std::endl;
	
	Maybe<int> d = compute(1);
	std::cout << "1/1 + 1 = " << show(d) << std::endl;
	
	Maybe<int> e = compute(0);
	std::cout << "1/0 + 1 = " << show(e) << std::endl;
	
	return 0;
}