The beginnings of a C++ parser combinator library

parser_combinator.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <functional>
#include <tuple>
#include <type_traits>
#include <vector>

template< typename T >
using ParseResult = std::vector<std::tuple<T, std::string>>;

template< typename A >
class Parser {
public:
    using AmplifiedType = A;
    using ParseResult = ParseResult<AmplifiedType>;
    
private:
    using LambdaType = std::function<ParseResult (std::string const&)>;
    LambdaType lambda;
    
public:
    Parser(AmplifiedType const& t)
    : Parser([=](std::string const& s) -> ParseResult { return {std::make_tuple(t, s)}; })
    {}
    
    Parser(LambdaType l) : lambda(l) {}
    
    ParseResult parse(std::string const& s) const {
        return lambda(s);
    }
    
    // Bind: Monad a -> (a -> Monad b) -> Monad b
    template< typename F >
    auto operator>>=(F k) const -> decltype(k(std::get<0>(parse("")[0]))) {
        using ResultParser = decltype(k(std::get<0>(parse("")[0])));
        using FuncType = std::function<ResultParser(AmplifiedType)>;
        static_assert(std::is_convertible<F, FuncType>::value, "not callable");
        
        auto thiscopy = *this;
        return ResultParser([thiscopy, k](std::string const& s) {
            typename ResultParser::ParseResult results;
            for (auto const& result : thiscopy.parse(s)) {
                auto& fst = std::get<0>(result);
                auto newParser = k(fst);
                auto xys = newParser.parse(std::get<1>(result));
                std::copy(std::begin(xys), std::end(xys), std::inserter(results, std::end(results)));
            }
            return results;
        });
    }
    
    Parser bchoice(Parser<AmplifiedType> const& n) const {
        auto thiscopy = *this;
        return Parser{[thiscopy, n](std::string const& s) -> ParseResult {
            auto res = thiscopy.parse(s);
            if (!res.empty()) {
                return res;
            } else {
                return n.parse(s);
            }
        }};
    }
    
    template< typename F >
    Parser filter(F p) const {
        return (*this) >>= [p](AmplifiedType const& t) {
            if (p(t)) {
                return Parser(t);
            } else {
                // zero
                return Parser{
                    [](std::string const&) -> ParseResult {
                        return {};
                    }
                };
            }
        };
    }
    
    Parser<std::vector<AmplifiedType>> reiterate() const {
        using IteratedParser = Parser<std::vector<AmplifiedType>>;
        using IteratedParseResult = typename Parser<std::vector<AmplifiedType>>::ParseResult;
        auto thiscopy = *this;
        IteratedParser multiple = (*this) >>= [thiscopy](AmplifiedType const& t) -> IteratedParser {
            return thiscopy.reiterate() >>= ([t](std::vector<AmplifiedType> ts) -> IteratedParser {
                ts.insert(std::begin(ts), t);
                return IteratedParser(ts);
            });
        };
        IteratedParser fallback{std::vector<AmplifiedType>()};
        return multiple.bchoice(fallback);
    }
};

int main(int argc, const char * argv[])
{
    Parser<char> item{[](std::string const& s) -> Parser<char>::ParseResult {
        if (s.empty()) {
            return {};
        } else {
            return {{s[0], std::string(s.begin() + 1, s.end())}};
        }
    }};
    
    auto lit = [&item](char c) -> Parser<char> {
        return item.filter([=](char c_p) { return c == c_p; });
    };
    
    Parser<char> digit = item.filter([](char c) {
        return std::isdigit(c) != 0;
    });
    
    Parser<int> number = digit.reiterate() >>= [](std::vector<char> const& ds) {
        return Parser<int>(std::stoi(std::string(ds.data(), ds.size())));
    };
    
    auto results = number.parse("123test");
    for (auto& res : results) {
        std::cout << "(" << std::get<0>(res) << ", \"" << std::get<1>(res) << "\")\n";
    }
    return 0;
}

For reference, the haskell version I'm basing this off of.