Last active
August 29, 2015 14:16
-
-
Save robmoore/0731779a49b3db7578d6 to your computer and use it in GitHub Desktop.
Trampoline example.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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." |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
}; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment