How can I let the compiler deduce the return type of a template?

Question

I'm coming from Haskell and currently tinker with C++11 to see what it can do. One of my toys is a small template which attempts to imitate the Haskell map function, i.e. it takes a container of values of X and a function mapping an X to a Y and yields a container of values of Y. I know that I could easily do that using std::transform, but that would spoil the fun.

Right now, my template looks like this:

template <typename T, typename U>
void myMap( const T &input,
            U &output,
            std::function<typename U::value_type (typename T::value_type)> f );

Now, my qustion is: is it possible to adjust the signature so that instead of taking the output container by reference (the second argument) I yield a new container via the return value and yet the compiler can deduce the return type? Something like

template <typename T, typename U>
U myMap( const T &input,
       std::function<typename U::value_type (typename T::value_type)> f );

unfortunately cannot be called like

std::vector<int> x = { 1, 2, 3, 4 };
std::list<bool> y = myMap( x, []( int x ) { return x % 2 == 0; } );

...at least Clang fails to deduce the return type here.

One idea I had was that given that the input container type and the function type is known, you could construct the output type from that. I.e. something like

template <typename C, typename T, typename U>
C<U> myMap( const C<T> &input,
            std::function<U (T)> f );

...but alas C<U> doesn't even seem to be valid syntax. I wonder if I just need the right decltype fairy dust as was the case in this question.

Answer 1

As I've stated before, I've done this before with everything but it fails to work with std::basic_string<T,U> (and std::set and friends due to the use of std::back_inserter) because it'll just rebind it to std::basic_string<stuff,U> rather than an underlying container. Do note however that it would be easy to extend it to work with a specialised case of std::basic_string<T, U>.

First thing I did was define a function_traits and a Rebind metafunction that would rebind types from Container<T> to Container<U> where U is the result type of the function being passed and T is the original type. The result type is found through the function_traits meta function. You can see the fully working code below:

#include <type_traits>
#include <algorithm>

/* Helpers */
template<typename T>
using Type = typename T::type;

template<typename T>
using Unqualified = Type<std::remove_reference<Type<std::remove_cv<T>>>>;

template<typename Specialization, typename Target>
struct rebind {};

/* Sensible default: assume first parameter is for the target */
template<template<typename...> class Cont, typename T, typename... Ts, typename Target>
struct rebind<Cont<T, Ts...>, Target> {
    using type = Cont<Target, Ts...>;
};

/* Special-case */
template<typename Old, std::size_t N, typename Target>
struct rebind<std::array<Old, N>, Target> {
    using type = std::array<Target, N>;
};

template<typename Specialization, typename Target>
using Rebind = Type<rebind<Specialization, Target>>;

#include <tuple>

template<typename T>
struct function_traits : public function_traits<decltype(&T::operator())> {};

template<typename T, typename R, typename... Args>
struct function_traits<R(T::*)(Args...) const> {

    static constexpr size_t args = sizeof...(Args);

    using result_type = R;
    template<size_t i>
    struct arg {
        using type = typename std::tuple_element<i,std::tuple<Args...>>::type;
    };
};

template<typename T>
using Resultant = typename function_traits<T>::result_type;

template<class Cont, typename Map>
auto map(const Cont& cont, Map&& mapped) -> Rebind<Cont, Resultant<Unqualified<Map>>> {
    Rebind<Cont, Resultant<Unqualified<Map>>> result;
    auto result_iterator = std::back_inserter(result);
    for(const auto& elem : cont) {
        *result_iterator = mapped(elem);
    }
    return result;
}

#include <iostream>

int main() {
    auto i = map(std::vector<int>{1,2,3,4,5,6}, [](int x) { return x % 2 == 0; });
    for(auto&& j : i) {
        std::cout << j << ' ';
    }
}

Output:

0 1 0 1 0 1

Live version on Coliru

Answer 2

You are probably looking for this syntax

#include <algorithm>
#include <functional>
#include <type_traits>
#include <list>

template 
    <
       template<typename, typename...> class Container, 
       typename InType, 
       typename FuncType, 
       typename... Rest
    >
auto myMap (const Container<InType, Rest...>& container,
            FuncType func) -> 
              Container<decltype(func(std::declval<InType>())), Rest...>
{
    Container<decltype(func(std::declval<InType>())), Rest...> result;
    std::transform(std::begin(container), 
                   std::end(container),
                   std::back_inserter(result), 
                   func);
    return result;
}

though I would not recommend using this style of code in any real project.