Skip to content

Instantly share code, notes, and snippets.

@johncarl81
Last active May 10, 2018 21:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save johncarl81/88b7d2aaabac241b3245a4b4ce68ecc0 to your computer and use it in GitHub Desktop.
Save johncarl81/88b7d2aaabac241b3245a4b4ce68ecc0 to your computer and use it in GitHub Desktop.
Java factorial tail-call elimination
import java.math.BigInteger;
import static java.math.BigInteger.ONE;
// Factorial care of functional Programming in Java - Venkat Subramaniam
class Factorial {
static TailCall<BigInteger> factorial(long n) {
return factorialRec(ONE, BigInteger.valueOf(n));
}
static TailCall<BigInteger> factorialRec(BigInteger factorial, BigInteger number) {
if(number.equals(ONE)) {
return TailCalls.done(factorial);
} else {
return TailCalls.call(() -> factorialRec(factorial.multiply(number), number.subtract(ONE)));
}
}
public static void main(String[] args) {
System.out.println(factorial(100).invoke());
// Outputs 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
// Verify here: http://www.wolframalpha.com/input/?i=factorial+100
}
}
@FunctionalInterface
interface TailCall<T> {
TailCall<T> apply();
default boolean isComplete() { return false; }
default T result() { throw new Error("not implemented"); }
default T invoke() { return Stream.iterate(this, TailCall::apply).filter(TailCall::isComplete).findFirst().get().result();}
}
class TailCalls {
static <T> TailCall<T> call(TailCall<T> nextCall) {
return nextCall;
}
static <T> TailCall<T> done(T value) {
return new TailCall<T>() {
public boolean isComplete() { return true; }
public T result() { return value; }
public TailCall<T> apply() { throw new Error("Not implemented");}
};
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment