Parsec.java

package example.playground.parsec;

import lombok.EqualsAndHashCode;
import lombok.Value;
import lombok.val;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;

interface F3<A, B, C, R> {
  R apply(A a, B b, C c);
}
interface F2<A, B, R> {
  R apply(A a, B b);
}
interface F1<A, R> {
  R apply(A a);

  default <B, C, S> F3<A, B, C, S> andThen(F3<R, B, C, S> f) {
    return (a, b, c) -> f.apply(this.apply(a), b, c);
  }

  static <T> F1<T, T> id() {
    return x -> x;
  }
}
interface F0<R> {
  R apply();
}

@Value
class Unit {
  private Unit() {}
  static Unit get() {
    return new Unit();
  }
}

abstract class Maybe<A> {

  abstract <R> R match(F0<R> nothing, F1<A, R> just);

  static <A> Maybe<A> just(A value) {
    return new Just<>(value);
  }
  static <A> Maybe<A> nothing() {
    return new Nothing<>();
  }

  @Value
  @EqualsAndHashCode(callSuper = false)
  static class Just<A> extends Maybe<A> {
    A value;

    @Override
    <R> R match(F0<R> nothing, F1<A, R> just) {
      return just.apply(value);
    }
  }
  @Value
  @EqualsAndHashCode(callSuper = false)
  static class Nothing<A> extends Maybe<A> {
    @Override
    <R> R match(F0<R> nothing, F1<A, R> just) {
      return nothing.apply();
    }
  }
}

abstract class Either<A, B> {

  abstract <C> Either<A, C> map(F1<B, C> f);

  static <A, B> Either<A, B> left(A a) {
    return new Left<>(a);
  }
  static <A, B> Either<A, B> right(B b) {
    return new Right<>(b);
  }

  @Value
  @EqualsAndHashCode(callSuper = false)
  static class Left<A, B> extends Either<A, B> {
    A value;

    @Override
    <C> Either<A, C> map(F1<B, C> f) {
      return new Left<>(value);
    }
  }
  @Value
  @EqualsAndHashCode(callSuper = false)
  static class Right<A, B> extends Either<A, B> {
    B value;

    @Override
    <C> Either<A, C> map(F1<B, C> f) {
      return new Right<>(f.apply(value));
    }
  }
}

abstract class Lists {

  static <T> List<T> zero() {
    return Collections.emptyList();
  }

  static <T> List<T> one(T t) {
    return Collections.singletonList(t);
  }

  static <T> List<T> cons(T t, List<T> ts) {
    ArrayList<T> ts_ = new ArrayList<>(ts.size() + 1);
    ts_.add(t);
    ts_.addAll(ts);
    return ts_;
  }

  static <T> List<T> reverse(List<T> ts) {
    ArrayList<T> copy = new ArrayList<>(ts);
    Collections.reverse(copy);
    return copy;
  }

  static <T> boolean isEmpty(List<T> ts) {
    return ts.isEmpty();
  }

  public static <T> List<T> concat(List<T> ts1, List<T> ts2) {
    ArrayList<T> ts_ = new ArrayList<>(ts1.size() + ts2.size());
    ts_.addAll(ts1);
    ts_.addAll(ts2);
    return ts_;
  }

  public static <A, B> B foldr(List<A> as, B nil, F2<A, B, B> cons) {
    B curr = nil;
    for (int i = as.size() - 1; i >= 0; i--) {
      curr = cons.apply(as.get(i), curr);
    }
    return curr;
  }

  public static <A, B> B foldl(List<A> as, B nil, F2<B, A, B> cons) {
    B curr = nil;
    for (A a : as) {
      curr = cons.apply(curr, a);
    }
    return curr;
  }

  public static <A, B> List<B> map(List<A> as, F1<A, B> f) {
    return as.stream().map(f::apply).collect(Collectors.toList());
  }

  public static String asString(List<Character> cs) {
    StringBuilder sb = new StringBuilder();
    for (Character c : cs) {
      sb.append(c);
    }
    return sb.toString();
  }

  public static List<Character> ofString(String s) {
    List<Character> cs = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
      cs.add(s.charAt(i));
    }
    return cs;
  }

  public static Integer sum(List<Integer> is) {
    return Lists.foldl(is, 0, Integer::sum);
  }
}

enum Ordering {
  LT, EQ, GT
}

abstract class Prelude {
  static Ordering compare(int i1, int i2) {
    switch (Integer.compare(i1, i2)) {
      case -1:
        return Ordering.LT;
      case 0:
        return Ordering.EQ;
      case 1:
        return Ordering.GT;
      default:
        throw new IllegalStateException();
    }
  }

  static String show(Character c) {
    return String.format("\"%c\"", c);
  }

  static String show(Object o) {
    if (o instanceof Character) {
      return Prelude.show((Character) o);
    } else {
      return Objects.toString(o);
    }
  }
}

@Value
class SourcePos {
  String name;
  int line;
  int column;

  static SourcePos initial(String name) {
    return new SourcePos(name, 1, 1);
  }

  public static SourcePos of(String name, int row, int column) {
    return new SourcePos(name, row, column);
  }
}

@Value
class State<S, U> {
  S input;
  SourcePos pos;
  U user;

  static <S, U> State<S, U> of(S input, SourcePos pos, U user) {
    return new State<>(input, pos, user);
  }
}

abstract class Message {
  static Message sysUnExpect(String m) {
    return new SysUnExpect(m);
  }
  static Message unExpect(String m) {
    return new UnExpect(m);
  }
  static Message expect(String m) {
    return new Expect(m);
  }
  static Message message(String m) {
    return new Plain(m);
  }

  @Value
  @EqualsAndHashCode(callSuper = false)
  static class SysUnExpect extends Message {
    String msg;
  }
  @Value
  @EqualsAndHashCode(callSuper = false)
  static class UnExpect extends Message {
    String msg;
  }
  @Value
  @EqualsAndHashCode(callSuper = false)
  static class Expect extends Message {
    String msg;
  }
  @Value
  @EqualsAndHashCode(callSuper = false)
  static class Plain extends Message {
    String msg;
  }
}

@Value
class ParseError {
  SourcePos pos;
  List<Message> messages;

  @Override
  public String toString() {
    return ErrorMethods.show(this);
  }

  static ParseError of(SourcePos pos, List<Message> msgs) {
    return new ParseError(pos, msgs);
  }
}

abstract class Consumed<A> {

  abstract <R> R match(F1<A, R> yes, F1<A, R> no);

  A value() {
    return match(a -> a, a -> a);
  }

  static <A> Consumed<A> yes(A value) {
    return new Yes<>(value);
  }

  static <A> Consumed<A> no(A value) {
    return new No<>(value);
  }

  @Value
  @EqualsAndHashCode(callSuper = false)
  static class Yes<A> extends Consumed<A> {
    A value;

    @Override
    <R> R match(F1<A, R> yes, F1<A, R> no) {
      return yes.apply(value);
    }
  }
  @Value
  @EqualsAndHashCode(callSuper = false)
  static class No<A> extends Consumed<A> {
    A value;

    @Override
    <R> R match(F1<A, R> yes, F1<A, R> no) {
      return no.apply(value);
    }
  }
}

abstract class Reply<S, U, A> {

  abstract <R> R match(F1<Ok<S, U, A>, R> ok, F1<ParseError, R> err);

  static <S, U, A> Reply<S, U, A> ok(A value, State<S, U> state, ParseError error) {
    return new Ok<>(value, state, error);
  }

  static <S, U, A> Reply<S, U, A> error(ParseError error) {
    return new Error<>(error);
  }

  @Value
  @EqualsAndHashCode(callSuper = false)
  static class Ok<S, U, A> extends Reply<S, U, A> {
    A value;
    State<S, U> state;
    ParseError error;

    @Override
    <R> R match(F1<Ok<S, U, A>, R> ok, F1<ParseError, R> err) {
      return ok.apply(this);
    }
  }
  @Value
  @EqualsAndHashCode(callSuper = false)
  static class Error<S, U, A> extends Reply<S, U, A> {
    ParseError error;

    @Override
    <R> R match(F1<Ok<S, U, A>, R> ok, F1<ParseError, R> err) {
      return err.apply(error);
    }
  }
}

interface Rules<S, U, A, R> {

  R consumedOk(A result, State<S, U> state, ParseError error);
  R consumedError(ParseError error);
  R emptyOk(A result, State<S, U> state, ParseError error);
  R emptyError(ParseError error);

  default F3<A, State<S, U>, ParseError, R> cok() {
    return this::consumedOk;
  }

  default F1<ParseError, R> cerr() {
    return this::consumedError;
  }

  default F3<A, State<S, U>, ParseError, R> eok() {
    return this::emptyOk;
  }

  default F1<ParseError, R> eerr() {
    return this::emptyError;
  }

  static <S, U, A, R> Rules<S, U, A, R> of(
          F3<A, State<S, U>, ParseError, R> cok,
          F1<ParseError, R> cerr,
          F3<A, State<S, U>, ParseError, R> eok,
          F1<ParseError, R> eerr) {
    return new Rules<S, U, A, R>() {
      @Override
      public R consumedOk(A result, State<S, U> state, ParseError error) {
        return cok.apply(result, state, error);
      }

      @Override
      public R consumedError(ParseError error) {
        return cerr.apply(error);
      }

      @Override
      public R emptyOk(A result, State<S, U> state, ParseError error) {
        return eok.apply(result, state, error);
      }

      @Override
      public R emptyError(ParseError error) {
        return eerr.apply(error);
      }
    };
  }
}

interface ParsecT<S, U, A> {

  <R> R parse(State<S, U> state, Rules<S, U, A, R> rules);

  default <B> ParsecT<S, U, B> map(F1<A, B> f) {
    return Prim.parsecMap(this, f);
  }

  default <B> ParsecT<S, U, B> flatMap(F1<A, ParsecT<S, U, B>> k) {
    return Prim.parserBind(this, k);
  }

  default ParsecT<S, U, List<A>> many() {
    return Combo.many(this);
  }

  default ParsecT<S, U, List<A>> many1() {
    return Combo.many1(this);
  }

  default <B> ParsecT<S, U, B> then(ParsecT<S, U, B> p) {
    return Methods.apR(this, p);
  }

  default <B> ParsecT<S, U, A> followedBy(ParsecT<S, U, B> p) {
    return Methods.apL(this, p);
  }

  default ParsecT<S, U, A> orElse(ParsecT<S, U, A> p) {
    return Prim.parserPlus(this, p);
  }

  default ParsecT<S, U, A> failBack() {
    return Prim.try_(this);
  }

  default ParsecT<S, U, Unit> discard() {
    return Combo.discard(this);
  }

  default <B> ParsecT<S, U, B> emplace(B b) {
    return Methods.apR(this, Methods.pure(b));
  }
}

interface Stream<S extends Stream<S, T>, T> {
  Maybe<Next<T, S>> uncons();
}

@Value
class Next<T, S> {

  T token;
  S state;

  static <T, S> Next<T, S> of(T token, S state) {
    return new Next<>(token, state);
  }
}

abstract class Pos {
  static SourcePos updatePosChar(SourcePos pos, Character c) {
    switch (c) {
      case '\n':
        return SourcePos.of(pos.getName(), pos.getLine() + 1, 1);
      default:
        return SourcePos.of(pos.getName(), pos.getLine(), pos.getColumn() + 1);
    }
  }
}

abstract class Errors {
  static ParseError newErrorMessage(Message msg, SourcePos pos) {
    return ParseError.of(pos, Lists.one(msg));
  }

  static ParseError newErrorUnknown(SourcePos pos) {
    return new ParseError(pos, Lists.zero());
  }

  static ParseError unexpectError(String msg, SourcePos pos) {
    return newErrorMessage(Message.sysUnExpect(msg), pos);
  }

  static <S, U> ParseError unknownError(State<S, U> s) {
    return newErrorUnknown(s.getPos());
  }

  static ParseError mergeError(ParseError e1, ParseError e2) {
    if (Lists.isEmpty(e2.getMessages()) && !Lists.isEmpty(e1.getMessages())) {
      return e1;
    } else if (Lists.isEmpty(e1.getMessages()) && !Lists.isEmpty(e2.getMessages())) {
      return e2;
    } else {
      switch (ErrorMethods.compare(e1.getPos(), e2.getPos())) {
        case EQ:
          return ParseError.of(e1.getPos(), Lists.concat(e1.getMessages(), e2.getMessages()));
        case GT:
          return e1;
        case LT:
          return e2;
        default:
          throw new IllegalStateException();
      }
    }
  }
}

