Re: [boost] About template metaprogramming and functional programming

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-07-21 21:14:25

From: "Ronald Garcia" <garcia_at_[hidden]>
[snip]
> your foldr sounds a lot like std::accumulate in the STL world, but
> applied to template metaprograms.

Just to clarify things: foldr has not been invented by me and may predate
std::accumulate possibly by decades - I don't know when it was first invented.

Yes, std::accumulate (with binary_op) is basically the same as foldr.
std::accumulate (and foldr) is a very general function. I recommend that you
find some textbook on functional programming and read the chapter that
describes list manipulation functions. 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):

template
< class in_ite
, class out_ite
, class un_op
>
void
  transform
  ( in_ite
      begin
  , in_ite
      end
  , out_ite
      out
  , un_op
      op
  )
{ return
    accumulate
    ( begin
    , end
    , out
    , transform_adapter
      < out_ite
      , un_op
      , typename iterator_traits<in_ite>::reference_type
      >(op)
    );
}

template
< class out_ite
, class un_op
, class reference_type
>
struct transform_adapter
{   transform_adapter
    ( un_op
        op
    )
    : m_op(op)
  {
  }

  out_ite
    operator
    ( out_ite
        out
    , reference_type
        t
    ) const
  { *out = m_op(t);
    return ++out;
  }
private:
  un_op
    m_op;
};