algebraic_data_type

algebraic_data_type.hpp

#pragma once

#ifndef PLASMA_ALGEBRAIC_DATA_TYPE
#define PLASMA_ALGEBRAIC_DATA_TYPE
// Copyright plasma-effect 2015
// Distributed under the Boost Software License, Version 1.0.
// (See http://www.boost.org/LICENSE_1_0.txt)

#include<tuple>
#include<memory>
#include<type_traits>
#include<functional>
#include<vector>
#include<utility>

namespace plasma
{
	namespace algebraic_data_type
	{
		struct recursion_tag {};
		namespace detail
		{
			template<class>constexpr std::nullptr_t get_null()
			{
				return nullptr;
			}
			template<class T>std::unique_ptr<T> clone_i(std::unique_ptr<T> const& p)
			{
				return static_cast<bool>(p) ? std::make_unique<T>(*p) : nullptr;
			}
			template<class T,std::size_t... Is>T clone(T const& v,std::index_sequence<Is...>)
			{
				return std::make_tuple(clone_i(std::get<Is>(v))...);
			}
			template<class U, std::size_t I, class T>U get_tuple(T const&, std::size_t, std::enable_if_t<std::tuple_size<T>::value == I>* = nullptr)
			{
				return U();
			}
			template<class U,std::size_t I, class T>U get_tuple(T const& x, std::size_t i, std::enable_if_t<std::tuple_size<T>::value != I>* =nullptr)
			{
				return i == I ? std::get<I>(x) : get_tuple<U, I + 1>(x, i);
			}
			constexpr bool all_and(bool f)
			{
				return f;
			}
			template<class... Ts>constexpr std::enable_if_t<sizeof...(Ts)!=0, bool> all_and(bool f, Ts... args)
			{
				return f&&all_and(args...);
			}
		}