abstract class ErrorMethods {
  static String show(SourcePos pos) {
    return String.format("\"%s\" (line %d, column %d)", pos.getName(), pos.getLine(), pos.getColumn());
  }
  static String show(ParseError err) {
    return String.format("%s: %s", ErrorMethods.show(err.getPos()), new HashSet<>(err.getMessages()));
  }
  static Ordering compare(SourcePos p1, SourcePos p2) {
    switch (Prelude.compare(p1.getLine(), p2.getLine())) {
      case EQ:
        return Prelude.compare(p1.getColumn(), p2.getColumn());
      case LT:
        return Ordering.LT;
      case GT:
        return Ordering.GT;
      default:
        throw new IllegalStateException();
    }
  }
}

abstract class Prim {

  static <S, U, A, B> ParsecT<S, U, B> parsecMap(ParsecT<S, U, A> p, F1<A, B> f) {
    return new ParsecT<S, U, B>() {
      @Override
      public <R> R parse(State<S, U> state, Rules<S, U, B, R> rules) {
        return p.parse(state, Rules.of(
                f.andThen(rules.cok()),
                rules.cerr(),
                f.andThen(rules.eok()),
                rules.eerr()));
      }
    };
  }

  static <S, U, A> ParsecT<S, U, A> parserReturn(A a) {
    return new ParsecT<S, U, A>() {
      @Override
      public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) {
        return rules.emptyOk(a, state, Errors.unknownError(state));
      }
    };
  }

  static <S, U, A, B> ParsecT<S, U, B> parserBind(ParsecT<S, U, A> m, F1<A, ParsecT<S, U, B>> k) {
    return new ParsecT<S, U, B>() {
      @Override
      public <R> R parse(State<S, U> s, Rules<S, U, B, R> rules) {
        return m.parse(s, Rules.of(
                // consumed-okay case for m
                (x, s_, err) -> k.apply(x).parse(s_, Rules.of(
                        // if (k x) consumes, those go straight up
                        rules.cok(),
                        rules.cerr(),
                        // if (k x) doesn't consume input, but is okay,
                        // we still return in the consumed continuation
                        (y, s__, err_) -> rules.consumedOk(y, s__, Errors.mergeError(err, err_)),
                        // if (k x) doesn't consume input, but errors,
                        // we return the error in the 'consumed-error'
                        // continuation
                        (err_) -> rules.consumedError(Errors.mergeError(err, err_))
                )),
                // consumed-error case for m
                rules.cerr(),
                // empty-ok case for m
                (x, s_, err) -> k.apply(x).parse(s_, Rules.of(
                        // in these cases, (k x) can return as empty
                        rules.cok(),
                        rules.cerr(),
                        (y, s__, err_) -> rules.emptyOk(y, s__, Errors.mergeError(err, err_)),
                        (err_) -> rules.emptyError(Errors.mergeError(err, err_))
                )),
                // empty-error case for m
                rules.eerr()
        ));
      }
    };
  }

  static <S, U, A> ParsecT<S, U, A> parserZero() {
    return new ParsecT<S, U, A>() {
      @Override
      public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) {
        return rules.emptyError(Errors.unknownError(state));
      }
    };
  }

  static <S, U, A> ParsecT<S, U, A> parserPlus(
          ParsecT<S, U, A> m,
          ParsecT<S, U, A> n
  ) {
    return new ParsecT<S, U, A>() {
      @Override
      public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) {
        return m.parse(state, Rules.of(
                rules.cok(),
                rules.cerr(),
                rules.eok(),
                (err) -> n.parse(state, Rules.of(
                        rules.cok(),
                        rules.cerr(),
                        (y, s_, err_) -> rules.emptyOk(y, s_, Errors.mergeError(err, err_)),
                        (err_) -> rules.emptyError(Errors.mergeError(err, err_))
                ))
        ));
      }
    };
  }

  static <S, U, A> ParsecT<S, U, A> parserFail(String msg) {
    return new ParsecT<S, U, A>() {
      @Override
      public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) {
        return rules.emptyError(Errors.newErrorMessage(Message.message(msg), state.getPos()));
      }
    };
  }

  static <S extends Stream<S, T>, U, A, T> ParsecT<S, U, A> tokenPrim(
          F1<T, String> showToken,
          F3<SourcePos, T, S, SourcePos> nextPos,
          F1<T, Maybe<A>> test
  ) {
    return new ParsecT<S, U, A>() {
      @Override
      public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) {
        return state.getInput().uncons().match(
                () -> rules.emptyError(Errors.unexpectError("", state.getPos())),
                next -> test.apply(next.getToken()).match(
                        () -> rules.emptyError(
                                Errors.unexpectError(showToken.apply(next.getToken()), state.getPos())),
                        x -> {
                          SourcePos newPos = nextPos.apply(state.getPos(), next.getToken(), next.getState());
                          State<S, U> newState = State.of(next.getState(), newPos, state.getUser());
                          return rules.consumedOk(x, newState, Errors.newErrorUnknown(newPos));
                        }
                )
        );
      }
    };
  }

  static <S, U, A> ParsecT<S, U, A> try_(
          ParsecT<S, U, A> p
  ) {
    return new ParsecT<S, U, A>() {
      @Override
      public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) {
        return p.parse(state, Rules.of(
                rules.cok(),
                rules.eerr(), // switched 'cerr' with 'eerr'
                rules.eok(),
                rules.eerr())
        );
      }
    };
  }

  static <S extends Stream<S, T>, U, A, T> ParsecT<S, U, A> lookAhead(
          ParsecT<S, U, A> p
  ) {
    return new ParsecT<S, U, A>() {
      @Override
      public <R> R parse(State<S, U> s, Rules<S, U, A, R> rules) {
        F3<A, State<S, U>, ParseError, R> eok_ =
                // purposefully use 's' instead of 's_'
                (a, s_, err) -> rules.emptyOk(a, s, Errors.unknownError(s));
        return p.parse(s, Rules.of(
                eok_,
                rules.cerr(),
                eok_,
                rules.eerr())
        );
      }
    };
  }

  static <S, U, A> ParsecT<S, U, List<A>> manyAccum(
          F2<A, List<A>, List<A>> acc,
          ParsecT<S, U, A> p
  ) {
    return new ParsecT<S, U, List<A>>() {
      @Override
      public <R> R parse(State<S, U> s, Rules<S, U, List<A>, R> rules) {

        F1<List<A>, F3<A, State<S, U>, ParseError, R>> walk =
                new F1<List<A>, F3<A, State<S, U>, ParseError, R>>() {
                  @Override
                  public F3<A, State<S, U>, ParseError, R> apply(List<A> xs) {
                    return (x, s_, err) -> p.parse(s_, Rules.of(
                            // explicitly nested because not lazy
                            (y, s__, err_) -> apply(acc.apply(x, xs)).apply(y, s__, err_),
                            rules.cerr(),
                            (y, s__, err_) -> manyErr(),
                            err_ -> rules.consumedOk(acc.apply(x, xs), s_, err)
                    ));
                  }
                };

        return p.parse(s, Rules.of(
                walk.apply(Lists.zero()),
                rules.cerr(),
                (x, s_, err) -> manyErr(),
                (err) -> rules.emptyOk(Lists.zero(), s, err)
        ));
      }
    };
  }

  static <T> T manyErr() {
    throw new RuntimeException("combinator 'many' is applied to a parser that accepts an empty string");
  }

  static <S, U, A> ParsecT<S, U, A> unexpected(String msg) {
    return new ParsecT<S, U, A>() {
      @Override
      public <R> R parse(State<S, U> state, Rules<S, U, A, R> rules) {
        return rules.emptyError(Errors.newErrorMessage(Message.unExpect(msg), state.getPos()));
      }
    };
  }
}

abstract class Run {

  static <S, U, A> Consumed<Reply<S, U, A>> runParsecT(ParsecT<S, U, A> p, State<S, U> s) {
    return p.parse(s,
            Rules.of(
                    (a, s_, err) -> Consumed.yes(Reply.ok(a, s_, err)),
                    (err) -> Consumed.yes(Reply.error(err)),
                    (a, s_, err) -> Consumed.no(Reply.ok(a, s_, err)),
                    (err) -> Consumed.no(Reply.error(err))));
  }

  static <S extends Stream<S, T>, U, A, T> Either<ParseError, A> runP(
          ParsecT<S, U, A> p,
          U u,
          String name,
          S s
  ) {
    return runParsecT(p, State.of(s, SourcePos.initial(name), u)).value().match(
            ok -> Either.right(ok.getValue()),
            err -> Either.left(err)
    );
  }
}

abstract class Methods {

  static <S, U, A> ParsecT<S, U, A> pure(A a) {
    return Prim.parserReturn(a);
  }

  static <S, U, A, B, C> ParsecT<S, U, C> liftA2(
          F2<A, B, C> f,
          ParsecT<S, U, A> p1,
          ParsecT<S, U, B> p2
  ) {
    return Prim.parserBind(p1, a -> p2.map(b -> f.apply(a, b)));
  }

