4 ms·
The concept (lower case c) of monads cannot be represented in C++, but you can certainly write monads in it like in just about any language. You just can't make
by Sharlin 13y ago
The concept (lower case c) of monads cannot be represented in C++, but you can certainly write monads in it like in just about any language. You just can't make the compiler verify that what you have is actually a monad. As you suspect, Concepts (capital C) should make it possible to type-check monads in C++ like in Haskell).
- dllthomas 13y agoYou can't make the compiler check monad laws in Haskell, either. It would seem to me you should be able to write a Monad template class, though I admittedly haven't tried. Edited to add: Ah, it seems a template argument can't itself be a template, which would seem to rule it out (though I'm running on very little sleep, so I might very well be wrong).
- ajtulloch 13y agoYou can use templated template parameters in C++ - http://stackoverflow.com/questions/213761/what-are-some-uses-of-template-template-parameters-in-c http://stackoverflow.com/questions/213761/what-are-some-uses...
- dllthomas 13y agoAh, so you can! Here's the list monad. I'm not sure the type unification on templates is sophisticated enough to get all of the niceness of Haskell monads (I wasn't able to get bind to work generically, for instance, and I'm not sure what would happen with another instance of pure differentiated only by return type...) and certainly there's no do-notation), but clearly the functionality can be expressed. Still fun. It prints the results of expressions prefixed by their (loose) Haskell equivalents. Applicative included for good measure. #include <iostream> #include <list> #include <functional> using namespace std; // fmap :: (a -> b) -> f a -> f b template <template<typename> class F, typename A, typename B> F<B> fmap(function<B (A)>, const F<A> &); // pure :: a -> f a template <template<typename> class F, typename A> F<A> pure(A); // appl :: f (a -> b) -> f a -> f b template <template<typename> class F, typename A, typename B> F<B> appl(F< function<B (A)> >, F<A>); // join :: m (m a) -> m a template <template<typename> class M, typename A> M<A> join(M< M<A> >); // mbind :: m a -> (a -> m b) -> m b template <template<typename> class M, typename A, typename B> M<A> mbind(M<A> &x, function<M<B> (A)> f); template <typename A, typename B> list<B> fmap(function<B (A)> f, list<A> xs) { list<B> ys; for(auto x : xs) { ys.push_back(f(x)); } return ys; } template <typename A> list<A> pure(A x) { return { x }; } template <typename A, typename B> list<B> appl(list< function<B (A)> > fs, list<A> xs) { list<B> ys; for(auto f : fs) for(auto x : xs) ys.push_back(f(x)); return ys; } template <typename A> list<A> join(list< list<A> > xss) { list<A> ys; for(auto xs : xss) for(auto x : xs) ys.push_back(x); return ys; } template <typename A, typename B> list<A> mbind(const list<A> &x, function<list<B> (A)> f) { return join(fmap(f, x)); } template <typename A> ostream &operator<<(ostream &out, const list<A> &xs) { int i = 0; cout << "["; for(auto x : xs) { out << (i++ ? ", " : " ") << x; } cout << " ]"; } int main() { list<int> xs = {1,2,3}; function<double (int)> halve = [] (int x) -> double { return 0.5 * x; }; function<double (int)> quarter = [] (int x) -> double { return 0.25 * x; }; function<list<int> (int)> repeatOnce = [] (int x) -> list<int> { list<int> ys = { x, x }; return ys; }; function<list<int> (int)> repeatIfEven = [&] (int x) { if(x % 2) return pure(x); return repeatOnce(x); }; list< function<double (int)> > fs = { halve, quarter }; cout << "return 7 = " << pure(7) << endl; cout << "xs = " << xs << endl; cout << "fmap halve xs = " << fmap(halve, xs) << endl; cout << "fmap repeatOnce xs = " << fmap(repeatOnce, xs) << endl; cout << "fs <*> xs = " << appl(fs, xs) << endl; cout << "xs >>= repeatOnce = " << mbind(xs, repeatOnce) << endl; cout << "xs >>= repeatOnce >>= repeatOnce = " << mbind(mbind(xs, repeatOnce), repeatOnce) << endl; cout << "xs >>= repeatIfEven = " << mbind(xs, repeatIfEven) << endl; return 0; }
- detrino 13y agoNice result :) Btw, it's tempting to use std::function in the same way as you would use a function in Haskell, but it usually isn't a very good idea. In C++ std::function is for when you want type erasure, usually because you wish to store a functor somewhere with a uniform type. Type erasure in C++ is similar to existential typing + a type class in Haskell. You could say that all Haskell closures are implicitly using type erasure and then the compiler has to work hard to optimize away the extra boxing/indirect calls. Here is another way to write map in C++: #include <iostream> #include <list> template<typename F, typename A, typename B = typename std::result_of<F(A)>::type> std::list<B> map(std::list<A> const & xs, F f) { std::list<B> ys; for (auto const & x : xs) ys.push_back(f(x)); return ys; } int main() { std::list<int> xs{1, 2, 3, 4, 5}; auto ys = map(xs, [](int i) { return i * 2; }); for (auto y : ys) std::cout << y << "\n"; } You can expect this code to run exactly as fast as if you had written the loop by hand instead of using the map template function.
- dllthomas 13y agoYeah, wasn't meant to be idiomatic C++ code, just a simple proof-of-concept. If you'd care to translate it into the former I'd be fascinated to see the result. Playing around a bit, I've been having trouble expressing the type of mbind when I make the function type a parameter to the template. I'm 70% sure it's my failure, not the language, though.
- deleted 13y ago[deleted]
- detrino 13y agoThat's not really true. A C++ compiler will verify that an instantiated template type checks. What concepts gives you is better error messages, overloading, and I presume it allows type checking of uninstantiated templates.