Created
December 12, 2012 14:17
-
-
Save splinterofchaos/4268029 to your computer and use it in GitHub Desktop.
More fun with tuples.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <tuple> | |
#include <iostream> | |
template< size_t ...i > struct IndexList {}; | |
template< size_t ... > struct EnumBuilder; | |
// Increment cur until cur == end. | |
template< size_t end, size_t cur, size_t ...i > | |
struct EnumBuilder< end, cur, i... > | |
// Recurse, adding cur to i... | |
: EnumBuilder< end, cur+1, i..., cur > | |
{ | |
}; | |
// cur == end; the list has been built. | |
template< size_t end, size_t ...i > | |
struct EnumBuilder< end, end, i... > { | |
using type = IndexList< i... >; | |
}; | |
template< size_t b, size_t e > | |
struct Enumerate { | |
using type = typename EnumBuilder< e, b >::type; | |
}; | |
template< class > struct IListFrom; | |
template< class ...X > | |
struct IListFrom< std::tuple<X...> > { | |
static constexpr size_t N = sizeof ...(X); | |
using type = typename Enumerate< 0, N >::type; | |
}; | |
// std::tuple_element<i,T> does not perfect forward. | |
template< size_t i, class T > | |
using Elem = decltype( std::get<i>(std::declval<T>()) ); | |
template< size_t i > struct Get { | |
template< class T > | |
constexpr auto operator () ( T&& t ) | |
-> Elem< i, T > | |
{ | |
return std::get<i>( std::forward<T>(t) ); | |
} | |
}; | |
template< size_t i, class T, | |
class _T = typename std::decay<T>::type, | |
size_t N = std::tuple_size<_T>::value - 1, // Highest index | |
size_t j = N - i > | |
constexpr auto rget( T&& t ) | |
-> Elem< j, T > | |
{ | |
return std::get<j>( std::forward<T>(t) ); | |
} | |
template< size_t i > struct RGet { | |
template< class T > | |
constexpr auto operator () ( T&& t ) | |
-> decltype( rget<i>( std::forward<T>(t) ) ) | |
{ | |
return rget<i>( std::forward<T>(t) ); | |
} | |
}; | |
template< size_t i, class T, | |
class _T = typename std::decay<T>::type, | |
size_t N = std::tuple_size<_T>::value, | |
size_t j = i % N > | |
constexpr auto mod_get( T&& t ) | |
-> Elem< j, T > | |
{ | |
return std::get<j>( std::forward<T>(t) ); | |
} | |
template< template<size_t> class Fi = Get, size_t ...i, class F, class T > | |
constexpr auto applyIndexList( IndexList<i...>, const F& f, T&& t ) | |
-> typename std::result_of< F( | |
typename std::result_of< Fi<i>(T) >::type... | |
) >::type | |
{ | |
return f( Fi<i>()(std::forward<T>(t))... ); | |
} | |
template< template<size_t> class Fi = Get, class F, class T, | |
class _T = typename std::decay<T>::type, | |
class IL = typename IListFrom<_T>::type > | |
constexpr auto applyTuple( const F& f, T&& t ) | |
-> decltype( applyIndexList<Fi>(IL(),f,std::forward<T>(t)) ) | |
{ | |
return applyIndexList<Fi>( IL(), f, std::forward<T>(t) ); | |
} | |
// Because std::make_tuple can't be passed | |
// to higher order functions. | |
constexpr struct MakeTuple { | |
template< class ...X > | |
constexpr std::tuple<X...> operator () ( X ...x ) { | |
return std::tuple<X...>( std::move(x)... ); | |
} | |
} tuple{}; | |
// Returns the initial elements. (All but the last.) | |
// init( {1,2,3} ) = {1,2} | |
template< class T, | |
size_t N = std::tuple_size<T>::value, | |
class IL = typename Enumerate< 0, N-1 >::type > | |
constexpr auto init( const T& t ) | |
-> decltype( applyIndexList(IL(),tuple,t) ) | |
{ | |
return applyIndexList( IL(), tuple, t ); | |
} | |
// Returns a new tuple with every value from t except the first. | |
// tail( {1,2,3} ) = {2,3} | |
template< class T, | |
size_t N = std::tuple_size<T>::value, | |
class IL = typename Enumerate< 1, N >::type > | |
constexpr auto tail( const T& t ) | |
-> decltype( applyIndexList(IL(),tuple,t) ) | |
{ | |
return applyIndexList( IL(), tuple, t ); | |
} | |
// Reconstruct t in reverse. | |
template< class T > | |
constexpr auto reverse( const T& t ) | |
-> decltype( applyTuple<RGet>(tuple,t) ) | |
{ | |
return applyTuple< RGet >( tuple, t ); | |
} | |
template< size_t i, size_t ...j, class F, class T > | |
void forEachIndex( IndexList<i,j...>, const F& f, const T& t ) { | |
f( std::get<i>(t) ); | |
forEachIndex( IndexList<j...>(), f, t ); | |
} | |
template< class F, class T > | |
void forEachIndex( IndexList<>, const F& f, const T& t ) { | |
} | |
template< class F, class T > | |
void forEach( const F& f, const T& t ) { | |
constexpr size_t N = std::tuple_size<T>::value; | |
using IL = typename Enumerate<0,N>::type; | |
forEachIndex( IL(), f, t ); | |
} | |
constexpr struct PrintItem { | |
template< class X > | |
void operator () ( const X& x ) const { | |
std::cout << x << ' '; | |
} | |
} printItem{}; | |
constexpr struct PushBack { | |
template< class ...X, class Y > | |
constexpr auto operator () ( std::tuple<X...> t, Y y ) | |
-> std::tuple< X..., Y > | |
{ | |
return std::tuple_cat( std::move(t), tuple(std::move(y)) ); | |
} | |
} pushBack{}; | |
constexpr struct PushFront { | |
template< class ...X, class Y > | |
constexpr auto operator () ( std::tuple<X...> t, Y y ) | |
-> std::tuple< Y, X... > | |
{ | |
return std::tuple_cat( tuple(std::move(y)), std::move(t) ); | |
} | |
} pushFront{}; | |
constexpr auto head = Get<0>(); | |
constexpr auto last = RGet<0>(); | |
// Chain Left. | |
constexpr struct ChainL { | |
template< class F, class X > | |
constexpr X operator () ( const F&, X x ) { | |
return x; | |
} | |
template< class F, class X, class Y, class ...Z > | |
constexpr auto operator () ( const F& b, const X& x, const Y& y, const Z& ...z) | |
-> decltype( (*this)(b, b(x,y), z... ) ) | |
{ | |
return (*this)(b, b(x,y), z... ); | |
} | |
} chainl{}; | |
// Fold Left. | |
constexpr struct FoldL { | |
// Given f and {x,y,z}, returns f( f(x,y), z ). | |
template< class F, class T > | |
constexpr auto operator () ( const F& f, const T& t ) | |
-> decltype( applyTuple(chainl,pushFront(t,f)) ) | |
{ | |
return applyTuple( chainl, pushFront(t,f) ); | |
} | |
} foldl{}; | |
// Fold Right. | |
constexpr struct FoldR { | |
// Given f and {x,y,z}, returns f( f(z,y), x ). | |
template< class F, class T > | |
constexpr auto operator () ( const F& f, const T& t ) | |
-> decltype( foldl(f,reverse(t)) ) | |
{ | |
return foldl( f, reverse(t) ); | |
} | |
} foldr{}; | |
auto ten = foldl( std::plus<int>(), std::make_tuple(1,2,3,4) ); | |
template< class ...X > | |
constexpr auto third_arg( X&& ...x ) | |
-> Elem< 2, std::tuple<X...> > | |
{ | |
return std::get<2>( std::forward_as_tuple(std::forward<X>(x)...) ); | |
} | |
template< class F, class ...X > | |
struct TFunction { | |
F f; | |
std::tuple<X...> applied; // applied arguments. | |
template< class ...Y > | |
constexpr TFunction( F f, Y&& ...y ) | |
: f( std::move(f) ), applied( std::forward<Y>(y)... ) | |
{ | |
} | |
template< class ...Y, class T = std::tuple<X...,Y...> > | |
constexpr T add( Y&& ...y ) { | |
return std::tuple_cat ( | |
applied, | |
std::forward_as_tuple( std::forward<Y>(y)... ) | |
); | |
} | |
template< class ...Y > | |
constexpr auto operator () ( Y&& ...y ) | |
-> typename std::result_of< F( X..., Y... ) >::type | |
{ | |
return applyTuple( f, add(std::forward<Y>(y)...) ); | |
} | |
}; | |
template< class F, class ...X, class R = TFunction<F,X...> > | |
R tfun( F f, X ...x ) { | |
return R( std::move(f), std::move(x)... ); | |
} | |
#include <cmath> | |
// Quadratic root. | |
constexpr struct QRoot { | |
using result = std::tuple<float,float>; | |
result operator () ( float a, float b, float c ) const { | |
float root = std::sqrt( b*b - 4*a*c ); | |
float den = 2 * a; | |
return result( (-b+root)/den, (-b-root)/den ); | |
} | |
} qroot{}; | |
std::ostream& operator << ( std::ostream& os, const QRoot::result r ) { | |
return os << std::get<0>(r) << " or " << std::get<1>(r); | |
} | |
// Convert a tuple-taking function to a normal one. | |
// curry : ( (a,b...) -> c ) x a x b... -> c | |
template< class F, class ...X > | |
constexpr auto curry( const F& f, X&& ...x ) | |
-> decltype( f( std::forward_as_tuple(std::forward<X>(x)...) ) ) | |
{ | |
return f( std::forward_as_tuple(std::forward<X>(x)...) ); | |
} | |
// Pair Sum. | |
// psum : (int,int) -> int | |
unsigned int psum( std::tuple<int,int> p ) { | |
return head(p) + last(p); | |
} | |
int five = curry( psum, 3, 2 ); | |
template< template<size_t> class Fi = Get, size_t i, | |
class F, class ...T > | |
constexpr auto zipRow( const F& f, T&& ...t ) | |
-> decltype( f(Fi<i>()(std::forward<T>(t))...) ) | |
{ | |
return f( Fi<i>()( std::forward<T>(t) )... ); | |
} | |
template< template<size_t> class Fi = Get, size_t ...i, | |
class Ret, class F, class ...T > | |
constexpr auto zipIndexList( IndexList<i...>, | |
const Ret& r, const F& f, T&& ...t ) | |
-> decltype( r(zipRow<Fi,i>(f,std::forward<T>(t)...)...) ) | |
{ | |
return r( zipRow< Fi, i >( f, std::forward<T>(t)... )... ); | |
} | |
template< template<size_t> class Fi = Get, | |
class Ret, class F, class T, class ...U, | |
class _T = typename std::decay<T>::type, | |
class IL = typename IListFrom<_T>::type > | |
constexpr auto zipTupleTo( const Ret& r, const F& f, T&& t, U&& ...u ) | |
-> decltype( zipIndexList<Fi>(IL(),r,f,std::forward<T>(t),std::forward<U>(u)...) ) | |
{ | |
return zipIndexList<Fi>( IL(), r, f, std::forward<T>(t), std::forward<U>(u)... ); | |
} | |
template< template<size_t> class Fi = Get, | |
class F, class ...T > | |
constexpr auto zipTuple( const F& f, T&& ...t ) | |
-> decltype( zipTupleTo<Fi>(tuple,f,std::forward<T>(t)...) ) | |
{ | |
return zipTupleTo<Fi>( tuple, f, std::forward<T>(t)... ); | |
} | |
template< class X, class ...Y > | |
bool noneTrue( const X& x, const Y& ...rest ) { | |
return x ? false : noneTrue(rest...); | |
} | |
bool noneTrue() { return true; } | |
// We require these polymorphic function objects. | |
constexpr struct Inc { | |
template< class X > | |
constexpr X operator () ( X x ) { return ++x; } | |
} inc{}; | |
constexpr struct Eq { | |
template< class X > | |
constexpr bool operator () ( const X& a, const X& b ) | |
{ return a == b; } | |
} eq{}; | |
struct Or { | |
template< class X > | |
constexpr bool operator () ( const X& a, const X& b ) | |
{ return a || b; } | |
}; | |
// Wrapper to dereference arguments before applying. | |
// indirect : (a -> b) -> (*a -> b) | |
template< class F > struct Indirect { | |
F f = F(); | |
constexpr Indirect( F f ) : f(std::move(f)) { } | |
template< class ...It > | |
constexpr auto operator () ( It ...it ) | |
-> decltype( f(*it...) ) | |
{ | |
return f( *it... ); | |
} | |
}; | |
template< class F, class I = Indirect<F> > | |
constexpr I indirect( F f ) { | |
return I( std::move(f) ); | |
} | |
#include <vector> | |
#include <algorithm> | |
template< class F, class ...X, | |
class Result = typename std::result_of<F(X...)>::type, | |
class Ret = std::vector<Result> > | |
Ret transform( const F& f, const std::vector<X>& ...vs ) | |
{ | |
Ret r; | |
const auto ends = tuple( vs.end()... ); | |
// Iterate through each vector in parallel. | |
for( auto its = tuple( vs.begin()... ); | |
// This unrolls to: not (it0==end0 || it1==end1 || ...) | |
not foldl( Or(), zipTuple(eq,its,ends) ); | |
// Increment each iterator. | |
its = zipTuple( inc, its ) ) | |
{ | |
r.emplace_back ( | |
applyTuple( indirect(f), its ) | |
); | |
} | |
return r; | |
} | |
// product : {x,y} x {a,b} -> {{x,a},{x,b},{y,a},{y,b}} | |
constexpr struct Product { | |
// {...xi...} x {...aj...} -> {xi,aj} | |
template< size_t i, size_t j, class T, class U > | |
static constexpr auto zip( const T& t, const U& u ) | |
-> decltype( tuple(std::get<i>(t),std::get<j>(u)) ) | |
{ | |
return tuple( std::get<i>(t), std::get<j>(u) ); | |
} | |
// {...xi...} x {a0,a1,a2...} -> { {xi,a0}, {xi,a1}, ... } | |
template< size_t i, size_t ...j, class T, class U > | |
static constexpr auto withI( IndexList<j...>, const T& t, const U& u ) | |
-> decltype( tuple(zip<i,j>(t,u)...) ) | |
{ | |
return tuple( zip<i,j>(t,u)... ); | |
} | |
// {x...} x {a...} -> { {x,a}... } | |
template< size_t ...i, size_t ...j, class T, class U > | |
static constexpr auto withIndexes( IndexList<i...>, IndexList<j...> js, | |
const T& t, const U& u ) | |
-> decltype( std::tuple_cat(withI<i>(js,t,u)...) ) | |
{ | |
return std::tuple_cat( withI<i>(js,t,u)... ); | |
} | |
template< class T, class U, | |
class IL = typename IListFrom<T>::type, | |
class IL2 = typename IListFrom<U>::type > | |
constexpr auto operator () ( const T& t, const U& u ) | |
-> decltype( withIndexes(IL(),IL2(),t,u) ) | |
{ | |
return withIndexes( IL(), IL2(), t, u ); | |
} | |
} product{}; | |
template< class F > struct ApplyF { | |
F f = F(); | |
constexpr ApplyF( F f ) : f(std::move(f)) { } | |
template< class T > | |
constexpr auto operator () ( T&& t ) | |
-> decltype( applyTuple(f,std::forward<T>(t)) ) | |
{ | |
return applyTuple( f, std::forward<T>(t) ); | |
} | |
}; | |
template< class F > | |
constexpr ApplyF<F> applyF( F f ) { | |
return ApplyF<F>(std::move(f)); | |
} | |
constexpr struct MapTuple { | |
template< class F, class T, class U > | |
constexpr auto operator () ( const F& f, const T& t, const U& u ) | |
-> decltype( zipTuple(applyF(f),product(t,u)) ) | |
{ | |
return zipTuple( applyF(f), product(t,u) ); | |
} | |
} mapTuple{}; | |
constexpr struct Id { | |
template< class X > | |
constexpr X operator () ( X&& x ) { | |
return std::forward<X>(x); | |
} | |
template< class F, class X, class ...Y > | |
constexpr auto operator () ( const F& f, X&& x, Y&& ...y ) | |
-> typename std::result_of< F(X,Y...) >::type | |
{ | |
return f( std::forward<X>(x), std::forward<Y>(y)... ); | |
} | |
} id{}; | |
int main() { | |
auto sums = mapTuple( std::plus<int>(), tuple(1,2,3), tuple(7,8,9) ); | |
std::cout << "map (+) (1,2,3) (7,8,9) = "; | |
forEach( printItem, sums ); | |
std::cout << std::endl; | |
auto zipped = zipTupleTo( tuple, std::plus<int>(), tuple(1,10), | |
tuple(2,20) ); | |
std::cout << " 1 + 2 = " << std::get<0>(zipped) << std::endl; | |
std::cout << "10 + 20 = " << std::get<1>(zipped) << std::endl; | |
std::vector<int> v = {1,10,100}, | |
w = {2,20,200}, | |
x = {3,30,300}; | |
auto vw = transform ( | |
[](int x, int y, int z){ return x+y+z; }, | |
v, w, x | |
); | |
std::cout << " 1 + 2 + 3 = " << vw[0] << std::endl; | |
std::cout << " 10 + 20 + 30 = " << vw[1] << std::endl; | |
std::cout << "100 + 200 + 300 = " << vw[2] << std::endl; | |
auto ab = std::make_tuple( 1, 3 ); | |
auto qroot_ab = [&] ( float c ) { | |
return applyTuple( qroot, pushBack(ab,c) ); | |
}; | |
std::cout << "qroot(1,3,-4) = " << qroot_ab(-4) << std::endl; | |
std::cout << "qroot(1,3,-5) = " << qroot_ab(-5) << std::endl; | |
auto bc = std::make_tuple( 3, -4 ); | |
auto qroot_bc = [&] ( float a ) { | |
return applyTuple( qroot, pushFront(bc,a) ); | |
}; | |
std::cout << "qroot(1,3,-4) = " << qroot_bc(1) << std::endl; | |
std::cout << "qroot(1,3,-5) = " << qroot_bc(2) << std::endl; | |
std::cout << "ten = " << ten << std::endl; // foldl example. | |
std::cout << "five = " << five << std::endl; // Curry example. | |
std::cout << "third_arg(1,2,3,4) = " << third_arg(1,2,3,4) << std::endl; | |
std::cout << "2 + 4 = " | |
<< applyTuple( std::plus<int>(), std::make_tuple(2,4) ) | |
<< std::endl; | |
constexpr auto t = std::make_tuple( 1, 'a', "str" ); | |
std::cout << "t = "; | |
forEach( printItem, t ); | |
std::cout << std::endl; | |
std::cout << "head = " << head(t) << std::endl; | |
std::cout << "last = " << last(t) << std::endl; | |
std::cout << "reverse = "; | |
forEach( printItem, reverse(t) ); | |
std::cout << std::endl; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment