Problems with implementing the Haskell `map` function with C ++ templates

Question

I like to use Haskell, but I have to use C ++ for school assignments. I am writing my own C ++ library that emulates Haskell Prelude functions, so I can write in a more concise and functional style in C ++ if I want ( repo on GitHub ).

The problem I am facing is the implementation of functions like map that work with lists. In Haskell, String equivalent to [Char] , so you can use strings in functions that take lists. In C ++, std::string is not the same as std::vector<char> , so I need to write several versions of functions to take std::string or std::vector<Type> . This works great for functions like filter or tail , because their input and output are of the same type. But with map I need to be able to convert an int vector to char s or String to a bool s vector.

---

When trying to run a simple Latin lead converter ( pigLatin.cpp on GitHub ), the unwords function unwords not work because map isn Works.

 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 so that it behaves like in Haskell ( map in Hackage ):

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

I don’t know enough about the nuances of C ++ templates to figure this out. This is what I still have ( 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 ad:

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

Output is a non-output context. The compiler infers the types Function and Input from the supplied arguments, but Output cannot be inferred - it must be explicitly provided. This will not happen.

What you want to do is figure out yourself that Output is a Function and Input function. With a C ++ 17 compiler / library, std::invoke_result_t (in C ++ 11 use result_of ). I.e:

 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); 

This is the default template parameter, but since the user will never actually provide it, the default argument you want is used. Now this is not entirely correct, since invoke_result_t can return what you cannot put in vector (for example, a link). Therefore, we need std::decay it. In addition, you want to reserve the output vector, since we know what its size is:

 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 it to be able to take a string and either return a vector<X> or a string , which now becomes quite complicated. You cannot overload the return type in C ++, therefore, provided that these two overloads are poorly formed. This is happening in your case now, since overloading string --> vector<X> will be removed from consideration due to X not being output. But as soon as you fix it, you will encounter this problem.