  static <S, U, A, B> ParsecT<S, U, A> apL(
          ParsecT<S, U, A> p1,
          ParsecT<S, U, B> p2
  ) {
    return Methods.liftA2((a, b) -> a, p1, p2);
  }

  static <S, U, A, B> ParsecT<S, U, B> apR(
          ParsecT<S, U, A> p1,
          ParsecT<S, U, B> p2
  ) {
    return Methods.liftA2((a, b) -> b, p1, p2);
  }

  static <S, U, A> ParsecT<S, U, List<A>> sequence(
          List<ParsecT<S, U, A>> ms
  ) {
    return Methods.mapM(F1.id(), ms);
  }

  static <S, U, A, B> ParsecT<S, U, List<B>> mapM(
          F1<A, ParsecT<S, U, B>> f,
          List<A> as
  ) {
    return Lists.foldr(
            as,
            Methods.pure(Lists.zero()),
            (a, r) -> f.apply(a).flatMap(b -> r.map(bs -> Lists.cons(b, bs)))
    );
  }
}

abstract class Combo {

  static <S, U, A> ParsecT<S, U, Unit> discard(ParsecT<S, U, A> p) {
    return p.then(Methods.pure(Unit.get()));
  }

  static <S, U, A> ParsecT<S, U, List<A>> many(ParsecT<S, U, A> p) {
    return Prim.manyAccum(Lists::cons, p).map(Lists::reverse);
  }

  static <S, U, A> ParsecT<S, U, List<A>> many1(ParsecT<S, U, A> p) {
    return Methods.liftA2(Lists::cons, p, Combo.many(p));
  }

  @SafeVarargs
  static <S, U, A> ParsecT<S, U, A> choice(ParsecT<S, U, A>... ps) {
    return Combo.choice(Arrays.asList(ps));
  }

  static <S, U, A> ParsecT<S, U, A> choice(List<ParsecT<S, U, A>> ps) {
    return Lists.foldr(ps, Prim.parserZero(), Prim::parserPlus);
  }

  static <S, U, A> ParsecT<S, U, A> option(ParsecT<S, U, A> p, A a) {
    return p.orElse(Methods.pure(a));
  }

  static <S, U, A> ParsecT<S, U, Maybe<A>> optionMaybe(ParsecT<S, U, A> p) {
    return Combo.option(p.map(Maybe::just), Maybe.nothing());
  }

  static <S, U, A> ParsecT<S, U, Unit> optional(ParsecT<S, U, A> p) {
    return p.flatMap(a -> Methods.pure(Unit.get())).orElse(Methods.pure(Unit.get()));
  }

  static <S, U, A, Sep> ParsecT<S, U, List<A>> sepBy(ParsecT<S, U, A> p, ParsecT<S, U, Sep> sep) {
    return Combo.sepBy1(p, sep).orElse(Methods.pure(Lists.zero()));
  }

  static <S, U, A, Sep> ParsecT<S, U, List<A>> sepBy1(ParsecT<S, U, A> p, ParsecT<S, U, Sep> sep) {
    return p.flatMap(x -> Combo.many(sep.then(p)).map(xs -> Lists.cons(x, xs)));
  }

  static <S extends Stream<S, T>, U, T> ParsecT<S, U, T> anyToken() {
    return Prim.tokenPrim(Prelude::show, (pos, _t, _ts) -> pos, Maybe::just);
  }

  static <S extends Stream<S, T>, U, T> ParsecT<S, U, Unit> eof() {
    return Combo.notFollowedBy(Combo.<S, U, T>anyToken());
  }

  static <S, U, A> ParsecT<S, U, Unit> notFollowedBy(ParsecT<S, U, A> p) {
    return p.failBack()
            .flatMap(c -> Prim.unexpected(Prelude.show(c)))
            .discard()
            .orElse(Methods.pure(Unit.get()))
            .failBack();
  }
}

