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

std::move and lambda? It's just partial application!

So, "Learn how to capture by move" was posted on isocpp.org and then this morning, "Another Alternative to lambda move capture" was on reddit. These are both impressive solutions and I look forward to seeing what other creative answers the C++ community will come up with. I also want to go over how this problem can be solved with partial application.

First, here's the definition.

template< class F, class X >
struct Part {
    F f;
    X x;

    template< class _F, class _X >
    constexpr Part( _F&& f, _X&& x )
        : f(forward<_F>(f)), x(forward<_X>(x))
    {
    }

    template< class ... Xs >
    auto operator () ( Xs&& ...xs ) 
        -> decltype( f(x,declval<Xs>()...) )
    {
        return f( x, forward<Xs>(xs)... );
    }
};

template< class F, class X >
constexpr Part<F,X> closet( F f, X x ) {
    return Part<F,X>( std::move(f), std::move(x) );
}

So, there's this thing called the upward funarg problem. Let's say we wrote a function like this:

std::function<std::vector<int>()> bad_originate() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };
    return [&]{ return v; };
}
 
auto bad = bad_originate();
bad(); // Runtime error!

This fails because the reference to v becomes invalidated when it goes out of scope. We could copy v into the lambda, but our goal is a move.

So can we fix this with partial application? Let's add a bit to the example by including a function to partially apply.

std::vector<int> add_all( std::vector<int>& v, int x ) {
    // Arbitrarily move v.
    auto w = std::move(v);

    std::transform( w.begin(), w.end(), w.begin(),
                    closet(std::plus<int>(),x) );

    return w;
}

using Origin = Part<decltype(add_all)*,std::vector<int>>;
Origin originate() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };
    return closet( add_all, std::move(v) );
}

And it ain't hard at all.

Origin f = originate();
print_vec( "original : ", f.x );
print_vec( "added 10 : ", f(10) );
print_vec( "original : ", f.x );

will output

    original :  = 1 2 3 4 5
    added 10 :  = 11 12 13 14 15
    original :  =

Maybe one would prefer that add_all take its argument by value; now, composition becomes useful.

template< class F, class G > struct Composition {
    F f = F();
    G g = G();

    Composition() { }
    Composition( F f, G g) 
        : f(move(f)), g(move(g)) { }

    template< class X, class ...Y >
    auto operator () ( X&& x, Y&& ...y ) 
        -> decltype( f(g(declval<X>()), declval<Y>()...) )
    {
        return f( g( forward<X>(x) ), forward<Y>(y)... );
    }
};

template< class F, class G > 
Composition<F,G> comp( F f, G g ) {
    return Composition<F,G>( std::move(f), std::move(g) );
}

constexpr struct Mover {
    template< class X >
    X&& operator () ( X& x ) const {
        return std::move(x);
    }
} mover{}; 

std::vector<int> add_all2( std::vector<int> w, int x ) {
    std::transform( w.begin(), w.end(), w.begin(),
                    closet(std::plus<int>(),x) );

    return w;
}
 
using MoveAddAll = decltype( comp(add_all2,mover) );
using Origin2 = Part< MoveAddAll, std::vector<int> >;
Origin2 originate2() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };
    return Origin2( comp(add_all2,mover), std::move(v) );
}

and

Origin2 g = originate2();
print_vec( "original : ", g.x );
print_vec( "added 10 : ", g(10) );
print_vec( "original : ", g.x );

will output the same as above.

The code to this mini-article can be found here: https://gist.github.com/4182570

Generic Function Objects, or Generalizing Associativity, Transitivity, and such abstractions over functions and types.

So, I posted "Rethinking std::binary_function", which was this epiphany that instead of writing all these variadic operator types, I could actually define a base class and inherit its operator overloads. That lead to another realization: https://gist.github.com/4049946. What I am about to elaborate on below feels like a discovery rather than an invention. It's also only a few days old. I normally try to present something much more polished, but this is exciting enough to myself that I want to share it sooner rather than later.

Starting from the top.

In "Rethinking std::binary_function", I thought that all binary functions might benefit from being chained, but actually, not all can be. We can write add(1,2,3) and think of it as (1+2)+3 = 6, but what about <, or less? less(1,2,3) would be equivalent to (true < 3), which is only incidentally correct. And so chaining might not be good for all binary functions, but we can at least say that partially applying the front and back might be useful.

template< class F, class X >
struct Part {
    F f;
    X x;

    template< class _F, class _X >
    constexpr Part( _F&& f, _X&& x )
        : f(forward<_F>(f)), x(forward<_X>(x))
    {
    }

    template< class ... Xs >
    constexpr auto operator () ( Xs&& ...xs )
        -> decltype( f(x,declval<Xs>()...) )
    {
        return f( x, forward<Xs>(xs)... );
    }
};

template< class F, class X > struct RPart {
    F f;
    X x;

    template< class _F, class _X >
    constexpr RPart( _F&& f, _X&& x ) 
        : f( forward<_F>(f) ), x( forward<_X>(x) ) { }

    template< class ...Y >
    constexpr decltype( f(declval<Y>()..., x) )
    operator() ( Y&& ...y ) {
        return f( forward<Y>(y)..., x );
    }
};

template< class F > struct Binary {
    template< class X >
    constexpr Part<F,X> operator () ( X x ) {
        return Part<F,X>( F(), move(x) );
    }

    template< class X >
    constexpr RPart<F,X> with( X x ) {
        return RPart<F,X>( F(), move(x) );
    }
};

We might define a subtraction type like so:

constexpr struct Sub : public Binary<Sub> {
    using Binary<Sub>::operator();

    template< class X, class Y >
    constexpr auto operator () ( X&& x, Y&& y ) 
        -> decltype( std::declval<X>() - std::declval<Y>() )
    {
        return std::forward<X>(x) - std::forward<Y>(y);
    }
} sub{}; 

sub is a function object of type Sub and inherits the partial- and reverse partial-application from Binary<Sub>.

    constepxr auto twoMinus = sub(2); // Calls Binary<Sub>::operator(int); returns Part<Sub,int>.
    constexptr int zero = twoMinus(2); 
  
    constexpr auto minusTwo = sub.with(2); // Calls Binary<Sub>::with(int); returns RPart<Sub,int>;
    constexpr int two = minusTwo(4);

    constexpr int one = sub(2,1); // Calls Sub::operator(int,int).

Associativity and Transitivity.

 Addition is an associative operation, by which I mean

    x + y + z = (x+y) + z

In particular, this demonstrates left (left-to-right) associativity. We can apply this same principle of associativity to functions!

template< class F > struct Chainable : Binary<F> {
    using Binary<F>::operator();

    template< class X, class Y >
    using R = typename std::result_of< F(X,Y) >::type;

    // Three arguments: unroll.
    template< class X, class Y, class Z >
    constexpr auto operator () ( X&& x, Y&& y, Z&& z )
        -> R< R<X,Y>, Z >
    {
        return F()(
            F()( std::forward<X>(x), std::forward<Y>(y) ),
            std::forward<Z>(z)
        );
    }

    template< class X, class Y, class ...Z >
    using Unroll = typename std::result_of <
        Chainable<F>( typename std::result_of<F(X,Y)>, Z... )
    >::type;

    // Any more? recurse.
    template< class X, class Y, class Z, class H, class ...J >
    constexpr auto operator () ( X&& x, Y&& y, Z&& z, H&& h, J&& ...j )
        -> Unroll<X,Y,Z,H,J...>
    {
        // Notice how (*this) always gets applied at LEAST three arguments.
        return (*this)(
            F()( std::forward<X>(x), std::forward<Y>(y) ),
            std::forward<Z>(z), std::forward<H>(h), std::forward<J>(j)...
        );
    }
};

One might define an addition type like this:

constexpr struct Add : public Chainable<Add> {
    using Chainable<Add>::operator();

    template< class X, class Y >
    constexpr auto operator () ( X&& x, Y&& y ) 
        -> decltype( std::declval<X>() + std::declval<Y>() )
    {
        return std::forward<X>(x) + std::forward<Y>(y);
    }
} add{}; 

