FunctionalParsers.java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.function.*;


// Scott encoding of a Haskell's Maybe
interface Maybe<T> {

  <R> R match(Supplier<R> nothing, Function<T, R> just);

  // --- Constructors

  static <T> Maybe<T> nothing() {
    return new Maybe<T>() {
      @Override
      public <R> R match(Supplier<R> nothing, Function<T, R> just) {
        return nothing.get();
      }
    };
  }

  static <T> Maybe<T> just(T value) {
    return new Maybe<T>() {
      @Override
      public <R> R match(Supplier<R> nothing, Function<T, R> just) {
        return just.apply(value);
      }
    };
  }

  // --- Methods

  default <U> Maybe<U> map(Function<T, U> f) {
    return match(Maybe::nothing, x -> just(f.apply(x)));
  }

  default <U> Maybe<U> flatMap(Function<T, Maybe<U>> f) {
    return match(Maybe::nothing, f::apply);
  }

  default Maybe<T> or(Supplier<Maybe<T>> f) {
    return match(f, Maybe::just);
  }

  default T orElse(T fallback) {
    return match(() -> fallback, x -> x);
  }

  default void ifPresent(Consumer<T> f) {
    match(() -> null, x -> {
      f.accept(x);
      return null;
    });
  }
}


// Scott encoding of a pair
interface Pair<T, U> {

  <R> R match(BiFunction<T, U, R> pair);

  // --- Constructors

  static <T, U> Pair<T, U> of(T fst, U snd) {
    return new Pair<T, U>() {
      @Override
      public <R> R match(BiFunction<T, U, R> pair) {
        return pair.apply(fst, snd);
      }
    };
  }

  // --- Methods

  default T fst() {
    return match((t, u) -> t);
  }

  default U snd() {
    return match((t, u) -> u);
  }

  default <R> Pair<R, U> mapFst(Function<T, R> f) {
    return match((t, u) -> of(f.apply(t), u));
  }

  default <R> Pair<T, R> mapSnd(Function<U, R> f) {
    return match((t, u) -> of(t, f.apply(u)));
  }
}


// Scott encoding of a forward-only singly-linked list (a la Haskell)
interface Forward<T>  {

  <R> R match(Supplier<R> nil, BiFunction<T, Forward<T>, R> cons);

  // --- Constructors

  static <T> Forward<T> nil() {
    return new Forward<T>() {
      @Override
      public <R> R match(Supplier<R> nil, BiFunction<T, Forward<T>, R> cons) {
        return nil.get();
      }
    };
  }

  static <T> Forward<T> cons(T head, Forward<T> tail) {
    return new Forward<T>() {
      @Override
      public <R> R match(Supplier<R> nil, BiFunction<T, Forward<T>, R> cons) {
        return cons.apply(head, tail);
      }
    };
  }

  // --- Methods

  default <U> Forward<U> map(Function<T, U> f) {
    return match(Forward::nil, (head, tail) -> cons(f.apply(head), tail.map(f)));
  }

  default <R> R foldRight(R init, BiFunction<T, R, R> f) {
    return match(() -> init, (head, tail) -> tail.foldRight(f.apply(head, init), f));
  }

  default void forEach(Consumer<T> consumer) {
    foldRight(null, (value, nothing) -> {
      consumer.accept(value);
      return nothing;
    });
  }

  default List<T> toList() {
    ArrayList<T> list = new ArrayList<>();
    forEach(list::add);
    return list;
  }

  static String stringOf(Forward<Character> cs) {
    StringBuilder builder = new StringBuilder();
    cs.forEach(builder::append);
    return builder.toString();
  }

  static <T, S> Forward<T> unfoldRight(S init, Function<S, Maybe<Pair<T, S>>> f) {
    return
        f.apply(init).match(
            Forward::nil,
            step -> cons(step.fst(), unfoldRight(step.snd(), f))
        );
  }

  static Forward<Character> of(String s) {
    return unfoldRight(0, index -> {
      if (index < s.length()) {
        return Maybe.just(Pair.of(s.charAt(index), index + 1));
      } else {
        return Maybe.nothing();
      }
    });
  }
}


interface Parser<T> {

