Wie man nützliche Java-Programme schreibt, ohne veränderbare Variablen zu verwenden

Ich habe einen Artikel über funktionale Programmierung gelesen, in dem der Autor angibt

(take 25 (squares-of (integers)))

Beachten Sie, dass es keine Variablen hat. In der Tat hat es nicht mehr als drei Funktionen und eine Konstante. Versuchen Sie, die Quadrate von Ganzzahlen in Java zu schreiben, ohne eine Variable zu verwenden. Oh, es gibt wahrscheinlich eine Möglichkeit, dies zu tun, aber es ist sicherlich nicht natürlich und es würde nicht so gut lesen wie mein Programm oben.

Ist es möglich, dies in Java zu erreichen? Angenommen, Sie müssen die Quadrate der ersten 15 Ganzzahlen drucken. Können Sie eine for- oder while-Schleife schreiben, ohne Variablen zu verwenden?

Mod hinweis

Diese Frage ist kein Code-Golf-Wettbewerb. Wir suchen nach Antworten, die die Konzepte erklären (im Idealfall ohne Wiederholung früherer Antworten), und nicht nur nach einem weiteren Teil des Codes.

Ist es möglich, ein solches Beispiel in Java zu implementieren, ohne destruktive Updates zu verwenden? Ja. Wie @Thiton und der Artikel selbst bereits erwähnten, wird es jedoch hässlich sein (je nach Geschmack). Eine Möglichkeit ist die Verwendung von Rekursion. Hier ist ein Haskell- Beispiel, das etwas Ähnliches tut:

unfoldr      :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b  =
  case f b of
   Just (a,new_b) -> a : unfoldr f new_b
   Nothing        -> []  

Anm. 1) das Fehlen von Mutationen, 2) die Verwendung von Rekursionen und 3) das Fehlen von Schleifen. Der letzte Punkt ist sehr wichtig - funktionale Sprachen benötigen keine in die Sprache eingebauten Schleifenkonstrukte, da die Rekursion für die meisten (alle?) Fälle verwendet werden kann, in denen Schleifen in Java verwendet werden. Hier ist eine bekannte Reihe von Artikeln, die zeigen, wie unglaublich ausdrucksstark Funktionsaufrufe sein können.

Ich fand den Artikel unbefriedigend und möchte ein paar zusätzliche Punkte ansprechen:

Dieser Artikel ist eine sehr schlechte und verwirrende Erklärung der funktionalen Programmierung und ihrer Vorteile. Für das Erlernen der funktionalen Programmierung empfehle ich dringend andere Quellen .

Der verwirrendste Teil des Artikels ist, dass nicht erwähnt wird, dass es in Java (und den meisten anderen gängigen Sprachen) zwei Verwendungszwecke für Zuweisungsanweisungen gibt:

1. Einen Wert an einen Namen binden: final int MAX_SIZE = 100;

2. destruktives Update: int a = 3; a += 1; a++;

Die funktionale Programmierung vermeidet die zweite, umfasst aber die erste (Beispiele: let-Ausdrücke, Funktionsparameter, I definetionen der obersten Ebene ) . Dies ist ein sehr wichtiger Punkt zu erfassen, da sonst nur der Artikel albern scheint , und vielleicht lassen Sie sich fragen, was ist take, squares-ofund integerswenn keine Variablen?

Darüber hinaus ist das Beispiel bedeutungslos. Es zeigt nicht die Implementierungen take, squares-ofoder integers. Soweit wir wissen, werden sie mit veränderlichen Variablen implementiert. Wie @Martin sagte, können Sie dieses Beispiel einfach in Java schreiben.

Ich würde wieder einmal empfehlen, diesen Artikel zu meiden und andere mögen ihn, wenn Sie wirklich etwas über funktionale Programmierung lernen möchten. Es scheint eher mit dem Ziel geschrieben zu sein, zu schockieren und zu beleidigen, als Konzepte und Grundlagen zu vermitteln. Schauen Sie sich stattdessen eine meiner Lieblingszeitungen von John Hughes an. Hughes versucht, einige der gleichen Probleme anzugehen, die in dem Artikel behandelt wurden (obwohl Hughes nicht über Parallelität / Parallelisierung spricht). Hier ist ein Teaser:

