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

Question

我喜欢使用 Haskell，但不得不使用 C++ 来完成学校作业。我正在为 C++ 编写自己的库，它模拟 Haskell 的 Prelude 函数，因此如果我愿意，我可以用 C++ 编写更简洁、更实用的风格(repo on GitHub)。

我遇到的一个问题是实现类似 map 的功能对列表进行操作。在 Haskell 中，String相当于[Char] ，因此您可以在采用列表的函数中使用字符串。在 C++ 中，std::string 不与std::vector<char>是一回事，所以我必须编写多个版本的函数来取 std::string或 std::vector<Type> .这适用于像 filter 这样的功能或 tail因为它们的输入和输出是同一类型。但是用map ，我需要能够转换 int 的 vector 进入char s，或 string进入 vector bool

---

当尝试运行一个简单的 pig 拉丁语转换器 ( pigLatin.cpp on 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 on Hackage):

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

我对 C++ 模板的细微差别了解不够，无法解决这个问题。这是我目前所拥有的( 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

在此声明中:

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 它。此外，您需要保留输出 vector ，因为我们预先知道它的大小:

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

---

现在，如果您希望它能够接受 string要么返回 vector<X> 或一个string ，现在变得相当复杂。您不能在 C++ 中重载返回类型，因此提供这两个重载是错误的。它现在恰好适用于你的情况，因为 string --> vector<X>由于X，过载将从考虑中移除不可推论。但是一旦你解决了这个问题，你就会遇到那个问题。