first stab at transducers —map, filter and flatmap— in idiomatic (‽) C++, now with FizzBuzz !

transducers.cxx

#include <array>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <sstream>
/* const correctness and pass by value vs const ref, move semantics
   left as an exercise to the reader.
iterator range API prevents a flatmap as the flatmapped function
 could not either return a value or a range.
(would return the paste-the-end iterator of an output range)*/


template<typename Op, template<typename, typename> class Transducer >
struct transducer_helper {
  Op op;
  transducer_helper(Op o):op(o){}
  template <typename Reducer>
  Transducer<Op, Reducer> operator()(Reducer r)
  {return Transducer<Op, Reducer>(op, r);}
};

template <typename Op, typename Reducer>
struct transducer_base {
  Op op;
  Reducer reducer;
  transducer_base(Op o, Reducer r): op(o), reducer(r){}
};

template <typename Op, typename Reducer>
struct map_transducer : transducer_base<Op, Reducer> {
  using transducer_base<Op, Reducer>::transducer_base;
  template<typename Result, typename Input>
  Result operator()(Result r, Input data)
  { return this->reducer(r, this->op(data));}
};

template <typename Op>
transducer_helper<Op, map_transducer> map(Op const& op)
  { return transducer_helper<Op, map_transducer>(op); }

template <typename Op, typename Reducer>
struct filter_transducer : transducer_base<Op, Reducer>{
  using transducer_base<Op, Reducer>::transducer_base;
  template<typename Result, typename Input>
  Result operator()(Result r, Input data)
  { return this->op(data) ? this->reducer(r, data) : r ;}
};


template <typename Op>
transducer_helper<Op, filter_transducer> filter(Op const& op)
{ return transducer_helper<Op, filter_transducer>(op); }

// We will want to compose the transducers
template<typename... Fn> struct composer;
template<> struct composer<> {
  template<typename Data> Data operator()(Data d){ return d; }
};
template<typename F0, typename... Fn>
struct composer<F0, Fn...> : private composer<Fn...> {
  F0 f;
  composer(F0 f0, Fn const&... fn): composer<Fn...>(fn...), f(f0){}
  template<typename Data> auto operator()(Data d)->decltype(f(composer<Fn...>::operator()(d)))
  { return f(composer<Fn...>::operator()(d)); }
};

template <typename... Fn>
composer<Fn...> comp(Fn const&... fn)
{ return composer<Fn...>(fn...); }


template < typename Transducer, typename Reducer, typename Init, typename In>
Init transduce (Transducer xform, Reducer f, Init res, In b, In e)
{ return std::accumulate(b, e, res, xform(f)); }

// for flatmap, the idiomatic c++ way of "returning"
// multiple values is to take an output iterator

template <typename Data, typename Size, typename Out>
Out expand_rle(std::pair<Data, Size> p, Out out)
{ return std::generate_n(out, p.second, [p]{ return p.first;}); }

// the problem is that we have to defer because we don't know the output iterator type
// so maybe we should
// use another object indirection
struct run_length_decoder {
  template<typename Data, typename Size, typename Out>
  Out operator()(std::pair<Data, Size> p, Out out)
  { return std::generate_n(out, p.second, [p]{ return p.first;}); }
};

// instead, we want to reduce the values, so we use a
// generalization of back_insert_iterator
template <typename Reducer, typename Init>
struct reducing_output_iterator
  : public std::iterator<std::output_iterator_tag, void, void, void, void> {
  Reducer reducer;
  Init res;
  reducing_output_iterator(Reducer r, Init init): reducer(r), res(init){}
  reducing_output_iterator& operator*(){ return *this;}
  template <typename Data>
  reducing_output_iterator& operator=(Data data){ res= reducer(res, data); return *this;}
  reducing_output_iterator& operator=(reducing_output_iterator<Reducer, Init> const& other)
  { reducer= other.reducer; res= other.res; return *this;}
  reducing_output_iterator& operator++() { return *this; }
  reducing_output_iterator& operator++(int) { return *this; }
};

template <typename Reducer, typename Init>
reducing_output_iterator<Reducer, Init> make_reducing_output_iterator (Reducer r, Init i)
{return reducing_output_iterator<Reducer, Init>(r, i) ;}

// the flatmap Op takes two args, the data and an output iter
// (and returns the past-the-end output iter)
template <typename Op, typename Reducer>
struct flatmap_transducer : transducer_base<Op, Reducer>{
  using transducer_base<Op, Reducer>::transducer_base;
  template<typename Result, typename Input>
  Result operator()(Result r, Input data){
    return (this->op(data, make_reducing_output_iterator(this->reducer, r))).res;
  }
};

template <typename Op>
transducer_helper<Op, flatmap_transducer> flatmap(Op const& op)
{ return transducer_helper<Op, flatmap_transducer>(op); }

template<typename T> std::string to_str(T const& d)
{ std::ostringstream os; os << d; return os.str(); }

int main(int argc, char* argv[]){
  typedef int data_t;
  std::array<data_t, 3> data={1, 3, -10};

  std::plus<data_t> plus;

  std::cout<<std::accumulate(data.begin(), data.end(), 0., plus) << std::endl;

  auto times_2= map([](data_t d){return 2 * d;});
  std::cout<< transduce(times_2, plus, 0, data.begin(), data.end()) << std::endl;

  auto strictly_positive= filter([](data_t d){ return d > 0 ;});
  std::cout<< transduce(strictly_positive, plus, 0, data.begin(), data.end())
           << std::endl;

  std::cout<< transduce(comp(strictly_positive, times_2)
                        , plus, 0, data.begin(), data.end()) << std::endl;

  auto only_even= filter([](data_t d){ return d % 2 == 0 ;});
  std::cout<< transduce(comp(only_even, times_2)
                        , plus, 0, data.begin(), data.end()) << std::endl;
  std::cout<< transduce(comp(times_2, only_even)
                        , plus, 0, data.begin(), data.end()) << std::endl;

  std::cout<< std::copy(data.begin(), data.end(), make_reducing_output_iterator(plus, 0)).res <<std::endl;
  std::array<std::pair<int, int>, 3> pairs={{{2,3},{1,2},{-3,4}}};
  auto rld= flatmap(run_length_decoder());
  std::cout<< transduce(rld, plus, 0, pairs.begin(), pairs.end()) << std::endl;
  std::cout<< transduce(comp(rld, times_2), plus, 0, pairs.begin(), pairs.end()) << std::endl;
  std::cout<< transduce(comp(rld, only_even, times_2), plus, 0, pairs.begin(), pairs.end()) << std::endl;


  auto with_empty_str= map([](data_t d){return std::make_pair(d, std::string());});
  auto fizzbuzzer= [](data_t factor, std::string const& name){
    return map([factor, name](std::pair<data_t, std::string> const& dn)
    { return (dn.first % factor) ? dn : std::make_pair(dn.first, dn.second + name);});};



  auto writer= map([](std::pair<data_t, std::string> const& dn)
                   { return dn.second.empty() ? to_str(dn.first) : dn.second;});
  std::vector<data_t> seq;
  {
    data_t d(0);
    std::generate_n(std::back_inserter(seq), 20, [d]() mutable{return ++d;});
  }
  std::cout <<  transduce(comp(with_empty_str, fizzbuzzer(3, "Fizz"), fizzbuzzer(5, "Buzz"), writer)
                          , [](std::string const& res, std::string const& s){return res+' '+s;}
                          , std::string(), seq.begin(),  seq.end());

  return 0;
}