Monad - Draft that is partially working

gistfile1.cpp

#include <iostream>
#include <algorithm>
#include <functional>
#include <utility>
#include <memory>
#include <future>
#include <tuple>
#include <type_traits>
#include <iostream>
#include <string>
#include <cstdio>

using std::declval;
using std::unique_ptr;
using std::future;
using std::forward;
using std::move;
using std::result_of;
using std::tuple;
using std::pair;
using std::remove_reference;
using std::is_function;
using std::is_same;
using std::is_class;
using std::enable_if;
using std::cin;
using std::cout;

/////dummy//////
template <class T>
struct optional {};
template <class T>
struct expected {};

struct just_type {};
struct function_type {};
struct sequence_type {};
struct iterator_type {};
struct optional_type {};
struct expected_type {};
struct monad_type {};
struct pointer_type {};
struct future_type {};
// type deduction, ideas from Pure library

template <typename...>
just_type categorise(...);

// sequences should have begin(), end() member functions
template <typename T>
auto categorise(const T& sequence) -> decltype(begin(sequence), end(sequence), sequence_type());

// optional(maybe) should support dereferencing and conversion to bool (for validation)
template <typename T>
auto categorise(const T& optional) -> decltype(*optional, (bool) optional, optional_type());

// expected should support dereferencing and valid()
template <class T>
static auto categorise(const T& expected) -> decltype(*expected, expected.valid(), expected_type());

// iterator should support dereferencing, next operators and inequality
template <typename Iterator, class Next, class End>
static auto categorise(const tuple<Iterator, Next, End>& iterator)
	-> decltype(
		*(iterator.get(0)),
		iterator.get(1)(iterator.get(0)),
		!iterator.get(2)(iterator.get(0)),
		iterator_type());

// own proposal: pair of (functor, policy)
// futures should support wait(), get() is optional
template <class Future>
auto categorise(const Future& future)
    -> decltype(future.wait(), future_type());

template <class T>
auto categorise(const std::pair<std::launch, T>& future)
	-> future_type;

// a single std::launch policy flag is also a future
template <class T>
auto categorise(const T& future)
	-> typename enable_if<is_same<T, std::launch>::value, future_type>::type;

// pointers should support dereferencing and becoming nullptr
template<class T>
auto categorise(const T& pointer)
	-> decltype(*pointer, pointer == nullptr, pointer_type());

// functors are callable
// functions in traditional sense
template <typename T>
auto categorise(const T& functor)
	-> typename enable_if<is_function<T>::value, function_type>::type;
// callable objects
template <class Functor>
struct is_callable {
	struct success {};
	struct Base {
		void operator()(){}; // operator() that will be tested against
	};
	struct Derived : Functor, Base {};

	template <typename T, T t>
	struct Compare {};

	template <typename T>
	static void test(T*, Compare<void (Base::*)(), &T::operator()>* = 0);
	// When testing, the combined class is passed in
	// If conversion from a pointer to the combined class's operator() to a pointer to Base::operator()
	// is successful, there is no operator() in Functor.
	static success test(...);

	static const bool value = is_same<decltype(test((Derived*)(0))), success>::value;
};

template<bool, typename>
struct is_functor {
	static const bool value = false;
};

template<typename T>
struct is_functor <true, T> {
	static const bool value = is_callable<T>::value;
};
// currently callable union is not supported
template <typename T>
auto categorise (const T& functor)
	-> typename enable_if<is_functor<is_class<T>::value, T>::value, function_type>::type;

// fmaps

template<class Traits, class... Args>
struct fmap_type {
    
};

template<class T>
struct fmap_type<just_type, T> {
    void operator() () {
        //
    }
};

template<class T>
struct fmap_type<sequence_type, T> {
    //
};

template<class T>
struct fmap_type<iterator_type, T> {
    //
};

template<class T, class Category = decltype(categorise(declval<T>()))>
struct fmap : fmap_type<Category, T> {
    typedef Category traits;
    typedef T type;
    using fmap_type<Category,T>::operator();
};

// interface open to abstracted functors
template <class Traits> struct monad_species{};