abstract class Char {

  static <S extends Stream<S, Character>, U> ParsecT<S, U, Character> of(
          Character c
  ) {
    return Char.satisfy(d -> c == d);
  }

  static <S extends Stream<S, Character>, U> ParsecT<S, U, Character> digit() {
    return Char.satisfy(Character::isDigit);
  }

  static <S extends Stream<S, Character>, U> ParsecT<S, U, Character> satisfy(
          F1<Character, Boolean> f
  ) {
    return Prim.tokenPrim(
            Prelude::show,
            (pos, c, s_) -> Pos.updatePosChar(pos, c),
            c -> f.apply(c) ? Maybe.just(c) : Maybe.nothing()
    );
  }

  static <S extends Stream<S, Character>, U> ParsecT<S, U, String> string(
          String s
  ) {
    ParsecT<S, U, List<Character>> p_cs = Methods.sequence(Lists.map(Lists.ofString(s), Char::of));
    return p_cs.map(Lists::asString);
  }
}

@Value
class StringStream implements Stream<StringStream, Character> {

  String s;
  int pos;

  StringStream advanced() {
    return new StringStream(s, pos + 1);
  }

  @Override
  public Maybe<Next<Character, StringStream>> uncons() {
    if (pos >= s.length()) {
      return Maybe.nothing();
    } else {
      return Maybe.just(Next.of(s.charAt(pos), advanced()));
    }
  }

  static StringStream of(String s) {
    return new StringStream(s, 0);
  }
}

@Value
class ListStream<T> implements Stream<ListStream<T>, T> {

  List<T> ts;
  int pos;

  ListStream advanced() {
    return new ListStream<>(ts, pos + 1);
  }

  @Override
  public Maybe<Next<T, ListStream<T>>> uncons() {
    if (pos >= ts.size()) {
      return Maybe.nothing();
    } else {
      return Maybe.just(Next.of(ts.get(pos), advanced()));
    }
  }

  static <T> ListStream<T> of(List<T> ts) {
    return new ListStream<>(ts, 0);
  }
}

public class Program {

  private static <S extends Stream<S, Character>, U> ParsecT<S, U, Character> parser1() {
    return Char.<S, U>of('c').many1().then(Char.of('b')).failBack().orElse(Char.of('c'));
  }

  private static <S extends Stream<S, Character>, U> ParsecT<S, U, Integer> integer() {
    return Char.<S, U>digit().many1().map(Lists::asString).map(Integer::valueOf);
  }

  private static <S extends Stream<S, Character>, U, A> ParsecT<S, U, List<A>> csv(ParsecT<S, U, A> p) {
    return Combo.sepBy1(p, Char.of(','));
  }

  private static <S extends Stream<S, Character>, U> ParsecT<S, U, String> coolWords() {
    return Combo.choice(
            Char.<S, U>string("what").failBack(),
            Char.string("wild"),
            Char.string("hello")
    );
  }

  enum Token {
    LParen,
    RParen,
    Plus
  }

  private static <S extends Stream<S, Character>, U> ParsecT<S, U, Token> dumbToken() {
    return Combo.choice(
            Char.<S, U>of('(').emplace(Token.LParen),
            Char.<S, U>of(')').emplace(Token.RParen),
            Char.<S, U>of('+').emplace(Token.Plus)
    );
  }

  private static <S extends Stream<S, Character>, U> ParsecT<S, U, List<Token>> dumbTokens() {
    val whitespace = Combo.many(Char.<S, U>of(' '));
    val token = Program.<S, U>dumbToken().followedBy(whitespace);
    return whitespace.then(Combo.many(token)).followedBy(Combo.eof());
  }

  public static void main(String[] args) {
    val result1 = Run.runP(
            csv(Program.<StringStream, Object>integer()).followedBy(Combo.eof()),
            new Object(),
            "<stdin>",
            StringStream.of("1,2,3,4,5"));
    System.out.println(result1.map(Lists::sum));

    val result2 = Run.runP(
            coolWords(),
            new Object(),
            "<stdin>",
            StringStream.of("wild"));
    System.out.println(result2);

    val result3 = Run.runP(
            dumbTokens(),
            new Object(),
            "<stdin>",
            StringStream.of("   ( + + )))    +  "));
    System.out.println(result3);
  }
}