Created
July 18, 2012 06:32
-
-
Save brotchie/3134600 to your computer and use it in GitHub Desktop.
Minimal C++ implementation of Functor, Monad and Maybe using c++0x variadic templates and lambda expressions.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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 <brotchie@gmail.com> | |
* 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); | |
} | |
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 { | |
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); | |
} | |
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 { | |
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" << length % just << endl; | |
cout << "\t" << 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" << (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 = v >= fv; | |
vector<int> vrr = 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment