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