wake-up-neo.net

Implementieren Sie die rekursive Lambda-Funktion mit Java 8

In Java 8 wurden Lambda-Funktionen eingeführt, und ich möchte etwas wie Fakultät implementieren:

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

Zusammenstellung kehrt zurück

  error: variable fact might not have been initialized

Wie kann ich die Funktion selbst referenzieren? Klasse ist anonym, aber eine Instanz ist vorhanden: Sie heißt fact.

47
user2678835

Normalerweise verwende ich eine (für alle Funktionalitäten definierte Schnittstelle), die die generische Helper-Klasse definiert, die die Variable des funktionalen Schnittstellentyps umgibt. Dieser Ansatz löst das Problem mit der Initialisierung der lokalen Variablen und lässt den Code klarer aussehen.

Im Falle dieser Frage sieht der Code folgendermaßen aus:

// 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);
}
38
Andrey Morozov

Eine Möglichkeit ist, eine sekundäre Funktion, helper, zu schreiben, die eine Funktion und eine Zahl als Argumente verwendet, und dann die gewünschte Funktion zu schreiben, fact = helper(helper,x).

So wie:

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

Dies scheint mir etwas eleganter zu sein, als sich auf die Eckfall-Semantik zu verlassen, beispielsweise auf einen Verschluss, der einen Bezug zu einer veränderlichen Struktur aufnimmt, oder das Erlauben einer Selbstreferenz mit der Warnung vor der Möglichkeit, dass "möglicherweise nicht initialisiert wird".

Aufgrund des Java-Typensystems ist dies jedoch keine perfekte Lösung - die Generics können nicht garantieren, dass f, das Argument für factHelper, vom selben Typ ist wie factHelper (dh dieselben Eingabe- und Ausgabetypen), da dies unendlich verschachtelt wäre generisch.

Eine sicherere Lösung könnte daher sein:

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

Der Code-Geruch, der durch den weniger als perfekten generischen Typ von factHelper entsteht, ist jetzt im Lambda enthalten (oder kann ich sagen, dass er eingekapselt ist), um sicherzustellen, dass factHelper niemals unwissentlich aufgerufen wird.

16
rationalis

Lokale und anonyme Klassen sowie Lambdas erfassen lokale Variablen nach Wert , wenn sie erstellt werden. Daher ist es ihnen unmöglich, sich durch Erfassen einer lokalen Variablen auf sich selbst zu beziehen, da der Wert für das Zeigen auf sich selbst zum Zeitpunkt der Erstellung noch nicht vorhanden ist.

Code in lokalen und anonymen Klassen kann mithilfe von this weiterhin auf sich selbst verweisen. this in einem Lambda bezieht sich jedoch nicht auf das Lambda; es bezieht sich auf die this von außerhalb.

Sie können stattdessen eine veränderliche Datenstruktur wie ein Array erfassen:

IntToDoubleFunction[] foo = { null };
foo[0] = x -> { return  ( x == 0)?1:x* foo[0].applyAsDouble(x-1);};

aber kaum eine elegante Lösung.

13
newacct

Wenn Sie dies häufig tun müssen, können Sie eine Hilfsschnittstelle und -methode erstellen:

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

Und dann schreibe:

Function<Integer, Double> fact = recurse(
    (i, f) -> 0 == i ? 1 : i * f.apply(i - 1, f));

(Während ich dies generisch mit Referenztypen gemacht habe, können Sie auch primitivspezifische Versionen erstellen.).

Dies entlehnt einen alten Trick in The Little Lisper für die Erstellung unbenannter Funktionen.

Ich bin mir nicht sicher, ob ich das jemals im Produktionscode machen würde, aber es ist interessant ...

5
Ian Robertson

Sie können ein rekursives Lambda als Instanz- oder Klassenvariable definieren:

static DoubleUnaryOperator factorial = x -> x == 0 ? 1
                                          : x * factorial.applyAsDouble(x - 1);

zum Beispiel:

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

druckt 120.0.

2
assylias
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));
    }
}
2
Danil Gaponov

Ein bisschen wie die allererste Antwort ... 

public static Function<Integer,Double> factorial;

static {
    factorial = n -> {
        assert n >= 0;
        return (n == 0) ? 1.0 : n * factorial.apply(n - 1);
    };
}
2
Rene.v.P.

Eine andere Version, die einen Akkumulator verwendet, so dass die Rekursion optimiert werden kann.

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

Das folgende funktioniert aber es erscheint unsichtbar. 

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
2
Jerrolds

Eine Lösung besteht darin, diese Funktion als INSTANCE-Attribut zu definieren.

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

Sie können sie auch als lokale Variable definieren, indem Sie ein letztes Array der Größe eins erstellen (zB Funktion []) und die Funktion dann Element 0 zuweisen. Geben Sie mir Bescheid, wenn Sie die genaue Syntax benötigen

1
Victor Grazi

Diese Frage wurde in einem Vortrag über Lambdas beantwortet, in dem Fibonacci als möglicher Anwendungsfall verwendet wurde.

Sie können einen rekursiven Lambda wie folgt machen:

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

Was muss man beachten?

  • Lambdas werden bei der Ausführung ausgewertet -> sie können rekursiv sein

  • Um eine Lambda-Variable in einem anderen Lambda zu verwenden, muss die -Variable initialisiert werden ->, bevor ein rekursives Lambda definiert werden kann. Sie Muss es mit einem foo-Wert definieren

  • um eine lokale Lambda-Variable in einem Lambda zu verwenden, muss die Variable als final angegeben werden. Daher kann sie nicht neu definiert werden -> Verwenden Sie eine Klasse/Objekt-Variable für das Lambda , da es mit einem Standardwert initialisiert wird

Ich habe dieses Jahr auf der JAX gehört, dass "Lambads keine Rekursion unterstützen". Mit dieser Aussage ist gemeint, dass sich das "dieses" im Lambda immer auf die umgebende Klasse bezieht.

Aber es gelang mir - zumindest wie ich den Begriff "Rekursion" verstehe - ein rekursives Lambda zu definieren und es geht so:

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

Speichern Sie dies in einer Datei "Recursion.Java" und mit den beiden Befehlen "javac Recursion.Java" und "Java Recursion" hat es für mich funktioniert.

Der Clou besteht darin, die Schnittstelle, die das Lambda als Feldvariable implementieren muss, in der umgebenden Klasse beizubehalten. Das Lambda kann sich auf dieses Feld beziehen, und das Feld ist nicht implizit endgültig.

1
beck

Die Antwort lautet: Sie müssen eine this before name-Variable verwenden, die die Funktion applyAsDouble aufruft: -

IntToDoubleFunction fact = x -> x == 0 ? 1 : x * this.fact.applyAsDouble(x-1);

wenn Sie die Tatsache endgültig machen, wird es auch funktionieren

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

Wir können funktionale Schnittstelle UnaryOperator hier verwenden. Ein unärer Operator, der immer sein Eingabeargument zurückgibt.

1) Füge einfach this hinzu. vor dem Namen der Funktion, wie in:

UnaryOperator<Long> fact = x -> x == 0 ? 1  : x * this.fact.apply(x - 1 );

Dies vermeidet Folgendes: "Kann nicht auf ein Feld verweisen, bevor es definiert ist" .

2) Wenn Sie ein statisches Feld bevorzugen, ersetzen Sie dieses einfach durch den Namen der Klasse:

static final UnaryOperator<Long> fact = x -> x== 0? 1: x * MyFactorial.fact.apply(x - 1 );
1
Arundev

In Anbetracht der Tatsache, dass "dieses" im Lambda sich auf die enthaltende Klasse bezieht, wird Folgendes fehlerfrei kompiliert (natürlich mit zusätzlichen Abhängigkeiten):

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;
    };
}
1
Rebel Geek