  Maybe<Pair<T, Forward<Character>>> parse(Forward<Character> input);

  default Maybe<Pair<T, Forward<Character>>> parse(String input) {
    return parse(Forward.of(input));
  }

  default <U> Parser<U> map(Function<T, U> f) {
    return input -> parse(input).map(result -> result.mapFst(f));
  }

  default <U> Parser<U> replace(U value) {
    return map(x -> value);
  }
}


class P {

  static <T> Parser<T> lazy(Supplier<Parser<T>> p) {
    return input -> p.get().parse(input);
  }

  static Parser<Character> satisfy(Predicate<Character> pred) {
    return input ->
        input.match(
            Maybe::nothing,
            (c, cs) -> pred.test(c) ? Maybe.just(Pair.of(c, cs)) : Maybe.nothing()
        );
  }

  static Parser<Character> of(Character target) {
    return satisfy(c -> c == target);
  }

  static <T, U, R> Parser<R> pmap2(BiFunction<T, U, R> f, Parser<T> p1, Parser<U> p2) {
    return input ->
        p1.parse(input)
            .flatMap(result1 ->
                p2.parse(result1.snd())
                    .map(result2 ->
                        Pair.of(f.apply(result1.fst(), result2.fst()), result2.snd())));
  }

  static <T> Parser<T> inject(T value) {
    return inject(() -> value);
  }

  static <T> Parser<T> inject(Supplier<T> f) {
    return input -> Maybe.just(Pair.of(f.get(), input));
  }

  static <T> Parser<T> alt(Parser<T> p1, Parser<T> p2) {
    return input -> p1.parse(input).or(() -> p2.parse(input));
  }

  static <T> Parser<Forward<T>> many(Parser<T> p) {
    return alt(many1(p), inject(Forward::nil));
  }

  static <T> Parser<Forward<T>> many1(Parser<T> p) {
    return pmap2(Forward::cons, p, lazy(() -> many(p)));
  }
}

class Read {

  static BigInteger readBigInteger(Forward<Character> cs) {
    return cs.map(Character::getNumericValue)
        .map(BigInteger::valueOf)
        .foldRight(BigInteger.ZERO,
            (digit, total) ->
                total.multiply(BigInteger.TEN).add(digit));
  }
}

class BigIntegerParser {

  static Parser<BigInteger> get() {
    return P.pmap2(Function::apply, sign(), value());
  }

  private static Parser<Function<BigInteger, BigInteger>> sign() {
    return P.alt(P.of('-').replace(BigInteger::negate), P.inject(() -> x -> x));
  }

  private static Parser<BigInteger> value() {
    return P.many1(P.satisfy(Character::isDigit)).map(Read::readBigInteger);
  }
}


public class FunctionalParsers {

  public static void main(String[] args) {

    test(P.satisfy(c -> false), "abc");
    test(P.satisfy(c -> true), "abc", 'a', "bc");

    test(P.of('x'), "y");
    test(P.of('x'), "x", 'x', "");
    test(P.of('x'), "xy", 'x', "y");

    test(P.inject(42), "abc", 42, "abc");

    test(BigIntegerParser.get(), "-42000123", new BigInteger("-42000123"), "");
    test(BigIntegerParser.get(), "-42000123abc", new BigInteger("-42000123"), "abc");
    test(BigIntegerParser.get(), "123a456", new BigInteger("123"), "a456");
  }

  private static <T> void test(Parser<T> p, String input) {
    p.parse(input).match(
        () -> null,
        result -> {
          fail("parser expected to fail");
          return null;
        }
    );
  }

  private static <T> void test(Parser<T> p, String input, T expected, String remainder) {
    p.parse(input).match(
        () -> {
          fail("parser not expected to fail");
          return null;
        },
        result -> {
          assertEqual(expected, result.fst());
          assertEqual(remainder, Forward.stringOf(result.snd()));
          return null;
        }
    );
  }

  private static <T> void assertEqual(T expected, T actual) {
    if (!expected.equals(actual)) {
      fail(actual + " is not equal to expected " + expected);
    }
  }

  private static void fail(String message) {
    throw new AssertionError(message);
  }
}