Add inherits Binary<Add>'s ::operator() and ::with, and Chainable<Add>'s overloads as well. The three argument overload in Chainable will return add(add(x,y),z). If given four or more arguments, it will call add on the first two, and call itself on the rest, being at least three. The base case for Chainable will always be the three-argument overload.

    consexpr auto plusTwo = add(2); // Calls Binary<Add>::operator(int); returns Part<Add,int>.
    constexpr int fifteen = add(1,2,3,4,5) // Calls Chainable<Add>::operator(int,int,int,int...).

Operations like less, as mentioned above, are not associative. They are, however, transitive, by which I mean:

    x < y < z = (x<y) and (y<z)

In writing a class for transitivity, we can have it just apply each argument to the one right of it, but we need this and to glue the results together. My Transitive class will require both defining the operation (<) and the function that folds the results together (and).

template< class F, class Fold > struct Transitive : Binary<F> {
    using Binary<F>::operator();

    template< class X, class Y, class Z >
    constexpr auto operator () ( X&& x, Y&& y, Z&& z )
        -> typename std::result_of<F(X,Y)>::type
    {
        return Fold() (
            F()( forward<X>(x), forward<Y>(y) ),
            F()( forward<Y>(y), forward<Z>(z) )
        );
    }

    template< class X, class Y, class Z, class A, class ...B >
    constexpr auto operator () ( X&& x, Y&& y, Z&& z, A&& a, B&& ...b )
        -> typename std::result_of<F(X,Y)>::type
    {
        return Fold() ( F()( forward<X>(x), forward<Y>(y) ),
                        F()( forward<Y>(y), forward<Z>(z),
                             forward<A>(a), forward<B>(b)... ) );
    }
}; 

We can define less like so:

struct And : Chainable<And> {
    using Chainable<And>::operator();

    template< class X, class Y >
    constexpr auto operator () ( X&& x, Y&& y )
        -> decltype( declval<X>() && declval<Y>() )
    {
        return forward<X>(x) && forward<Y>(y);
    }
};

constexpr struct Less : Transitive<Less,And> {
    using Transitive<Less,And>::operator();

    template< class X, class Y >
    constexpr bool operator() ( X&& x, Y&& y ) {
        return forward<X>(x) < forward<Y>(y);
    }
} less{};

Now, writing less(1,2,3) would be equivalent to writing 1<2 and 2<3. less.with(3) would be a function returning whether x is "less than three".

Here's where things get really interesting. What if I want to use these properties of associativity and transitivity to construct types?

From the top, again.

The biggest problem is that types are not functions. Sure, we can write std::pair<X,Y>(x,y) and you might say "Look! A constructor! It's a function!", but we don't like needing to specify our types, so we prefer std::make_pair(x,y). Even though we have this type with a construction function, it's not as useful as a general function. This is a surprisingly common pattern. We make a type, but we want the result's type to be argument dependent, so we make a function that constructs the type. And we do this for every type.

There's make_pair, make_tuple, make_shared, make_unique (eventually), and many, many others. Instead of writing any of these, let's abstract the pattern away using our OOP principles!

template< template<class...> class T > struct ConstructT {
    template< class ...X, class R = T< typename std::decay<X>::type... > >
    constexpr R operator () ( X&& ...x ) {
        return R( forward<X>(x)... );
    }
};

std::decay is a handy type that removes any reference or const until we get the type itself.

    typename std::decay<const int>::type = int
    typename std::decay<int&&>::type = int
    typename std::decay<int>::type = int;

When we call an instance of ConstructT, we may pass in references, r-values, or const values, but the return, R, will hold values.

Now, we can write

    constexpr auto make_pair = ConstructT<std::pair>();
    std::pair<int,int> p = make_pair(1,2);

    constexpr auto make_tuple = ConstructT<std::tuple>();

Each of what used to be an entire function, a paragraph, is now a line. Now, for associativity!