template <class Traits, class Species = typename monad_species<Traits>::species >
struct monad : monad_type {
	// deduct type without instantiating that particular monad species, see below
    template <class Functor, typename T, class MonadSpecies>
    struct mbind_type {
        typedef
            decltype(MonadSpecies::mbind(
                forward<Functor>(declval<Functor>()),
                forward<T>(declval<T>())))
            type;
    };

	template <class Functor, typename T>
	static constexpr auto mbind (Functor&& f, T&& t)
	    -> typename mbind_type<Functor, T, Species>::type // return type is making a trouble
	{
		return Species::mbind(forward<Functor>(f), forward<T>(t));
	}
	
	template <class T, class X, class MonadSpecies>
	struct mreturn_type {
	    typedef decltype(MonadSpecies::template mreturn<T>(forward<X>(declval<X>()))) type;
	};

	template <typename T, class X>
	static constexpr auto mreturn (X&& x)
	    -> typename mreturn_type<T, X, Species>::type
	{
		// put into a new container, which is determined by
		// respective monad species
		return Species::template mreturn<T>(forward<X>(x));
	}
};

// real stuff starts here
// just monad
struct monad_just : monad<just_type, monad_just> {
	template <class Functor, typename T, class Ret = typename result_of<Functor(T&&)>::type>
	static Ret mbind (Functor&& f, T&& t) {
	    return forward<Functor>(f)(forward<T>(t));
	}
	
	template <typename T, class X>
	static constexpr T mreturn(X&& x) {
	    return T(forward<X>(x));
	}
};

template <>
struct monad_species<just_type> {
	typedef monad_just species;
};

struct monad_pointer : monad<pointer_type, monad_pointer> {
	// pointer monad
	template <
	    class Functor,
	    typename Ptr,
	    class T = decltype(*declval<Ptr>()),
	    class Ret = typename result_of<Functor(T)>::type>
	static Ret mbind (Functor&& f, Ptr&& ptr) {
		return ptr ? forward<Functor>(f)(*ptr) : nullptr;
	}

	template <typename Ptr, class X, class T = decltype(*declval<Ptr>())>
	static constexpr Ptr mreturn (X&& x) {
		return Ptr (new T(forward<X>(x)));
	}
};

template <>
struct monad_species<pointer_type> {
	typedef monad_pointer species;
};

// future monad
struct monad_future : monad<future_type, monad_future> {
	// future monad
	// initial call to future - plan to abstract the process
	// with fmap
	/*template <
	    class Functor,
	    class T,
	    class Future = future<typename result_of<Functor(T&&)>::type> >
	static Future mbind (Functor&& f, T&& t) {
	    return std::async (std::launch::async,
	        [&]{return forward<Functor>(f)(forward<T>(t));});
	}*/
	// with appointed policy
	template <
		class Functor,
		class T,
		class Future = future<typename result_of<Functor(T&&)>::type> >
	static Future mbind (Functor&& f, std::pair<std::launch, T>&& t) {
		return std::async (t.first, forward<Functor>(f), forward<T>(t.second));
	}

	template <class Functor, class Future = future<typename result_of<Functor(void)>::type> >
	static Future mbind (Functor&& f, std::launch&& t) {
		return std::async (t, forward<Functor>(f));
	}
	// futures can chain together and may be asynchronous according to
	// the indicated policy
	template <
	    class Functor,
	    class Future,
	    class Ret = typename result_of<Functor(Future&&)>::type,
	    class FutureRet = future<Ret> >
	static FutureRet mbind (Functor&& f, Future&& ftr) {
		// currently no support for then, so ...
	    // return ftr.then(
    	//         [&](FutureR&& prev) -> Ret {
    	//             return forward<Functor>(f)(forward<FutureR>(ftr));
    	//             });
    	return std::async (
    		std::launch::async,
    		forward<Functor>(f),
    		forward<Future>(ftr));
	}
	// functors that does not take in future objects will have
	// their parameters lifted out before application and will put
	// back into future object
	template <
		class Functor,
		class Future,
		class T = decltype(declval<Future>().get()),
		class Ret = typename result_of<Functor(T&&)>::type,
		class FutureRet = future<Ret> >
	static FutureRet mbind (Functor&& f, Future&& ftr) {
		static_assert(
			!is_same<void, T>::value,
			"return type void is not allowed for lifting from future monad");
		return std::async (std::launch::async, [&]{
			return forward<Functor>(f)(forward<T>(ftr.get()));
		});
	}
	
