Home | Libraries | People | FAQ | More |

**Table of Contents**

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

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

some_other_func( mymap, ... ); // illegal if mymap is template functionThis 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

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" wordsrepresents the result type when a function of type

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

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

typename F::template sig<X,Y>::result_typewe just say

typename RT<F,X,Y>::result_typeThat is,

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`.

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.

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

Last revised: October 03, 2003 at 23:27:22 GMT | Copyright © 2000-2003 Brian McNamara and Yannis Smaragdakis |