Skip to content

Instantly share code, notes, and snippets.

@plasma-effect
Last active October 7, 2015 17:11
Show Gist options
  • Save plasma-effect/a8b8185105011a6d635f to your computer and use it in GitHub Desktop.
Save plasma-effect/a8b8185105011a6d635f to your computer and use it in GitHub Desktop.
algebraic_data_type
#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
#pragma once
// 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<typeinfo>
#include<utility>
#include<memory>
#include<functional>
#include<vector>
namespace plasma
{
namespace algebraic_data_type
{
struct recursion_tag {};
namespace detail
{
bool all_and(bool f)
{
return f;
}
template<class... Ts>bool all_and(bool f, Ts... args)
{
return f&&all_and(args...);
}
}
template<class... Types>class data_type
{
typedef data_type<Types...> this_type;
typedef std::tuple<Types...> template_parameter;
struct base_type
{
virtual ~base_type() {}
base_type() = default;
base_type(base_type const&) = default;
base_type(base_type&&) = default;
base_type& operator=(base_type const&) = default;
base_type& operator=(base_type&&) = default;
virtual std::type_info const& type()
{
return typeid(*this);
}
virtual std::unique_ptr<base_type> clone()const = 0;
virtual bool equal(base_type& rhs) = 0;
};
template<class T, class = void>struct ptr_type
{
T ptr_;
typedef T value_type;
value_type get_value()const
{
return ptr_;
}
ptr_type(value_type const& arg) :ptr_(arg) {}
ptr_type(ptr_type const&) = delete;
ptr_type(ptr_type&&) = default;
ptr_type& operator=(ptr_type const&) = delete;
ptr_type& operator=(ptr_type&&) = default;
};
template<class T>struct ptr_type<T, std::enable_if_t<std::is_same<T, recursion_tag>::value>>
{
std::unique_ptr<this_type> ptr_;
typedef this_type value_type;
value_type get_value()const
{
return *ptr_;
}
ptr_type(value_type const& arg) :ptr_(std::make_unique<value_type>(arg)) {}
ptr_type(ptr_type const&) = delete;
ptr_type(ptr_type&&) = default;
ptr_type& operator=(ptr_type const&) = delete;
ptr_type& operator=(ptr_type&&) = default;
};
template<class T>using true_t = typename ptr_type<T>::value_type;
template<std::size_t I, class T>struct inside_data :base_type
{
std::tuple<ptr_type<T>> datas;
std::unique_ptr<base_type> clone()const
{
return std::make_unique<inside_data<I, T>>(std::make_tuple(ptr_type<T>(std::get<0>(datas).get_value())));
}
typedef std::tuple<true_t<T>> argument_type;
bool equal(base_type& rhs)
{
if (this->type() != rhs.type())
{
return false;
}
inside_data<I, T>& p = dynamic_cast<inside_data<I, T>&>(rhs);
return std::get<0>(datas).get_value() == std::get<0>(p.datas).get_value();
}
inside_data(std::tuple<ptr_type<T>>&& arg) :datas(std::move(arg)) {}
inside_data(true_t<T>const& arg) :datas(ptr_type<T>(arg)){}
inside_data(inside_data const&) = delete;
inside_data(inside_data&&) = default;
inside_data& operator=(inside_data const&) = delete;
inside_data& operator=(inside_data&&) = default;
};
template<std::size_t I, class... Ts>struct inside_data<I, std::tuple<Ts...>> :base_type
{
std::tuple<ptr_type<Ts>...> datas;
std::unique_ptr<base_type> clone()const
{
return clone_i(std::make_index_sequence<sizeof...(Ts)>());
}
template<std::size_t... Us>auto clone_i(std::index_sequence<Us...>)const
{
return std::make_unique<inside_data<I, std::tuple<Ts...>>>(std::make_tuple((ptr_type<Ts>(std::get<Us>(datas).get_value()))...));
}
bool equal(base_type& rhs)
{
return this->type() == rhs.type() && equal_i(dynamic_cast<inside_data<I, std::tuple<Ts...>>&>(rhs), std::make_index_sequence<sizeof...(Ts)>());
}
template<std::size_t... Is>bool equal_i(inside_data<I, std::tuple<Ts...>>& rhs, std::index_sequence<Is...>)
{
return detail::all_and((std::get<Is>(datas).get_value() == std::get<Is>(rhs.datas).get_value())...);
}
inside_data(std::tuple<ptr_type<Ts>...>&& arg) :datas(std::move(arg)) {}
inside_data(true_t<Ts>const&... arg) :datas(ptr_type<Ts>(arg)...) {}
inside_data(inside_data const&) = delete;
inside_data(inside_data&&) = default;
inside_data& operator=(inside_data const&) = delete;
inside_data& operator=(inside_data&&) = default;
};
template<std::size_t I>struct inside_data<I, void> :base_type
{
std::unique_ptr<base_type> clone()const
{
return std::make_unique<inside_data<I, void>>();
}
inside_data() = default;
inside_data(inside_data const&) = delete;
inside_data(inside_data&&) = default;
inside_data& operator=(inside_data const&) = delete;
inside_data& operator=(inside_data&&) = default;
bool equal(base_type& rhs)
{
return this->type() == rhs.type();
}
};
template<std::size_t I, class T>struct make_inside_data_t
{
static std::unique_ptr<base_type> run(true_t<T>const& arg)
{
return std::make_unique<inside_data<I, T>>(arg);
}
};
template<std::size_t I, class... Ts>struct make_inside_data_t<I, std::tuple<Ts...>>
{
static std::unique_ptr<base_type> run(true_t<Ts>const&...args)
{
return std::make_unique<inside_data<I, std::tuple<Ts...>>>(args...);
}
};
template<std::size_t I>struct make_inside_data_t<I, void>
{
static std::unique_ptr<base_type> run()
{
return std::make_unique<inside_data<I, void>>();
}
};
template<std::size_t I, class T>struct make_data_type_t
{
static this_type run(true_t<T>const& arg)
{
this_type ret{};
ret.this_ptr_ = make_inside_data_t<I, T>::run(arg);
return ret;
}
};
template<std::size_t I, class... Ts>struct make_data_type_t<I, std::tuple<Ts...>>
{
static this_type run(true_t<Ts> const&... args)
{
this_type ret{};
ret.this_ptr_ = make_inside_data_t<I, std::tuple<Ts...>>::run(args...);
return ret;
}
};
template<std::size_t I>struct make_data_type_t<I, void>
{
static this_type run()
{
this_type ret{};
ret.this_ptr_ = make_inside_data_t<I, void>::run();
return ret;
}
};
template<class Return, class T>struct function_call_t
{
template<std::size_t I>static Return run(std::function<Return(true_t<T>)>const& func, inside_data<I, T> const& arg)
{
return func(std::get<0>(arg.datas).get_value());
}
typedef std::function<Return(true_t<T>)> function_t;
};
template<class Return, class... Ts>struct function_call_t<Return, std::tuple<Ts...>>
{
template<std::size_t I>static Return run(std::function<Return(true_t<Ts>...)>const& func, inside_data<I, std::tuple<Ts...>> const& arg)
{
return run_i(func, arg, std::make_index_sequence<sizeof...(Ts)>());
}
template<std::size_t I,std::size_t... Is>static Return run_i(std::function<Return(true_t<Ts>...)>const& func, inside_data<I, std::tuple<Ts...>> const& arg, std::index_sequence<Is...>)
{
return func(std::get<Is>(arg.datas).get_value()...);
}
typedef std::function<Return(true_t<Ts>...)> function_t;
};
template<class Return>struct function_call_t<Return, void>
{
template<std::size_t I>static Return run(std::function<Return(void)> const& func, inside_data<I, void>const&)
{
return func();
}
typedef std::function<Return(void)> function_t;
};
template<class Return, class T>struct recursion_call_t
{
template<std::size_t I>static Return run(
std::function<Return(std::function<Return(this_type)>,true_t<T>)>const& func,
std::function<Return(this_type)> const& recur,
inside_data<I, T> const& arg)
{
return func(recur, std::get<0>(arg.datas).get_value());
}
typedef std::function<Return(std::function<Return(this_type)>, true_t<T>)> function_t;
};
template<class Return, class... Ts>struct recursion_call_t<Return, std::tuple<Ts...>>
{
template<std::size_t I>static Return run(
std::function<Return(std::function<Return(this_type)>, true_t<Ts>...)>const& func,
std::function<Return(this_type)>const& recur,
inside_data<I, std::tuple<Ts...>> const& arg)
{
return run_i(func, recur, arg, std::make_index_sequence<sizeof...(Ts)>());
}
template<std::size_t I, std::size_t... Is>static Return run_i(
std::function<Return(std::function<Return(this_type)>, true_t<Ts>...)>const& func,
std::function<Return(this_type)>const& recur,
inside_data<I, std::tuple<Ts...>> const& arg,
std::index_sequence<Is...>)
{
return func(recur, std::get<Is>(arg.datas).get_value()...);
}
typedef std::function<Return(std::function<Return(this_type)>, true_t<Ts>...)> function_t;
};
template<class Return>struct recursion_call_t<Return, void>
{
template<std::size_t I>static Return run(
std::function<Return(std::function<Return(this_type)>)> const& func,
std::function<Return(this_type)> const& recur,
inside_data<I, void>const&)
{
return func(recur);
}
typedef std::function<Return(std::function<Return(this_type)>)> function_t;
};
template<std::size_t I>using get_inside_type = inside_data<I, std::tuple_element_t<I, template_parameter>>;
std::unique_ptr<base_type> this_ptr_;
data_type() = default;
public:
data_type(data_type const& arg) :this_ptr_(arg.this_ptr_->clone()) {}
data_type(data_type&&) = default;
data_type& operator=(data_type const& arg)
{
this_ptr_ = arg.this_ptr_->clone();
return *this;
}
data_type& operator=(data_type&&) = default;
template<std::size_t I>static auto make_instance_function()
{
return make_data_type_t<I, std::tuple_element_t<I, template_parameter>>::run;
}
template<class Return>struct pattern_match_t
{
std::tuple<typename function_call_t<Return, Types>::function_t...> funcs;
Return operator()(this_type const& arg)const
{
return run<0>(arg);
}
template<std::size_t I>std::enable_if_t<I == sizeof...(Types), Return> run(this_type const&)const
{
return Return();
}
template<std::size_t I>std::enable_if_t<I != sizeof...(Types), Return> run(this_type const& arg)const
{
return (arg.this_ptr_->type() == typeid(get_inside_type<I>) ?
function_call_t<Return, std::tuple_element_t<I, template_parameter>>::run(
std::get<I>(funcs),
dynamic_cast<get_inside_type<I> const&>(*arg.this_ptr_)) :
run<I + 1>(arg));
}
};
template<class Return>static pattern_match_t<Return>make_pattern(typename function_call_t<Return, Types>::function_t const&... funcs)
{
return pattern_match_t<Return>{std::make_tuple(funcs...)};
}
template<class Return>struct recursion_pattern_match_t
{
std::tuple<typename recursion_call_t<Return, Types>::function_t...> funcs;
Return operator()(this_type const& arg)const
{
return run<0>(arg);
}
template<std::size_t I>std::enable_if_t<I == sizeof...(Types), Return> run(this_type const&)const
{
return Return();
}
template<std::size_t I>std::enable_if_t<I != sizeof...(Types), Return> run(this_type const& arg)const
{
return (arg.this_ptr_->type() == typeid(get_inside_type<I>) ?
recursion_call_t<Return, std::tuple_element_t<I, template_parameter>>::run(
std::get<I>(funcs),
std::ref(*this),
dynamic_cast<get_inside_type<I> const&>(*arg.this_ptr_)) :
run<I + 1>(arg));
}
};
template<class Return>static recursion_pattern_match_t<Return>make_recursion(typename recursion_call_t<Return, Types>::function_t const&... funcs)
{
return recursion_pattern_match_t<Return>{std::make_tuple(funcs...)};
}
template<class Return>struct memoization_pattern_match_t
{
std::tuple<typename function_call_t<Return, Types>::function_t...> funcs;
std::shared_ptr<std::vector<std::pair<this_type, Return>>> vec;
Return operator()(this_type const& arg)const
{
for (auto const& v : *vec)
{
if (v.first == arg)
{
return v.second;
}
}
auto ret = run<0>(arg);
vec->emplace_back(arg, ret);
return ret;
}
template<std::size_t I>std::enable_if_t<I == sizeof...(Types), Return> run(this_type const&)const
{
return Return();
}
template<std::size_t I>std::enable_if_t<I != sizeof...(Types), Return> run(this_type const& arg)const
{
return (arg.this_ptr_->type() == typeid(get_inside_type<I>) ?
function_call_t<Return, std::tuple_element_t<I, template_parameter>>::run(
std::get<I>(funcs),
dynamic_cast<get_inside_type<I> const&>(*arg.this_ptr_)) :
run<I + 1>(arg));
}
};
template<class Return>static auto make_memoization_pattern(typename function_call_t<Return, Types>::function_t const&... funcs)
{
return memoization_pattern_match_t<Return>{std::make_tuple(funcs...), std::make_shared<std::vector<std::pair<this_type, Return>>>()};
}
template<class Return>struct memoization_recursion_pattern_match_t
{
std::tuple<typename recursion_call_t<Return, Types>::function_t...> funcs;
std::shared_ptr<std::vector<std::pair<this_type, Return>>> vec;
Return operator()(this_type const& arg)const
{
for (auto const& v : *vec)
{
if (v.first == arg)
{
return v.second;
}
}
auto ret = run<0>(arg);
vec->emplace_back(arg, ret);
return ret;
}
template<std::size_t I>std::enable_if_t<I == sizeof...(Types), Return> run(this_type const&)const
{
return Return();
}
template<std::size_t I>std::enable_if_t<I != sizeof...(Types), Return> run(this_type const& arg)const
{
return (arg.this_ptr_->type() == typeid(get_inside_type<I>) ?
recursion_call_t<Return, std::tuple_element_t<I, template_parameter>>::run(
std::get<I>(funcs),
std::ref(*this),
dynamic_cast<get_inside_type<I> const&>(*arg.this_ptr_)) :
run<I + 1>(arg));
}
};
template<class Return>static auto make_memoization_recursion(typename recursion_call_t<Return, Types>::function_t const&... funcs)
{
return memoization_recursion_pattern_match_t<Return>{std::make_tuple(funcs...), std::make_shared<std::vector<std::pair<this_type, Return>>>()};
}
bool operator==(this_type const& rhs)const
{
return this_ptr_->equal(*rhs.this_ptr_);
}
bool operator!=(this_type const& rhs)const
{
return !this_ptr_->equal(*rhs.this_ptr_);
}
};
}
}
#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;
}
#include"algebraic_data_type_pt2.hpp"
#include<iostream>
int main()
{
typedef plasma::algebraic_data_type::recursion_tag self;
typedef plasma::algebraic_data_type::data_type<void, std::tuple<int,self>> type;
const auto Nil = type::make_instance_function<0>()();
const auto Tree = type::make_instance_function<1>();
auto test = Tree(1, Tree(2, Nil));
const auto sum = type::make_memoization_recursion<int>(
[](auto) {return 0;},
[](auto f, int x, type t) {return x + f(t);});
std::cout << sum(test) << std::endl;
std::cout << sum(test) << std::endl;
}

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

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

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

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

##どうでもいい話 クソみたいな実装だったのでクソ度合いを下げた美しい(当社比)実装で作りなおしました(algebraic_data_type_pt2.hpp) 一部関数名が変わってるので注意

##Special Thanks @wx257osn2 氏(recursion_pattern_match_function周り)

##大切なお知らせ deprecatedになりました、adt_rebirth.hppを使ってください

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment