list monad in c++ 11

listMonad11.cpp

    //https://news.ycombinator.com/item?id=7319417
    
    #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;
    }
    
    //https://news.ycombinator.com/item?id=7319417