Problems implementing Haskell's `map` function with C++ templates

Question

I love using Haskell but am forced to use C++ for school assignments. I am writing my own library for C++ that emulates Haskell's Prelude functions so I can write in a more concise and functional style in C++ if I wish (repo on GitHub).

A problem I have run into is implementing functions like map that operate on lists. In Haskell, String is equivalent to [Char], so you can use strings in functions that take lists. In C++, std::string is not the same thing as std::vector<char>, so I have to write multiple versions of functions to take std::string or std::vector<Type>. This works fine for functions like filter or tail because their input and output are the same type. But with map, I need to be able to transform a vector of ints into chars, or a string into a vector of bools.

---

When trying to run a simple pig latin converter (pigLatin.cpp on GitHub), the unwords function fails because map isn't working.

examples/pigLatin.cpp:20:29: error: no matching function for call to 'unwords'
  std::string translation = unwords(map(pigLatin, words(input)));
                            ^~~~~~~
examples/../prelude.hpp:591:15: note: candidate function not viable: no known conversion from 'std::string' (aka 'basic_string<char, char_traits<char>, allocator<char> >') to 'const std::vector<std::string>'
      (aka 'const vector<basic_string<char, char_traits<char>, allocator<char> > >') for 1st argument
  std::string unwords(const std::vector<std::string> &xs) {
              ^
1 error generated.

How can I write my map function such that it behaves like the one in Haskell (map on Hackage):

map :: (a -> b) -> [a] -> [b]

I don't know enough about the nuances of C++ templates to figure this one out. This is what I have so far (map from prelude.hpp on GitHub):

// map :: (a -> b) -> [a] -> [b]
template <typename Function, typename Input, typename Output>
std::vector<Output> map(const Function &f, const std::vector<Input> &xs) {
  const int size = xs.size();
  std::vector<Output> temp;
  for (int i = 0; i < size; ++i) {
    temp.push_back(f(xs[i]));
  }
  return temp;
}

// map :: (String -> a) -> String -> [a]
template <typename Function, typename Output>
std::vector<Output> map(const Function &f, const std::string &xs) {
  const int size = xs.size();
  std::vector<Output> temp;
  for (int i = 0; i < size; ++i) {
    temp.push_back(f(xs[i]));
  }
  return temp;
}

// map :: (a -> String) -> [a] -> String
template <typename Function, typename Input>
std::string map(const Function &f, const std::vector<Input> &xs) {
  const int size = xs.size();
  std::string temp;
  for (int i = 0; i < size; ++i) {
    temp += f(xs[i]);
  }
  return temp;
}

// map :: (String -> String) -> String -> String
template <typename Function>
std::string map(const Function &f, const std::string &xs) {
  const int size = xs.size();
  std::string temp;
  for (int i = 0; i < size; ++i) {
    temp += f(xs[i]);
  }
  return temp;
}

Answer 1

In this declaration:

template <typename Function, typename Input, typename Output>
std::vector<Output> map(const Function &f, const std::vector<Input> &xs);

Output is a non-deduced context. The compiler will deduce the type of Function and Input from the provided arguments, but Output cannot be deduced - it would have to be explicitly provided. That's not going to happen.

What you want to do is yourself compute what Output is as a function of Function and Input. With a C++17 compiler/library, that's std::invoke_result_t (on C++11, use result_of). That is:

template <typename Function, typename Input,
    typename Output = std::invoke_result_t<Function const&, Input const&>>
std::vector<Output> map(const Function &f, const std::vector<Input> &xs);

It's a defaulted template parameter, but since the user won't actually ever provide it, the default argument will get used, which is what you want. Now this isn't entirely right either, since invoke_result_t could return something that you can't put in a vector (like, a reference). So we need to std::decay it. Moreover, you'll want to reserve the output vector since we know up front what its size will be:

template <typename Function, typename Input,
    typename Output = std::decay_t<std::invoke_result_t<Function&, Input const&>>>
std::vector<Output> map(Function&& f, const std::vector<Input> &xs)
{
    std::vector<Output> res;
    res.reserve(xs.size());
    for (auto&& elem : xs) {
        res.push_back(f(elem));
    }
    return res;
}

---

Now, if you want this to be able to take a string and either return a vector<X> or a string, that's now getting pretty complicated. You can't overload on return type in C++, so providing those two overloads is ill-formed. It happens to work in your case now, since the string --> vector<X> overload will be removed from consideration due to X not being deducible. But once you fix that, you'll run into that problem.