Monadic parsing in C++

monad-parser.cpp

#include <memory>
#include <iostream>
#include <sstream>
#include <utility>
#include <algorithm>
#include <iterator>

struct sequence_tag {};
struct pointer_tag {};

template< class X >
X category( ... );

template< class S >
auto category( const S& s ) -> decltype( std::begin(s), sequence_tag() );

template< class Ptr >
auto category( const Ptr& p ) -> decltype( *p, p==nullptr, pointer_tag() );

template< class T > struct Category {
    using type = decltype( category<T>(std::declval<T>()) );
};

template< class R, class ... X > struct Category< R(&)(X...) > {
    using type = R(&)(X...);
};

template< class T >
using Cat = typename Category< typename std::decay<T>::type >::type;

template<class...> struct Part;

template< class F, class X >
struct Part< F, X >
{
    F f;
    X x;

    template< class _F, class _X >
    constexpr Part( _F&& f, _X&& x )
        : f(std::forward<_F>(f)), x(std::forward<_X>(x))
    {
    }

    /* 
     * The return type of F only gets deduced based on the number of xuments
     * supplied. Part otherwise has no idea whether f takes 1 or 10 xs.
     */
    template< class ... Xs >
    constexpr auto operator() ( Xs&& ...xs )
        -> decltype( f(x,std::declval<Xs>()...) )
    {
        return f( x, std::forward<Xs>(xs)... );
    }
};

/* Recursive, variadic version. */
template< class F, class X1, class ...Xs >
struct Part< F, X1, Xs... > 
    : public Part< Part<F,X1>, Xs... >
{
    template< class _F, class _X1, class ..._Xs >
    constexpr Part( _F&& f, _X1&& x1, _Xs&& ...xs )
        : Part< Part<F,X1>, Xs... > (
            Part<F,X1>( std::forward<_F>(f), std::forward<_X1>(x1) ),
            std::forward<_Xs>(xs)...
        )
    {
    }
};

template< class F, class ...X >
constexpr Part<F,X...> closure( F&& f, X&& ...x ) {
    return Part<F,X...>( std::forward<F>(f), std::forward<X>(x)... );
}

template< class F, class ...X >
constexpr Part<F,X...> closet( F f, X ...x ) {
    return Part<F,X...>( std::move(f), std::move(x)... );
}

template< class F, class ...G >
struct Composition;

template< class F, class G >
struct Composition<F,G>
{
    F f; G g;

    template< class _F, class _G >
    constexpr Composition( _F&& f, _G&& g ) 
        : f(std::forward<_F>(f)), g(std::forward<_G>(g)) { }

    template< class X, class ...Y >
    constexpr decltype( f(g(std::declval<X>()), std::declval<Y>()...) )
    operator() ( X&& x, Y&& ...y ) {
        return f( g( std::forward<X>(x) ), std::forward<Y>(y)... );
    }
};

template< class F, class G, class ...H >
struct Composition<F,G,H...> : Composition<F,Composition<G,H...>>
{
    typedef Composition<G,H...> Comp;

    template< class _F, class _G, class ..._H >
    constexpr Composition( _F&& f, _G&& g, _H&& ...h )
        : Composition<_F,Composition<_G,_H...>> ( 
            std::forward<_F>(f), 
            Comp( std::forward<_G>(g), std::forward<_H>(h)... )
        )
    {
    }
};

template< class F, class ...G >
constexpr Composition<F,G...> compose( F f, G ...g ) {
    return Composition<F,G...>( std::move(f), std::move(g)... );
}

template< class ... > struct Monad;

template< class F, class M, class ...N, class Mo=Monad<Cat<M>> >
constexpr auto mbind( F&& f, M&& m, N&& ...n ) 
    -> decltype( Mo::mbind(std::declval<F>(),
                           std::declval<M>(),std::declval<N>()...) )
{
    return Mo::mbind( std::forward<F>(f), 
                      std::forward<M>(m), std::forward<N>(n)... );
}

template< class F, class M, class ...N, class Mo=Monad<Cat<M>> >
constexpr auto mdo( F&& f, M&& m ) 
    -> decltype( Mo::mdo(std::declval<F>(), std::declval<M>()) )
{
    return Mo::mdo( std::forward<F>(f), std::forward<M>(m) );
}

// The first template argument must be explicit!
template< class M, class X, class ...Y, class Mo = Monad<Cat<M>> >
constexpr auto mreturn( X&& x, Y&& ...y ) 
    -> decltype( Mo::template mreturn<M>( std::declval<X>(),
                                          std::declval<Y>()... ) )
{
    return Mo::template mreturn<M>( std::forward<X>(x), 
                                    std::forward<Y>(y)... );
}

template< template<class...>class M, class X, class ...Y,
    class _M = M< typename std::decay<X>::type >,
    class Mo = Monad<Cat<_M>> >
constexpr auto mreturn( X&& x, Y&& ...y ) 
    -> decltype( Mo::template mreturn<_M>( std::declval<X>(),
                                           std::declval<Y>()... ) )
{
    return Mo::template mreturn<_M>( std::forward<X>(x),
                                     std::forward<Y>(y)... );
}

// Also has explicit template argument.
template< class M, class Mo = Monad<Cat<M>> >
auto mfail() -> decltype( Mo::template mfail<M>() ) {
    return Mo::template mfail<M>();
}

template< class M, class F >
constexpr auto operator >>= ( M&& m, F&& f ) 
    -> decltype( mbind(std::declval<F>(),std::declval<M>()) )
{
    return mbind( std::forward<F>(f), std::forward<M>(m) );
}

template< class M, class F >
constexpr auto operator >> ( M&& m, F&& f ) 
    -> decltype( mdo(std::declval<M>(),std::declval<F>()) )
{
    return mdo( std::forward<M>(m), std::forward<F>(f) );
}

template< class F, class M >
constexpr auto operator ^ ( F&& f, M&& m ) 
    -> decltype( fmap(std::declval<F>(),std::declval<M>()) )
{
    return fmap( std::forward<F>(f), std::forward<M>(m) );
}

template< > struct Monad< sequence_tag > {

    template< class S >
    using mvalue = typename S::value_type;

    template< class F, template<class...>class S, class X,
        class R = typename std::result_of<F(X)>::type >
    static R mbind( F&& f, const S<X>& xs ) {
        R r;
        for( const X& x : xs ) {
            auto ys = std::forward<F>(f)( x );
            std::move( std::begin(ys), std::end(ys), std::back_inserter(r) );
        }
        return r;
    }

    template< class F, template<class...>class S, 
              class X, class Y,
              class R = typename std::result_of<F(X,Y)>::type >
    static R mbind( F&& f, const S<X>& xs, const S<Y>& ys ) {
        R r;
        for( const X& x : xs ) {
            for( const Y& y : ys ) {
                auto zs = std::forward<F>(f)( x, y );
                std::move( std::begin(zs), std::end(zs), 
                           std::back_inserter(r) );
            }
        }
        return r;
    }

    template< template< class... > class S, class X, class Y >
    static S<Y> mdo( const S<X>& mx, const S<Y>& my ) {
        // Note: This is not a strictly correct definition. 
        // It should return my concatenated to itself for every element of mx.
        return mx.size() ? my : S<Y>{};
    }

    template< class S, class X >
    static S mreturn( X&& x ) {
        return S{ std::forward<X>(x) }; // Construct an S of one element.
    }

    template< class S >
    static S mfail() { return S{}; }
};

constexpr bool is_int( char c ) {
    return c >= '0' and c <= '9';
}

/* A Parser is a function taking a string and returning a vector of matches. */
template< class X > struct Parser {
    // The value is the target of the parse. (For example "1" may parse to int(1).
    using value_type    = X;

    // A match consists of a value and the rest of the input to process.
    using parse_state   = std::pair<X,std::string>;

    // A parse results in a list of matches.
    using result_type   = std::vector< std::pair<X,std::string> >;

    using function_type = std::function< result_type( const std::string& ) >;

    function_type f;

    Parser( function_type f ) : f(std::move(f)) { }

    Parser( const Parser<X>& p ) : f(p.f) { }
    Parser() { }

    result_type operator () ( const std::string& s ) const {
        return f( s );
    }
};

template< class X, class F > Parser<X> parser( F f ) {
    using G = typename Parser<X>::function_type;
    return Parser<X>( G(std::move(f)) );
}

std::string tail( const std::string& s ) {
    return std::string( std::next(s.begin()), s.end() );
}

/* 
 * Unconditionally match a char if the string is not empty.
 * Ex: item("abc") = ('a',"bc")
 */
auto item = parser<char> (
    []( const std::string& s ) {
        using Pair = Parser<char>::parse_state;
        using R = Parser<char>::result_type;
        return s.size() ? R{ Pair( s[0], tail(s) ) } : R();
    }
);

template< class X > struct Monad< Parser<X> > {
    using Pair = typename Parser<X>::parse_state;
    using R    = typename Parser<X>::result_type;

    /* 
     * mreturn x = parser(s){ vector( pair(x,s) ) }
     * Return a parsed value. Forwards rest of input to the next parser.
     */
    template< class M >
    static M mreturn( X x ) {
        return parser<typename M::value_type> (
            [x]( const std::string& s ) { 
                return R{ Pair(std::move(x),s) }; 
            }
        );
    }
    
    /* a >> b = b */
    template< class Y, class Z >
    static Parser<Y> mdo( Parser<Z> a, Parser<Y> b ) {
        return a >>= [b]( const Z& z ) { return b; };
    }

    /* Continue parsing from p into f. */
    template< class F, class Y = typename std::result_of<F(X)>::type >
    static Y mbind( F f, Parser<X> p ) 
    {
        using Z = typename Y::value_type;
        return parser<Z> (
                [f,p]( const std::string& s ) {
                    // First, extract p's matches.
                    return p(s) >>= [&]( Pair p ) {
                        // Then construct the new parser from the p's output.
                        // Continue parsing the remaining input with the new parser.
                        return f( std::move(p.first) )( std::move(p.second) );
                    };
                }
        );
    }
};

template< class ... > struct MonadZero;
template< class ... > struct MonadPlus;

template< class M, class Mo = MonadZero< Cat<M> > >
auto mzero() -> decltype( Mo::template mzero<M>() )
{
    return Mo::template mzero<M>();
}

template< class A, class B, class Mo = MonadPlus<Cat<A>> >
auto mplus( A&& a, B&& b ) -> decltype( Mo::mplus(std::declval<A>(),std::declval<B>()) )
{
    return Mo::mplus( std::forward<A>(a), std::forward<B>(b) );
}

