使用C++模板实现Haskell的`map`函数的问题

Question

我喜欢使用Haskell,但我被迫使用C++进行学校作业.我正在为C++编写自己的库来模拟Haskell的Prelude函数,所以如果我愿意的话,我可以在C++ 中用更简洁和实用的风格编写(在GitHub上回购).

我遇到的一个问题是实现类似于map列表操作的函数.在Haskell中,String相当于[Char],所以你可以在带有列表的函数中使用字符串.在C++中,std::string是不一样的东西std::vector<char>,所以我必须写功能的多个版本,以充分std::string或std::vector<Type>.这适用于类似filter或tail因为它们的输入和输出是相同类型的函数.但是map,我需要能够将ints 的矢量转换为chars,或者string转换为bools 的矢量.

---

当试图运行一个简单的猪拉丁转换器(pigLatin.cpp在GitHub上)时,该unwords功能失败,因为map无法正常工作.

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.

如何编写我的map函数,使其行为类似于Haskell中的函数(map在Hackage上):

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

我不太了解C++模板的细微差别来解决这个问题.这是我到目前为止(map来自prelude.hppGitHub):

// 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

在这个声明中:

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

Output是一个非推断的上下文.编译器将推断的类型Function,并Input从提供的参数,但Output不能推断-它必须被明确规定.这不会发生.

你想要做的是自己计算什么Output是函数Function和Input.使用C++ 17编译器/库,std::invoke_result_t(在C++ 11上使用result_of).那是:

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

这是一个默认的模板参数,但由于用户实际上不会提供它,因此将使用默认参数,这就是您想要的.现在这也不完全正确,因为invoke_result_t可以返回一些你不能放入的东西vector(比如,参考).所以我们需要std::decay它.此外,您需要保留输出向量,因为我们预先知道它的大小:

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

现在,如果你想让它能够拿a string并且返回a vector<X> 或 a string,那现在变得非常复杂.你不能在C++中重载返回类型,所以提供这两个重载是不正确的.它现在恰好适用于你的情况,因为string --> vector<X>由于X不可推导而导致过载被排除在外.但是一旦你解决了这个问题,你就会遇到这个问题.