template< template<class...> class T >
struct ConstructChainable : Chainable<ConstructT<T>> {
    using Self = ConstructChainable<T>;
    using Chainable<ConstructT<T>>::operator();

    template< class X >
    using D = typename std::decay<X>::type;
    template< class X, class Y, class R = T< D<X>, D<Y> > >
    constexpr R operator () ( X&& x, Y&& y ) {
        return R( forward<X>(x), forward<Y>(y) );
    }
};

ConstructChainable inherits from Chainable which inherits from Binary, so now we can rewrite the above:

    constexpr auto make_pair = ConstructChainable<std::pair>();
    constexpr auto pairWith = make_pair.with(y); // Calls Binary<ConstructT<std::pair>>::operator(int).
    constexpr auto pairPair = make_pair(1,2,3); // Returns an std::pair< std::pair<int,int>, int >.

All this without having ever explicitly defining make_pair!

Remember the definition of Part from above?

    constexpr auto closet   = ConstructChainable<Part>();

This one line is very powerful. Let me demonstrate by showing all the code it replaces!

// An extra, variadic definition of the class.
template< class F, class X1, class ...Xs >
struct Part< F, X1, Xs... > 
    : public Part< Part<F,X1>, Xs... >
{
    template< class _F, class _X1, class ..._Xs >
    constexpr Part( _F&& f, _X1&& x1, _Xs&& ...xs )
        : Part< Part<F,X1>, Xs... > (
            Part<F,X1>( forward<_F>(f), forward<_X1>(x1) ),
            forward<_Xs>(xs)...
        )
    {
    }
};

template< class F, class ...X >
constexpr Part<F,X...> closet( F f, X ...x ) {
    return Part<F,X...>( move(f), move(x)... );
}

So what does ConstructChainable do? It makes mole hills out of mountains! What's more; it does so optimally. It perfect forwards the arguments all the way to the constructor, whereas I often would write moving functions in order to simplify type deduction.

So, one might have noticed that closet creates a Part, but it's also derived from Binary, so we can write things like

    constexpr auto cc = closet(closet);

and all sorts of unexpected things!

Conclusion.

I guess one way to describe this phenomenon is perhaps as an update to the factory pattern. I'm tempted to call it a type constructor, but I'm not sure that's technically correct.

This post has been more off-the-cuff than I normally try to be, and I haven't prepared any test source to ease in the process of learning. Still, I hope you find this as fascinating as I do.

Gist: https://gist.github.com/4055136

I use this trick extensively in my library, Pure. (Functional.h)

Rethinking std::binary_function.

Update: I have expanded on this concept: http://yapb-soc.blogspot.com/2012/11/generic-function-objects-or.html

Before the word "lambda" could be found in almost any C++ coder's vocabulary, the standardizing committee had stuffed <functional> with a bunch of operator functions (plus, minus, equal_to, etc), and they were very helpful. But everything else from C++03 in that file became deprecated in C++11. Things like bind1st, pointer_to_unary_function, mem_fun (not mem_fn), etc.. Even std::unary_function and std::binary_function are now deprecated.

They used to be helpful because they defined typedefs like result_type and argument_type. When you wrote a function object, you could inherit from unary_ or binary_function and get these typedefs for free. Now that we have std::result_of and decltype to do the same thing so these aren't helpful any more; but we can also do more with functions than in the past. We can partially apply them without knowing what arguments or return types the functions will give until we call them. We can also create variadic versions. We can combine, compose, and build them from other functions.

The core idea of having your function objects inherit from a base type that offers extended functionality isn't a bad idea.

Rethinking std::binary_function.

What can we do with a binary function, f(x,y)? We can partially apply them (g(y) = f(x,y)) or chain them arbitrarily (g(x,y,z) = f(f(x,y),z)). So let's do that! To implement it, I'll use the curiously recurring template pattern.

