Exa*_*gon 14 c++ monads functional-programming c++14
我目前正在学习一点点哈斯克尔并开始弄清楚monad是如何工作的.由于我正常编写C++代码,我认为monad模式(就像我现在理解的那样)在C++中也非常棒,例如对于期货等,
我想知道是否有一种方法可以实现一个接口或一个基类来强制执行函数的正确重载bind和return(对于C++的返回而不是返回C++的原因)派生类型？
为了更清楚我在想什么:
考虑我们有以下非成员函数:
auto foo(const int x) const -> std::string;
和一个成员函数bar,它对不同的类有不同的重载:
auto bar() const -> const *Monad<int>;
如果我们现在想做这样的事情:foo(someMember.bar())这根本不起作用.因此,如果必须知道哪个bar返回,例如,如果它返回a future<int>,我们必须调用bar().get(),哪些块,即使我们不需要在这里阻止.
在haskell我们可以做类似的事情 bar >>= foo
所以我问自己是否可以在C++中实现这样的行为,因为在调用时foo(x)我们不关心x是否是一个盒子的对象int,以及盒子里的类int,我们只想foo在盒装类型上应用函数.
对不起,我有一些问题用英语表达我的想法,因为我不是母语人士.
Cor*_*sto 23
首先请注意,作为一个monad不是一个类型的属性,而是一个类型构造函数.
例如,在Haskell中,您将拥有List a一个类型和List类型构造函数.在C++中,我们与模板具有相同的功能:std::list是一个可以构造类型的类型构造函数std::list<int>.这List是一个单子,但List Bool不是.
为了使类型构造函数M成为monadic,它需要提供两个特殊函数:
T到monad的函数,即类型函数T -> M<T>.return在Haskell中调用此函数.bind)M<T> ->(T -> M<T'>) -> M<T'>,即一个接受类型对象和类型M<T>函数的函数,T -> M<T'>并将参数函数应用于包含在参数内的T对象M<T>.这两个函数还必须满足一些属性,但由于在编译时无法检查语义属性(在Haskell和C++中都没有),我们在这里并不需要关心它们.
然而,一旦我们确定了它们的语法/名称,我们可以检查这两个函数的存在和类型.对于第一个,显而易见的选择是构造函数,它只接受任何给定类型的一个元素T.对于第二个我决定使用,operator>>=因为我希望它是一个运算符,以避免嵌套的函数调用,它类似于Haskell表示法(但不幸的是它是右关联 - 哦,好吧).
那么如何检查模板的属性呢？幸运的是,C++中有模板模板参数和SFINAE.
首先,我们需要一种方法来确定是否存在一个采用任意类型的构造函数.我们可以通过检查对于给定类型构造函数来M确定类型M<DummyType>是否适合struct DummyType{};我们定义的虚拟类型.通过这种方式,我们可以确保不会对我们要检查的类型进行专门化.
因为bind我们做同样的事情:检查是否存在operator>>=(M<DummyType> const&, M<DummyType2>(*)(DummyType))并且返回的类型实际上是M<DummyType2>.
检查函数是否存在可以使用C++ 17s完成std::void_t(我强烈推荐Walter Browns在2014年CppCon上的讲话,他介绍了该技术).可以使用std :: is_same检查类型是否正确.
总之,这看起来像这样:
// declare the two dummy types we need for detecting constructor and bind
struct DummyType{};
struct DummyType2{};
// returns the return type of the constructor call with a single
// object of type T if such a constructor exists and nothing
// otherwise. Here `Monad` is a fixed type constructor.
template <template<typename, typename...> class Monad, typename T>
using constructor_return_t
= decltype(Monad<T>{std::declval<T>()});
// returns the return type of operator>>=(const Monad<T>&, Monad<T'>(*)(T))
// if such an operator is defined and nothing otherwise. Here Monad
// is a fixed type constructor and T and funcType are arbitrary types.
template <template <typename, typename...> class Monad, typename T, typename T'>
using monadic_bind_t
= decltype(std::declval<Monad<T> const&>() >>= std::declval<Monad<T'>(*)(T)>());
// logical 'and' for std::true_type and it's children
template <typename, typename, typename = void>
struct type_and : std::false_type{};
template<typename T, typename T2>
struct type_and<T, T2, std::enable_if_t<std::is_base_of<std::true_type, T>::value && std::is_base_of<std::true_type, T2>::value>>
: std::true_type{};
// the actual check that our type constructor indeed satisfies our concept
template <template <typename, typename...> class, typename = void>
struct is_monad : std::false_type {};
template <template <typename, typename...> class Monad>
struct is_monad<Monad,
void_t<constructor_return_t<Monad, DummyType>,
monadic_bind_t<Monad, DummyType, DummyType2>>>
: type_and<std::is_same<monadic_bind_t<Monad, DummyType, DummyType2>,
Monad<DummyType2>>,
std::is_same<constructor_return_t<Monad, DummyType>,
Monad<DummyType>>> {};
请注意,即使我们通常希望类型构造函数将单个类型T作为参数,我也使用可变参数模板模板参数来考虑STL容器中通常使用的默认分配器.如果没有这个,你就无法std::vector在上面定义的概念意义上建立一个monad.
monad的巨大优势在于,只有monadic接口才能做很多事情.例如,我们知道每个monad也是一个应用程序,因此我们可以编写Haskell的ap函数并使用它来实现liftM允许将任何普通函数应用于monadic值.
// ap
template <template <typename, typename...> class Monad, typename T, typename funcType>
auto ap(const Monad<funcType>& wrappedFn, const Monad<T>& x) {
static_assert(is_monad<Monad>{}(), "");
return wrappedFn >>= [x] (auto&& x1) { return x >>= [x1 = std::forward<decltype(x1)>(x1)] (auto&& x2) {
return Monad<decltype(std::declval<funcType>()(std::declval<T>()))> { x1 (std::forward<decltype(x2)>(x2)) }; }; };
}
// convenience function to lift arbitrary values into the monad, i.e.
// just a wrapper for the constructor that takes a single argument.
template <template <typename, typename...> class Monad, typename T>
Monad<std::remove_const_t<std::remove_reference_t<T>>> pure(T&& val) {
static_assert(is_monad<Monad>{}(), "");
return Monad<std::remove_const_t<std::remove_reference_t<T>>> { std::forward<decltype(val)>(val) };
}
// liftM
template <template <typename, typename...> class Monad, typename funcType>
auto liftM(funcType&& f) {
static_assert(is_monad<Monad>{}(), "");
return [_f = std::forward<decltype(f)>(f)] (auto x) {
return ap(pure<Monad>(_f), x);
};
}
// fmap
template <template <typename, typename...> class Monad, typename T, typename funcType>
auto fmap(funcType&& f, Monad<T> const& x) {
static_assert(is_monad<Monad>{}(), "");
return x >>= ( [_f = std::forward<funcType>(f)] (const T& val) {
return Monad<decltype(_f(std::declval<T>()))> {_f(val)}; });
}
让我们看看我们如何使用它,假设你已经实现operator>>=了std::vector和optional.
// functor similar to std::plus<>, etc.
template <typename T = void>
struct square {
auto operator()(T&& x) {
return x * std::forward<decltype(x)>(x);
}
};
template <>
struct square<void> {
template <typename T>
auto operator()(T&& x) const {
return x * std::forward<decltype(x)>(x);
}
};
int main(int, char**) {
auto vector_empty = std::vector<double>{};
auto vector_with_values = std::vector<int>{2, 3, 31};
auto optional_with_value = optional<double>{42.0};
auto optional_empty = optional<int>{};
auto v1 = liftM<std::vector>(square<>{})(vector_empty); // still an empty vector
auto v2 = liftM<std::vector>(square<>{})(vector_with_values); // == vector<int>{4, 9, 961};
auto o1 = liftM<optional>(square<>{})(optional_empty); // still an empty optional
auto o2 = liftM<optional>(square<>{})(optional_with_value); // == optional<int>{1764.0};
std::cout << std::boolalpha << is_monad<std::vector>::value << std::endl; // prints true
std::cout << std::boolalpha << is_monad<std::list>::value << std::endl; // prints false
}
虽然这允许以通用方式定义monad的概念并且使monadic类型构造函数的直接实现,但是存在一些缺点.
首先,我不知道有一种方法可以让编译器推断使用哪种类型的构造函数来创建模板化类型,即我不知道必须编译器发现该std::vector模板已被用于创建类型std::vector<int>.因此,您必须在调用例如fmap.的实现中手动添加类型构造函数的名称.
其次,编写适用于泛型monad的函数是非常难看的,正如你可以看到ap和liftM.另一方面,这些必须只写一次.最重要的是,一旦我们获得概念,整个方法将变得更容易编写和使用(希望在C++ 2x中).
最后但并非最不重要的是,在我写下来的形式中,Haskell monad的大部分优点都无法使用,因为它们严重依赖于currying.例如,在此实现中,您只能通过仅使用一个参数的monad映射函数.在我的github上你可以找到一个也有currying支持的版本,但语法更糟糕.
对于感兴趣的人来说,这是一个coliru.
编辑:我只是注意到我错误的事实是编译器不能推断,Monad = std::vector并T = int在提供类型的参数时std::vector<int>.这意味着您可以使用统一的语法将函数映射到任意容器上fmap,即
auto v3 = fmap(square<>{}, v2);
auto o3 = fmap(square<>{}, o2);
编译并做正确的事.
我把这个例子添加到了coliru.
我担心Haskell风格的多态性和C++模板在实际上可以使用的方式实际上在C++中实际定义monad是太过分了.
从技术上讲,您可以将monad定义为M以下形式的模板类(我将按值传递所有内容以保持简单)
template <typename A>
struct M {
// ...
// this provides return :: a -> M a
M(A a) { .... }
// this provides (>>=) :: M a -> (a -> M b) -> M b
template <typename B>
M<B> bind(std::function< M<B> (A) > f) { ... }
// this provides flip fmap :: M a -> (a -> b) -> M b
template <typename B>
M<B> map(std::function< B (A) > f) { ... }
};
这可能有用(我不是C++专家),但我不确定它是否可以在C++中使用.肯定会导致非惯用代码.
然后,您的问题是如何要求类具有此类接口.你可以用类似的东西
template <typename A>
struct M : public Monad<M, A> {
...
};
哪里
template <template <typename T> M, typename A>
class Monad {
// this provides return :: a -> M a
Monad(A a) = 0;
// this provides (>>=) :: M a -> (a -> M b) -> M b
template <typename B>
M<B> bind(std::function< M<B> (A) > f) = 0;
// this provides flip fmap :: M a -> (a -> b) -> M b
template <typename B>
M<B> map(std::function< B (A) > f) = 0;
};
可惜,
monads.cpp:31:44: error: templates may not be ‘virtual’
M<B> bind(std::function< M<B> (A) > f) = 0;
模板看起来类似于多态函数,但它们是不同的东西.
新方法似乎有效,但它没有:
template <template <typename T> typename M, typename A>
class Monad {
// this provides return :: a -> M a
Monad(A a) = 0;
// this provides (>>=) :: M a -> (a -> M b) -> M b
template <typename B>
M<B> bind(std::function< M<B> (A) > f);
// this provides flip fmap :: M a -> (a -> b) -> M b
template <typename B>
M<B> map(std::function< B (A) > f);
};
// The identity monad, as a basic case
template <typename A>
struct M : public Monad<M, A> {
A x;
// ...
// this provides return :: a -> M a
M(A a) : x(a) { }
// this provides (>>=) :: M a -> (a -> M b) -> M b
template <typename B>
M<B> bind(std::function< M<B> (A) > f) {
return f(x);
}
// this provides flip fmap :: M a -> (a -> b) -> M b
template <typename B>
M<B> map(std::function< B (A) > f) {
return M(f(x));
}
};
但是,map从M类型中删除不会触发类型错误.实际上,错误只会在实例化时产生.模板不再forall是.