Skip to content

Instantly share code, notes, and snippets.

@brotchie

brotchie/main.cpp

Created July 18, 2012 06:32
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save brotchie/3134600 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save brotchie/3134600 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. brotchie revised this gist Jul 18, 2012. 1 changed file with 24 additions and 6 deletions.
    30 changes: 24 additions & 6 deletions main.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -38,6 +38,11 @@ static F<B> fmap_(function <B(A)> f, F<A> v) {
    return Functor<F>::fmap(f)(v);
    }

    template <template <typename...> class F, typename A, typename B>
    static F<B> operator %(function <B(A)> f, F<A> v) {
    return Functor<F>::fmap(f)(v);
    }

    /* Monad */
    template <template <typename...> class F>
    struct Monad {
    @@ -58,6 +63,17 @@ static F<A> return_(A a) {
    return Monad<F>::return_(a);
    }

    template <template <typename...> class F, typename A, typename B>
    static F<B> operator >=(F<A> m, function<F<B>(A)> f) {
    return Monad<F>::bind(m, f);
    }

    template <template <typename...> class F, typename A, typename B>
    static F<B> operator >>(F<A> a, F<B> b) {
    function<F<B>(A)> f = [b](A){ return b; };
    return a >= f;
    }

    /* Maybe */
    template <typename T>
    class Maybe {
    @@ -165,6 +181,7 @@ static function<C(A)> compose(function<B(A)> f1, function<C(B)> f2) {
    };
    }


    int main(int argc, char *argv[]){
    /* Returns the length of a string. */
    function<int(string)> length = [](string s){return s.size();};
    @@ -184,8 +201,8 @@ int main(int argc, char *argv[]){
    cout << "\t" << nothing << endl;

    cout << "Maybes fmapped with length:" << endl;
    cout << "\t" << fmap_(length, just) << endl;
    cout << "\t" << fmap_(length, nothing) << endl;
    cout << "\t" << length % just << endl;
    cout << "\t" << length % nothing << endl;

    /* A function to test monadic bind on Maybe.
    * Returns Just x if x > 5 otherwise Nothing.
    @@ -199,14 +216,15 @@ int main(int argc, char *argv[]){
    cout << "\t" << bad << endl;

    cout << "After bind (if x > 5 Just x else Nothing):" << endl;
    cout << "\t" << bind(good, fm) << endl;
    cout << "\t" << bind(bad, fm) << endl;
    //cout << "\t" << bind(good, fm) << endl;
    cout << "\t" << (good >= fm) << endl;
    cout << "\t" << (bad >= fm) << endl;

    function<vector<int>(int)> fv = [](int v){ return vector<int>{v,v*v};};
    cout << "Monadic bind on vector \\v -> [v,v*v]:" << endl;
    vector<int> v{1,2,3,4,5};
    vector<int> vr = bind(v, fv);
    vector<int> vrr = bind(bind(v, fv), fv);
    vector<int> vr = v >= fv;
    vector<int> vrr = v >= fv >= fv;
    cout << "\t";
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl << "\t";
  2. brotchie created this gist Jul 18, 2012.
    219 changes: 219 additions & 0 deletions main.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,219 @@
    /*
    * Minimal C++ implementation of Functor, Monad and Maybe.
    *
    * Requires c++0x variadic templates and lambda expressions:
    *
    * g++ -std=c++0x main.cpp -o main
    *
    * fmap, monadic bind and return implementations for std::vector
    * and Maybe.
    *
    * Copyright 2012 James Brotchie <[email protected]>
    * https://github.com/brotchie/
    * @brotchie
    *
    */

    #include <iostream>
    #include <vector>
    #include <iterator>
    #include <algorithm>

    using namespace std;

    /* Functor */
    template <template <typename...> class F>
    struct Functor {
    template <typename A, typename B>
    static function <F<B>(F<A>)> fmap(function <B(A)>);
    };

    template <template <typename...> class F, typename A, typename B>
    static function <F<B>(F<A>)> fmap(function <B(A)> f) {
    return Functor<F>::fmap(f);
    }

    template <template <typename...> class F, typename A, typename B>
    static F<B> fmap_(function <B(A)> f, F<A> v) {
    return Functor<F>::fmap(f)(v);
    }

    /* Monad */
    template <template <typename...> class F>
    struct Monad {
    template <typename A>
    static F<A> return_(A);

    template <typename A, typename B>
    static F<B> bind(F<A>, function<F<B>(A)>);
    };

    template <template <typename...> class F, typename A, typename B>
    static F<B> bind(F<A> m, function<F<B>(A)> f) {
    return Monad<F>::bind(m, f);
    }

    template <template <typename...> class F, typename A>
    static F<A> return_(A a) {
    return Monad<F>::return_(a);
    }

    /* Maybe */
    template <typename T>
    class Maybe {
    public:
    Maybe() : _empty(true){};
    explicit Maybe(T value) : _empty(false), _value(value){};

    T fromJust() const {
    if (isJust()) {
    return _value;
    } else {
    throw "Cannot get value from Nothing";
    }
    }

    bool isJust() const { return !_empty; }
    bool isNothing() const { return _empty; }

    static bool isJust(Maybe &m) { return m.isJust(); }
    static bool isNothing(Maybe &m) { return m.isNothing(); }
    private:
    bool _empty;
    T _value;
    };

    template <typename T>
    ostream& operator<<(ostream& s, const Maybe<T> m)
    {
    if (m.isJust()) {
    return s << "Just " << m.fromJust();
    } else {
    return s << "Nothing";
    }
    }

    /* Functor Maybe */
    template <>
    struct Functor<Maybe> {
    template <typename A, typename B>
    static function <Maybe<B>(Maybe<A>)> fmap(function <B(A)> f) {
    return [f](Maybe<A> m) -> Maybe<B> {
    if (m.isNothing()) {
    return Maybe<B>();
    } else {
    return Maybe<B>(f(m.fromJust()));
    }
    };
    };
    };

    /* Monad Maybe */
    template <>
    struct Monad<Maybe> {
    template <typename A>
    static Maybe<A> return_(A v){
    return Maybe<A>(v);
    }

    template <typename A, typename B>
    static Maybe<B> bind(Maybe<A> m, function<Maybe<B>(A)> f){
    if (m.isNothing()){
    return Maybe<B>();
    } else {
    return f(m.fromJust());
    }
    }
    };

    /* Functor vector */
    template <>
    struct Functor<vector> {
    template <typename A, typename B>
    static function <vector<B>(vector<A>)> fmap(function <B(A)> f) {
    return [f](vector<A> v){
    vector<B> result;
    transform(v.begin(), v.end(), back_inserter(result), f);
    return result;
    };
    }
    };

    /* Monad vector */
    template <>
    struct Monad<vector> {
    template <typename A>
    static vector<A> return_(A v){
    return vector<A>{v};
    }

    template <typename A, typename B>
    static vector<B> bind(vector<A> m, function<vector<B>(A)> f){
    vector<B> v;
    for_each(m.begin(), m.end(), [f, &v](A a){
    vector<B> result = f(a);
    copy(result.begin(), result.end(), back_inserter(v));
    });
    return v;
    }
    };

    template <typename A, typename B, typename C>
    static function<C(A)> compose(function<B(A)> f1, function<C(B)> f2) {
    return [f1,f2](A v) -> C {
    return f2(f1(v));
    };
    }

    int main(int argc, char *argv[]){
    /* Returns the length of a string. */
    function<int(string)> length = [](string s){return s.size();};

    /* Squares an integer arugment. */
    function<int(int)> square = [](int i) { return i*i; };

    /* Tests function composition. */
    cout << "Square of length of \"testing 1234\": " <<
    compose(length, square)("testing 1234") << endl;

    Maybe<string> just("Hello World");
    Maybe<string> nothing;

    cout << "Untouched Maybes:" << endl;
    cout << "\t" << just << endl;
    cout << "\t" << nothing << endl;

    cout << "Maybes fmapped with length:" << endl;
    cout << "\t" << fmap_(length, just) << endl;
    cout << "\t" << fmap_(length, nothing) << endl;

    /* A function to test monadic bind on Maybe.
    * Returns Just x if x > 5 otherwise Nothing.
    */
    function<Maybe<int>(int)> fm = [](int v){ return v > 5 ? Maybe<int>(v) : Maybe<int>(); };

    auto good = return_<Maybe>(6);
    auto bad = return_<Maybe>(4);
    cout << "Before bind:" << endl;
    cout << "\t" << good << endl;
    cout << "\t" << bad << endl;

    cout << "After bind (if x > 5 Just x else Nothing):" << endl;
    cout << "\t" << bind(good, fm) << endl;
    cout << "\t" << bind(bad, fm) << endl;

    function<vector<int>(int)> fv = [](int v){ return vector<int>{v,v*v};};
    cout << "Monadic bind on vector \\v -> [v,v*v]:" << endl;
    vector<int> v{1,2,3,4,5};
    vector<int> vr = bind(v, fv);
    vector<int> vrr = bind(bind(v, fv), fv);
    cout << "\t";
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl << "\t";
    copy(vr.begin(), vr.end(), ostream_iterator<int>(cout, " "));
    cout << endl << "\t";
    copy(vrr.begin(), vrr.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
    }