Re: [boost] About template metaprogramming and functional programming

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-07-22 19:09:00

From: "David Abrahams" <david.abrahams_at_[hidden]>
> From: "Vesa Karvonen" <vesa.karvonen_at_[hidden]>
[snip]
> > It is possible to implement most
> > sequence algorithms using std::accumulate and trivial adapters. For
> instance,
> > std::transform can be implemented as follows (I'm writing this code from
> the
> > top of my head, so it will probably have bugs):
>
> <snip tall skinny code with approx. one identifier per line, names like
> "out_ite", and no comments>

;-)

It is not the amount of lines of code or how many identifier per line you have
that counts. What counts is that logic is not duplicated and code manipulation
is easy.

> Hmm, the above comment says it all. I didn't understand your code. Maybe you
> could try again with a more conventional formatting style?

I've underlined the bugs I've noticed so far. I also changed template type
parameters to mixed case. Technically, the transform_adapter<> should be
declared before using it in transform(), but I think that the code is easier
to understand like this.

  template<class InIte, class OutIte, class UnOp>
  OutIte transform(InIte begin, InIte end, OutIte out, UnOp op)
//^^^^^^
  {
    return accumulate(
      begin,
      end,
      out,
      transform_adapter<
        OutIte,
        UnOp,
        typename iterator_traits<InIte>::reference_type>(op));
  }

  template<class OutIte, class UnOp, class RefType>
  struct transform_adapter
  {
    transform_adapter(UnOp op) : m_op(op) {}

    OutIte operator()(OutIte out, RefType t) const
//                 ^^
    {
      *out = m_op(t);
      return ++out;
    }

  private:
    UnOp m_op;
  };

The above code probably seems rather complex compared to a straightforward
implementation of transform. This is basically caused by C++ syntax (which has
lots of separators), manifest typing and inability to create unnamed
closures/classes. In a functional programming language, this style of
programming generally leads to simpler programs.

In Haskell, the recursive definition of map, which is the equivalent of
transform for lists, goes like this:

  map f [] = []
  map f (x:xs) = f x : map f xs

However, using foldr and various features of the language, such as function
composition, it is possible to implement map as:

  map f = foldr ((:).f) []

As you can see, the definition using foldr is simpler than the recursive
definition.