	template <
	    class Functor,
	    class Ret = typename result_of<Functor(void)>::type,
	    class Future = future<Ret> >
	static constexpr Future mreturn (Functor&& f) {
	    return std::async(std::launch::async, forward<Functor>(f));
	}
};

template <>
struct monad_species<future_type> {
	typedef monad_future species;
};

struct monad_sequence : monad<sequence_type, monad_sequence> {
    template <
        class T,
        class Sequence,
        class Functor,
        class Ret = typename result_of<Functor(T)>::type>
    static Ret mbind (Functor&& f, Sequence&& s) { // TODO
        /*auto& iterator = begin(s);
        auto& end = end(s);
        Ret m;
        while (iterator != end)
            m = forward<Functor>(f)(forward<T>(*iterator));
        return m;*/
    }
    
    template <class Sequence, class X>
    static constexpr Sequence mreturn (X&& x) {
        return Sequence(x); // TODO
    }
};

template <>
struct monad_species<sequence_type> {
	typedef monad_sequence species;
};

// optional (maybe) monard
struct monad_optional : monad<optional_type, monad_optional> {
    template <
        class Optional,
        class Functor,
        class T = decltype(*declval<Optional>()),
        class Ret = typename result_of<Functor(T&&)>::type>
    static Ret mbind (Functor&& f, Optional&& opt) {
        return opt ? forward<Functor>(f)(*opt) : Optional();
    }
    template <class Optional, class X>
    static constexpr Optional mreturn (X&& x) {
        return Optional(T(forward<X>(x))); //initialise optional
    }
};

template <>
struct monad_species<optional_type> {
	typedef monad_optional species;
};

// error-handling expected monad
struct monad_expected : monad<expected_type, monad_expected> {
    template <
        class Expected,
        class Functor,
        class T = decltype(*declval<Expected>()),
        class Ret = typename result_of<Functor(T&&)>::type>
    static Ret mbind (Functor&& f, Expected&& ex) {
        return forward<Functor>(f)(*ex);
    }
    
    /*template <
        class Expected,
        class Functor,
        class T = decltype (*declval<Expected>())
        class Ret = typename result_of<Functor(T&&)>::type>
    static Ret mbind (Functor&& f, const Expected& ex) {
        return ex.valid() ? forward<Functor>(f)(*ex) : Ret();
    }*/
    
    template <class Expected, class X, class T = decltype(*declval<Expected>())>
    static constexpr Expected mreturn (X&& x) {
        return Expected(T(forward<X>(x)));
    }
};

template <>
struct monad_species<expected_type> {
	typedef monad_expected species;
};

// public monad bind operation
// Functor: function type
// T: container type
template <class Functor, class T, class Traits = decltype(categorise(declval<T>()))>
constexpr auto mbind (Functor&& f, T&& t)
    -> decltype(
    	monad<Traits, typename monad_species<Traits>::species>
    		::mbind (forward<Functor>(f), forward<T>(t))) {
	return monad<Traits, typename monad_species<Traits>::species>::mbind(forward<Functor>(f), forward<T>(t));
}

// public monad return operation
// T: container type
// X: contained data type
template <typename T, class X, class Traits = decltype(categorise(declval<T>()))>
constexpr auto mreturn (X&& x)
	-> decltype(monad<Traits, typename monad_species<Traits>::species>::template mreturn<T>(forward<X>(x))) {
	return monad<Traits, typename monad_species<Traits>::species>::template mreturn<T>(forward<X>(x));
}

template <class L, class R>
constexpr auto operator>> (L&& left, R&& right)
	-> decltype(mbind (forward<R>(right), forward<L>(left))) {
    return mbind (forward<R>(right), forward<L>(left));
}
//-----------------------------------------

