Java 8 introduced lambda functions and I want to implement something like factorial:
IntToDoubleFunction fact = x -> x == 0 ? 1 : x * fact.applyAsDouble(x-1);
Compilation returns
error: variable fact might not have been initialized
How can I reference function itself. Class is anonymous but instance exists: It is called fact.
I usually use (once-for-all-functional-interfaces defined) generic helper class which wraps the variable of the functional interface type. This approach solves the problem with the local variable initialization and allows the code to look more clearly.
In case of this question the code will look as follows:
// Recursive.java
// @param <I> - Functional Interface Type
public class Recursive<I> {
public I func;
}
// Test.java
public double factorial(int n) {
Recursive<IntToDoubleFunction> recursive = new Recursive<>();
recursive.func = x -> (x == 0) ? 1 : x * recursive.func.applyAsDouble(x - 1);
return recursive.func.applyAsDouble(n);
}
One way is to write a secondary function, helper, which takes a function and a number as arguments, and then write the function you actually want, fact = helper(helper,x).
Like so:
BiFunction<BiFunction, Double, Double> factHelper =
(f, x) -> (x == 0) ? 1.0 : x*(double)f.apply(f,x-1);
Function<Double, Double> fact =
x -> factHelper.apply(factHelper, x);
This seems to me to be slightly more elegant than relying on corner case semantics like a closure that captures a reference to a mutable structure, or allowing self-reference with a warning of the possibility of "might not be initialized."
Still, it's not a perfect solution because of Java's type system -- the generics cannot guarantee that f, the argument to factHelper, is of the same type as factHelper (i.e. same input types and output types), since that would be an infinitely nested generic.
Thus, instead, a safer solution might be:
Function<Double, Double> fact = x -> {
BiFunction<BiFunction, Double, Double> factHelper =
(f, d) -> (d == 0) ? 1.0 : d*(double)f.apply(f,d-1);
return factHelper.apply(factHelper, x);
};
The code smell incurred from factHelper's less-than-perfect generic type is now contained (or, dare I say, encapsulated) within the lambda, ensuring that factHelper will never be called unknowingly.
Local and anonymous classes, as well as lambdas, capture local variables by value when they are created. Therefore, it is impossible for them to refer to themselves by capturing a local variable, because the value for pointing to themself does not exist yet at the time they are being created.
Code in local and anonymous classes can still refer to themselves using this. However, this in a lambda does not refer to the lambda; it refers to the this from the outside scope.
You could capture a mutable data structure, like an array, instead:
IntToDoubleFunction[] foo = { null };
foo[0] = x -> { return ( x == 0)?1:x* foo[0].applyAsDouble(x-1);};
though hardly an elegant solution.
If you find yourself needing to do this sort of thing often, another option is to create a helper interface and method:
public static interface Recursable<T, U> {
U apply(T t, Recursable<T, U> r);
}
public static <T, U> Function<T, U> recurse(Recursable<T, U> f) {
return t -> f.apply(t, f);
}
And then write:
Function<Integer, Double> fact = recurse(
(i, f) -> 0 == i ? 1 : i * f.apply(i - 1, f));
(While I did this generically with reference types, you can also make primitive-specific versions).
This borrows from an old trick in The Little Lisper for making unnamed functions.
I'm not sure I'd ever do this in production code, but it is interesting...
One solution is to define this function as an INSTANCE attribute.
import java.util.function.*;
public class Test{
IntToDoubleFunction fact = x -> { return ( x == 0)?1:x* fact.applyAsDouble(x-1);};
public static void main(String[] args) {
Test test = new Test();
test.doIt();
}
public void doIt(){
System.out.println("fact(3)=" + fact.applyAsDouble(3));
}
}
Another version using accumulator so that recursion can be optimised. Moved to Generic interface definition.
Function<Integer,Double> facts = x -> { return ( x == 0)?1:x* facts.apply(x-1);};
BiFunction<Integer,Double,Double> factAcc= (x,acc) -> { return (x == 0)?acc:factAcc.apply(x- 1,acc*x);};
Function<Integer,Double> fact = x -> factAcc.apply(x,1.0) ;
public static void main(String[] args) {
Test test = new Test();
test.doIt();
}
public void doIt(){
int val=70;
System.out.println("fact(" + val + ")=" + fact.apply(val));
}
}
You can define a recursive lambda as an instance or class variable:
static DoubleUnaryOperator factorial = x -> x == 0 ? 1
: x * factorial.applyAsDouble(x - 1);
for example:
class Test {
static DoubleUnaryOperator factorial = x -> x == 0 ? 1
: x * factorial.applyAsDouble(x - 1));
public static void main(String[] args) {
System.out.println(factorial.applyAsDouble(5));
}
}
prints 120.0.
public class Main {
static class Wrapper {
Function<Integer, Integer> f;
}
public static void main(String[] args) {
final Wrapper w = new Wrapper();
w.f = x -> x == 0 ? 1 : x * w.f.apply(x - 1);
System.out.println(w.f.apply(10));
}
}
The following works but it does seem arcane.
import java.util.function.Function;
class recursion{
Function<Integer,Integer> factorial_lambda; // The positions of the lambda declaration and initialization must be as is.
public static void main(String[] args) { new recursion();}
public recursion() {
factorial_lambda=(i)->{
if(i==1)
return 1;
else
return i*(factorial_lambda.apply(i-1));
};
System.out.println(factorial_lambda.apply(5));
}
}
// Output 120
A bit like the very first reply ...
public static Function<Integer,Double> factorial;
static {
factorial = n -> {
assert n >= 0;
return (n == 0) ? 1.0 : n * factorial.apply(n - 1);
};
}
I heard at the JAX this year, that "lambads do not support recursion". What is meant with this statement is that the "this" inside the lambda always refer to the surrounding class.
But I managed to define - at least how I understand the term "recursion" - a recursive lambda and it goes like that:
interface FacInterface {
int fac(int i);
}
public class Recursion {
static FacInterface f;
public static void main(String[] args)
{
int j = (args.length == 1) ? new Integer(args[0]) : 10;
f = (i) -> { if ( i == 1) return 1;
else return i*f.fac( i-1 ); };
System.out.println( j+ "! = " + f.fac(j));
}
}
Save this inside a file "Recursion.java" and with the two commands "javac Recursion.java" and "java Recursion" it worked for me.
The clou is to keep the interface that the lambda has to implement as a field variable in the surrounding class. The lambda can refer to that field and the field will not be implicitly final.
You can also define it as a local variable by creating a final array of size one (of say Function[]) and then assign the function to element 0. Let me know if you need the exact syntax
Given the fact that "this" in the lambda refers to the containing class, the following compiles with no errors (with added dependencies, of course):
public class MyClass {
Function<Map, CustomStruct> sourceToStruct = source -> {
CustomStruct result;
Object value;
for (String key : source.keySet()) {
value = source.get(key);
if (value instanceof Map) {
value = this.sourceToStruct.apply((Map) value);
}
result.setValue(key, value);
}
return result;
};
}
Came accross this question during a lecture on Lambdas that used Fibonacci as a possible use case.
You can make a recursive lambda like this:
import java.util.function.Function;
public class Fib {
static Function<Integer, Integer> fib;
public static void main(String[] args) {
fib = (n) -> { return n > 1 ? fib.apply(n-1) + fib.apply(n-2) : n; };
for(int i = 0; i < 10; i++){
System.out.println("fib(" + i + ") = " + fib.apply(i));
}
}
}
What do you have to keep in mind?
Lambdas are evaluated on execution -> they may be recursive
Using a lambda-variable inside of another lambda requires the variable to be initialized -> before defining a recursive lambda you must define it with a foo-value
using a local lambda-variable inside a lambda requires the variable to be final, thus it cannot be redefined -> use a class/ object variable for the lambda as it is initialized with a default value
The problem, is that lambda-functions want to operate on final variables, while we need a mutable Function-reference that can be replaced with our lambda.
The easiest trick, appears to be to, to define the variable as a member variable, and the compiler won't complain.
I changed my example to use IntUnaryOperator instead of IntToDoubleFunction, since we're just operating on Integers anyway here.
import org.junit.Test;
import java.util.function.IntUnaryOperator;
import static org.junit.Assert.assertEquals;
public class RecursiveTest {
private IntUnaryOperator operator;
@Test
public void factorialOfFive(){
IntUnaryOperator factorial = factorial();
assertEquals(factorial.applyAsInt(5), 120); // passes
}
public IntUnaryOperator factorial() {
return operator = x -> (x == 0) ? 1 : x * operator.applyAsInt(x - 1);
}
}
Here is a solution that does not rely on a side effect. To make the purpose interesting, let's say that you want to abstract over the recursion (otherwise the instance field solution is perfectly valid). The trick is to use an anonymous class to get the 'this' reference:
public static IntToLongFunction reduce(int zeroCase, LongBinaryOperator reduce) {
return new Object() {
IntToLongFunction f = x -> x == 0
? zeroCase
: reduce.applyAsLong(x, this.f.applyAsLong(x - 1));
}.f;
}
public static void main(String[] args) {
IntToLongFunction fact = reduce(1, (a, b) -> a * b);
IntToLongFunction sum = reduce(0, (a, b) -> a + b);
System.out.println(fact.applyAsLong(5)); // 120
System.out.println(sum.applyAsLong(5)); // 15
}
public class LambdaExperiments {
@FunctionalInterface
public interface RFunction<T, R> extends Function<T, R> {
R recursiveCall(Function<? super T, ? extends R> func, T in);
default R apply(T in) {
return recursiveCall(this, in);
}
}
@FunctionalInterface
public interface RConsumer<T> extends Consumer<T> {
void recursiveCall(Consumer<? super T> func, T in);
default void accept(T in) {
recursiveCall(this, in);
}
}
@FunctionalInterface
public interface RBiConsumer<T, U> extends BiConsumer<T, U> {
void recursiveCall(BiConsumer<T, U> func, T t, U u);
default void accept(T t, U u) {
recursiveCall(this, t, u);
}
}
public static void main(String[] args) {
RFunction<Integer, Integer> fibo = (f, x) -> x > 1 ? f.apply(x - 1) + f.apply(x - 2) : x;
RConsumer<Integer> decreasingPrint = (f, x) -> {
System.out.println(x);
if (x > 0) f.accept(x - 1);
};
System.out.println("Fibonnaci(15):" + fibo.apply(15));
decreasingPrint.accept(5);
}
}
During my tests, this is the best that i could achieve for local recursive lambdas. They can be used in streams as well but we loose the easyness of the target typing.
You can create a recursive function using this class:
public class Recursive<I> {
private Recursive() {
}
private I i;
public static <I> I of(Function<RecursiveSupplier<I>, I> f) {
Recursive<I> rec = new Recursive<>();
RecursiveSupplier<I> sup = new RecursiveSupplier<>();
rec.i = f.apply(sup);
sup.i = rec.i;
return rec.i;
}
public static class RecursiveSupplier<I> {
private I i;
public I call() {
return i;
}
}
}
And then you can use any functional interface in just 1 line using a lambda and the definition of your functional interface like the following:
Function<Integer, Integer> factorial = Recursive.of(recursive ->
x -> x == 0 ? 1 : x * recursive.call().apply(x - 1));
System.out.println(factorial.apply(5));
I found it very intuitive and easy to use.
Another recursive factorial with Java 8
public static int factorial(int i) {
final UnaryOperator<Integer> func = x -> x == 0 ? 1 : x * factorial(x - 1);
return func.apply(i);
}
I don't have a Java8 compiler handy, so can't test my answer. But will it work if you define the 'fact' variable to be final?
final IntToDoubleFunction fact = x -> {
return ( x == 0)?1:x* fact.applyAsDouble(x-1);
};
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://img.manongdao.com/sparkler-677774__340.jpg', '推荐 再贱就再见 的文章《Implement recursive lambda function using Java 8》','https://www.manongdao.com/article-145367.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}