Zipping and Mapping tuples.

Previously, I discussed some basic things that can be done with tuples. I showed how a tuple can be applied to a function, however I did not show how member-wise transformations could be done.

The code of this article builds on the code of the prior.

Zipping.

If we have several tuples, what if we want to apply a function to the nth element of each one?

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) )... );
}

Not hard at all! It basically squishes that row (thinking of t as a column and ti... as a row), using f, into one value. Now, let's say we want to zip together t... into one tuple.

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)... );
}

int main() {
    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;
}

In zipIndexList, r represents the function defining how the output is returned. tuple (gist), from the previous article, is just a function object form of std::make_tuple that can be passed to higher order functions. By supplying it as our r, we're saying "just make it a tuple again."

Since most often, we want to zip back into a tuple, it makes sense to define zipTuple like so:

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)... );
}

zipTuple is to tuples what std::transform is to sequences. The drawback of std::transform is that it only allows for a unary transformation or binary. Let's write a version that accepts any number of arguments.

// 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;
}

int main() {
    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;
}

Note: foldl (gist).

Mapping.

Suppose we want to know the results of adding every combination of {1,2,3} with {9,8,7}. We could write a function that cross-applied every variable from each tuple, but slightly more generally, we can start by taking the Cartesian product.

// 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{};

We can now define a map operation to apply the 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{};

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;
}

This prints out:

map (+) (1,2,3) (7,8,9) = 8 9 10 9 10 11 10 11 12 

Zipping applies elements across from each other. Mapping applies everything to everything. (Note: a unary definition of map would be equivalent to a unary definition of zip.)

Tuples as function environments.

This might seem a little off topic, but Haskell has this neat function, id. It works like this:

    id x = x

Simple, right?

    (id f) x y = f x y = id f x y

 id has this neat property that if applied multiple arguments, it applies the tail arguments to the first. This is an artifact of Haskell's curried notation, but we can emulate this behaviour:

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{};
 

And now tuples take on a new role: Contained function environments. Consider:

    applyTuple( id, tuple(std::plus<int>(),1,2) );

What does this output? How about

    mapTuple( id, tuple(inc,dec), tuple(5,9) );

    auto pm = tuple(std::plus<int>(),std::minus<int>());
    zipTuple( id, pm, tuple(10,5), tuple(10,5) );

 Or:

    mapTuple( id, pm, tuple(1,2), tuple(3,4);

I leave implementing the three-tuple version of mapTuple as an exercise, but here's a hint: cross( cross({f},{x}), {y}) = {{{f,x},{y}}}, but you need to take it from that to {{f,x,y}}. (Another good exercise might be to write zipTuple in terms of transposition (wiki).)

Conclusions.

This flushes out some basic applications of tuples to functions. applyTuple unpacks a tuple and applies it to a function. foldl and foldr let one apply binary functions to nary tuples, or even singletons (maths concept, not design pattern). zipTuple transforms multiples tuples by a functions, member-wise. mapTuple performs a function for every combination of arguments.

Tuples have unusual mathematical properties compared to other data structures due to the profundity of what they generalize. They can help us shorthand functions to operate in parallel (zip), be passed around as partial or complete function environments, control variadic template parameters, and much, much more that I have either not discussed or yet realized.

One use I haven't discussed, for example, is as a relation, but for an example of this use of tuples, look no further than std::map.

I hope this post has been interesting. Happy coding!


Source for this article: https://gist.github.com/4268029

Fun with tuples.

std::tuple is an odd-but-fun part of the new standard. A lot can be done with them. The members of a tuple can be applied to functions, both in groups and individually. The tuple itself can be treated as a function environment. They can be reorganized, appended, and truncated. The list goes on.

The thing is, what can tuples be used for? Any POD struct or class can be a tuple instead, although this may or may not be desirable. Still, we can write generic algorithms with tuples, whereas we cannot with structs. If we wrote a function that printed any tuple, then any POD we turned into a tuple would suddenly become printable.

Indexing.

Tuples are indexed, which makes accessing them odd.

// A normal struct
struct Vec { int x, y; };
Vec a = { 1, 2 };
a.x = 2; // Normal access.

std::tuple<int,int> b(1,2);
std::get<0>(b) = 2; // Weird access. 

One might think "I'll just write an accessor function!", and that certainly would work. It becomes easier if std::get is made into a function object.

// 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) );
    }
};

constexpr auto getx = Get<0>();
constexpr auto gety = Get<1>();

getx(b) = 2; // Less weird.

I define Elem because using std::tuple_element returns what the tuple actually holds. std::get<0>(b) would return an int&, but tuple_element<0,decltype(b)>::type would be int.

One might find it useful to index the tuple backwards, so let's define a function, rget.

 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) );
}

Now we can also define functions to get the first and last elements of any tuple.

constexpr auto head = Get<0>();
constexpr auto last = RGet<0>(); // RGet is defined similarly to Get.

int main() {
    constexpr auto t = std::make_tuple( 1, 'a', "str" );
    std::cout << "head = " << head(t) << std::endl; // prints 1
    std::cout << "last = " << last(t) << std::endl; // prints str
}

Just for fun, let's also write a function that, if the index is too high, wraps around to the begining.

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) );
} 

Now, let's say we want to call a function for every member of a tuple. We need a way of indexing it and applying some function for each index. It starts with the definition of a type to "hold" a list of indexes.

template< size_t ...i > struct IndexList {};

Now, if given a tuple of size 3, we want an IndexList<0,1,2> to represent each index. There are many solutions for how to do this, but they all have in common being obtuse or difficult to understand. The following solution is designed first and foremost to be obvious and intuitive.

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;
};

Now, a function that applies each index, and one that prints a tuple's elements for testing.

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) );
    
    // Recurs, removing the first index.
    forEachIndex( IndexList<j...>(), f, t ); 
}

template< class F, class T >
void forEachIndex( IndexList<>, const F& f, const T& t ) {
    // No more indexes.
}

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{};

int main() {
    constexpr auto t = std::make_tuple( 1, "and", 2 );
    std::cout << "t = "; 
    forEach( printItem, t ); // Prints "1 and 2"
    std::cout << std::endl;
}

Applying a tuple to a function.

This is probably one of the most pondered questions about tuples. "How do I apply one to a function?" This is easy since we already have IndexList defined.

template< size_t ...i, class F, class T >
constexpr auto applyIndexList( IndexList<i...>, F f, T&& t )
    -> typename std::result_of< F( Elem<i,T>... ) >::type
{
    return f( std::get<i>(std::forward<T>(t))... );
}

template< 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(IL(),f,std::forward<T>(t)) )
{
    return applyIndexList( IL(), f, std::forward<T>(t) );
}

// Functional programmers may recognize this as cons.
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{};

// 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{};

auto ten = foldl( std::plus<int>(), std::make_tuple(1,2,3,4) );

We can call applyIndexList with different index lists to get interesting results.

// 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{}; // function tuple that construct std::tuples.

// 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) )
{
     // Construct a new tuple from the initial indexes.
     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 );
} 

Remember Get and RGet from above? They're templated function objects based on an index. We can write a more generic applyIndexList that allows specifying such a function and without losing the default behaviour.

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) );
}

// Reconstruct t in reverse.
template< class T >
constexpr auto reverse( const T& t ) 
    -> decltype( applyTuple<RGet>(tuple,t) )
{
    return applyTuple< RGet >( tuple, t );
}

// 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{};

This leaves us with two ways of transforming tuples: modifying the index list and defining an alternative get function. foldr and foldl give us a way to fold a tuple into one value.

Tuples and functions.

Perhaps we have a function that takes a tuple, but its arguments are not tuples. Haskell defined a function, curry, to transform the function from a pair-taking one to a two-argument function. Haskell does not have the same expressiveness with variadic types, so they can't write this more general C++ version.

// 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);
}

auto five = curry( psum, 3, 2 );

Haskell also defines uncurry, which is the same as applyTuple. The most important distinction between Haskell's curry and uncurry and this is that Haskell's curry is a unary higher order function, whereas this is binary. However, the two are the same if one considers the unary version a partial application of the binary one.

Tuples can be used as a sort of partial application on their own. One might store some values in a tuple, and add more arguments later to be applied to some function. For a somewhat contrived example, consider the following:

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{};

#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);
}

int main() {
    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;
}

One persuasive use-case of tuples is being able to freely manipulate variadic parameters.

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)...) );
}

Variadic parameters can be forwarded into a tuple, meaning anything we can do with tuples, we can do with variadic parameters. Arguments can be compacted into tuples, modified, reordered, and re-expanded into functions. One annoyance with the ... is that it eats up everything to the right. The following is ill-formed.

template< class ...X, class F >
constexpr auto backwards( X&& ...x, const F& f )
    -> typename std::result_of< F(X...) >::type
{
    return f( std::forward<X>(x)... )
}

I leave the solution as an exercise for the reader.

Conclusions.

This article is introductory, at best. I must admit I have much less practice with them than other C++11 features, but this seems to be true of GCC, too! Attempting to compile the following will cause an internal error since at least 4.7.

#include <tuple>

template< class X > struct Hold {
 X x;
 constexpr Hold( X x ) : x(std::move(x)) { }
};

constexpr auto a = Hold<int>( 1 ); //ok
auto b = Hold<std::tuple<char>>( std::tuple<char>('c') ); // not
constexpr auto c = Hold<std::tuple<char>>( std::tuple<char>('c') ); // not

int main() {} 

I believe it's quite possible that whole programs could be written with tuples and basic data types, whether or not it should be preferred. We could look at them as a general utility class, but I think it would be appropriate to see them as lightweight, generalized, composable, structs. I plan on writing a follow-up to cover applying multiple tuples, transforming tuples by functions, and a few other things. If anyone has any interesting use-cases or neat tricks for tuples, I'd love to hear about it in the comments.  

The next article covers element-wise application, applying multiple tuples, and more: "Zipping and Mapping Tuples".


Source code: https://gist.github.com/4256092  
Tuple reference: http://en.cppreference.com/w/cpp/utility/tuple