template<> struct MonadZero< sequence_tag > {
    template< class S >
    S mzero() { return S{}; }
};

/* mzero: a parser that matches nothing, no matter the input. */
template< class X > struct MonadZero< Parser<X> > {
    template< class P >
    static P mzero() { 
        return parser<X> (
            []( const std::string& s ){
                return std::vector<std::pair<X,std::string>>(); 
            }
        );
    }
};

template< class X, class Y >
auto operator + ( X&& x, Y&& y ) -> decltype( mplus(std::declval<X>(),std::declval<Y>()) )
{
    return mplus( std::forward<X>(x), std::forward<Y>(y) );
}

/* mplus( xs, ys ) = "append xs with ys" */
template<> struct MonadPlus< sequence_tag > {
    template< class A, class B >
    static A mplus( A a, const B& b ) {
        std::copy( b.begin(), b.end(), std::back_inserter(a) );
        return a;
    }
};

/* mplus( pa, pb ) = "append the results of pa with the results of pb" */
template< class X > struct MonadPlus< Parser<X> > {
    using P = Parser<X>;
    static P mplus( P a, P b ) {
        return parser<X> (
            [=]( const std::string& s ) { return a(s) + b(s); }
        );
    }
};

/* Like mplus, but take only one result. */
template< class X >
Parser<X> mplus_first( const Parser<X>& a, const Parser<X>& b ) {
    return parser<X> (
        [=]( const std::string s ) {
            using V = std::vector< std::pair< X, std::string > >;
            V c = (a + b)( s );
            return c.size() ?  V{ c[0] } : V{};
        }
    );
}

/* sat( pred ) = "item, if pred" */
template< class P >
Parser<char> sat( P p ) {
    return item >>= [=]( char c ) { 
        return p(c) ? mreturn<Parser>(c) : mzero<Parser<char>>();
    };
}

/* Accept only a specific char. */
Parser<char> pchar( char c ) {
    return sat( [=](char d){ return c == d; } );
}

/* Accept only a specific string. */
Parser<std::string> string_( const std::string& s ) {
    if( s.size() == 0 )
        return mreturn<Parser>( s );

    Parser<char> p = pchar( s[0] );
    for( auto it=std::next(s.begin()); it != s.end(); it++ )
        p = p >> pchar( *it );

    return p >> mreturn<Parser>(s);
}

Parser<std::string> string( const std::string& str ) {
    return parser<std::string> (
        [str]( const std::string& s ) {
            using R = typename Parser<std::string>::result_type;
            if( std::equal(str.begin(),str.end(),s.begin()) ) {
                return R {
                    { str, s.substr( str.size() ) }
                };
            } else {
                return R();
            }
        }
    );
}

template< class X >
Parser<std::vector<X>> many( Parser<X> p );
template< class X >
Parser<std::vector<X>> many1( Parser<X> p );

/* Parse one or zero items with p. */
template< class X >
Parser<std::vector<X>> many( Parser<X> p ) {
    using V = std::vector<X>;
    using Pair = std::pair<V,std::string>;
    using R = std::vector< Pair >;
    using P = Parser<V>;
    return mplus( 
        parser<V> (
            [=]( const std::string& s ) {
                auto matches = p(s);

                if( not matches.size() )
                    return R{};

                else {
                    // Recurse with the rest of the input.
                    R rest = many(p)( matches[0].second );

                    // Create a vector out of the result from the first match.
                    V first = { std::move(matches[0].first) };

                    // Prepend the previous result to every new match.
                    for( auto& match : rest ) 
                        match = Pair( first + match.first, match.second );

                    // Return all the matches.
                    return R { 
                        Pair( std::move(first), matches[0].second ) 
                    } + rest;
                }
            }
        ),
        mreturn<Parser>( V{} )
    );
}

/* Parse one or zero items with p. */
template< class X >
Parser<std::vector<X>> some( Parser<X> p ) {
    using V = std::vector<X>;
    using Pair = std::pair<V,std::string>;
    using R = std::vector< Pair >;
    using P = Parser<V>;
    return mplus_first( 
        parser<V> (
            [=]( const std::string& s ) {
                auto matches = p(s);

                return matches.size() == 0 ? R{}
                    : R{ 
                        Pair( 
                            V{std::move(matches[0].first)}, 
                            std::move( matches[0].second )
                        ) 
                    };
            }
        ),
        mreturn<Parser>( V{} )
    );
}

template< class X >
using ManyParser = Parser< std::vector<X> >;

ManyParser<char> space = some( sat([](char c){return std::isspace(c);}) );

/* Parses p and consumes fallowing whitespace. */
constexpr struct Token {
    template< class X >
    Parser<X> operator () ( Parser<X> p ) const {
        return p >>= []( X x ) {
            return space >> mreturn<Parser>(std::move(x));
        };
    }
} token{};

/* symb(str) : Tokenize this string! */
auto symb = compose( token, string );
/* csymb(c) : Tokenize this char! */
auto csymb = compose( token, pchar );

/* Consume whitespace, then parse p. */
constexpr struct Apply {
    template< class X >
    Parser<X> operator () ( Parser<X> p ) const {
        return space >> std::move(p);
    }
} apply{};

/* 
 * chain(p,op): Parse with p infinitely (until there is no match) folding with op.
 *
 * p and op are both parsers, but op returns a binary function, given some
 * input, and p returns the inputs to that function. For example, if:
 *      input: "4"
 *      p returns: 4
 * No operator is read, no operation is performed. But:
 *      input: "4+4"
 *      p returns: 4
 * op is then parsed with the function, rest:
 *      input: "+4"
 *      op returns: do_add
 *      input: "4"
 *      p returns: 4
 *      rest returns: 8
 * rest applies the operation parsed by op. It alternates between parsing p and
 * op until there are no more matches. op will fail if not fallowed by a p.
 */
constexpr struct Chainl1 {
    template< class X, class F >
    static Parser<X> rest( const Parser<X>& p, const Parser<F>& op, const X& a ) {
        // Alternate between op and p until input is consumed or a parse fails.
        auto r = op >>= [=]( const F& f ) {
                return p >>= [&]( const X& b ) {
                    return rest( p, op, f(a,b) );
                };
        };

        // Return the first successful parse, or a if none.
        return mplus_first( r, mreturn<Parser>(a) );
    }

    template< class X, class F >
    Parser<X> operator () ( Parser<X> p, Parser<F> op ) const {
        return p >>= closet( rest<X,F>, std::move(p), std::move(op) );
    }
} chainl1{};

// Binary operations of type int(*)(int,int).
int do_add(  int x, int y ) { return x + y; }
int do_sub(  int x, int y ) { return x - y; }
int do_mult( int x, int y ) { return x * y; }
int do_div(  int x, int y ) { return x / y; }

/* Convert a string (i.e. "+") and a function (do_add) to a symbolic parser. */
template< class F >
Parser<F> csymb_op( char c, F f ) {
    return csymb(c) >> mreturn<Parser>(f);
}

auto addop = csymb_op( '+', do_add )  + csymb_op( '-', do_sub );
auto mulop = csymb_op( '*', do_mult ) + csymb_op( '/', do_div );

//auto addop = mplus (
//    pchar('+') >> mreturn<Parser>(do_add),
//    pchar('-') >> mreturn<Parser>(do_sub)
//);
//
//auto mulop = mplus (
//    pchar('*') >> mreturn<Parser>(do_mult),
//    pchar('/') >> mreturn<Parser>(do_div)
//);

//auto digits = token( sat(is_num) ) >> mreturn<Parser>(consDigit);

constexpr bool is_num( char c ) {
    return c >= '0' and c <= '9';
}

/* Parse one digit. */
Parser<int> digit = token( sat(is_num) ) >>= []( char i ) { 
    return mreturn<Parser>(i-'0'); 
};

/* 
 * Parse numbers.
 * Ex: "123" -> (1,"23") -> (12,"3") -> 123
 */
int consDigit( int accum, int digit ) { return accum*10 + digit; }
Parser<int> num = chainl1( digit, mreturn<Parser>(consDigit) );

/* 
 * Parse terms: series of numbers, multiplications and divisions.
 * Ex: "1*3*2" -> (3,"*2") -> 6
 */
Parser<int> term = chainl1( num, mulop );

/*
 * Parse expressions: series of terms, additions and subtractions.
 * Ex: "1+7*9-1" -> (1."+7*9-1") -> (63,"-1") -> 62
 */
Parser<int> expr = chainl1( term, addop );

auto factor = mplus_first (
    digit,
    symb("(") >> expr >>= []( int n ) {
        return symb(")") >> mreturn<Parser>(n); 
    }
);

//auto term = chainl1( factor, mulop );

static std::ostringstream oss;
template< class X >
static std::string show( const X& x ) {
    oss.str( "" );
    oss << x;
    return oss.str();
}

static std::string show( std::string str ) {
    return str;
}

static constexpr const char* show( const char* str ) {
    return str;
}

template< class X, class Y, class ...Z >
static std::string show( const X& x, const Y& y, const Z& ...z ) 
{
    return show(x) + show(y,z...);
}

std::ostream& operator << ( std::ostream& os, const std::string& s ) {
    return os << '"' << s.c_str() << '"';
}

template< class X, class Y >
std::ostream& operator << ( std::ostream& os, const std::pair<X,Y>& p ) {
    return os << '(' << p.first << ',' << p.second << ')';
}

template< class X >
std::ostream& operator << ( std::ostream& os, const std::unique_ptr<X>& p ) {
    if( p ) 
        os << "Just " << *p;
    else
        os << "Nothing";
    return os;
}

template< class X >
std::ostream& operator << ( std::ostream& os, const std::vector<X>& v ) {
    os << '[';
    
    for( auto it=std::begin(v); it != std::end(v); it++ ) {
        os << *it;
        if( std::next(it) != std::end(v) )
            os << ',';
    }

    os << ']';
    return os;
}

auto p = item >>= []( char c ) {
    return item >> item >>= [c]( char d ) {
        return mreturn<Parser>( std::make_pair(c,d) );
    };
};

