Monday, December 10, 2012

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

4 comments:

  1. It will not compile:

    constexpr struct PushFront {
    template< class ...X, class Y >
    constexpr auto operator () (std::tuple t, Y y ) -> std::tuple< Y, X... >
    {
    return std::tuple_cat(tuple(std::move(y)), std::move(t) );
    }
    } pushFront{};


    The reason is : the variadic template parameter must be the last, in the primary template.

    Correct me if I'm wrong. :-)

    ReplyDelete
    Replies
    1. Posts are in script environments, so I think that line should read

      constexpr auto operator () (std::tuple< X... > t, Y y ) -> std::tuple< Y, X... >

      which is what I have in the article.

      This compiles because "class ...X" is deduced by pattern matching the tuple itself. Similarly, "class Y" is deduced by matching the "Y y" parameter. The compiler can easily tell the difference.

      Delete
  2. Thanks for this article - but couldn't get past the line RGet - Tried various combinations of the code - but couldn't get that to work. Would you please clarify that portion on how to define RGet Struct?

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

    Thanks
    ------------------------

    ReplyDelete
  3. Never mind about RGet - Noticed how you have defined it in the source code link !!

    ReplyDelete

Please feel free to post any comments, concerns, questions, thoughts and ideas. I am perhaps more interested in what you have to say than you are in what I do.