Dieses Papier ist ein Versuch, der größeren Gemeinschaft von (nicht funktionsfähigen) Programmierern die Bedeutung der funktionalen Programmierung zu demonstrieren und den funktionalen Programmierern dabei zu helfen, ihre Vorteile voll auszuschöpfen, indem klargestellt wird, was diese Vorteile sind.

[...]

Wir werden im Rest dieses Papiers argumentieren, dass funktionale Sprachen zwei neue, sehr wichtige Arten von Leim liefern. Wir werden einige Beispiele für Programme nennen, die auf neue Weise modularisiert und dadurch vereinfacht werden können. Dies ist der Schlüssel zur Leistungsfähigkeit der funktionalen Programmierung - sie ermöglicht eine verbesserte Modularisierung. Es ist auch das Ziel, nach dem sich funktionierende Programmierer bemühen müssen - kleinere, einfachere und allgemeinere Module, die mit den neuen Klebstoffen, die wir beschreiben werden, zusammengeklebt werden.

Das würdest du nicht. Variablen sind der Kern der imperativen Programmierung, und wenn Sie versuchen, imperativ zu programmieren, ohne Variablen zu verwenden, bereiten Sie nur allen Ärgernissen. In unterschiedlichen Programmierparadigmen sind die Stile unterschiedlich, und unterschiedliche Konzepte bilden Ihre Grundlage. Eine Variable in Java ist, wenn sie mit einem kleinen Bereich gut verwendet wird, nicht böse. Ein Java-Programm ohne Variablen anzufordern ist wie ein Haskell-Programm ohne Funktionen anzufordern, also fragen Sie nicht danach und lassen Sie sich nicht dazu verleiten, die imperative Programmierung als minderwertig anzusehen, weil sie Variablen verwendet.

Der Java-Weg wäre also:

for (int i = 1; i <= 25; ++i) {
    System.out.println(i*i);
}

und lassen Sie sich nicht täuschen, es aufgrund des Hasses auf Variablen auf komplexere Weise zu schreiben.

Das einfachste, was ich mit Rekursion machen kann, ist eine Funktion mit einem Parameter. Es ist nicht sehr Java-artig, aber es funktioniert:

public class squares
{
    public static void main(String[] args)
    {
        squares(15);
    }

    private static void squares(int x)
    {
        if (x>0)
        {
            System.out.println(x*x);
            squares(x-1);
        }
    }
}

In Ihrem Funktionsbeispiel sehen wir nicht, wie die Funktionen squares-ofund takeimplementiert sind. Ich bin kein Java-Experte, aber ich bin mir ziemlich sicher, dass wir diese Funktionen schreiben könnten, um eine Aussage wie diese zu ermöglichen ...

squares_of(integers).take(25);

das ist nicht so ganz anders.

In Java können Sie dies (insbesondere den unendlichen Listenteil) mit Iteratoren tun. Im folgenden Codebeispiel kann die an den TakeKonstruktor übergebene Zahl beliebig hoch sein.

class Example {
    public static void main(String[] a) {
        Numbers test = new Take(25, new SquaresOf(new Integers()));
        while (test.hasNext())
            System.out.println(test.next());
    }
}

Oder mit verkettbaren Factory-Methoden:

class Example {
    public static void main(String[] a) {
        Numbers test = Numbers.integers().squares().take(23);
        while (test.hasNext())
            System.out.println(test.next());
    }
}

Wo SquaresOf, Takeund IntegerserweiternNumbers

abstract class Numbers implements Iterator<Integer> {
    public static Numbers integers() {
        return new Integers();
    }

    public Numbers squares() {
        return new SquaresOf(this);
    }