int main() {
    using std::cin;
    using std::cout;
    using std::endl;

    cout << "Welcome to the calculator!\n" 
         << "Press ctrl+d or ctrl+c to exit.\n"
         << "Type in an equation and press enter to solve it!\n" << endl;

    std::string input;
    while( cout << "Solve : " and std::getline(std::cin,input) ) {
        auto ans = apply(expr)(input);
        if( ans.size() and ans[0].second.size() == 0 )
            cout << " = " << ans[0].first;
        else
            cout << "No answer.";
        cout << endl;
    }
    

    // TEST CODE
    //std::cout << p("abc") << endl;
    //cout << space("   abc") << endl;
    //
    //Parser<int> twoDigit = digit >>= []( int x ) {
    //    return digit >>= [x]( int y ) {
    //        return mreturn<Parser>( x*10 + y );
    //    };
    //};
    
    //cout << "digit >> digit \"22\" = " << (twoDigit)("22") << endl;


    //std::string in = "121";
    //std::string in2 = "1221";
    //std::string in3 = "22212";
    //cout << "pchar '1' 121: " << pchar('1')( in ) << endl;
    //cout << "pchar '1' >> pchar '2' 121: " << (pchar('1') >> pchar('2'))( in ) << endl;
    //cout << "pchar '0' 1221: " << pchar('0')( in2 ) << endl;
    //cout << "string '1' 121: " << string("1")( in ) << endl;
    //cout << "string '12' 121: " << string("12")( in ) << endl;
    //cout << "string '121' 121: " << string("121")( in ) << endl;
    //cout << "string '021' 1221: " << string("121")( in2 ) << endl;
    //cout << "many (pchar '2') 22212: " << many(pchar('2'))( in3 ) << endl;

    //cout << "apply expr 1 - 2 = " << expr( "1 - 2 " ) << endl;
    //cout << "apply expr 1 + 2 = " << expr( "1 + 2 " ) << endl;
    //cout << "apply expr 1 * 2 = " << expr( "1 * 2 " ) << endl;
    //cout << "apply expr 1 / 2 = " << expr( "1 / 2 " ) << endl;
    //cout << "apply expr 1 - 2 * 3 = " << expr( "1 - 2 * 3 " ) << endl;
    //cout << "apply expr 2 * 3 + 4 = " << expr( "2 * 3 + 4 " ) << endl;
    //cout << "apply expr 1 - 20 * 3 +   4 = " << expr( "1 - 20 * 3 + 4" ) << endl;
    //cout << "apply expr 1 - 2 / 3 + 4 = " << expr( "1-6 / 3+4" ) << endl;
}

trivial-parser.cpp

#include <memory>
#include <iostream>
#include <sstream>
#include <utility>
#include <algorithm>
#include <iterator>

struct sequence_tag {};
struct pointer_tag {};

template< class X >
X category( ... );

template< class S >
auto category( const S& s ) -> decltype( std::begin(s), sequence_tag() );

template< class Ptr >
auto category( const Ptr& p ) -> decltype( *p, p==nullptr, pointer_tag() );

template< class T > struct Category {
    using type = decltype( category<T>(std::declval<T>()) );
};

template< class R, class ... X > struct Category< R(&)(X...) > {
    using type = R(&)(X...);
};

template< class T >
using Cat = typename Category< typename std::decay<T>::type >::type;

template<class...> struct Part;

template< class F, class X >
struct Part< F, X >
{
    F f;
    X x;

    template< class _F, class _X >
    constexpr Part( _F&& f, _X&& x )
        : f(std::forward<_F>(f)), x(std::forward<_X>(x))
    {
    }

    /* 
     * The return type of F only gets deduced based on the number of xuments
     * supplied. Part otherwise has no idea whether f takes 1 or 10 xs.
     */
    template< class ... Xs >
    constexpr auto operator() ( Xs&& ...xs )
        -> decltype( f(x,std::declval<Xs>()...) )
    {
        return f( x, std::forward<Xs>(xs)... );
    }
};

/* Recursive, variadic version. */
template< class F, class X1, class ...Xs >
struct Part< F, X1, Xs... > 
    : public Part< Part<F,X1>, Xs... >
{
    template< class _F, class _X1, class ..._Xs >
    constexpr Part( _F&& f, _X1&& x1, _Xs&& ...xs )
        : Part< Part<F,X1>, Xs... > (
            Part<F,X1>( std::forward<_F>(f), std::forward<_X1>(x1) ),
            std::forward<_Xs>(xs)...
        )
    {
    }
};

template< class F, class ...X >
constexpr Part<F,X...> closure( F&& f, X&& ...x ) {
    return Part<F,X...>( std::forward<F>(f), std::forward<X>(x)... );
}

template< class F, class ...X >
constexpr Part<F,X...> closet( F f, X ...x ) {
    return Part<F,X...>( std::move(f), std::move(x)... );
}

template< class F, class ...G >
struct Composition;

template< class F, class G >
struct Composition<F,G>
{
    F f; G g;

    template< class _F, class _G >
    constexpr Composition( _F&& f, _G&& g ) 
        : f(std::forward<_F>(f)), g(std::forward<_G>(g)) { }

    template< class X, class ...Y >
    constexpr decltype( f(g(std::declval<X>()), std::declval<Y>()...) )
    operator() ( X&& x, Y&& ...y ) {
        return f( g( std::forward<X>(x) ), std::forward<Y>(y)... );
    }

    constexpr decltype( f(g()) ) operator () () {
        return f(g());
    }
};

template< class F, class G, class ...H >
struct Composition<F,G,H...> : Composition<F,Composition<G,H...>>
{
    typedef Composition<G,H...> Comp;

    template< class _F, class _G, class ..._H >
    constexpr Composition( _F&& f, _G&& g, _H&& ...h )
        : Composition<_F,Composition<_G,_H...>> ( 
            std::forward<_F>(f), 
            Comp( std::forward<_G>(g), std::forward<_H>(h)... )
        )
    {
    }
};