@IanRobertson Gut gemacht, in der Tat können Sie die statische 'Factory' in den Hauptteil der Schnittstelle selbst verschieben und so vollständig einkapseln:

public static interface Recursable<T, U> {
        U apply(T t, Recursable<T, U> r);

        public static <T, U> Function<T, U> recurseable(Recursable<T, U> f) {
            return t -> f.apply(t, f);
        }
}

Dies ist die sauberste Lösung/Antwort, die ich bisher gesehen habe ... zumal der Aufruf von "fact" "natural" lautet: fac.apply (n), was Sie für eine unäre Funktion wie fac (erwarten würden. )

1
Larry Cable

Das Problem ist, dass Lambda-Funktionen mit final-Variablen arbeiten wollen, während wir eine veränderliche Function- Referenz benötigen, die durch unser Lambda ersetzt werden kann.

Der einfachste Trick scheint zu sein, die Variable als Member-Variable zu definieren, und der Compiler beschwert sich nicht.

Ich habe mein Beispiel geändert, um IntUnaryOperator anstelle von IntToDoubleFunction zu verwenden, da wir hier sowieso nur mit Integers arbeiten.

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

Während meiner Tests ist dies das Beste, was ich für lokale rekursive Lambdas erreichen könnte .. __ Sie können auch in Streams verwendet werden, aber wir verlieren die Leichtigkeit der Zieltypisierung.

0

Das übliche Thema bei Antworten ist, dass Lambdas rekursiv sein können, vorausgesetzt, sie haben einen festen Bezugspunkt (daher die klassen-/schnittstellenbasierten Antworten wie @ assylias , @ Andrey Morozov) , @ Ian Robertson , etc).

Die Antwort von @ 0000000000000000000 mit der Problemumgehung für die Mitgliedsvariable hat mir sehr gut gefallen, aber ich habe Bedenken, ob die beabsichtigte Lambda-Funktion auf andere Variablen aus dem Bereich der enthaltenden Funktion verweisen wollte. Sicherlich werden diese lokalen Referenzen bei der Zuweisung ausgewertet und die resultierende Funktion in eine Mitgliedsvariable eingefügt, auf die mit anderen Methoden in der Klasse zugegriffen werden kann. Das klingt nicht ... richtig (und könnte recht interessant werden, wenn die enthaltende Methode selbst rekursiv aufgerufen wird).

Das Folgende ist eine Variation der klassenbasierten Lösungen, ausgedrückt in einer Form, die dem ursprünglichen einzeiligen Lambda des OP nahe kommt, über die sich Eclipse jedoch nicht beschwert.

IntToDoubleFunction fact = new IntToDoubleFunction() {
    @Override
    public double applyAsDouble(int x) {
        return x == 0 ? 1 : x * this.applyAsDouble(x-1);
    }
};

Das {} erzeugt natürlich eine anonyme Klasse und damit einen neuen Gültigkeitsbereich mit Bezugspunkten für die Lambda-Bewertung, mit dem zusätzlichen Vorteil, weiterhin im eigenen Gültigkeitsbereich der Funktion und damit in "Geschwistervariablen" zu sein.

0
A Paul Anthony

Sie können mit dieser Klasse eine rekursive Funktion erstellen:

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

Und dann können Sie jede funktionale Schnittstelle in nur einer Zeile mit einem Lambda und der Definition Ihrer funktionalen Schnittstelle wie folgt verwenden:

Function<Integer, Integer> factorial = Recursive.of(recursive ->
        x -> x == 0 ? 1 : x * recursive.call().apply(x - 1));
System.out.println(factorial.apply(5));

Ich fand es sehr intuitiv und einfach zu bedienen.

0
Jose Da Silva

Hier ist eine Lösung, die sich nicht auf einen Nebeneffekt stützt. Um den Zweck interessant zu machen, lassen Sie uns sagen, dass Sie über die Rekursion abstrahieren möchten (andernfalls ist die Instanzfeldlösung vollkommen gültig).

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
}
0
JbGi

Ein weiterer rekursiver Faktor mit Java 8

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