Skip to content

Instantly share code, notes, and snippets.

@Garciat
Last active September 24, 2019 09:50
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Garciat/c334cdef1abef57a33272b8787496b1a to your computer and use it in GitHub Desktop.
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