template< class F, class ...G >
constexpr Composition<F,G...> compose( F f, G ...g ) {
    return Composition<F,G...>( std::move(f), std::move(g)... );
}

template< class... > struct Functor;

template< class F, class FX, class Fun=Functor< Cat<FX> > >
constexpr auto fmap( F&& f, FX&& fx ) 
    -> decltype( Fun::fmap( std::declval<F>(), std::declval<FX>() ) )
{
    return Fun::fmap( std::forward<F>(f), std::forward<FX>(fx) );
}

// General case: compose
template< class Function > struct Functor<Function> {
    template< class F, class G, class C = Composition<F,G> >
    static constexpr C fmap( F f, G g ) {
        C( std::move(f), std::move(g) );
    }
};

template<> struct Functor< sequence_tag > {
    template< class F, template<class...>class S, class X,
              class R = typename std::result_of<F(X)>::type >
    static S<R> fmap( F&& f, const S<X>& s ) {
        S<R> r;
        r.reserve( s.size() );
        std::transform( std::begin(s), std::end(s), 
                        std::back_inserter(r), 
                        std::forward<F>(f) );
        return r;
    }
};

template<> struct Functor< pointer_tag > {
    template< class F, template<class...>class Ptr, class X,
              class R = typename std::result_of<F(X)>::type >
    static Ptr<R> fmap( F&& f, const Ptr<X>& p ) 
    {
        return p != nullptr 
            ? Ptr<R>( new R( std::forward<F>(f)(*p) ) )
            : nullptr;
    }
};

template< class ... > struct Monad;

template< class F, class M, class ...N, class Mo=Monad<Cat<M>> >
constexpr auto mbind( F&& f, M&& m, N&& ...n ) 
    -> decltype( Mo::mbind(std::declval<F>(),
                           std::declval<M>(),std::declval<N>()...) )
{
    return Mo::mbind( std::forward<F>(f), 
                      std::forward<M>(m), std::forward<N>(n)... );
}

template< class F, class M, class ...N, class Mo=Monad<Cat<M>> >
constexpr auto mdo( F&& f, M&& m ) 
    -> decltype( Mo::mdo(std::declval<F>(), std::declval<M>()) )
{
    return Mo::mdo( std::forward<F>(f), std::forward<M>(m) );
}

// The first template argument must be explicit!
template< class M, class X, class ...Y, class Mo = Monad<Cat<M>> >
constexpr auto mreturn( X&& x, Y&& ...y ) 
    -> decltype( Mo::template mreturn<M>( std::declval<X>(),
                                          std::declval<Y>()... ) )
{
    return Mo::template mreturn<M>( std::forward<X>(x), 
                                    std::forward<Y>(y)... );
}

template< template<class...>class M, class X, class ...Y,
    class _M = M< typename std::decay<X>::type >,
    class Mo = Monad<Cat<_M>> >
constexpr auto mreturn( X&& x, Y&& ...y ) 
    -> decltype( Mo::template mreturn<_M>( std::declval<X>(),
                                           std::declval<Y>()... ) )
{
    return Mo::template mreturn<_M>( std::forward<X>(x),
                                     std::forward<Y>(y)... );
}

// Also has explicit template argument.
template< class M, class Mo = Monad<Cat<M>> >
auto mfail() -> decltype( Mo::template mfail<M>() ) {
    return Mo::template mfail<M>();
}

namespace monad {
template< class M, class F >
constexpr auto operator >>= ( M&& m, F&& f ) 
    -> decltype( mbind(std::declval<F>(),std::declval<M>()) )
{
    return mbind( std::forward<F>(f), std::forward<M>(m) );
}

template< class M, class F >
constexpr auto operator >> ( M&& m, F&& f ) 
    -> decltype( mdo(std::declval<M>(),std::declval<F>()) )
{
    return mdo( std::forward<M>(m), std::forward<F>(f) );
}

template< class F, class M >
constexpr auto operator ^ ( F&& f, M&& m ) 
    -> decltype( fmap(std::declval<F>(),std::declval<M>()) )
{
    return fmap( std::forward<F>(f), std::forward<M>(m) );
}
}

template< > struct Monad< pointer_tag > {

    template< class P >
    using mvalue = typename P::element_type;

    template< class F, template<class...>class Ptr, class X,
              class R = typename std::result_of<F(X)>::type >
    static R mbind( F&& f, const Ptr<X>& p ) {
        return p ? std::forward<F>(f)( *p ) : nullptr;
    }

    template< class F, template<class...>class Ptr, 
              class X, class Y,
              class R = typename std::result_of<F(X,Y)>::type >
    static R mbind( F&& f, const Ptr<X>& p, const Ptr<Y>& q ) {
        return p and q ? std::forward<F>(f)( *p, *q ) : nullptr;
    }

    template< template< class... > class M, class X, class Y >
    static M<Y> mdo( const M<X>& mx, const M<Y>& my ) {
        return mx ? (my ? mreturn<M<Y>>(*my) : nullptr) 
            : nullptr;
    }

    template< class M, class X >
    static M mreturn( X&& x ) {
        using Y = typename M::element_type;
        return M( new Y(std::forward<X>(x)) );
    }

    template< class M >
    static M mfail() { return nullptr; }
}; 

template< > struct Monad< sequence_tag > {

    template< class S >
    using mvalue = typename S::value_type;

    template< class F, template<class...>class S, class X,
        class R = typename std::result_of<F(X)>::type >
    static R mbind( F&& f, const S<X>& xs ) {
        R r;
        for( const X& x : xs ) {
            auto ys = std::forward<F>(f)( x );
            std::move( std::begin(ys), std::end(ys), std::back_inserter(r) );
        }
        return r;
    }

    template< class F, template<class...>class S, 
              class X, class Y,
              class R = typename std::result_of<F(X,Y)>::type >
    static R mbind( F&& f, const S<X>& xs, const S<Y>& ys ) {
        R r;
        for( const X& x : xs ) {
            for( const Y& y : ys ) {
                auto zs = std::forward<F>(f)( x, y );
                std::move( std::begin(zs), std::end(zs), 
                           std::back_inserter(r) );
            }
        }
        return r;
    }

    template< template< class... > class S, class X, class Y >
    static S<Y> mdo( const S<X>& mx, const S<Y>& my ) {
        // Note: This is not a strictly correct definition. 
        // It should return my concatenated to itself for every element of mx.
        return mx.size() ? my : S<Y>{};
    }

    template< class S, class X >
    static S mreturn( X&& x ) {
        return S{ std::forward<X>(x) }; // Construct an S of one element.
    }

    template< class S >
    static S mfail() { return S{}; }
};

struct ExprType {
    virtual int eval() = 0;
};

using Expr = std::unique_ptr<ExprType>;

template< class E >
Expr expr( E e ) {
    return Expr( new E(std::move(e)) );
}

template< class R, class ...E >
Expr expr( E&& ...e ) {
    return Expr( new R(std::forward<E>(e)...) );
}

struct SubExp : ExprType {
    Expr expr;

    SubExp( Expr e ) : expr(std::move(e)) { }
};

struct Int : ExprType {
    int x = 0;
    constexpr Int( int x ) : x(x) { }
    
    Int( const std::string& str ) {
        std::istringstream iss( str );
        iss >> x;

        if( not iss ) 
            throw "expected int, got " + str;
    }

    int eval() { return x; }
};

template< class F >
struct BinOp : ExprType {
    Expr left, right;
    BinOp( Expr left, Expr right ) 
        : left(std::move(left)), right(std::move(right)) { }

    int eval() {
        return F()( left->eval(), right->eval() );
    }
};

using Adder      = BinOp< std::plus<int> >;
using Subtractor = BinOp< std::minus<int> >;
using Multiplier = BinOp< std::multiplies<int> >;
using Divider    = BinOp< std::divides<int> >;

std::vector<std::string> words( const std::string& sentence ) {
    auto it = sentence.begin();
    std::vector<std::string> ws = {""};
    while( it != sentence.end() ) {
        if( *it != ' ' )
            ws.back().push_back( *it );
        else
            ws.emplace_back( "" );
        it++;
    }

    return ws;
}

struct Token {
    enum TokenClass {
        NUMBER, OPERATOR, PARREN, NCLASSES
    };

    static const char* classNames[NCLASSES]; 

    TokenClass type;
    std::string lexeme;

    Token( TokenClass c, std::string s ) : type(c), lexeme(std::move(s)) { }
};

const char* Token::classNames[] = {
    "Number", "Operator", "Parren" 
};

constexpr bool is_int( char c ) {
    return c >= '0' and c <= '9';
}

#include <sstream>
std::vector<Token> tokenize( const std::string& sentence ) {
    std::vector<Token> ts;

    auto it = std::begin( sentence );
    for( ; *it and it != std::end(sentence); it++ ) {
        if( *it == ' ' )
            continue;
        else if( *it == ')' )
            ts.emplace_back( Token::PARREN, ")" );
        else if( *it == '(' )
            ts.emplace_back( Token::PARREN, "(" );
        else if( *it == '+' )
            ts.emplace_back( Token::OPERATOR, "+" );
        else if( *it == '-' )
            ts.emplace_back( Token::OPERATOR, "-" );
        else if( *it == '*' )
            ts.emplace_back( Token::OPERATOR, "*" );
        else if( *it == '/' )
            ts.emplace_back( Token::OPERATOR, "/" );
        else if( is_int(*it) ) {
            auto e = it;
            for( ; *e and is_int(*e); e++ )
                ;
            ts.emplace_back( Token::NUMBER, std::string(it,e) );
            it = e - 1;
        } else {
            std::stringstream ss;
            ss << "unparsable token: '" << *it << "' (" << (int)*it << ')';
            throw ss.str();
        }
    }

    return ts;
}

using Tokens = std::vector<Token>;
using TokIt  = Tokens::const_iterator;

struct TokenRange {
    TokIt b, e;

    TokenRange( Tokens ts ) : b(ts.begin()), e(ts.end()) { }
    TokenRange( TokIt b, TokIt e ) : b(b), e(e) { }

    bool empty() { return b == e; }
    size_t size() { return e - b; }
};

TokenRange shrink( TokenRange r ) {
    r.b++;
    return r;
}

Expr parse( const Tokens& );

Expr parse_num_state( TokenRange );
Expr parse_raise_state( Expr&& e, TokenRange );
std::pair<TokenRange,Expr> parse_mult( TokenRange r );

Expr parse( const Tokens& ts ) {
    return parse_mult( ts ).second;
}