    public Numbers take(int c) {
        return new Take(c, this);
    }
    public void remove() {}
}

Kurzfassung:

Damit Single-Assignment-Stile in Java zuverlässig funktionieren, benötigen Sie (1) eine unveränderliche Infrastruktur und (2) Unterstützung auf Compiler- oder Laufzeitebene für die Tail-Call-Eliminierung.

Wir können einen Großteil der Infrastruktur schreiben und Dinge arrangieren, um zu vermeiden, dass der Stapel gefüllt wird. Solange jedoch jeder Aufruf einen Stack-Frame benötigt, ist die Anzahl der möglichen Rekursionen begrenzt. Halten Sie Ihre iterables klein und / oder faul, und Sie sollten keine größeren Probleme haben. Zumindest die meisten Probleme, auf die Sie stoßen, erfordern nicht die sofortige Rückgabe von einer Million Ergebnissen. :)

Beachten Sie auch, dass Sie nicht alles unveränderlich machen können, da das Programm sichtbare Änderungen vornehmen muss, damit es sich lohnt, ausgeführt zu werden . Sie können jedoch den Großteil Ihrer eigenen Daten unveränderlich halten, indem Sie nur an bestimmten wichtigen Stellen, an denen die Alternativen zu lästig wären, eine winzige Teilmenge der wesentlichen veränderlichen Daten (z. B. Streams) verwenden.

Lange Version:

Einfach ausgedrückt, ein Java-Programm kann Variablen nicht vollständig vermeiden, wenn es etwas tun möchte, das es wert ist, getan zu werden. Sie können enthalten und somit die Veränderlichkeit in hohem Maße einschränken, aber das eigentliche Design der Sprache und der API sowie die Notwendigkeit, das zugrunde liegende System zu ändern, machen eine vollständige Unveränderlichkeit unmöglich.

Java wurde von Anfang an als imperative , objektorientierte Sprache konzipiert.

• Imperative Sprachen hängen fast immer von veränderlichen Variablen ab. Sie bevorzugen zum Beispiel die Iteration gegenüber der Rekursion und fast alle iterativen Konstrukte - sogar while (true)und for (;;)! - sind absolut abhängig von einer Variablen, die sich von Iteration zu Iteration ändert.
• Objektorientierte Sprachen stellen sich fast jedes Programm als ein Diagramm von Objekten vor, die Nachrichten aneinander senden und in fast allen Fällen auf diese Nachrichten reagieren, indem sie etwas mutieren.

Das Endergebnis dieser Entwurfsentscheidungen ist, dass Java ohne veränderbare Variablen keine Möglichkeit hat, den Status von irgendetwas zu ändern - selbst von etwas so Einfachem wie dem Drucken von "Hallo Welt!" zum Bildschirm gehört ein Ausgabestream, bei dem Bytes in eine veränderbare Datei eingefügt werden Puffer .

Aus praktischen Gründen beschränken wir uns darauf, die Variablen aus unserem eigenen Code zu verbannen . OK, das können wir irgendwie machen. Fast. Grundsätzlich müssten wir fast alle Iterationen durch Rekursionen und alle Mutationen durch rekursive Aufrufe ersetzen, die den geänderten Wert zurückgeben. wie so ...

class Ints {
     final int value;
     final Ints tail;

     public Ints(int value, Ints rest) {
         this.value = value;
         this.tail = rest;
     }
     public Ints next() { return this.tail; }
     public int value() { return this.value; }
}

public Ints take(int count, Ints input) {
    if (count == 0 || input == null) return null;
    return new Ints(input.value(), take(count - 1, input.next()));
}    

public Ints squares_of(Ints input) {
    if (input == null) return null;
    int i = input.value();
    return new Ints(i * i, squares_of(input.next()));
}

