Flatmap implementation

Question

I have an implementation of flatmap for std::vector. However, I find the repetition of the inferred return type to be ugly. And, in general, I suspect that the implementation could be cleaner or more general.

template<typename T, typename FN>
static auto flatmap(const std::vector<T> &vec, FN fn) -> std::vector<typename std::remove_reference<decltype(fn(T())[0])>::type> {
 std::vector<typename std::remove_reference<decltype(fn(T())[0])>::type> result;
 for(auto x : vec) {
 auto y = fn(x);
 for( auto v : y ) {
 result.push_back(v);
 }
 }
 return result;
};

It can be used like this:

TEST_F(MarkdownUtilTests, testFlatmap) {
 std::vector<int> v = { 1, 2, 3};
 std::vector<int> result = flatmap(v, [](int x) { return std::vector<int> { x, x*2, x*3 }; } );
 assertThat(result, is(std::vector<int> {1,2,3,2,4,6,3,6,9} ));
}

Answer 1

There's a reason the algorithms in the standard library use iterators instead of dealing with containers directly. One is that it makes code like this quite a bit simpler. For example, using iterators, we could write Flatmap something like this:

template <typename InIter, typename OutIter, typename FN>
void Flatmap(InIter begin, InIter end, OutIter out, FN fn) {
 for (; begin != end; ++begin) {
 auto y = fn(*begin);
 std::copy(std::begin(y), std::end(y), out);
 }
}

This is somewhat more versatile, since it can take input from/write output to essentially any iterator, rather than necessarily reading from one vector and producing another vector. Likewise, what's produced by fn doesn't have to be a vector either--it can be essentially any container (anything for which we can use std::begin() and std::end(), to be more exact). While vector is certainly common, there are reasons for using other containers--and sometimes even a reason to write to something that isn't exactly a container either. For example:

std::vector<int> inputs { 1, 2, 3 };
Flatmap(inputs.begin(), inputs.end(), 
 std::ostream_iterator<int>(std::cout, "\t"), 
 [](auto x) { return std::vector<decltype(x)> { x, x * 2, x * 3 }; });

Note that I've used auto as the parameter type in the lambda, so this test code requires C++14, but Flatmap itself is fine with C++11.

If you wanted to be a bit more forward thinking, you could write this to work with ranges instead of iterators. Eric Neibler's range library is fairly nice, and seems well on its way toward being included in an upcoming C++ standard.

Along with the code being simpler and more versatile, the other obvious advantage would be that this follows the same style as standard library code--for example, its signature and usage is essentially identical to std::transform.

• Michael Anderson: The advantage of not using iterators is that composition is easier. I can do a flat_map( filter( vec, f1), f2 ) type thing which is pretty ugly to express using iterators . However the range based option looks like a nice way to clean some of that up.
• Jerry Coffin: @MichaelAnderson: Yes, ranges do compose much more nicely, while retaining most of the advantages of iterators.
• Michael Anderson: Perhaps I'm just not handy enough with c++11, but what is required to implement flatmap in the range library... I've tried a bit, but guess I just dont grok it well enough yet.
• Michael Anderson: These comments are diverging far enough from reviewing the existing code that I've opened a new question on stack overflow. stackoverflow.com/questions/36051851/…
• bradgonesurfing: The problem with this is that it doesn't compose. Flatmap of Flatmap is not possible?? You want a type signiture something like `` Flatmap = (Range<T>) (T->Range<U>) -> (Range<U>)`` ie Flatmap takes a range of element type T and a function that for every element t of the input range produces a new range of element type U which is then concatenated together produces a new range of element type U. Theoretically it should be possible in c++ to do this with a zero overhead abstraction. I've tried myself and it is not so easy. The advantage of the above solution is that it is fast.