使用Java 8实现递归lambda函数

Java 8 introduced lambda functions and I want to implement something like factorial:

Java 8引入了lambda函数，我想实现像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.

我怎样才能参考功能本身。类是匿名的但是实例存在：它被称为事实。

20 个解决方案

#1

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);
}

#2

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).

一种方法是编写辅助函数helper，它接受一个函数和一个数字作为参数，然后编写你真正想要的函数，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.

但是，由于Java的类型系统，它不是一个完美的解决方案 - 泛型不能保证f（factHelper的参数）与factHelper（即相同的输入类型和输出类型）的类型相同，因为它将是无限嵌套的通用的。

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.

从factHelper的不完美的泛型类型产生的代码气味现在包含在lambda中（或者，我敢说，封装），确保在不知情的情况下永远不会调用factHelper。

#3

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.

本地和匿名类以及lambdas在创建时按值捕获局部变量。因此，他们不可能通过捕获局部变量来引用自己，因为在创建它们时，指向它们的值还不存在。

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.

本地和匿名类中的代码仍然可以使用它来引用自己。然而，这在lambda中并不是指lambda;它从外部范围引用这个。

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.

虽然不是优雅的解决方案。

#4

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.

这借用了The Little Lisper中的一个老技巧来制作未命名的功能。

I'm not sure I'd ever do this in production code, but it is interesting...

我不确定我是否会在生产代码中执行此操作，但它很有趣......

#5

One solution is to define this function as an INSTANCE attribute.

一种解决方案是将此函数定义为INSTANCE属性。

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));
    }
}

#6

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));
}
}

#7

You can define a recursive lambda as an instance or class variable:

您可以将递归lambda定义为实例或类变量：

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.

打印120.0。

#8

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));
    }
}

#9

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

#10

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);
    };
}

#11

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.

我今年在JAX上听说过“lambads不支持递归”。这个陈述的含义是lambda中的“this”总是指周围的类。

But I managed to define - at least how I understand the term "recursion" - a recursive lambda and it goes like that:

但我设法定义 - 至少我如何理解术语“递归” - 一个递归的lambda，它就像这样：

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.

将其保存在文件“Recursion.java”中，并使用两个命令“javac Recursion.java”和“java Recursion”，它对我有用。

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.

clou是保持lambda必须实现的接口作为周围类中的字段变量。 lambda可以引用该字段，该字段不会隐式最终。

#12

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

您还可以通过创建一个大小为1的最终数组（比如Function []）将其定义为局部变量，然后将该函数分配给元素0.如果您需要确切的语法，请告诉我。

#13

Given the fact that "this" in the lambda refers to the containing class, the following compiles with no errors (with added dependencies, of course):

鉴于lambda中的“this”指向包含类，以下编译时没有错误（当然，添加了依赖项）：

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;
    };
}

#14

Came accross this question during a lecture on Lambdas that used Fibonacci as a possible use case.

在使用Fibonacci作为可能的用例的Lambdas讲座中遇到了这个问题。

You can make a recursive lambda like this:

你可以像这样制作一个递归的lambda：

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

  Lambda在执行时进行评估 - >它们可能是递归的

• 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

  在另一个lambda中使用lambda变量需要初始化变量 - >在定义递归lambda之前，你必须用foo值定义它

• 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

  在lambda中使用局部lambda变量需要变量为final，因此无法重新定义 - >使用lambda的类/对象变量，因为它使用默认值初始化

#15

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.

问题是，lambda函数想要对最终变量进行操作，而我们需要一个可以用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.

我改变了我的例子以使用IntUnaryOperator而不是IntToDoubleFunction，因为我们只是在这里操作Integers。

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);
    }
}

#16

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:

这是一个不依赖于副作用的解决方案。为了使目的有趣，让我们说你想要在递归上进行抽象（否则实例字段解决方案是完全有效的）。诀窍是使用匿名类来获取'this'引用：

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
}

#17

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.

在我的测试中，这是我可以为本地递归lambdas实现的最好的。它们也可以在流中使用，但是我们放弃了目标类型的简单性。

#18

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:

然后，您可以使用lambda和功能界面的定义在一行中使用任何功能界面，如下所示：

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.

我发现它非常直观且易于使用。

#19

Another recursive factorial with Java 8

Java 8的另一个递归因子

public static int factorial(int i) {
    final UnaryOperator<Integer> func = x -> x == 0 ? 1 : x * factorial(x - 1);
    return func.apply(i);
}

#20

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?

我没有Java8编译器方便，所以无法测试我的答案。但如果你将'fact'变量定义为final，它会起作用吗？

final IntToDoubleFunction fact = x -> {
    return  ( x == 0)?1:x* fact.applyAsDouble(x-1);
};