Grundsätzlich erstellen wir eine verknüpfte Liste, wobei jeder Knoten eine Liste für sich ist. Jede Liste hat einen "Kopf" (den aktuellen Wert) und einen "Schwanz" (die verbleibende Unterliste). Die meisten funktionalen Sprachen tun etwas Ähnliches, weil sie einer effizienten Unveränderlichkeit sehr zugänglich sind. Eine "nächste" Operation gibt nur das Ende zurück, das normalerweise in einem Stapel rekursiver Aufrufe an die nächste Ebene übergeben wird.

Dies ist eine extrem vereinfachte Version dieses Materials. Aber es ist gut genug, um ein ernstes Problem mit diesem Ansatz in Java zu demonstrieren. Betrachten Sie diesen Code:

public function doStuff() {
    final Ints integers = ...somehow assemble list of 20 million ints...;
    final Ints result = take(25, squares_of(integers));
    ...
}

Obwohl wir nur 25 Zoll für das Ergebnis benötigen, squares_ofweiß das nicht. Es wird das Quadrat jeder Zahl in zurückgeben integers. Eine Rekursion mit einer Tiefe von 20 Millionen Ebenen verursacht in Java ziemlich große Probleme.

Sehen Sie, die funktionalen Sprachen, in denen Sie normalerweise so verrückt sind, haben eine Funktion namens "Tail Call Elimination". Dies bedeutet, dass der Compiler, wenn er sieht, dass der Code zuletzt sich selbst aufruft (und das Ergebnis zurückgibt, wenn die Funktion nicht ungültig ist), den Stapelrahmen des aktuellen Aufrufs verwendet, anstatt einen neuen zu erstellen, und stattdessen einen "Sprung" ausführt eines "Aufrufs" (so bleibt der verwendete Stapelspeicherplatz konstant). Kurz gesagt geht es um 90% des Weges, um die Schwanzrekursion in Iteration umzuwandeln. Es könnte mit diesen Milliarden-Ints umgehen, ohne den Stapel zu überschwemmen. (Es würde schließlich immer noch nicht genügend Arbeitsspeicher zur Verfügung stehen, aber das Zusammenstellen einer Liste mit einer Milliarde Ints wird Sie auf einem 32-Bit-System sowieso speicherintensiv machen.)

Java macht das in den meisten Fällen nicht. (Es hängt vom Compiler und der Laufzeit ab, aber die Oracle-Implementierung tut dies nicht.) Jeder Aufruf einer rekursiven Funktion beansprucht den Speicher eines Stack-Frames. Wenn Sie zu viel verbrauchen, kommt es zu einem Stapelüberlauf. Ein Überlaufen des Stapels garantiert jedoch den Tod des Programms. Also müssen wir sicherstellen, dass wir das nicht tun.

Eine Problemumgehung ... faule Auswertung. Wir haben immer noch die Stack-Beschränkungen, aber sie können mit Faktoren zusammenhängen, über die wir mehr Kontrolle haben. Wir müssen nicht eine Million Ints kalkulieren, um 25 zurückzugeben. :)

Bauen wir also eine Lazy-Evaluation-Infrastruktur auf. (Dieser Code wurde vor einiger Zeit getestet, aber ich habe ihn seitdem ziemlich verändert. Lies die Idee, nicht die Syntaxfehler. :))

// Represents something that can give us instances of OutType.
// We can basically treat this class like a list.
interface Source<OutType> {
     public Source<OutType> next();
     public OutType value();
}

// Represents an operation that turns an InType into an OutType.
// Note, these can be the same type.  We're just flexible like that.
interface Transform<InType, OutType> {
    public OutType appliedTo(InType input);
}

// Represents an action (as opposed to a function) that can run on
// every element of a sequence.
abstract class Action<InType> {
    abstract void doWith(final InType input);
    public void doWithEach(final Source<InType> input) {
        if (input == null) return;
        doWith(input.value());
        doWithEach(input.next());
    }
}