template< class Derr > struct Binary {
    // One argument: curry.
    template< class X >
    constexpr auto operator () ( X x ) -> PartialApplication<Derr,X> {
        return closet( Derr(), std::move(x) );
    }

    template< class X, class Y >
    using Result = typename std::result_of< Derr(X,Y) >::type;

    // Three arguments: unroll.
    template< class X, class Y, class Z >
    constexpr auto operator () ( X&& x, Y&& y, Z&& z ) 
        -> Result<Result<X,Y>,Z> 
    {
        return Derr()( 
            Derr()( std::forward<X>(x), std::forward<Y>(y) ), 
            std::forward<Z>(z)
        );
    }

    template< class X, class Y, class ...Z >
    using Unroll = typename std::result_of <
        Binary<Derr>( Result<X,Y>, Z... )
    >::type;

    // Any more? recurse.
    template< class X, class Y, class Z, class H, class ...J >
    constexpr auto operator () ( X&& x, Y&& y, Z&& z, H&& h, J&& ...j ) 
        -> Unroll<X,Y,Z,H,J...> 
    {
        // Notice how (*this) always gets applied at LEAST three arguments.
        return (*this)( 
            Derr()( std::forward<X>(x), std::forward<Y>(y) ), 
            std::forward<Z>(z), std::forward<H>(h), std::forward<J>(j)... 
        );
    }
};

constexpr struct Add : public Binary<Add> {
    using Binary::operator();

    template< class X, class Y >
    constexpr auto operator () ( X&& x, Y&& y ) 
        -> decltype( std::declval<X>() + std::declval<Y>() )
    {
        return std::forward<X>(x) + std::forward<Y>(y);
    }
} add{};

Note that Add must include the line using Binary::operator() for it to inherit Binary's overloads.

Now, we can create a partially applied addition

    constexpr auto plusTwo = add(2);
    constexpr auto five = plusTwo(3);

And we can string arbitrarily long additions in one function.

    constexpr int sum = add(1,2,3,4,5); 
    std::string helloWorld = add( std::string("Hello"), ' ', "world!" );

Note how for helloWorld's add, the first argument is a string, the second a char, the third a char*. The most sensible way to do this with the standard plus would be to instantiate it as an std::plus<std::string>, which would require converting the char and char* to a string before calling. Luckily, in the future, we may be able to use the syntax std::plus<> (N3421), and its behaviour would allow for mixed-type arguments, but not currying or chaining.

Moving on, we can define Subtract, Multiply, and all of the other binary <functional> types in this way. It might not be useful for all functions. For example, if you wrote a function, find(x,xs), taking a value and a sequence and returning an iterator, then it might not be helpful to chain. find(x,xs,ys) would check ys for the iterator of the item found in xs, which is probably not what we want. But find(x) would return a function that looks for x in any container and that could easily be desirable behaviour.

A note on efficiency.

I am a big fan of constexpr. There is no optimization greater than skipping the whole computation and inlining the result. So when I checked out the assembly generated for the line,

    std::cout << add(1,2,3,4,5) << std::endl;

imagine my surprise when I found out GCC had neither computed the result at compile time nor inlined the call to add! However, when I made the following change:

    constexpr int x = add(1,2,3,4,5);
    std::cout << x << std::endl;

it basically converted it to

    std::cout << 15 << std::endl;

This is very exciting technology, but perhaps too new to work perfectly.  I expect GCC, and compilers in general, to improve over time, but for the moment, they can be fickle. Subtle changes in the code can cause drastic changes in the assembly.

Could we go further?

There are other operations that might make sense on binary function; their arguments can be swapped (or flipped), one could apply only the second argument, and we could find interesting ways of composing them. As always, the limit is our imagination. I think this is a good start. Features that extend beyond overloading () require the calling code to "know" that its function object is a Binary, and so it's less generally useful. Why write a member named Binary::flip() when one could write a function called flip that worked on function pointers, too?

Are there operations on unary functions that might make sense? What about ternary functions?

The lesson here isn't so much that one thing should be a feature over another, but when defining function objects, do not forget about using inheritance to limit code duplication!


The source: https://gist.github.com/4024658
(Oops, I forgot to post it this time!)