template<typename T>
void swap(T&& a, T&& b, bool order) {
	if (a > b ^ order) {
		std::cout << "swapping " << a << " and " << b << std::endl;
		typename remove_reference<T>::type t = std::move<T>(a);
		a = move<T>(b);
		b = move<T>(t);
	}
}

// my own implementation of wait_for_all for std::future
template<class Rep, class Period, typename ...Types>
constexpr bool check_ready_for_all(
	const std::chrono::duration<Rep, Period>& duration,
	const std::future<Types>&... rest);

template<class Rep, class Period, typename T, typename ...Types>
constexpr bool check_ready_for_all(
	const std::chrono::duration<Rep, Period>& duration,
	const std::future<T>& ftr,
	const std::future<Types>&... rest) {
    return (ftr.wait_for(duration) != std::future_status::ready) ? false : check_ready_for_all(duration, rest...);
}

template<class Rep, class Period, typename T>
constexpr bool check_ready_for_all(
	const std::chrono::duration<Rep, Period>& duration,
	const std::future<T>& ftr1,
	const std::future<T>& ftr2) {
    return ftr1.wait_for(duration) == std::future_status::ready ?
    	ftr2.wait_for(duration) == std::future_status::ready :
    	false;
}

template<typename ...Types>
void wait_for_all(const std::future<Types>&... futures) {
    while (!check_ready_for_all(std::chrono::nanoseconds(10),futures...))
        ;
}

int main () {
	int N = 16;
	scanf ("%d", &N);
	int check = N;
	while (check > 1)
		if (check & 1)
			return -1;
		else
			check /= 2;
	int *arr = new int[N];
	for (int i = 0; i < N; i++)
		scanf ("%d", &arr[i]); /* example : {14, 0, 8, 1, 5, 11, 2, 12, 3, 13, 7, 9, 10, 6, 4, 15}; */
	std::function<void(const int, const int, int*, const bool)> bitonic_divider, bitonic_merger;
	bitonic_divider = [&](const int start, const int end, int *arr, const bool order) {
		if (start >= end)
			return;
		std::cout << "divider: " << start << "-" << end << std::endl;
		if (start + 1 == end) {
			swap(arr[start], arr[end], order);
			return;
		}
		// dividing
		int middle = (start + end) / 2;
		// first divide (asynchronous)
		std::future<void> ftr =
		std::launch::async >> [&]{
			// use boost library's wait_for_all
			wait_for_all(
				std::async(std::launch::async, [&]{bitonic_divider(start, middle, arr, false);}),
				std::async(std::launch::async, [&]{bitonic_divider(middle + 1, end, arr, true);}));
		}
			// mbind operator that automatically passes the function below
			// as a parameter to then() method of the former future object and return a future object,
			// so bitonic_divider and bitonic_merger are sequentially chained up.
			// once the former future has done the job, since it was passed to the second future functor,
			// the second future functor then can proceed.
			>> [&](std::future<void>&& prev){
				// previous job must be done
				prev.wait();
				bitonic_merger(start, end, arr, order);
			};
		// block here and wait
		ftr.wait();
	};
	bitonic_merger = [&](const int start, const int end, int *arr, const bool order) {
		if (start >= end)
			return;
		std::cout << "merger: " << start << "-" << end << std::endl;
		if (start + 1 == end) {
			swap(arr[start], arr[end], order);
			return;
		}
		int middle = (start + end) / 2;
		std::future<void> ftr =
		std::launch::async >> [&]{
			for (int i = start, j = (start + end) / 2 + 1, flag = j - 1; i <= flag && j <= end; i++, j++)
				swap(arr[i], arr[j], order);
		}
			>> [&](std::future<void>&& prev) {
				prev.wait();
				wait_for_all(
					std::async(std::launch::async, [&]{bitonic_merger(start, middle, arr, order);}),
					std::async(std::launch::async, [&]{bitonic_merger(middle + 1, end, arr, order);}));
			};
		ftr.wait();
	};
	//.......
	bitonic_divider(0, N - 1, arr, false);
	for (int i = 0; i < N; i++)
		std::cout << arr[i] << std::endl;
	return 0;
}