Trampoline example.

TrampolineExample

Code from slides 41 - 44 of [Laziness, trampolines, monoids and other functional amenities: this is not your father's Java]
(http://www.slideshare.net/mariofusco/lazine).

"A trampoline is an iteration applying a list of functions. Each function returns the next function for the loop to run."

FactorialCalculator.java

package org.sdf.rkm.mariofusco;

import java.math.BigInteger;
import java.util.stream.IntStream;

import static org.sdf.rkm.mariofusco.TailCall.done;

public class FactorialCalculator {

    public BigInteger functional(int n) {
        return IntStream.rangeClosed(1, n)
                .boxed()
                .map(BigInteger::valueOf)
                .reduce(BigInteger::multiply)
                .get();
    }

    public BigInteger trampoline(int n) {
        return trampoline(n, BigInteger.ONE).invoke();
    }

    private TailCall<BigInteger> trampoline(int n, BigInteger acc) {
        if (n == 1)
            return done(acc);
        else
            return () -> trampoline(n - 1, acc.multiply(BigInteger.valueOf(n)));
    }

    public BigInteger recursive(int n) {
        return recursive(n, BigInteger.ONE);
    }

    private BigInteger recursive(int n, BigInteger acc) {
        if (n == 1)
            return acc;
        else
            return recursive(n - 1, acc.multiply(BigInteger.valueOf(n)));
    }

    public BigInteger iterative(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }

}

FactorialCalculatorTest.groovy

package org.sdf.rkm.mariofusco

import spock.lang.Specification

class FactorialCalculatorTest extends Specification {
    def n = 99900
    def expectedResult
    def calculator

    void setup() {
        calculator = new FactorialCalculator()
        expectedResult = calculator.functional(n)
    }

    def "Calculate the factorial of n using trampoline"() {
        when: "I calculate the factorial of n"
            def result = calculator.trampoline(n)
        then: "The calculator returns expected result"
            result == expectedResult
    }

    def "Calculate the factorial of n recursively"() {
        when: "I calculate the factorial of n"
            calculator.recursive(n)
        then: "The call results in a StackOverflowException"
            thrown(StackOverflowError)
    }

    def "Calculate the factorial of n iteratively"() {
        when: "I calculate the factorial of n"
            def result = calculator.iterative(n)
        then: "The calculator returns expected result"
            result == expectedResult
    }

}

PalindromePredicate.java

package org.sdf.rkm.mariofusco;

import java.util.function.Predicate;

import static java.lang.Character.isLetter;
import static java.lang.Character.toLowerCase;
import static org.sdf.rkm.mariofusco.TailCall.done;

public class PalindromePredicate implements Predicate<String> {
    @Override
    public boolean test(String s) {
        return isPalindrome(s, 0, s.length() - 1).invoke();
    }

    private TailCall<Boolean> isPalindrome(String s, int start, int end) {
        while (start < end && !isLetter(s.charAt(start)))
            start++;
        while (end > start && !isLetter(s.charAt(end)))
            end--;
        if (start >= end)
            return done(true);
        // letters must be equal
        if (toLowerCase(s.charAt(start)) != toLowerCase(s.charAt(end)))
            return done(false);
        int newStart = start + 1;
        int newEnd = end - 1;

        // lambda which calls isPalindrome (recursive)
        return () -> isPalindrome(s, newStart, newEnd);
    }
}

PalindromePredicateTest.groovy

package org.sdf.rkm.mariofusco

import spock.lang.Specification

class PalindromePredicateTest extends Specification {
    def predicate
    def setup() {
        predicate = new PalindromePredicate()
    }

    def "String is a palindrome"() {
        when: "I test a palindrome"
            def result = predicate.test("pop")
        then: "the predicate returns true"
            result
    }

    def "String is not a palindrome"() {
        when: "I test a palindrome"
            def result = predicate.test("snap")
        then: "the predicate returns false"
            !result
    }

    def "List of Strings contains a palindrome"() {
        when: "I test a list of Strings containing a palindrome"
            def list = new ArrayList<String>(["snap", "pop", "fiz"]);
            def result = list.stream().anyMatch(predicate);
        then: "the list is not empty"
            result
    }
}

TailCall.java

package org.sdf.rkm.mariofusco;

import java.util.stream.Stream;

/**
 * From http://www.slideshare.net/mariofusco/lazine
 * @param <T>
 */
@FunctionalInterface
public interface TailCall<T> {

    TailCall<T> apply();

    default boolean isComplete() {
        return false;
    }

    default T result() {
        throw new UnsupportedOperationException();
    }

    default T invoke() {
        return Stream.iterate(this, TailCall::apply)
                .filter(TailCall::isComplete)
                .findFirst()
                .get()
                .result();
    }

    public static <T> TailCall<T> done(final T value) {
        return new TailCall<T>() {
            @Override
            public boolean isComplete() {
                return true;
            }

            @Override
            public T result() {
                return value;
            }

            @Override
            public TailCall<T> apply() {
                throw new UnsupportedOperationException();
            }
        };
    }
}