// A list of Integers.
class Ints implements Source<Integer> {
     final Integer value;
     final Ints tail;
     public Ints(Integer value, Ints rest) {
         this.value = value;
         this.tail = rest;
     }
     public Ints(Source<Integer> input) {
         this.value = input.value();
         this.tail = new Ints(input.next());
     }
     public Source<Integer> next() { return this.tail; }
     public Integer value() { return this.value; }
     public static Ints fromArray(Integer[] input) {
         return fromArray(input, 0, input.length);
     }
     public static Ints fromArray(Integer[] input, int start, int end) {
         if (end == start || input == null) return null;
         return new Ints(input[start], fromArray(input, start + 1, end));
     }
}

// An example of the spiff we get by splitting the "iterator" interface
// off.  These ints are effectively generated on the fly, as opposed to
// us having to build a huge list.  This saves huge amounts of memory
// and CPU time, for the rather common case where the whole sequence
// isn't needed.
class Range implements Source<Integer> {
    final int start, end;
    public Range(int start, int end) {
        this.start = start;
        this.end = end;
    }
    public Integer value() { return start; }
    public Source<Integer> next() {
        if (start >= end) return null;
        return new Range(start + 1, end);
    }
}

// This takes each InType of a sequence and turns it into an OutType.
// This *takes* a Transform, rather than just *implementing* Transform,
// because the transforms applied are likely to be specified inline.
// If we just let people override `value()`, we wouldn't easily know what type
// to return, and returning our own type would lose the transform method.
static class Mapper<InType, OutType> implements Source<OutType> {
    private final Source<InType> input;
    private final Transform<InType, OutType> transform;

    public Mapper(Transform<InType, OutType> transform, Source<InType> input) {
        this.transform = transform;
        this.input = input;
    }

    public Source<OutType> next() {
         return new Mapper<InType, OutType>(transform, input.next());
    }
    public OutType value() {
         return transform.appliedTo(input.value());
    }
}

// ...

public <T> Source<T> take(int count, Source<T> input) {
    if (count <= 0 || input == null) return null;
    return new Source<T>() {
        public T value() { return input.value(); }
        public Source<T> next() { return take(count - 1, input.next()); }
    };
}

(Denken Sie daran, dass, wenn dies in Java tatsächlich möglich wäre, Code, der zumindest in etwa der oben genannten Form entspricht, bereits Teil der API ist.)

Wenn eine Infrastruktur vorhanden ist, ist das Schreiben von Code, der keine veränderlichen Variablen benötigt und zumindest für kleinere Eingabemengen stabil ist, eher trivial.

public Source<Integer> squares_of(Source<Integer> input) {
     final Transform<Integer, Integer> square = new Transform<Integer, Integer>() {
         public Integer appliedTo(final Integer i) { return i * i; }
     };
     return new Mapper<>(square, input);
}


public void example() {
    final Source<Integer> integers = new Range(0, 1000000000);

    // and, as for the author's "bet you can't do this"...
    final Source<Integer> squares = take(25, squares_of(integers));

    // Just to make sure we got it right :P
    final Action<Integer> printAction = new Action<Integer>() {
        public void doWith(Integer input) { System.out.println(input); }
    };
    printAction.doWithEach(squares);
}

Dies funktioniert meistens, aber es ist immer noch etwas anfällig für Stapelüberläufe. Versuchen takeSie es mit 2 Milliarden Ints und machen Sie etwas dagegen. : P Irgendwann wird eine Ausnahme ausgelöst, mindestens bis 64 GB RAM zum Standard werden. Das Problem ist, dass der für den Stack reservierte Speicher eines Programms nicht so groß ist. Es liegt normalerweise zwischen 1 und 8 MiB. (Sie können für größere fragen, aber es spielt keine Rolle , dass alle viel , wie viel Sie verlangen - Sie rufen take(1000000000, someInfiniteSequence)Sie wird . Eine Ausnahme erhalten) Zum Glück, mit lazy evaluation, die Schwachstelle liegt in einem Gebiet können wir besser kontrollieren . Wir müssen nur vorsichtig sein, wie viel wir take().

Es wird immer noch viele Probleme beim Skalieren geben, da unsere Stapelverwendung linear zunimmt. Jeder Aufruf behandelt ein Element und leitet den Rest an einen anderen Aufruf weiter. Nun, da ich darüber nachdenke, gibt es einen Trick, den wir anwenden können, der uns möglicherweise mehr Spielraum verschafft: Die Anrufkette in einen Baum von Anrufen verwandeln . Betrachten Sie etwas Ähnliches:

public <T> void doSomethingWith(T input) { /* magic happens here */ }
public <T> Source<T> workWith(Source<T> input, int count) {
    if (count < 0 || input == null) return null;
    if (count == 0) return input;
    if (count == 1) {
        doSomethingWith(input.value());
        return input.next();
    }
    return (workWith(workWith(input, count/2), count - count/2);
}

workWithteilt die Arbeit im Grunde genommen in zwei Hälften auf und ordnet jede Hälfte einem anderen Aufruf zu. Da jeder Aufruf die Größe der Arbeitsliste eher um die Hälfte als um eins verringert, sollte dies logarithmisch und nicht linear skaliert werden.

Das Problem ist, dass diese Funktion eine Eingabe benötigt - und bei einer verknüpften Liste muss die gesamte Liste durchlaufen werden, um die Länge zu ermitteln. Das ist jedoch leicht zu lösen. Es ist einfach egal, wie viele Einträge es gibt. :) Der obige Code würde mit so etwas wie Integer.MAX_VALUEder Zählung funktionieren , da eine Null die Verarbeitung sowieso anhält. Die Zählung ist größtenteils vorhanden, sodass wir einen soliden Basisfall haben. Wenn Sie damit rechnen, mehr als Integer.MAX_VALUEEinträge in einer Liste zu haben, können Sie workWithden Rückgabewert überprüfen - er sollte am Ende null sein. Ansonsten rekursiv.

Denken Sie daran, dies berührt so viele Elemente, wie Sie es wünschen. Es ist nicht faul; es macht seine Sache sofort. Sie möchten dies nur für Aktionen ausführen, d. H. Für Objekte, deren einziger Zweck darin besteht, sich auf jedes Element in einer Liste anzuwenden. Wenn ich es mir gerade überlege, scheint es mir, dass Sequenzen viel weniger kompliziert wären, wenn sie linear gehalten würden. sollte kein Problem sein, da Sequenzen sich sowieso nicht selbst aufrufen - sie erstellen einfach Objekte, die sie erneut aufrufen.

Ich habe zuvor versucht, einen Interpreter für eine Lispel-ähnliche Sprache in Java zu erstellen (vor ein paar Jahren ging der gesamte Code verloren, wie er in CVS bei SourceForge war), und die Java-Utiliteratoren sind ein bisschen wortreich für die funktionale Programmierung auf Listen.

Hier ist etwas basierend auf einer Sequenzschnittstelle, die nur die beiden Operationen enthält, die Sie benötigen, um den aktuellen Wert abzurufen und die Sequenz ab dem nächsten Element abzurufen. Diese werden nach den Funktionen im Schema head und tail genannt.

Es ist wichtig, so etwas wie die Seqoder Iterator-Schnittstellen zu verwenden, da dies bedeutet, dass die Liste träge erstellt wird. DasIterator Schnittstelle kann kein unveränderliches Objekt sein und ist daher für die funktionale Programmierung weniger geeignet. Wenn Sie nicht feststellen können, ob der Wert, den Sie in eine Funktion eingeben, dadurch geändert wurde, verlieren Sie einen der Hauptvorteile der funktionalen Programmierung.

Sollte natürlich integerseine Liste aller ganzen Zahlen sein, so habe ich bei Null angefangen und abwechselnd positive und negative zurückgegeben.

Es gibt zwei Versionen von Quadraten - eine, die eine benutzerdefinierte Sequenz erstellt, die andere, mapdie eine 'Funktion' verwendet - Java 7 hat keine Lambdas, daher habe ich eine Schnittstelle verwendet - und wendet diese nacheinander auf jedes Element in der Sequenz an.

