5. Direct Functoids

Table of Contents

5.1. Issues with representing higher-order polymorphic functions
5.2. The past and the future
5.3. Defining a direct functoid

Direct functoids enable the creation of functions which are simultaneously higher-order and polymorphic. Consider the map() function described in the previous section: map() takes two arguments—a function and a list—and applies the function to every element of the list. In Haskell we would describe the type signature of map like this:

   map :: [a] -> (a -> b) -> [b]

The letters a and b are placeholder type variables (like the T in template <class T>). The signature says that map() takes two arguments—a list of a objects and a function from a objects to b objects—and returns a list of b objects. Thus map() is an example of a higher-order (it takes a function as an argument) polymorphic (it can be instantiated for all types a and b) function.

5.1. Issues with representing higher-order polymorphic functions

Representing such a function in C++ is non-trivial. Suppose we try to implement map ourselves, and we call our version mymap. There are two key issues. The first issue is this: if we represent mymap as a template function:

   template <class F, class T>
   ... mymap( F some_func, list<T> some_list ) { ... }

then the symbol mymap does not name a C++ object. This means we cannot pass mymap to another higher-order function:

   some_other_func( mymap, ... );  // illegal if mymap is template function

This problem is relatively straightforward to surmount using a function object:

   struct mymap_type {
      template <class F, class T>
      ... operator()( F some_func, list<T> some_list ) const { ... }
   } mymap;

Now mymap is an instance of struct mymap_type, which has a template member operator(). As a result, we can call mymap using the same syntax as before, but now the symbol mymap does name a C++ object, and thus it can itself be passed as a parameter.

The second issue has to do with the return type. What should the return type of mymap be? It should be a list<U>, where U is the result type of applying an F function to a T object. Since the C++ language lacks a typeof operator, we need to represent the return type information ourselves. By convention, in FC++, we represent the return type of a function using a nested template member struct named sig:

   struct mymap_type {
      template <class F, class L>
      struct sig {
         typedef list< typename F::template sig<
                           typename L::value_type >::result_type >
            result_type;
      };
      ... 
   } mymap;

More generally, the expression

   typename F::template sig<X>::result_type
   // F::sig<X>::result_type   without the "noise" words

represents the result type when a function of type F is applied to an argument of type X.

As a result, we could define mymap as

   struct mymap_type {
      template <class F, class L>
      struct sig {
         typedef list< typename F::template sig<
                           typename L::value_type >::result_type >
            result_type;
      };
      template <class F, class T>
      typename sig< F, list<T> >::result_type
      operator()( F some_func, list<T> some_list ) const { ... }
   } mymap;

This is our first example of a functoid. A functoid is an instance of a struct which contains a (possibly templated) operator() method, as well as a nested template member struct named sig which works as a return-type computer.

To simplify naming return types, we have the RT helper. Rather than say

   typename F::template sig<X,Y>::result_type

we just say

   typename RT<F,X,Y>::result_type

That is, RT<F,A1,...An> computes the result type of a function of type F being applied to arguments with type Ai.

5.2. The past and the future

FC++ was the first C++ library to use this scheme as a general mechanism for representing higher-order polymorphic functions. Since then, a number of other libraries have arisen that all use variations of the same trick to enable return-type deduction.

A relatively new proposal standardizes the return-type deduction methods. It uses conventions and syntax different from FC++. FC++ "full functoids" (Section 7) ensure that functoids are forward-compatible with the new standard. At the same time, the RT type computer makes FC++ code backward compatible with functoids using the extant sig structures. As a result, FC++ interoperates with other libraries like boost::bind.

5.3. Defining a direct functoid

Now, with all of the explanation out of the way, we can finally show the definition of the mymap functoid (Figure 1). This is an example of a polymorphic direct functoid. It has a sig structure, which is a template over the parameter types which computes the result type, as well as a templated operator() function, which uses the sig to name its own result type. Note that, rather than defining the result_type typedef directly, we can inherit it from the fun_type class.

Figure 1. The mymap functoid

   struct mymap_type {
      template <class F, class L> struct sig : public fun_type<
         list<typename RT<F,typename L::value_type>::result_type> > {};
      template <class F, class T> 
      typename sig<F, list<T> >::result_type 
      operator()( const F& f, const list<T>& l ) const {
         // code to actually implement mymap() function elided
      }
   } mymap;

The definition of mymap given here is what we call a basic direct functoid. In Section 7, we will show how to promote mymap into a full direct functoid, which adds useful capabilities.

Finally, it should be noted that monomorphic direct functoids can be defined without explicitly coding a sig structure, by inheriting from the c_fun_type template class. For example, here is the definition of a function that increments an integer:

   struct inc_type : public c_fun_type<int,int> {
      int operator()( int x ) const {
         return x+1;
      }
   } inc;

The c_fun_type class defines a monomorphic sig structure which is inherited by the functoid directly. Note that the c_fun_type class takes (N+1) template arguments which represent the N parameter types and the result type.


4. Overview Examples		6. Indirect Functoids