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); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment