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)