		template<class... Types>class data_type
		{
			typedef data_type<Types...> this_type;
			static constexpr std::size_t size = sizeof...(Types);

			template<class T, class = void>struct pointer_type
			{
				std::unique_ptr<T> ptr;
				typedef T type;
				bool equal(pointer_type<T> const& rhs)const
				{
					return *ptr == *rhs.ptr;
				}
			};
			template<class T>struct pointer_type<T, std::enable_if_t<std::is_same<T,recursion_tag>::value>>
			{
				std::unique_ptr<this_type> ptr;
				typedef this_type type;
				bool equal(pointer_type<recursion_tag> const& rhs)const
				{
					return *ptr == *rhs.ptr;
				}
			};
			template<class T>using pointer_type_t = typename pointer_type<T>::type;
			template<class T>static pointer_type<T> make_pointer_type(T const& arg)
			{
				return pointer_type<T>{std::make_unique<T>(arg)};
			}
			static pointer_type<recursion_tag> make_pointer_type(this_type const& arg)
			{
				return pointer_type<recursion_tag>{std::make_unique<this_type>(arg)};
			}
			template<class T, std::size_t... Is>static auto clone_pointer_type_i(T const& arg, std::index_sequence<Is...>)
			{
				return std::make_tuple(make_pointer_type(*(std::get<Is>(arg).ptr))...);
			}
			template<class T>static auto clone_pointer_type(T const& arg)
			{
				return clone_pointer_type_i(arg, std::make_index_sequence<std::tuple_size<T>::value>());
			}

			template<class T, class = void>struct inside_data_type
			{
				static constexpr std::size_t size = 1;
				std::tuple<pointer_type<T>> data;
				inside_data_type(pointer_type_t<T> arg) :data(make_pointer_type(arg)) {}
				inside_data_type(inside_data_type const& arg) :data(clone_pointer_type(arg.data)) {}
				inside_data_type(inside_data_type&& arg) :data(std::move(arg.data)) {}
				inside_data_type& operator=(inside_data_type const& arg)
				{
					data = clone_pointer_type(arg.data);
					return *this;
				}
				inside_data_type& operator=(inside_data_type&& arg)
				{
					data = std::move(arg.data);
					return *this;
				}
				~inside_data_type() = default;

				bool equal(inside_data_type<T> const& rhs)const
				{
					return std::get<0>(data).equal(std::get<0>(rhs.data));
				}
			};
			template<class... Ts>struct inside_data_type<std::tuple<Ts...>, void>
			{
				static constexpr std::size_t size = sizeof...(Ts);
				std::tuple<pointer_type<Ts>...> data;
				inside_data_type(pointer_type_t<Ts>... args) :data(make_pointer_type(args)...) {}
				inside_data_type(inside_data_type const& arg) :data(clone_pointer_type(arg.data)) {}
				inside_data_type(inside_data_type&& arg) :data(std::move(arg.data)) {}
				inside_data_type& operator=(inside_data_type const& arg)
				{
					data = clone_pointer_type(arg.data);
					return *this;
				}
				inside_data_type& operator=(inside_data_type&& arg)
				{
					data = std::move(arg.data);
					return *this;
				}
				~inside_data_type() = default;

				template<std::size_t... Is>bool equal_i(inside_data_type<std::tuple<Ts...>> const& rhs,std::index_sequence<Is...>)const
				{
					return detail::all_and(std::get<Is>(data).equal(std::get<Is>(rhs.data))...);
				}
				bool equal(inside_data_type<std::tuple<Ts...>> const& rhs)
				{
					return equal_i(rhs, std::make_index_sequence<size>());
				}
			};
			template<class T>struct inside_data_type<T, std::enable_if_t<std::is_same<T,void>::value>>
			{
				static constexpr std::size_t size = 0;
				std::tuple<> data;
				bool equal(inside_data_type<void> const&)const
				{
					return true;
				}
			};
		
			std::tuple<std::unique_ptr<inside_data_type<Types>>...> data;
			std::size_t now;

			template<class U, class T>struct function_type
			{
				typedef std::function<U(pointer_type_t<T>)> type;
			};
			template<class U, class... Ts>struct function_type<U,std::tuple<Ts...>>
			{
				typedef std::function<U(pointer_type_t<Ts>...)> type;
			};
			template<class U, class T>using function_type_t = typename function_type<U, T>::type;

			template<class U, class T>struct recursion_function_type
			{
				typedef std::function<U(std::function<U(this_type)>, pointer_type_t<T>)> type;
			};
			template<class U, class... Ts>struct recursion_function_type<U, std::tuple<Ts...>>
			{
				typedef std::function<U(std::function<U(this_type)>, pointer_type_t<Ts>...)> type;
			};
			template<class U>struct recursion_function_type<U, void>
			{
				typedef std::function<U(std::function<U(this_type)>)> type;
			};
			template<class U, class T>using recursion_function_t = typename recursion_function_type<U, T>::type;

		public:
			template<std::size_t I,class T>struct make_instance_t
			{
				static data_type run(pointer_type_t<T> const& arg)
				{
					data_type ret{};
					std::get<I>(ret.data) = std::make_unique<inside_data_type<T>>(arg);
					ret.now = I;
					return ret;
				}
				typedef std::function<data_type(pointer_type_t<T>)> function_type;
			};
			template<std::size_t I, class... Ts>struct make_instance_t<I, std::tuple<Ts...>>
			{
				static data_type run(pointer_type_t<Ts> const&... args)
				{
					data_type ret{};
					std::get<I>(ret.data) = std::make_unique<inside_data_type<std::tuple<Ts...>>>(args...);
					ret.now = I;
					return ret;
				}
				typedef std::function<data_type(pointer_type_t<std::tuple<Ts...>>)> function_type;
			};
			template<std::size_t I>struct make_instance_t<I, void>
			{
				static data_type run()
				{
					data_type ret{};
					std::get<I>(ret.data) = std::make_unique<inside_data_type<void>>();
					ret.now = I;
					return ret;
				}
				typedef std::function<data_type(void)> function_type;
			};

			template<std::size_t I>using instance_t = make_instance_t<I, std::tuple_element_t<I, std::tuple<Types...>>>;

			template<std::size_t I>using inside_data_t = std::tuple_element_t<I, std::tuple<inside_data_type<Types>...>>;
			
			data_type() = default;
			data_type(data_type const& arg) :data(detail::clone(arg.data, std::make_index_sequence<size>())),now(arg.now) {}
			data_type(data_type&& arg) :data(std::move(arg.data)),now(arg.now) {}
			data_type& operator=(data_type const& arg)
			{
				data = detail::clone(arg.data, std::make_index_sequence<size>());
				now = arg.now;
				return *this;
			}
			data_type& operator=(data_type&& arg)
			{
				data = std::move(arg.data);
				now = arg.now;
				return *this;
			}
			~data_type() = default;

			template<std::size_t I>static auto get_instance_function()
			{
				return instance_t<I>::run;
			}

			template<class U>struct function_call
			{
				template<class T, class F, std::size_t... Is>static U run(T const& arg, F func, std::index_sequence<Is...>)
				{
					return func((*(std::get<Is>(arg).ptr))...);
				}
			};
			template<class U>struct recursion_function_call
			{
				template<class T, class F, class R, std::size_t... Is>static U run(T const& arg, F func, R recur, std::index_sequence<Is...>)
				{
					return func(recur, (*(std::get<Is>(arg).ptr))...);
				}
			};

			template<class U>struct pattern_match_function
			{
				std::tuple<function_type_t<U, Types>...> funcs;
				template<std::size_t... Is>U run(this_type const& arg,std::index_sequence<Is...>)const
				{
					return detail::get_tuple<U,0>(std::make_tuple(
						(static_cast<bool>(std::get<Is>(arg.data)) ?
							function_call<U>::run(
								(*(std::get<Is>(arg.data))).data,
								std::get<Is>(funcs),
								std::make_index_sequence<inside_data_t<Is>::size>()) :
							U())...), arg.now);
				}
				
				U operator()(this_type arg)const
				{
					return run(arg, std::make_index_sequence<this_type::size>());
				}
			};
			template<class U>static pattern_match_function<U> make_pattern_match_function(function_type_t<U, Types>... func)
			{
				return pattern_match_function<U>{std::make_tuple(func...)};
			}

			template<class U>struct memoization_pattern_match_function
			{
				std::tuple<function_type_t<U, Types>...> funcs;
				std::shared_ptr<std::vector<std::pair<this_type, U>>> data;
				template<std::size_t... Is>U run(this_type const& arg, std::index_sequence<Is...>)const
				{
					return detail::get_tuple<U, 0>(std::make_tuple(
						(static_cast<bool>(std::get<Is>(arg.data)) ?
							function_call<U>::run(
								(*(std::get<Is>(arg.data))).data,
								std::get<Is>(funcs),
								std::make_index_sequence<inside_data_t<Is>::size>()) :
							U())...), arg.now);
				}

				U operator()(this_type arg)const
				{
					for (auto const& x : *data)
					{
						if (arg.equal(x.first))
							return x.second;
					}
					auto ret = run(arg, std::make_index_sequence<this_type::size>());
					data->emplace_back(arg, ret);
					return ret;
				}
			};
			template<class U>static memoization_pattern_match_function<U> make_memoization_pattern_match_function(function_type_t<U, Types>... func)
			{
				return memoization_pattern_match_function<U>{std::make_tuple(func...), std::make_shared<std::vector<std::pair<this_type, U>>>()};
			}

			template<class U>struct recursion_pattern_match_function
			{
				std::tuple<recursion_function_t<U, Types>...> funcs;
				template<std::size_t... Is>U run(this_type const& arg, std::index_sequence<Is...>)const
				{
					return detail::get_tuple<U, 0>(std::make_tuple(
						(static_cast<bool>(std::get<Is>(arg.data)) ?
							recursion_function_call<U>::run(
								(*(std::get<Is>(arg.data))).data,
								std::get<Is>(funcs),
								std::ref(*this),
								std::make_index_sequence<inside_data_t<Is>::size>()):
							U())...), arg.now);
				}
				U operator()(this_type arg)const
				{
					return run(arg, std::make_index_sequence<size>());
				}
			};
			template<class U>static recursion_pattern_match_function<U>make_recursion_pattern_match_function(recursion_function_t<U, Types>... funcs)
			{
				return recursion_pattern_match_function<U>{std::make_tuple(funcs...)};
			}

			template<class U>struct memoization_recursion_pattern_match_function
			{
				std::tuple<recursion_function_t<U, Types>...> funcs;
				std::shared_ptr<std::vector<std::pair<this_type, U>>> data;
				template<std::size_t... Is>U run(this_type const& arg, std::index_sequence<Is...>)const
				{
					return detail::get_tuple<U, 0>(std::make_tuple(
						(static_cast<bool>(std::get<Is>(arg.data)) ?
							recursion_function_call<U>::run(
								(*(std::get<Is>(arg.data))).data,
								std::get<Is>(funcs),
								std::ref(*this),
								std::make_index_sequence<inside_data_t<Is>::size>()) :
							U())...), arg.now);
				}
				U operator()(this_type arg)const
				{
					for (auto const& x : *data)
					{
						if (arg == x.first)
						{
							return x.second;
						}
					}
					auto ret = run(arg, std::make_index_sequence<size>());
					data->emplace_back(arg, ret);
					return ret;
				}
			};
			template<class U>static memoization_recursion_pattern_match_function<U>make_memoization_recursion_pattern_match_function(recursion_function_t<U, Types>... funcs)
			{
				return memoization_recursion_pattern_match_function<U>{std::make_tuple(funcs...), std::make_shared<std::vector<std::pair<this_type, U>>>()};
			}

			template<std::size_t I>std::enable_if_t<I != size, bool> equal_i(this_type const& rhs, std::size_t i)const
			{
				return I == i ? std::get<I>(data)->equal(*std::get<I>(rhs.data)) : equal_i<I + 1>(rhs, i);
			}
			template<std::size_t I>std::enable_if_t<I == size, bool> equal_i(this_type const&, std::size_t)const
			{
				return false;
			}
			bool equal(this_type const& rhs)const
			{
				return now != rhs.now ? false : equal_i<0>(rhs, now);
			}

		};
		template<class... Ts>bool operator==(data_type<Ts...>const& lhs, data_type<Ts...> const& rhs)
		{
			return lhs.equal(rhs);
		}
		template<class... Ts>bool operator!=(data_type<Ts...>const& lhs, data_type<Ts...> const& rhs)
		{
			return !lhs.equal(rhs);
		}

	}
}
#endif

example.cpp

#include"algebraic_data_type.hpp"
#include<iostream>

using namespace plasma::algebraic_data_type;
typedef data_type<void, std::tuple<int, recursion_tag>> tree;
const auto sum = tree::make_memoization_recursion_pattern_match_function<int>(
	[](auto) {return 0;},
	[](auto f, int x, tree t) {return x + f(t);});

const auto Nil = tree::get_instance_function<0>();
const auto Tree = tree::get_instance_function<1>();

int main()
{
	std::cout << sum(Tree(1, Tree(2, Nil()))) << std::endl;
	std::cout << sum(Nil()) << std::endl;
}

reference.md

##なにこれ C++でも代数データ型したい！

##朗報 clangでも通るように修正できました

##gccは これらが原因で動かったので修正しました

##使い方 example.cppを参照
パターンマッチっぽく書ける(再帰する場合は先頭に再帰用の関数変数を入れる)