5 ms·

From skimming the article I can't tell if C++ will have anything akin to type classes, which is how Monad is expressed in Haskell? Is that what "Concepts" will

by sixbrx 13y ago

From skimming the article I can't tell if C++ will have anything akin to type classes, which is how Monad is expressed in Haskell? Is that what "Concepts" will bring and which enables Monad to be expressed as well?

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 ago
  You 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 ago
    You 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 ago
      Ah, 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 ago
        Nice 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 ago
        Yeah, 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 ago
  That'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.
Periodic 13y ago
Right, the article in question is just pointing out how C++ is implementing a specific monad. In this case the values of futures and then the futures library implements all the functions require for them to be a monad. The C++ spec certainly doesn't call them that and don't provide a generalized monad. I think the main point to take away is that this is a case where a monad is the right abstraction and can be implemented very logically, but since C++ doesn't and cannot really speak about monads directly, there comes a lot of boilerplate and you lose a lot of "free" utility functions you'd get in a language that can talk about arbitrary monads.
detrino 13y ago
C++ doesn't need type classes as it has more powerful overloading. this is valid C++14: template<typename A, typename B> auto add(A a, B b) { return a + b; }
- eru 13y ago
  Can overloading express parametricity?
  - detrino 13y ago
    Can you give an example of what you mean?
    - eru 13y ago
      E.g. the type of map is map :: forall a b. (a -> b) -> [a] -> [b] The important part here is the `forall'. This means, that Haskell guarantees that essentially the map function can not look at the elements of your list. The only way for map to produce a value of type `b' is to apply the given call-back on an `a'. So you know that `map' can not eg add up your `a's. Compare C++'s templates and overloading, where more function definitions with more specific types have precedence over more general ones. See the first answer of https://stackoverflow.com/questions/18180428/is-parametric-polymorphism-the-same-as-dispatching-on-arity https://stackoverflow.com/questions/18180428/is-parametric-p... for some discussion.
      - deleted 13y ago
        [deleted]
      - detrino 13y ago
        This doesn't appear to have anything to do with type classes or overloading, but rather with (unconstrained) parametric polymorphism. Such a function is easy to write in C++, but the function prototype can not provide a strong guarantee that your b value will only be produced by your callback.

by sixbrx 13y ago

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 ago
You 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 ago
  You 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 ago
    Ah, 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 ago
      Nice 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 ago
        Yeah, 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 ago
That'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.

Periodic 13y ago

Right, the article in question is just pointing out how C++ is implementing a specific monad. In this case the values of futures and then the futures library implements all the functions require for them to be a monad. The C++ spec certainly doesn't call them that and don't provide a generalized monad. I think the main point to take away is that this is a case where a monad is the right abstraction and can be implemented very logically, but since C++ doesn't and cannot really speak about monads directly, there comes a lot of boilerplate and you lose a lot of "free" utility functions you'd get in a language that can talk about arbitrary monads.

detrino 13y ago

C++ doesn't need type classes as it has more powerful overloading. this is valid C++14: template<typename A, typename B> auto add(A a, B b) { return a + b; }

eru 13y ago
Can overloading express parametricity?
- detrino 13y ago
  Can you give an example of what you mean?
  - eru 13y ago
    E.g. the type of map is map :: forall a b. (a -> b) -> [a] -> [b] The important part here is the `forall'. This means, that Haskell guarantees that essentially the map function can not look at the elements of your list. The only way for map to produce a value of type `b' is to apply the given call-back on an `a'. So you know that `map' can not eg add up your `a's. Compare C++'s templates and overloading, where more function definitions with more specific types have precedence over more general ones. See the first answer of https://stackoverflow.com/questions/18180428/is-parametric-polymorphism-the-same-as-dispatching-on-arity https://stackoverflow.com/questions/18180428/is-parametric-p... for some discussion.
    - deleted 13y ago
      [deleted]
    - detrino 13y ago
      This doesn't appear to have anything to do with type classes or overloading, but rather with (unconstrained) parametric polymorphism. Such a function is easy to write in C++, but the function prototype can not provide a strong guarantee that your b value will only be produced by your callback.