|
|
@@ -0,0 +1,324 @@ |
|
|
/* |
|
|
* Copyright (c) 2015 Plausible Labs Cooperative, Inc. |
|
|
* All rights reserved. |
|
|
*/ |
|
|
|
|
|
#pragma once |
|
|
|
|
|
#include <functional> |
|
|
#include <type_traits> |
|
|
#include <limits> |
|
|
#include <array> |
|
|
|
|
|
#include <PLStdCPP/ftl/functional.h> |
|
|
#include <PLStdCPP/ftl/type_functions.h> |
|
|
#include <PLStdCPP/ftl/concepts/monad.h> |
|
|
#include <PLStdCPP/ftl/concepts/monoid.h> |
|
|
|
|
|
/** |
|
|
* Polymorphic type-safe operations over tuples containing heterogeneous values. |
|
|
*/ |
|
|
namespace pl { |
|
|
namespace hlist { |
|
|
/* Internal implementation of C++14's index_sequence */ |
|
|
template <std::size_t ...> struct index_sequence {}; |
|
|
|
|
|
template <std::size_t N, std::size_t ... Indices> |
|
|
struct make_index_sequence : make_index_sequence<N - 1, N - 1, Indices...> {}; |
|
|
|
|
|
template <std::size_t ... Indices> |
|
|
struct make_index_sequence<std::size_t(0), Indices...> : index_sequence<Indices...> {}; |
|
|
|
|
|
/** |
|
|
* Range-based construction of index_sequence. |
|
|
* |
|
|
* @tparam I The initial index of the returned sequence. |
|
|
* @tparam Size The sequence length. |
|
|
*/ |
|
|
template <std::size_t I, std::size_t Size, std::size_t ... Indices> |
|
|
struct make_index_range : make_index_range<I, Size - 1, I + (Size - 1), Indices...> {}; |
|
|
|
|
|
template <std::size_t I, std::size_t ... Indices> |
|
|
struct make_index_range<I, std::size_t(0), Indices...> : index_sequence<Indices...> {}; |
|
|
|
|
|
#pragma mark Selection |
|
|
/** |
|
|
* Return a new tuple representing the selection of `Indices' from the provided @a tuple. |
|
|
* |
|
|
* @tparam Ts The element types of the provided tuple. |
|
|
* @param tuple The tuple from which to return the selected elements. |
|
|
*/ |
|
|
template <std::size_t ... Indices, typename ... Ts> static constexpr auto select (const std::tuple<Ts...> &tuple) -> decltype(std::make_tuple(std::get<Indices>(tuple)...)) { |
|
|
return std::make_tuple(std::get<Indices>(tuple)...); |
|
|
} |
|
|
|
|
|
/** |
|
|
* Return a new tuple representing the selection of `Indices' from the provided @a tuple. |
|
|
* |
|
|
* @tparam Ts The element types of the provided tuple. |
|
|
* @param tuple The tuple from which to return the selected elements. |
|
|
*/ |
|
|
template <std::size_t ... Indices, typename ... Ts> static constexpr auto select (const std::tuple<Ts...> &tuple, const index_sequence<Indices...> &) -> decltype(std::make_tuple(std::get<Indices>(tuple)...)) { |
|
|
return select<Indices...>(tuple); |
|
|
} |
|
|
|
|
|
/** |
|
|
* Return the head of the given @a tuple. |
|
|
* |
|
|
* @param tuple The tuple from which to return the first element. |
|
|
*/ |
|
|
template <typename ... Ts> static constexpr auto head (const std::tuple<Ts...> &tuple) -> typename std::tuple_element<0, std::tuple<Ts...>>::type { |
|
|
return std::get<0>(tuple); |
|
|
} |
|
|
|
|
|
/** |
|
|
* Return the tail of the given @a tuple. |
|
|
* |
|
|
* @param tuple The tuple from which to return the tail elements. |
|
|
*/ |
|
|
template <typename ... Ts> static constexpr auto tail (const std::tuple<Ts...> &tuple) -> decltype(select(tuple, make_index_range<1, sizeof...(Ts) - 1>())) { |
|
|
return select(tuple, make_index_range<1, sizeof...(Ts) - 1>()); |
|
|
} |
|
|
|
|
|
#pragma mark Map |
|
|
|
|
|
/** |
|
|
* @internal |
|
|
* Type-safe mapping via polymorphic application of F. |
|
|
*/ |
|
|
template<typename Fn, typename ... Ts> struct Mapper { |
|
|
template<std::size_t ... Indices> static constexpr auto map (const std::tuple<Ts...> &tuple, const Fn &fn, const index_sequence<Indices...> &) -> |
|
|
decltype(std::make_tuple(fn(std::get<Indices>(tuple))...)) |
|
|
{ |
|
|
return std::make_tuple(fn(std::get<Indices>(tuple))...); |
|
|
} |
|
|
}; |
|
|
|
|
|
|
|
|
|
|
|
/** |
|
|
* Map polymorphic function `F` over all values of @a tuple, returning a new tuple containing the well-typed results. |
|
|
* |
|
|
* @tparam Fn A templated function-like struct that accepts tuple elements as its single argument. |
|
|
* @param tuple The tuple over which `F` will be applied. |
|
|
*/ |
|
|
template <typename Fn, typename ... Ts> constexpr auto map (const std::tuple<Ts...> &tuple, const Fn &f) -> decltype(Mapper<Fn, Ts...>::map(tuple, f, make_index_sequence<sizeof...(Ts)>())) { |
|
|
return Mapper<Fn, Ts...>::map(tuple, f, make_index_sequence<sizeof...(Ts)>()); |
|
|
} |
|
|
|
|
|
|
|
|
#pragma mark Apply |
|
|
/** |
|
|
* @internal |
|
|
* Type-safe mapping via application of (fn1, f2, ...) and (val1, val2, ...) tuples. |
|
|
*/ |
|
|
template<typename ... Fn> struct Applier { |
|
|
template<std::size_t ... Indices> static constexpr std::tuple<typename std::decay<typename Fn::result_type>::type...> apply (const std::tuple<Fn...> &funcs, const std::tuple<typename std::decay<typename Fn::argument_type>::type...> &values, const index_sequence<Indices...> &) { |
|
|
return std::make_tuple(std::get<Indices>(funcs)(std::get<Indices>(values))...); |
|
|
} |
|
|
}; |
|
|
|
|
|
/** |
|
|
* Type-safe 1:1 function application. |
|
|
* |
|
|
* @param funcs The functions to be applied to @a values. |
|
|
* @param values The values to which @a funcs will be applied. |
|
|
*/ |
|
|
template <typename ... Fn> constexpr const std::tuple<typename std::decay<typename Fn::result_type>::type...> apply (const std::tuple<Fn...> &funcs, const std::tuple<typename std::decay<typename Fn::argument_type>::type...> &values) { |
|
|
return Applier<Fn...>::apply(funcs, values, make_index_sequence<sizeof...(Fn)>()); |
|
|
} |
|
|
|
|
|
|
|
|
#pragma mark Fold |
|
|
/** |
|
|
* @internal |
|
|
* Type-safe folding via polymorphic application of F. |
|
|
*/ |
|
|
template<typename F, typename S, typename ... Ts> struct Folder { |
|
|
/* Terminal leftFold implementation */ |
|
|
template<std::size_t Idx> static constexpr typename std::enable_if<Idx == sizeof...(Ts), S>::type leftFold (const S &state, const std::tuple<Ts...> &tuple, const F &fn) { |
|
|
return state; |
|
|
} |
|
|
|
|
|
/* Recursively defined left fold */ |
|
|
template<std::size_t Idx> static constexpr typename std::enable_if<Idx < sizeof...(Ts), S>::type leftFold (const S &state, const std::tuple<Ts...> &tuple, const F &fn) { |
|
|
return leftFold<Idx+1>(fn(state, std::get<Idx>(tuple)), tuple, fn); |
|
|
} |
|
|
}; |
|
|
|
|
|
/** |
|
|
* Type-safe polymorphic left fold over @a tuple. |
|
|
* |
|
|
* @param state Initial state. |
|
|
* @param tuple Tuple over which the left fold will be computed. |
|
|
* @param fn A struct providing a unary function-call operator that may be applied to all elements of @a tuple. |
|
|
*/ |
|
|
template <typename F, typename S, typename ... Ts> constexpr typename std::decay<S>::type leftFold (const S &state, const std::tuple<Ts ...> &tuple, const F &fn) { |
|
|
return Folder<F, typename std::decay<S>::type, Ts...>::template leftFold<0>(state, tuple, fn); |
|
|
} |
|
|
|
|
|
|
|
|
#pragma mark Zip |
|
|
/** |
|
|
* @internal |
|
|
* Type-safe zipping via polymorphic application of the given zipper function F. This is essentially a specialization of |
|
|
* map() across two tuples. |
|
|
*/ |
|
|
template<typename LHS, typename RHS> struct Zipper { |
|
|
static_assert(ftl::is_same_template<std::tuple<>, LHS>::value, "The `lhs' argument is not a tuple."); |
|
|
static_assert(ftl::is_same_template<std::tuple<>, RHS>::value, "The `rhs' argument is not a tuple."); |
|
|
static_assert(std::tuple_size<LHS>::value == std::tuple_size<RHS>::value, "The `lhs' and `rhs' tuple operands must be identically sized"); |
|
|
|
|
|
template<typename Fn, std::size_t ... Indices> static auto zipWith (const LHS &lhs, const RHS &rhs, const Fn &fn, const index_sequence<Indices...> &) -> |
|
|
decltype(std::make_tuple(fn(std::get<Indices>(lhs), std::get<Indices>(rhs))...)) |
|
|
{ |
|
|
return std::make_tuple(fn(std::get<Indices>(lhs), std::get<Indices>(rhs))...); |
|
|
} |
|
|
}; |
|
|
|
|
|
/** |
|
|
* @internal |
|
|
* Polymorphic zipper function; maps (L, R) pairs to std::pair<L, R>. |
|
|
*/ |
|
|
static constexpr struct zip_pair_fn { |
|
|
template <typename L, typename R> std::pair<L, R> constexpr operator() (const L &lhs, const R &rhs) const { |
|
|
return std::make_pair(lhs, rhs); |
|
|
} |
|
|
} zip_pair {}; |
|
|
|
|
|
/** |
|
|
* Type-safe polymorphic zipWith over @a lhs and @rhs tuple operands. |
|
|
* |
|
|
* @param lhs The first tuple operand. |
|
|
* @param rhs The second tuple operand. |
|
|
* @param fn A struct providing a binary function-call operator that may be applied to all pairs in @a lhs and @a rhs. |
|
|
*/ |
|
|
template <typename Fn, typename LHS, typename RHS> constexpr auto zipWith (const LHS &lhs, const RHS &rhs, const Fn &fn) -> |
|
|
decltype(Zipper<LHS, RHS>::zipWith(lhs, rhs, fn, make_index_sequence<std::tuple_size<RHS>::value>())) |
|
|
{ |
|
|
return Zipper<LHS, RHS>::zipWith(lhs, rhs, fn, make_index_sequence<std::tuple_size<RHS>::value>()); |
|
|
} |
|
|
|
|
|
/** |
|
|
* Type-safe zip over equally sized @a lhs and @rhs tuple operands, producing a new tuple |
|
|
* composed of std::pair<lhs..., rhs...> values. |
|
|
* |
|
|
* @param lhs The first tuple operand. |
|
|
* @param rhs The second tuple operand. |
|
|
*/ |
|
|
template <typename LHS, typename RHS> constexpr auto zip (const LHS &lhs, const RHS &rhs) -> |
|
|
decltype(zipWith(lhs, rhs, zip_pair)) |
|
|
{ |
|
|
return zipWith(lhs, rhs, zip_pair); |
|
|
} |
|
|
|
|
|
#pragma mark Array Conversion |
|
|
|
|
|
/** |
|
|
* @internal |
|
|
* |
|
|
* Conversion of std::tuple values to std::array. |
|
|
*/ |
|
|
template <typename T> struct ToArray { |
|
|
template<std::size_t ... Indices> constexpr static std::array< |
|
|
typename std::tuple_element<0, T>::type, |
|
|
std::tuple_size<T>::value |
|
|
> to_array (const T &tuple, const index_sequence<Indices...> &) { |
|
|
return {{ std::get<Indices>(tuple)... }}; |
|
|
} |
|
|
}; |
|
|
|
|
|
/** |
|
|
* Convert a std::tuple to a std::array. |
|
|
*/ |
|
|
template <typename T> constexpr static auto to_array (const T &tuple) -> decltype(ToArray<T>::to_array(tuple, make_index_sequence<std::tuple_size<T>::value>())) { |
|
|
return ToArray<T>::to_array(tuple, make_index_sequence<std::tuple_size<T>::value>()); |
|
|
} |
|
|
|
|
|
#pragma mark Sequence |
|
|
/** |
|
|
* @internal |
|
|
* |
|
|
* Sequencing (essentially a fold) over a tuple of Monad<Monoid> values. |
|
|
*/ |
|
|
template<typename M> struct Sequencer { |
|
|
/* Perform a sequence with the supplied initial value. */ |
|
|
template <typename ... Ms> static M sequence (const M &zero, const std::tuple<Ms...> &operand) |
|
|
{ |
|
|
typedef ftl::Value_type<M> V; |
|
|
typedef ftl::monad<M> TMonad; |
|
|
typedef ftl::monoid<V> VMonoid; |
|
|
|
|
|
const auto operands = to_array(operand); |
|
|
|
|
|
auto accum = zero; |
|
|
for (size_t i = 0; i < operands.size(); i++) { |
|
|
const auto &next = operands[i]; |
|
|
|
|
|
accum = accum >>= [&next](const V &a) { |
|
|
return [&a](const V &n) { |
|
|
return VMonoid::append(a, n); |
|
|
} % next; |
|
|
}; |
|
|
} |
|
|
|
|
|
return accum; |
|
|
} |
|
|
|
|
|
/* Perform a sequence with the monoid<V>-supplied zero value as the initial zero value. */ |
|
|
template <typename ... Ms> static M sequence (const std::tuple<Ms...> &operand) { |
|
|
typedef ftl::Value_type<M> V; |
|
|
typedef ftl::monad<M> TMonad; |
|
|
typedef ftl::monoid<V> VMonoid; |
|
|
|
|
|
const auto zero = TMonad::pure(VMonoid::id()); |
|
|
return sequence(zero, operand); |
|
|
} |
|
|
|
|
|
}; |
|
|
|
|
|
/** |
|
|
* Given a tuple containing monadic-wrapped monoidal values, sequence all values, producing a single accumulated value. |
|
|
* |
|
|
* @param initial The initial value to which all sequenced values will be appended. |
|
|
* @param tuple A tuple containing monadic values to be sequenced. |
|
|
*/ |
|
|
template <typename M, typename ... Ms> static auto sequence (const M &initial, const std::tuple<M, Ms...> &tuple) -> decltype(Sequencer<M>::sequence(tuple)) { |
|
|
return Sequencer<M>::sequence(initial, tuple); |
|
|
} |
|
|
|
|
|
/** |
|
|
* Given a tuple containing monadic-wrapped monoidal values, sequence all values, producing a single accumulated value. |
|
|
* |
|
|
* @param tuple A tuple containing monadic values to be sequenced. |
|
|
*/ |
|
|
template <typename M, typename ... Ms> static auto sequence (const std::tuple<M, Ms...> &tuple) -> decltype(Sequencer<M>::sequence(tuple)) { |
|
|
return Sequencer<M>::sequence(tuple); |
|
|
} |
|
|
|
|
|
/** |
|
|
* Given an empty tuple with a known type, sequence returns an empty result. |
|
|
* |
|
|
* @param tuple An empty tuple to sequence. |
|
|
*/ |
|
|
template < |
|
|
typename M, |
|
|
typename V = ftl::Value_type<M>, |
|
|
typename R = ftl::Requires<ftl::Monad<M>{}>, |
|
|
typename RV = ftl::Requires<ftl::Monoid<V>{}> |
|
|
> constexpr M sequence (const std::tuple<> &empty) { |
|
|
return ftl::monad<M>::pure(ftl::monoid<V>::id()); |
|
|
} |
|
|
|
|
|
/** |
|
|
* Given an empty tuple, sequence returns the initial value. |
|
|
* |
|
|
* @param initial The initial value to which all sequenced values will be appended. |
|
|
* @param tuple An empty tuple to sequence. |
|
|
*/ |
|
|
template <typename M> constexpr const M sequence (const M &initial, const std::tuple<> &empty) { |
|
|
return initial; |
|
|
} |
|
|
} |
|
|
}; |
|
|
#pragma mark - |
landonf created this gist