Common Higher Order Functions

For those of us who want to gain a greater understanding of how FunctionalProgrammingLanguages work, what are some of the more CommonHigherOrderFunctions that are included in their libraries?

• CurriedFunctions -- define the primary method being used where a HigherOrderFunction takes a CurriedFunctor. A common class of these functions are:
  • InternalIterators -- common enumerators in this category include:
    • MapFunction -- #collect in SmallTalk, can be approximated with std::for_each or std::transform in CeePlusPlus
    • FoldFunction -- #inject in SmallTalk, std::accumulate in CeePlusPlus
    • FilterFunction -- #select in SmallTalk, can be approximated with std::for_each or std::copy_if in CeePlusPlus
• ComposeFunction -- partially specify inputs and composes functors.
• Other combinators, like flip (flip f x y = f y x)
• Monadic bind (>>=)
• map is a generic concept not constrained to lists
• HaskellLanguage's interact
• higher order parsers, like lchain

---

re: ComposeFunction: In CeePlusPlus we have std::binder1st, std::binder2nd, std::binary_compose, and std::unary_compose which can only compose and partially specify the inputs for unary and binary operations.

• Technically speaking, binary_compose and unary_compose are not strictly std::, but an SGI extension to the StandardTemplateLibrary. Nicolai Josuttis, in his "TheCppStandardLibrary: A Tutorial and Reference", describes other composers:
  • compose_f_gx(f, g)(x) == f(g(x))
  • compose_f_gxy(f, g)(x, y) == f(g(x, y))
  • compose_f_gx_hx(f, g, h)(x) == f(g(x), h(x))
  • compose_f_gx_hy(f, g, h)(x, y) == f(g(x), h(y))

CurryingSchonfinkelling and lambda functions are for partially specifying inputs. ComposeFunction is only for composing other functions. The CeePlusPlus templates you give are an attempt to implement currying and functional composition in a language that does not have native support for curried functions or higher order functions, and so are not good examples.

Well, you would know more than I, but it still seems like compose1 and compose2 in CeePlusPlus are very much like the ComposeFunction. Can you give a CeePlusPlus like example for ComposeFunction?

Example of compose in C++:

 #include <iostream>

 // implementation of "compose" in C++
 template<class A, class B, class C>
 class Compose
 {
   public:
   Compose(A (*f)(B b), B (*g)(C c))
   {
     this->f = f;
     this->g = g;
   }

   A operator()(C c)
   {
     return (*f)((*g)(c));
   }

   private:
   A (*f)(B b);
   B (*g)(C c); 
 };

 // example of use
 int f(int x)
 {
   return x + 1; 
 }

 int g(int y)
 {
   return 2*y; 
 }

 int main()
 {
   Compose<int, int, int> f_o_g(&f, &g);

   // f(g(3)) should produce the same answer as f_o_g(3)
   std::cout << "f(g(3)) = " << f(g(3)) << std::endl;
   std::cout << "f_o_g(3) = " << f_o_g(3) << std::endl;

   return 0;
 }

This seems to reinforce what I said about unary_compose and binary_compose approximating ComposeFunction. What you've typed is very much like these templates in the CeePlusPlus STL. AlexanderStepanov just defined them to use function objects instead of pointers. Fortunately, through the use of std::ptr_fun() (a template adapter to create instances of std::pointer_to_unary_function and std::pointer_to_binary_function, you can mix and match both. For example:

  // create a CeePlusPlus style FunctorObject
  struct f( double arg )  {
     double operator()( double arg ) {
        return arg * ( pi / 180 );
     }
  }

  // compose FunctorObject and function pointer
  std::transform(
     angles.begin(), angles.end(),
     sines.begin(),
     std::compose1( std::ptr_fun( sin ), g() ) ); 

Or you can compose even further like:

  std::transform(
     angles.begin(), angles.end(),
     sines.begin(),
     std::compose1( 
        std::negate<double>(),
        std::compose1( 
            std::ptr_fun( sin ), g() ) ) );

Which is really just the same as:

  std::transform(
     angles.begin(), angles.end(),
     sines.begin(),
     std::compose1( 
        std::negate<double>(),
        std::compose1( 
            std::ptr_fun( sin ),
            std::bind2nd( std::multiplies<double>(), pi / 180. ) ) ) );

In the above, compose1 and compose2 are just template function wrappers that make it easier to use std::unary_compose and std::binary_compose. This is why I originally wrote that one could use unary_compose and binary_compose in CeePlusPlus to approximate a ComposeFunction. This is from some of its documentation:

This operation is called function composition, hence the name unary_compose. It is often represented in mathematics as the operation f o g, where f o g is a function such that (f o g)(x) == f(g(x)). Function composition is a very important concept in algebra. It is also extremely important as a method of building software components out of other components, because it makes it possible to construct arbitrarily complicated function objects out of simple ones.

However, I agree that binder1st and binder2nd, while important for most uses of compose1 and compose2 are not an required part of composition. Maybe that was what you meant to say -- i.e. not all the templates I mentioned, just the binders.

-- RobertDiFalco

---

CategoryFunctionalProgramming