Der Zweck der square ( int x )Funktion besteht darin, nur die Notwendigkeit zu beseitigen, head()zweimal aufzurufen - normalerweise hätte ich dies getan, indem ich den Wert in eine endgültige Variable eingegeben hätte, aber das Hinzufügen dieser Funktion bedeutet, dass das Programm keine Variablen enthält, sondern nur Funktionsparameter.

Die Ausführlichkeit von Java für diese Art der Programmierung veranlasste mich, stattdessen die zweite Version meines Interpreters in C99 zu schreiben.

public class Squares {
    interface Seq<T> {
        T head();
        Seq<T> tail();
    }

    public static void main (String...args) {
        print ( take (25, integers ) );
        print ( take (25, squaresOf ( integers ) ) );
        print ( take (25, squaresOfUsingMap ( integers ) ) );
    }

    static Seq<Integer> CreateIntSeq ( final int n) {
        return new Seq<Integer> () {
            public Integer head () {
                return n;
            }
            public Seq<Integer> tail () {
                return n > 0 ? CreateIntSeq ( -n ) : CreateIntSeq ( 1 - n );
            }
        };
    }

    public static final Seq<Integer> integers = CreateIntSeq(0);

    public static Seq<Integer> squaresOf ( final Seq<Integer> source ) {
        return new Seq<Integer> () {
            public Integer head () {
                return square ( source.head() );
            }
            public Seq<Integer> tail () {
                return squaresOf ( source.tail() );
            }
        };
    }

    // mapping a function over a list rather than implementing squaring of each element
    interface Fun<T> {
        T apply ( T value );
    }

    public static Seq<Integer> squaresOfUsingMap ( final Seq<Integer> source ) {
        return map ( new Fun<Integer> () {
            public Integer apply ( final Integer value ) {
                return square ( value );
            }
        }, source );
    }

    public static <T> Seq<T> map ( final Fun<T> fun, final Seq<T> source ) {
        return new Seq<T> () {
            public T head () {
                return fun.apply ( source.head() );
            }
            public Seq<T> tail () {
                return map ( fun, source.tail() );
            }
        };
    }

    public static Seq<Integer> take ( final int count,  final Seq<Integer> source ) {
        return new Seq<Integer> () {
            public Integer head () {
                return source.head();
            }
            public Seq<Integer> tail () {
                return count > 0 ? take ( count - 1, source.tail() ) : nil;
            }
        };
    }

    public static int square ( final int x ) {
        return x * x;
    }

    public static final Seq<Integer> nil = new Seq<Integer> () {
        public Integer head () {
            throw new RuntimeException();
        }
        public Seq<Integer> tail () {
            return this;
        }
    };

    public static <T> void print ( final Seq<T> seq ) {
        printPartSeq ( "[", seq.head(), seq.tail() );
    }

    private static <T> void printPartSeq ( final String prefix, final T value, final Seq<T> seq ) {
        if ( seq == nil) {
            System.out.println("]");
        } else {
            System.out.print(prefix);
            System.out.print(value);
            printPartSeq ( ",", seq.head(), seq.tail() );
        }
    }
}

Wie man nützliche Java-Programme schreibt , ohne veränderbare Variablen zu verwenden.

Sie können theoretisch so gut wie alles in Java implementieren, indem Sie nur eine Rekursion und keine veränderlichen Variablen verwenden.

In der Praxis:

• Die Java-Sprache ist dafür nicht ausgelegt. Viele Konstrukte sind für die Mutation konzipiert und ohne sie schwer zu verwenden. (Beispielsweise können Sie ein Java-Array mit variabler Länge nicht ohne Mutation initialisieren.)

• Das Gleiche gilt für die Bibliotheken. Und wenn Sie sich auf Bibliotheksklassen beschränken, die keine Mutation unter dem Deckmantel verwenden, ist es noch schwieriger. (Sie können nicht einmal String verwenden ... schauen Sie sich an, wie hashcodees implementiert ist.)

• Mainstream-Java-Implementierungen unterstützen keine Tail-Call-Optimierung. Das bedeutet, dass rekursive Versionen von Algorithmen dazu neigen, Stapelspeicherplatz "hungrig" zu machen. Und da Java-Thread-Stapel nicht wachsen, müssen Sie große Stapel vorbelegen ... oder Risiken eingehen StackOverflowError.

Kombinieren Sie diese drei Dinge, und Java ist keine wirklich praktikable Option, um nützliche (dh nicht triviale) Programme ohne veränderbare Variablen zu schreiben .

(Aber hey, das ist in Ordnung. Es gibt andere Programmiersprachen für die JVM, von denen einige die funktionale Programmierung unterstützen.)

Da wir nach einem Beispiel für die Konzepte suchen, lassen Sie uns Java beiseite legen und nach einer anderen, aber vertrauten Einstellung suchen, in der Sie eine vertraute Version der Konzepte finden. UNIX-Pipes ähneln eher der Verkettung von Lazy Functions.

cat /dev/zero | tr '\0' '\n' | cat -n | awk '{ print $0 * $0 }' | head 25

In Linux bedeutet dies, dass Sie mir Bytes geben, von denen jedes aus falschen und nicht aus wahren Bits besteht, bis ich den Appetit verliere. Ändern Sie jedes dieser Bytes in ein Zeilenumbruchszeichen. nummerieren Sie jede so erzeugte Zeile; und das Quadrat dieser Zahl erzeugen. Außerdem habe ich Appetit auf 25 Zeilen und nicht mehr.

Ich behaupte, ein Programmierer wäre nicht schlecht beraten, eine Linux-Pipeline auf diese Weise zu schreiben. Es ist ein relativ normales Linux-Shell-Scripting.

Ich behaupte, ein Programmierer wäre schlecht beraten, das Gleiche in Java zu schreiben. Der Grund dafür ist die Softwarewartung als Hauptfaktor für die Lebenszykluskosten von Softwareprojekten. Wir möchten den nächsten Programmierer nicht verwirren, indem wir das, was angeblich ein Java-Programm ist, präsentieren. Tatsächlich wird es in einer benutzerdefinierten Sprache geschrieben, indem Funktionen, die bereits auf der Java-Plattform vorhanden sind, aufwendig dupliziert werden.

Andererseits behaupte ich, dass der nächste Programmierer akzeptabler sein könnte, wenn einige unserer "Java" -Pakete tatsächlich Java Virtual Machine-Pakete sind, die in einer der Funktions- oder Objekt- / Funktionssprachen wie Clojure und Scala geschrieben sind. Diese sind so konzipiert, dass sie durch Verketten von Funktionen codiert werden und in der normalen Art und Weise von Java-Methodenaufrufen aus aufgerufen werden.

Andererseits kann es für einen Java-Programmierer immer noch eine gute Idee sein, sich an einigen Stellen von der funktionalen Programmierung inspirieren zu lassen.

Kürzlich bestand meine Lieblingstechnik darin, eine unveränderbare, nicht initialisierte Rückgabevariable und einen einzelnen Exit zu verwenden, so dass Java, wie es einige Compiler für funktionale Sprachen tun, überprüft, dass ich immer nur einen einzigen zur Verfügung stelle, unabhängig davon, was im Funktionskörper passiert Rückgabewert. Beispiel:

int f(final int n) {
    final int result; // not initialized here!
    if (n < 0) {
        result = -n;
    } else if (n < 1) {
        result = 0;
    } else {
        result = n - 1;
    }
    // If I would leave off the "else" clause,
    // Java would fail to compile complaining that
    // "result" is possibly uninitialized.
    return result;
}

Der einfachste Weg, dies herauszufinden, wäre, dem Frege- Compiler die folgenden Informationen zu übermitteln und den generierten Java-Code zu betrachten:

module Main where

result = take 25 (map sqr [1..]) where sqr x = x*x