using ParseState = std::pair<TokenRange,Expr>;

ParseState parse_paren( TokenRange r ) {
    unsigned int nestCount = 1;
    auto it = std::find_if (
        r.b, r.e, [&]( const Token& t ){ 
            if( t.lexeme == "(" )
                nestCount++;
            else if( t.lexeme == ")" )
                nestCount--;
            return nestCount == 0;
        }
    );

    return std::make_pair (
        TokenRange( std::next(it), r.e ),
        parse_num_state( TokenRange(r.b,it) )
    );
}

Expr parse_num_state( TokenRange r ) {
    if( r.empty() )
        throw "nothing to parse";

    if( r.b->type == Token::PARREN ) {
        if( r.b->lexeme == ")" )
            throw "unmatched closing parren";

        auto state = parse_paren( shrink(r) );

        return parse_raise_state (
            std::move( state.second ),
            state.first
        );
    }

    const std::string& i = r.b->lexeme;
    return parse_raise_state( expr<Int>(i), shrink(r) );
}

std::pair<TokenRange,Expr> parse_mult( TokenRange r ) {
    if( r.empty() )
        throw "nothing to parse";

    if( r.b->type == Token::PARREN ) {
        if( r.b->lexeme == ")" )
            throw "unmatched closing parren";

        auto state = parse_paren( shrink(r) );

        return std::make_pair (
            state.first,
            parse_raise_state( std::move(state.second), state.first )
        );
    }

    return std::make_pair (
        shrink( r ),
        expr<Int>( r.b->lexeme )
    );
}

Expr parse_raise_state( Expr&& e, TokenRange r ) {
    if( r.empty() )
        return Expr( std::move(e) );

    if( r.b->lexeme == "+" ) {
        auto state = parse_mult( shrink(r) );
        return expr< Adder > (
            std::move(e), 
            parse_raise_state( std::move(state.second), state.first )
        );
    }

    if( r.b->lexeme == "-" ) {
        auto state = parse_mult( shrink(r) );
        return expr< Subtractor > (
            std::move(e), 
            parse_raise_state( std::move(state.second), state.first )
        );
    }

    if( r.b->lexeme == "*" ) {
        r = shrink(r);

        auto operand = parse_mult( r );

        return parse_raise_state (
            expr< Multiplier >( std::move(e), std::move(operand.second) ),
            TokenRange( operand.first )
        );
    }

    if( r.b->lexeme == "/" ) {
        r = shrink(r);

        auto operand = parse_mult( r );

        return parse_raise_state (
            expr< Divider >( std::move(e), std::move(operand.second) ),
            TokenRange( operand.first )
        );
    }

    throw "raise state cannot parse \"" + r.b->lexeme + '"';
}


//Expr parse_mult( std::vector<Token> ts ) {
//    Expr e;
//
//    auto it = std::begin( ts );
//    for( ; it != std::end( ts ); it++ ) {
//        if( it->lexeme == "*" ) {
//            auto left = it-1, right = it+1;
//            if( left < std::begin(ts) )
//                throw "multiplication requires left operand";
//            if( right >= std::end(ts) )
//                throw "multiplication requires right operand";
//            if( left->type != Token::NUMBER )
//                throw "left argument must be a number";
//            if( right->type != Token::NUMBER )
//                throw "right argument must be a number";
//            e = new Multiplier{ left, right };
//            it = ts.erase( left, right );
//            ts.insert( it, 
//        }


struct exp_tag {};

template< class E >
auto category( const E& e ) -> decltype( e.eval() );


static std::ostringstream oss;
template< class X >
static std::string show( const X& x ) {
    oss.str( "" );
    oss << x;
    return oss.str();
}

static std::string show( std::string str ) {
    return str;
}

static constexpr const char* show( const char* str ) {
    return str;
}

template< class X, class Y, class ...Z >
static std::string show( const X& x, const Y& y, const Z& ...z ) 
{
    return show(x) + show(y,z...);
}

std::ostream& operator << ( std::ostream& os, const Token& t ) {
    os << '<' << Token::classNames[t.type] << ',' << t.lexeme << '>';
    return os;
}

template< class X, class Y >
std::ostream& operator << ( std::ostream& os, const std::pair<X,Y>& p ) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}

template< class X >
std::ostream& operator << ( std::ostream& os, const std::unique_ptr<X>& p ) {
    if( p ) 
        os << "Just " << *p;
    else
        os << "Nothing";
    return os;
}

template< class X >
std::ostream& operator << ( std::ostream& os, const std::vector<X>& v ) {
    os << '[';
    
    for( auto it=std::begin(v); it != std::end(v); it++ ) {
        os << *it;
        if( std::next(it) != std::end(v) )
            os << ',';
    }

    os << ']';
    return os;
}

int main() {
    try {
        std::string input = "(((1-33) * (3+4/2)) + 5 + 5 - 0)";
        std::cout << "Input: " << input << std::endl;
        auto ts = tokenize( input );
        std::cout << "Tokens: " << ts << std::endl;
        auto tree = parse( ts );
        std::cout << "Evaluation: " << tree->eval() << std::endl;
    } catch( const std::string& msg ) {
        std::cout << "Parser exited unexpectedly with: " << msg << std::endl;
    } catch( const char* const msg ) {
        std::cout << "Parser exited unexpectedly with: " << msg << std::endl;
    }

}