mattbierner/life_comonadic.cpp

## life_comonadic.cpp
/**
 * Conway's game of life implemented in C++ templates at compile time using Comonads.
 *
 * Logic based on: http://blog.emillon.org/posts/2012-10-18-comonadic-life.html
 */
#include <iostream>

/// Identity functor
template <typename X>
struct id {
    using type = X;
};

/// Create a meta functor that returns `X` when invoked with any argument.
template <typename X>
struct constant {
    template <typename>
    struct apply {
        using type = X;
    };
};

/// End of list marker type
struct Nil { };

/// Lazy list of values
template <typename head, template<typename> class get_rest>
struct List {
    using first = head;
    using rest = typename get_rest<head>::type;
};

/// Get head of list `L`.
template <typename L>
using car = typename L::first;

/// Get rest of list `L`.
template <typename L>
using cdr = typename L::rest;

// Prepend element `X` on to a list `L`.
template <typename X, typename L>
using cons = List<X, constant<L>::template apply>;

/// Create a list from a parameter pack.
template <typename...>
struct ListFromParams;

template <typename X, typename... XS>
struct ListFromParams<X, XS...> {
    using type = cons<X, typename ListFromParams<XS...>::type>;
};

template <>
struct ListFromParams<> {
    using type = Nil;
};

template <typename... elements>
using list_from_params = typename ListFromParams<elements...>::type;

/// Append list `L1` onto `L2`.
template <typename L1, typename L2>
struct ListConcat {
    template <typename>
    struct ConcatImpl {
        using type = typename ListConcat<cdr<L1>, L2>::type;
    };

    using type = List<car<L1>, ConcatImpl>;
};

template <typename L2>
struct ListConcat<Nil, L2> {
    using type = L2;
};

template <typename L1, typename L2>
using concat = typename ListConcat<L1, L2>::type;

/// Reverse a list.
template <typename L>
struct Reverse {
    using type = concat<
        typename Reverse<cdr<L>>::type,
        cons<car<L>, Nil>>;
};

template<>
struct Reverse<Nil> {
    using type = Nil;
};

template <typename L>
using reverse = typename Reverse<L>::type;

/// Create a list of at most `count` elements from list `L`.
template <size_t count, typename L>
struct ListTake {
    template <typename>
    struct TakeImpl {
        using type = typename ListTake<count - 1, cdr<L>>::type;
    };

    using type = List<car<L>, TakeImpl>;
};

template <typename L>
struct ListTake<0, L> {
    using type = Nil;
};

template <size_t count>
struct ListTake<count, Nil> {
    using type = Nil;
};

template <size_t count, typename L>
using take = typename ListTake<count, L>::type;


/// Perform a map operation on a list
template <template<typename> class F, typename L>
struct ListMap {
    template <typename>
    struct MapImpl {
        using type = typename ListMap<F, cdr<L>>::type;
    };

    using type = List<typename F<car<L>>::type, MapImpl>;
};

template <template<typename> class F>
struct ListMap<F, Nil> {
    using type = Nil;
};

template <template<typename> class F, typename L>
using map = typename ListMap<F, L>::type;

///
template <template<typename> class F, typename X>
struct Iterate {
    template <typename L>
    struct IterateImpl {
        using type = List<typename F<L>::type, ::Iterate<F, X>::IterateImpl>;
    };

    using type = List<X, IterateImpl>;
};

template <template<typename> class F, typename X>
using iterate = typename Iterate<F, X>::type;


/// Infinite list of values
template <typename X>
using gen = iterate<id, X>;

///
template <template<typename> class F, typename X>
using iterate_rest = cdr<iterate<F, X>>;

/// 1D list Zipper
template <typename z>
struct go_left {
    using type = typename z::left;
};

template <typename z>
struct go_right {
    using type = typename z::right;
};

template<typename L, typename X, typename R>
struct Zipper {
    using left = Zipper<cdr<L>, car<L>, cons<X, R>>;
    using right = Zipper<cons<X, L>, car<R>, cdr<R>>;

    using get = X;

    template <typename val>
    using put = Zipper<L, val, R>;

    template <template<typename> class F>
    using fmap = Zipper<
        map<F, L>,
        typename F<X>::type,
        map<F, R>>;

    template <size_t count>
    using to_list = concat<
        reverse<take<count, L>>,
        concat<
            cons<X, Nil>,
            take<count, R>>>;
};

template <
    template<typename> class left_mapper,
    template<typename> class right_mapper,
    typename z>
using move = Zipper<
    iterate_rest<left_mapper, z>,
    z,
    iterate_rest<right_mapper, z>>;

template <typename z>
using duplicate = move<go_left, go_right, z>;

template <template<typename> class f, typename z>
using fmap = typename z::template fmap<f>;

template <typename z>
using get = typename z::get;

template <typename z, typename x>
using put = typename z::template put<x>;

/// 2d plane Zipper
template <typename plane>
struct go_up {
    using type = typename plane::up;
};

template <typename plane>
struct go_down {
    using type = typename plane::down;
};

template<typename z>
struct PlaneZipper {
    using up = PlaneZipper<typename z::left>;
    using down = PlaneZipper<typename z::right>;

    using left = PlaneZipper<fmap<go_left, z>>;
    using right = PlaneZipper<fmap<go_right, z>>;

    using get = get<get<z>>;

    template <typename val>
    using put = PlaneZipper<put<z, put<typename z::get, val>>>;

    template <template<typename> class F>
    struct do_fmap {
        template <typename X>
        struct apply {
            using type = fmap<F, X>;
        };
    };

    template <template<typename> class F>
    using fmap = PlaneZipper<fmap<do_fmap<F>::template apply, z>>;
};

template <typename z>
using horizontal = move<go_left, go_right, z>;

template <typename z>
using vertical = move<go_up, go_down, z>;

template <typename z>
struct go_horizontal {
    using type = horizontal<z>;
};

template <typename z>
using duplicatePlane = PlaneZipper<fmap<go_horizontal, vertical<z>>>;

template <template<typename> class F, typename z>
using extendPlane = fmap<F, duplicatePlane<z>>;


/// Single cell in life.
template <bool alive>
struct Cell {
    static const bool value = alive;
};

using DeadCell = Cell<false>;
using LiveCell = Cell<true>;

/// Get the number of living neighbors to the focus of the plane Zipper `z`.
template <typename z>
struct living_neighbors_count {
    template <typename neighbor>
    struct get_weight {
        enum { value = neighbor::get::value };
    };

    enum { value =
        get_weight<typename z::left>::value +
        get_weight<typename z::right>::value +
        get_weight<typename z::up>::value +
        get_weight<typename z::down>::value +
        get_weight<typename z::left::up>::value +
        get_weight<typename z::left::down>::value +
        get_weight<typename z::right::up>::value +
        get_weight<typename z::right::down>::value };
};

/// Rules for Conway's game of life.
template <typename world>
struct life_rule {
    using living = living_neighbors_count<world>;

    using type = typename std::conditional<living::value == 2,
        typename world::get,
        Cell<living::value == 3>>::type;
};

template <typename world>
struct evolve {
    using type = extendPlane<life_rule, world>;
};

/// Game generation
using inf_dead_list = gen<DeadCell>;

using dead_row = Zipper<inf_dead_list, DeadCell, inf_dead_list>;

using inf_dead_rows = gen<dead_row>;

using dead_plane = Zipper<inf_dead_rows, dead_row, inf_dead_rows>;

template <typename... values>
using line = Zipper<
    inf_dead_list,
    DeadCell,
    concat<
        list_from_params<values...>,
        inf_dead_list>>;

using glider =
    PlaneZipper<
        Zipper<
            inf_dead_rows,
            dead_row,
            concat<
                list_from_params<
                    line<DeadCell, LiveCell, DeadCell>,
                    line<DeadCell, DeadCell, LiveCell>,
                    line<LiveCell, LiveCell, LiveCell>>,
                inf_dead_rows>>>;

/// Printer
template <typename>
struct Print;

template <>
struct Print<Cell<true>> {
    static void Do() {
        std::cout << "X";
    }
};

template <>
struct Print<Cell<false>> {
    static void Do() {
        std::cout << "-";
    }
};

template <typename x, template<typename> class xs>
struct Print<List<x, xs>> {
    static void Do() {
        Print<car<List<x, xs>>>::Do();
        Print<cdr<List<x, xs>>>::Do();
    }
};

template <>
struct Print<Nil> {
    static void Do() { /* noop */ }
};


template <typename l, typename x, typename r>
struct Print<Zipper<l, x, r>> {
    static void Do() {
        Print<typename Zipper<l, x, r>::template to_list<5>>::Do();
        std::cout << "\n";
    }
};

template <typename z>
struct Print<PlaneZipper<z>> {
    static void Do() {
        Print<typename z::template to_list<5>>::Do();
        std::cout << "\n";
    }
};

int main(int argc, const char * argv[]) {
    Print<take<3, iterate<evolve, glider>>>::Do();
    return 0;
}
	/**
	* Conway's game of life implemented in C++ templates at compile time using Comonads.
	*
	* Logic based on: http://blog.emillon.org/posts/2012-10-18-comonadic-life.html
	*/
	#include <iostream>

	/// Identity functor
	template <typename X>
	struct id {
	using type = X;
	};

	/// Create a meta functor that returns `X` when invoked with any argument.
	template <typename X>
	struct constant {
	template <typename>
	struct apply {
	using type = X;
	};
	};

	/// End of list marker type
	struct Nil { };

	/// Lazy list of values
	template <typename head, template<typename> class get_rest>
	struct List {
	using first = head;
	using rest = typename get_rest<head>::type;
	};

	/// Get head of list `L`.
	template <typename L>
	using car = typename L::first;

	/// Get rest of list `L`.
	template <typename L>
	using cdr = typename L::rest;

	// Prepend element `X` on to a list `L`.
	template <typename X, typename L>
	using cons = List<X, constant<L>::template apply>;

	/// Create a list from a parameter pack.
	template <typename...>
	struct ListFromParams;

	template <typename X, typename... XS>
	struct ListFromParams<X, XS...> {
	using type = cons<X, typename ListFromParams<XS...>::type>;
	};

	template <>
	struct ListFromParams<> {
	using type = Nil;
	};

	template <typename... elements>
	using list_from_params = typename ListFromParams<elements...>::type;

	/// Append list `L1` onto `L2`.
	template <typename L1, typename L2>
	struct ListConcat {
	template <typename>
	struct ConcatImpl {
	using type = typename ListConcat<cdr<L1>, L2>::type;
	};

	using type = List<car<L1>, ConcatImpl>;
	};

	template <typename L2>
	struct ListConcat<Nil, L2> {
	using type = L2;
	};

	template <typename L1, typename L2>
	using concat = typename ListConcat<L1, L2>::type;

	/// Reverse a list.
	template <typename L>
	struct Reverse {
	using type = concat<
	typename Reverse<cdr<L>>::type,
	cons<car<L>, Nil>>;
	};

	template<>
	struct Reverse<Nil> {
	using type = Nil;
	};

	template <typename L>
	using reverse = typename Reverse<L>::type;

	/// Create a list of at most `count` elements from list `L`.
	template <size_t count, typename L>
	struct ListTake {
	template <typename>
	struct TakeImpl {
	using type = typename ListTake<count - 1, cdr<L>>::type;
	};

	using type = List<car<L>, TakeImpl>;
	};

	template <typename L>
	struct ListTake<0, L> {
	using type = Nil;
	};

	template <size_t count>
	struct ListTake<count, Nil> {
	using type = Nil;
	};

	template <size_t count, typename L>
	using take = typename ListTake<count, L>::type;


	/// Perform a map operation on a list
	template <template<typename> class F, typename L>
	struct ListMap {
	template <typename>
	struct MapImpl {
	using type = typename ListMap<F, cdr<L>>::type;
	};

	using type = List<typename F<car<L>>::type, MapImpl>;
	};

	template <template<typename> class F>
	struct ListMap<F, Nil> {
	using type = Nil;
	};

	template <template<typename> class F, typename L>
	using map = typename ListMap<F, L>::type;

	///
	template <template<typename> class F, typename X>
	struct Iterate {
	template <typename L>
	struct IterateImpl {
	using type = List<typename F<L>::type, ::Iterate<F, X>::IterateImpl>;
	};

	using type = List<X, IterateImpl>;
	};

	template <template<typename> class F, typename X>
	using iterate = typename Iterate<F, X>::type;


	/// Infinite list of values
	template <typename X>
	using gen = iterate<id, X>;

	///
	template <template<typename> class F, typename X>
	using iterate_rest = cdr<iterate<F, X>>;

	/// 1D list Zipper
	template <typename z>
	struct go_left {
	using type = typename z::left;
	};

	template <typename z>
	struct go_right {
	using type = typename z::right;
	};

	template<typename L, typename X, typename R>
	struct Zipper {
	using left = Zipper<cdr<L>, car<L>, cons<X, R>>;
	using right = Zipper<cons<X, L>, car<R>, cdr<R>>;

	using get = X;

	template <typename val>
	using put = Zipper<L, val, R>;

	template <template<typename> class F>
	using fmap = Zipper<
	map<F, L>,
	typename F<X>::type,
	map<F, R>>;

	template <size_t count>
	using to_list = concat<
	reverse<take<count, L>>,
	concat<
	cons<X, Nil>,
	take<count, R>>>;
	};

	template <
	template<typename> class left_mapper,
	template<typename> class right_mapper,
	typename z>
	using move = Zipper<
	iterate_rest<left_mapper, z>,
	z,
	iterate_rest<right_mapper, z>>;

	template <typename z>
	using duplicate = move<go_left, go_right, z>;

	template <template<typename> class f, typename z>
	using fmap = typename z::template fmap<f>;

	template <typename z>
	using get = typename z::get;

	template <typename z, typename x>
	using put = typename z::template put<x>;

	/// 2d plane Zipper
	template <typename plane>
	struct go_up {
	using type = typename plane::up;
	};

	template <typename plane>
	struct go_down {
	using type = typename plane::down;
	};

	template<typename z>
	struct PlaneZipper {
	using up = PlaneZipper<typename z::left>;
	using down = PlaneZipper<typename z::right>;

	using left = PlaneZipper<fmap<go_left, z>>;
	using right = PlaneZipper<fmap<go_right, z>>;

	using get = get<get<z>>;

	template <typename val>
	using put = PlaneZipper<put<z, put<typename z::get, val>>>;

	template <template<typename> class F>
	struct do_fmap {
	template <typename X>
	struct apply {
	using type = fmap<F, X>;
	};
	};

	template <template<typename> class F>
	using fmap = PlaneZipper<fmap<do_fmap<F>::template apply, z>>;
	};

	template <typename z>
	using horizontal = move<go_left, go_right, z>;

	template <typename z>
	using vertical = move<go_up, go_down, z>;

	template <typename z>
	struct go_horizontal {
	using type = horizontal<z>;
	};

	template <typename z>
	using duplicatePlane = PlaneZipper<fmap<go_horizontal, vertical<z>>>;

	template <template<typename> class F, typename z>
	using extendPlane = fmap<F, duplicatePlane<z>>;


	/// Single cell in life.
	template <bool alive>
	struct Cell {
	static const bool value = alive;
	};

	using DeadCell = Cell<false>;
	using LiveCell = Cell<true>;

	/// Get the number of living neighbors to the focus of the plane Zipper `z`.
	template <typename z>
	struct living_neighbors_count {
	template <typename neighbor>
	struct get_weight {
	enum { value = neighbor::get::value };
	};

	enum { value =
	get_weight<typename z::left>::value +
	get_weight<typename z::right>::value +
	get_weight<typename z::up>::value +
	get_weight<typename z::down>::value +
	get_weight<typename z::left::up>::value +
	get_weight<typename z::left::down>::value +
	get_weight<typename z::right::up>::value +
	get_weight<typename z::right::down>::value };
	};

	/// Rules for Conway's game of life.
	template <typename world>
	struct life_rule {
	using living = living_neighbors_count<world>;

	using type = typename std::conditional<living::value == 2,
	typename world::get,
	Cell<living::value == 3>>::type;
	};

	template <typename world>
	struct evolve {
	using type = extendPlane<life_rule, world>;
	};

	/// Game generation
	using inf_dead_list = gen<DeadCell>;

	using dead_row = Zipper<inf_dead_list, DeadCell, inf_dead_list>;

	using inf_dead_rows = gen<dead_row>;

	using dead_plane = Zipper<inf_dead_rows, dead_row, inf_dead_rows>;

	template <typename... values>
	using line = Zipper<
	inf_dead_list,
	DeadCell,
	concat<
	list_from_params<values...>,
	inf_dead_list>>;

	using glider =
	PlaneZipper<
	Zipper<
	inf_dead_rows,
	dead_row,
	concat<
	list_from_params<
	line<DeadCell, LiveCell, DeadCell>,
	line<DeadCell, DeadCell, LiveCell>,
	line<LiveCell, LiveCell, LiveCell>>,
	inf_dead_rows>>>;

	/// Printer
	template <typename>
	struct Print;

	template <>
	struct Print<Cell<true>> {
	static void Do() {
	std::cout << "X";
	}
	};

	template <>
	struct Print<Cell<false>> {
	static void Do() {
	std::cout << "-";
	}
	};

	template <typename x, template<typename> class xs>
	struct Print<List<x, xs>> {
	static void Do() {
	Print<car<List<x, xs>>>::Do();
	Print<cdr<List<x, xs>>>::Do();
	}
	};

	template <>
	struct Print<Nil> {
	static void Do() { /* noop */ }
	};


	template <typename l, typename x, typename r>
	struct Print<Zipper<l, x, r>> {
	static void Do() {
	Print<typename Zipper<l, x, r>::template to_list<5>>::Do();
	std::cout << "\n";
	}
	};

	template <typename z>
	struct Print<PlaneZipper<z>> {
	static void Do() {
	Print<typename z::template to_list<5>>::Do();
	std::cout << "\n";
	}
	};

	int main(int argc, const char * argv[]) {
	Print<take<3, iterate<evolve, glider>>>::Do();
	return 0;
	}