Funktionale Programmierung lernen

Kapitel 4. Funktionale Datenstrukturen

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

Datenstrukturen sind ein grundlegendes Konzept in der Informatik. Zusammen mit Algorithmen gehören sie zu den Grundlagen, die ein Informatikstudent oder Programmierer beherrschen muss. Wie der Begriff funktionale Muster ist auch die funktionale Datenstruktur kein etabliertes Konzept mit einer einheitlichen Definition im Kanon des Codes.

In diesem Buch werde ich zwei Dinge als funktionale Datenstrukturen bezeichnen.

• Strukturen, die in funktionalen Mustern verwendet werden, wie z.B. Option, Either, Try, List. Dies sind Monaden.

• Gewöhnliche Datenstrukturen, die funktional implementiert sind, so dass sie ihren Zustand nicht verändern, wie z. B. eine verkettete Liste.

In diesem Kapitel befassen wir uns mit der ersten Art von funktionalen Datenstrukturen und gehen dann kurz auf einige Ideen rund um gewöhnliche Datenstrukturen ein, die auf funktionale Weise implementiert werden. Bevor wir uns bestimmte Datenstrukturen ansehen, möchte ich eine Idee über funktionale Datenstrukturen erwähnen, die in der Literatur diskutiert wurde. Da ist zunächst dieses Zitat von Alan Perlis:

Es ist besser, 100 Funktionen auf eine Datenstruktur wirken zu lassen als 10 Funktionen auf 10 Datenstrukturen.

Erfahrene funktionale Programmierer verwenden in der Regel eine kleine Anzahl von Datenstrukturen: verknüpfte Listen, Arrays und Hashtabellen sowie Strukturen wie Option, Either und Try, um nur einige zu nennen. Diese werden wir als nächstes untersuchen. Ich glaube, die Idee hinter diesem Zitat ist, dass weniger Datenstrukturen zu mehr Einheitlichkeit und Einfachheit in der Codebasis führen. Schauen wir uns nun einige Datenstrukturen an, die besonders funktional sind. Wir beginnen mit Option.

Die Datenstruktur der Option

Ich verwende das Wort Option als sprachneutralen Begriff (nicht als Teil einer bestimmten Programmiersprache). Verschiedene Programmiersprachen haben eine Version dieser Datenstruktur und ich werde Beispiele für einige von ihnen geben, aber zuerst wollen wir die Idee näher erläutern. Unsere Diskussion sollte eigentlich mit dem null Konstrukt beginnen. Null wird für einen Wert verwendet, der möglicherweise nicht existiert; ein optionaler Wert oder eine Situation, in der ein Wert nicht bekannt ist. Ein Problem mit null ist, dass, wenn eine Variable ein Objekt enthält und der Wert dieser Variable null ist, und eine Methode für dieses Objekt aufgerufen wird, das Programm eine Nullzeiger-Ausnahme auslöst. Ausnahmen unterbrechen die referenzielle Transparenz und sind daher bei funktionalen Programmierern verpönt. Tony Hoare, der Erfinder von null, sagte, dies sei sein Milliarden-Dollar-Fehler:

Ich nenne ihn meinen Milliarden-Dollar-Fehler. Es war die Erfindung der Null-Referenz im Jahr 1965. Zu dieser Zeit entwarf ich das erste umfassende Typsystem für Referenzen in einer objektorientierten Sprache (ALGOL W). Mein Ziel ( ) war es, sicherzustellen, dass die Verwendung von Referenzen absolut sicher ist und vom Compiler automatisch überprüft wird. Aber ich konnte der Versuchung nicht widerstehen, eine Null-Referenz einzufügen, einfach weil sie so einfach zu implementieren war. Das hat zu unzähligen Fehlern, Schwachstellen und Systemabstürzen geführt, die in den letzten vierzig Jahren wahrscheinlich eine Milliarde Dollar an Schmerz und Schaden verursacht haben.¹

Doch wie gehen wir ohne null mit Daten um, die optional sind oder die vielleicht keinen Wert haben? Nun, eines der Hauptprobleme von null ist, dass es keinen richtigen Typ hat. Was wäre, wenn wir einen Typ erstellen könnten, der den Fall darstellt, dass ein Wert fehlt oder optional ist? So etwas gibt es in vielen Sprachen. In den Sprachen, in denen es ihn nicht gibt, ist es nicht schwer, ihn zu erstellen. Es gibt einige Möglichkeiten, auf diesen Typ zu verweisen, aber die meisten davon beinhalten eine Version des Wortes Option. Wir haben Optional in Java.² In Python gibt es etwas, das Option in mancher Hinsicht ähnelt, aber nicht die volle Funktionalität von Option hat: das None Objekt. Es ist jedoch nicht schwer, Option in Python zu konstruieren. Die Idee hinter Option ist folgende: Angenommen, wir haben eine Methode, die ein id Objekt annimmt und ein Customer Objekt zurückgibt. Was tun wir, wenn es kein Customer mit dem angegebenen id gibt?

Warnung

Wir könnten eine Ausnahme auslösen, wenn die Customer nicht gefunden wird, aber wie ich schon sagte, ist das nicht funktional, da es die referenzielle Transparenz unterbricht. Wenn eine Funktion eine Ausnahme auslöst, ist es nicht mehr wahr, dass man bei der gleichen Eingabe auch die gleiche Ausgabe erhält.

Auch wenn du Ausnahmen magst, ist dieses Beispiel nicht wirklich ein geeigneter Fall für eine Ausnahme. Eine Ausnahme bezieht sich auf etwas, das nicht passieren sollte, aber doch passiert. Es gibt also keinen guten Grund zu glauben, dass jedes id System mit einer tatsächlichen Customer übereinstimmt. Die Situation, in der das passiert, ist nicht ungewöhnlich. Man könnte sogar sagen, dass es eines der Ergebnisse ist, die wir erwarten sollten. Wie können wir also damit umgehen, ohne eine Ausnahme zu machen? Betrachten wir das Konstrukt Option. Mit Option meine ich eine allgemeine Datenstruktur und nicht ein Konstrukt in einer bestimmten Programmiersprache. Eine Option besteht normalerweise aus zwei Teilen: Der eine ist ein Container, der einen Wert enthält. Das ist der Fall, wenn ein gültiger Wert irgendwie berechnet oder erhalten wurde. Der zweite Teil steht für den Fall, dass kein gültiger Wert vorhanden ist. Dies wäre eine Situation, in der eine Sprache ohne Option Typ ein null verwenden könnte. Sehen wir uns ein Beispiel in Scala an. Kehren wir zu dem Beispiel zurück, in dem wir einen Kunden mit dem Typ id abrufen. In Scala können wir wie folgt vorgehen:

Scala

def getCustomer(id: Int): Option[Customer] = {
    //code which retrieves customer from database.
}

Diese Funktion kann eines von zwei Dingen zurückgeben. Wenn die id einem Kunden entspricht, gibt die Methode zurück:

Some(customer)

Wenn kein Kunde zu diesem bestimmten id gehört, gibt die Funktion den Wert zurück:

None

Du kannst dann die notwendigen Maßnahmen ergreifen, um mit dieser Situation umzugehen. Wenn Some(customer) zurückgegeben wird, kannst du customer auf verschiedene Weise aus dem Container Some herausholen. Eine gängige Methode ist die Verwendung von Scalas Mustervergleichsfunktion. Hier ist ein Beispiel dafür:

getCustomer(17) match {
    case Some(customer) => //do something with customer
    case None => //Take action to handle this situation.
}

Ein anderer, vielleicht gängigerer Ansatz ist die Verwendung einer der Funktionen höherer Ordnung, wie map, flatMap oder filter. Zum Beispiel:

val customer = getCustomer(17) map { customer => customer.firstName}

Die Variable Kunde enthält in dem Fall, dass ein Wert ermittelt wurde, Some("Peter"). Wenn kein Kunde gefunden wurde, wird None zurückgegeben und der Programmierer kann damit umgehen.

Hinweis

Es ist wichtig zu verstehen, dass Some und None Typen sind und der Compiler daher helfen kann, Fehler zu finden, die mit ihnen verbunden sind, im Gegensatz zu null, das zur Laufzeit (nicht zur Compilierzeit) auftritt.

Nehmen wir an, du hättest eine Liste von Option Objekten, jedes ein Some(customer) oder ein None. Und nehmen wir an, du möchtest dies in eine Kundenliste ändern, bei der du die Nones ignorierst. Nehmen wir auch an, getCustomers gibt eine Liste von Optionen von Customer Objekten zurück. Das Customer Objekt könnte ein case class sein, das so aussieht:

case class Customer(id: Int, firstName: String)

Die Liste der Optionen für Kunden sieht wie folgt aus:

val customers = List(Some(Customer(1,"Bob")), None, Some(Customer(33, "Lee")),
    	      				      None, Some(Customer(5, "Rhonda")))

Dann könnten wir Folgendes tun:

customers.flatten

Dies würde zurückkehren:

List(Customer(1,"Bob"), Customer(33, "Lee"), Customer(5, "Rhonda"))

Beachte, dass die Nonebequemerweise weggelassen wurden.

Schauen wir uns nun einige Beispiele in Java an.

Java

     Optional<User> optUser = findUserById(123);

     optUser.ifPresent(user -> {
             System.out.println("User's name = "
     + user.getName());})
}

In diesem Beispiel gibt findUserById ein Optional eines User Objekts zurück, wenn es eines für das angegebene id findet. Wenn nicht, wird der Code in den geschweiften Klammern nicht ausgeführt. Die ältere Methode, die es vorOptional gab, wäre gewesen, dass findUserById ein null zurückgibt, wenn kein Benutzer gefunden wurde. Das Problem dabei ist, dass bei einem Methodenaufruf des User Objekts, das eigentlich ein null ist, ein NullPointerException ausgelöst werden würde. Bei dem vorangegangenen Code, der Optional verwendet, wird keine Ausnahme ausgelöst.

In Python gibt es keine Klasse Option. Es gibt zwar das Objekt None, aber das ist nur die Hälfte dessen, was eine Option ausmacht. Es ist aber auch für sich genommen nützlich. Du kannst Dinge wie diese tun:

Python

def getUser(id):
    #get user from database

    #if database call fails
    return None

Dann kannst du das tun, wenn du diese Funktion aufrufst:

if getUser(789) is not None:
   #do something

Du wirst vielleicht sagen, dass das sehr nach der Überprüfung von null aussieht, und ich würde dir zustimmen. Wenn du es wirklich willst, kannst du in Python eine Option Klasse erstellen. Eine Möglichkeit wird hier gezeigt:

class Option:
    def get_or_else(self, default):
        return self.value if isinstance(self, Some) else default

class Some(Option):
    def __init__(self, value):
        self.value = value

class Nothing(Option):
    pass

Ich habe dies Nothing genannt, weil Python bereits ein None Objekt hat. Das ist nicht besonders "pythonisch", aber es ist eine Möglichkeit, die Aufgabe zu erledigen.

Auch C# hat eine Version dieser Idee. Es ist zwar kein Option, aber es ist ein Konstrukt, das bei Problemen mit nullhilft: der Nullable Typ. Mit diesem Typ können wir explizit darstellen, dass eine Variable einen null Wert enthalten kann. Für einen bestimmten Typ, zum Beispiel int, können wir den Typ bilden:

C#

Nullable<int>

Wie du siehst, ist dies ein allgemeiner Typ. Eine Kurzform für diese Formulierung ist:

int?

Wir können auch Code schreiben wie:

Nullable<int> n1 = new Nullable<int>(10);
Nullable<int> n2 = null;

if (n1.HasValue) {
   process(n1.Value);
} else {
  //n1 has a null value.
}

Dies ist eine Möglichkeit, nulls zu navigieren, ohne eine NullPointerException zu riskieren.

Die Datenstruktur von Try

Das Option Konstrukt ist zwar nützlich und eine Verbesserung gegenüber nulls, aber es gibt dir keinen Hinweis darauf, warum es keinen legitimen Wert gibt. Ausnahmen tun dies, aber Options nicht. Options sind in vielen Situationen eine gute Lösung, aber manchmal brauchst du Informationen darüber, was schief gelaufen ist. Dafür gibt es das Try Konstrukt. So wie Option Some und None hat, hat Try Success und Failure. Failure umhüllt die Ausnahme, die ausgelöst wurde. Obwohl wir in FP versuchen, Ausnahmen so weit wie möglich zu vermeiden, lassen sie sich manchmal nicht vermeiden. Try ist eine Lösung für dieses Problem. Hier ist etwas Code.

Scala

def divide(a: Float, b: Float): Try[Float] = Try(a/b)

Dann können wir Folgendes tun:

divide(3, 0) match {
   case Success(result) => //do something with result
   case Failure(ex) => println(ex.getMessage)
}

Hier ist ein Beispiel für Try in einer for Verständigung:

def toInt(s: String): Try[Int] = Try(Integer.parseInt(s.trim))

val y = for {
    a <- toInt("9")
    b <- toInt("3.5")
    c <- toInt("6")
} yield a + b + c

Beachte, wie gut der Fehlerfall gehandhabt wird. y enthält entweder eine Success, die die Summe von a, b und c enthält, oder eine Failure, die eine Ausnahme enthält.

In diesem Fall wird das Ergebnis lauten:

Failure(java.lang.NumberFormatException: For input string: "3.5")

Die Datenstruktur von Either

Der Typ Try gibt dir zwar mehr Informationen über einen Fehler oder ein außergewöhnliches Ergebnis als Option, aber du könntest dich fragen, ob es einen Typ gibt, der dir mehr Flexibilität bietet. Das Either -Konstrukt löst dieses Problem auf folgende Weise: Ein Either -Objekt kann entweder ein Right oder ein Left sein. Right ist wie der Some -Typ von Option. Left ist wie None, nur dass es jeden Typ umhüllen kann. Betrachten wir ein Beispiel in Scala.

Scala

def divide(a: Int, b: Int): Either[String, Int] = {
    if (b == 0)
       Left("Can't divide by zero.")
    else
       Right(a/b)
}

Dann kannst du etwa so vorgehen:

divide(a, b) match {
    case Left(msg) => //do something with msg
    case Right(res) => //do something with res
}

Left und Right können beliebige Typen verpacken. Nehmen wir zum Beispiel an, du hättest zwei benutzerdefinierte Typen, User und Error:

Scala

case class User(id: Int, firstName: String)

case class Error(id: Int, text: String)

def getUser(id: Int): Either[Error,User] = {
    //If I retrieve a user from api
    Right(User(id, firstName)

    //else if there is an error
    Left(id, text)
}

Dann kann ich Folgendes tun:

getUser(4) match {
    case Right(user) => println(user.firstName)
    case Left(error) => println(error.text)
  }

Left kann sogar eine Ausnahme verpacken, wenn du es aus irgendeinem Grund für notwendig oder sinnvoll hältst, eine Ausnahme zu verwenden, und du keine Try verwenden willst. Du könntest zum Beispiel eine Bibliothek verwenden, die eine Ausnahme auslöst. Es ist immer möglich, die Ausnahme abzufangen und einen in Left verpackten Fehlertyp zurückzugeben.

Wenn wir tiefer in die FP einsteigen, wird es nützlich und in einigen Fällen notwendig sein, funktionale Bibliotheken von Drittanbietern zu verwenden, die viele der besprochenen Strukturen enthalten. Du hast bereits Beispiele in Scala, Java, Python und C# gesehen. Diese Sprachen unterscheiden sich darin, wie viel FP sie ohne Bibliotheken ausführen können, aber alle brauchen Bibliothekenfür einige Dinge.³ Für Java gibt es mindestens zwei Bibliotheken, die funktionale Konstrukte ermöglichen. Die eine heißt Functional Java und die andere ist Vavr. Ich werde Beispiele aus Vavr geben. Ich werde immer angeben, wenn ein Code auf Vavr basiert. Schauen wir uns an, wie Either in Java mit Vavr aussieht.

Java mit Vavr

private static Either<String, User> getUser(int id) {
    //code that sucessfully found a user
        return Either.right(user);
    } else {
        return Either.left(String.format("No user found with id  %s", id);
    }
}

Wie wäre es mit einer funktionalen Bibliothek für Python? Eine hervorragende Bibliothek ist OSlash. Mit OSlash können wir Dinge in Python schreiben wie die folgende :

Python (mit OSlash)

def get_user(id):
    #successful case yields a user object
    return Right(user)
    #error case returns an error object
    return Left(error)

Dann können wir das tun:

if isinstance(result,Right):
   #do something with successfull result
else:
    # result is an error

Funktionen höherer Ordnung

Funktionen, die diese funktionalen Datenstrukturen wie Option oder Either zurückgeben, eignen sich für Funktionen höherer Ordnung. Sehen wir uns zunächst einige einfache Beispiele dafür an.

Scala

case class User(id, firstName)

val users: List[Option[User]] = List(Some(User(1, "Jack")),
				     None, Some(User(2, "Andrea")), None, None)

Die users Liste könnte das Ergebnis einer Funktion sein, die eine API abfragt und die Optionen der Nutzer zurückbekommt. In den Fällen, in denen kein User für ein bestimmtes id gefunden wurde, gibt die Funktion ein None zurück. Um nur die users und nicht die Nones zu erhalten, können wir Folgendes tun:

users.flatten

Dies wird zurückgegeben:

List(User(1,"Jack"),User(2,"Andrea"))

Oft hat man eine Datenpipeline von Werten, die man umwandelt, während man eine Reihe von Funktionen höherer Ordnung aufruft. Nehmen wir zum Beispiel an, wir haben eine Scala-Funktion, getUsers, die eine Liste von Either[Error,User] zurückgibt, wobei User ein Feld namens email hat. Nehmen wir an, dass wir alle Nutzer mit einem example.com-Konto herausfiltern wollen. Wir erwarten, dass das Ergebnis eine List[Either[Error,String]] ist, wobei String die E-Mail-Adresse darstellt. Ein imperativer Ansatz, der die List in einer Schleife durchläuft, wäre ein bisschen unübersichtlich. Sehen wir uns an, wie ein funktionaler Ansatz, der Funktionen höherer Ordnung verwendet, den Code stark vereinfacht. Dabei geht es direkt um das Wesentliche, was vor sich geht. Schleifen gehören nicht zu diesem Kern. Schauen wir uns etwas Code an.

Scala

case class User(id: Int, email: String)
case class Error(id: Int, text: String)

def getUsers(): List[Either[Error,User]] =
    List(Right(User(1, "[e-mail]")), Left(Error(4,"user not found")),
         Right(User(2, "[e-mail]")))

Dann können wir das tun:

val emails = getUsers().map(either => either.map(u => u.email))

Jetzt enthalten die E-Mails Folgendes:

List(Right([e-mail]), Left(Error(4,user not found)),
    Right([e-mail]))

So kannst du die Hierarchie der Felder bis zu dem gewünschten Feld aufschlüsseln.

Monaden in für Comprehensions in Scala

Wie wir gesehen haben, sind Dinge wie List, Option, Try, und Either Monaden. Eine sehr nützliche Sache, die du mit Monaden in Scala machen kannst, sind for comprehensions. Hier ist ein Beispiel:

Scala

case class Student(id: Int, email: String)
case class FinalGrade(grade: Int)
def getStudent(id: Int): Option[Student] = ???
def getFinalGrade(student: Student): Option[FinalGrade]

Diese Funktion versucht, ein Benutzerobjekt zu finden, das der angegebenen ID entspricht. Wenn sie es findet, gibt sie zum Beispiel Some(User(493, "Alex")) zurück. Wenn sie es nicht findet, gibt sie None zurück. Wir können nun Folgendes tun:

for {
    student <- getStudent(999) //getStudent returns a monad
    finalGrade <- getFinalGrade(student) //getFinalGrade returns a monad
} yield (student,finalGrade)

Dies würde ein Tupel zurückgeben, das aus einem Option der student und einem Option der finalGrade besteht. Wenn einer der Options None wäre, würde der Wert des for Verstehens None sein und nicht das Tupel von Werten. Für das Verständnis bedeutet dies, dass perfekt funktionaler Code eher wie traditioneller imperativer Code aussieht. In vielen Fällen führt dies zu einem klareren Code. Es stellt sich heraus, dass eine for comprehension eigentlich nur ein syntaktischer Zucker für eine Reihe von flatMap und map Aufrufen ist und wir wissen, dass jede Monade flatMap und map hat. Beginnen wir mit einer Liste von Options von students:

Scala

case class Student(id: Int, email: String)
val students = List(Some(Student(1,"[e-mail]")), None,
    	            Some(Student(2, "[e-mail]")), None)

Nehmen wir zunächst an, du willst nur die students aus den Optionen herausholen und die Nones ignorieren. Das kannst du mit einem einfachen Aufruf von flatten erreichen:

students.flatten // returns List(Student(1,"[e-mail]"),
    Student(2,"[e-mail]"))

Nehmen wir an, du interessierst dich nur für die emails und möchtest eine Liste von ihnen bekommen. Dann kannst du Folgendes tun:

students.flatten.map(student => student.email)

// This will return List("[e-mail]","[e-mail]")

Wir haben also ein flatten und dann ein map gemacht. Manchmal willst du zuerst map und dann flatten machen. Das ist genau das, was flatMap macht. Schauen wir uns ein Beispiel dafür an:

students.flatMap(optStudent => opStudent)

// returns List(Student(1,"[e-mail]"), Student(2,"[e-mail]"))

In diesem Fall haben wir für die map die Identitätsfunktion verwendet. Damit ist der Aufruf von flatMap dasselbe wie der von flatten. Wir haben nicht die volle Potenz von flatMap verwendet. Sehen wir uns ein komplizierteres Beispiel an. Nehmen wir an, wir haben eine getStudent Funktion, die ein id annimmt und ein Option eines Student zurückgibt. Das ist eine gute Idee, denn manche ids verweisen vielleicht auf gar kein Student. Hier ist etwas Code.

def getStudent(id: Int): Option[Student] = {
    id match {
      case 1 => Some(Student(1, "[e-mail]"))
      case 2 => Some(Student(2, "[e-mail]"))
      case _ => None
    }
  }

Nehmen wir nun an, dass wir a von ids haben und wir die vorherige Funktion auf der Liste irgendwie aufrufen wollen, aber die Funktion gibt Option zurück. Wir können Folgendes tun:

List(1,2,3).map(id => getStudent(id))

Dies wird zurückgegeben:

List(Some(Student(1,[e-mail])), Some(Student(2,[e-mail])), None)

Das ist wahrscheinlich nicht das, was wir wollten. flatMap zur Rettung.

List(1,2,3).flatMap(id => getStudent(id))

Jetzt wird das wiederkommen:

List(Student(1,[e-mail]), Student(2,[e-mail]))

Perfekt! flatMap ist nützlich, wenn du eine Liste (oder eine beliebige Monade) hast und sie map willst, aber die Funktion, mit der du sie map willst, selbst eine Monade zurückgibt. Der flatten Teil von flatMap entfernt das Ergebnis aus seinem Container, d.h .seiner Monade.

Traditionelle Datenstrukturen

Jetzt werden wir uns die traditionellen Datenstrukturen ansehen, im Gegensatz zu den funktionalenDatenstrukturen.

Unveränderlichkeit und Geschichte

Wie bei allem, was funktional ist, ist die Unveränderlichkeit ein wichtiges Teil des Puzzles. Was ich hier Geschichte nenne, bezieht sich auf die Tatsache, dass wir, da wir nichts ändern, etwas kopieren müssen, das sich ändert (und seinen früheren Zustand beibehält). Ein Stapel kann zum Beispiel funktional sein, wenn er auf eine bestimmte Weise implementiert wird. Bei Operationen wie push müsste eine Kopie des Stapels erstellt werden, anstatt ihn an Ort und Stelle zu verändern. Das erfordert im Allgemeinen eine Möglichkeit, schnelle Kopien zu erstellen. Hierfür gibt es verschiedene Algorithmen. Es gibt sogar Datenbanken, die diesem Paradigma folgen. Datomic zum Beispiel, eine Datenbank, die von Rich Hickey, dem Schöpfer der Sprache Clojure (die viele funktionale Fähigkeiten hat), entwickelt wurde, ist eine Datenbank, die niemals Daten überschreibt. Sie behält eine Kopie aller Daten und Änderungen. Das ist eine weitere Möglichkeit, wie sich das funktionale Paradigma durchsetzen kann.

Hinweis

Ob eine traditionelle Datenstruktur funktional ist oder nicht, hängt von der jeweiligen Implementierung der Datenstruktur ab.

Faulheit

Wir haben Faulheit schon einmal im Zusammenhang mit dem, was eine Sprache funktional macht, erwähnt (siehe "Lazy Evaluation"). Der Grundgedanke ist, dass eine Funktion oder ein Prozess faul ist, wenn er nur bei Bedarf ausgewertet wird. Dazu gehört auch, dass eine Funktion, die eine lange Berechnung durchführt, den Wert speichert oder memoisiert und dann das nächste Mal verwendet, wenn er benötigt wird (wenn möglich). Diese Fähigkeit ist nützlich, um effiziente funktionale Datenstrukturen zu erstellen. Haskell ist eine Lazy-Sprache und Scala hat zwar ein Lazy-Schlüsselwort, ist aber nicht standardmäßig lazy. In der Regel ist eine Sprache, die teilweise oder vollständig lazy ist, eine Sprache, die explizit dafür entwickelt wurde, zumindest teilweise funktional zu sein.

Hinweis

Die Faulheit erlaubt es uns, mit der Auswertung eines Ausdrucks zu warten, wenn und nur wenn wir ihn brauchen.

Fazit

Zusammenfassend kann man sagen, dass es zwei Arten von funktionalen Datenstrukturen gibt. Die erste ist eine Reihe von Konstrukten, die aus der Kategorientheorie stammen, in der Regel über Haskell, und die eine map und flatMap Funktion haben, was sie zu Monaden macht. Die zweite besteht aus traditionellen Datenstrukturen, die nach den bereits erwähnten Prinzipien implementiert wurden.

¹ Hoare, Tony. "Null-Referenzen: Der Milliarden-Dollar-Fehler". Historically Bad Ideas. Vortrag gehalten auf der QCon, 2009. https://oreil.ly/sQSnH.

² Wie viele funktionale Konstrukte erfordert auch dieses Java 8 oder höher.

³ Eine Ausnahme ist die reine FP-Sprache Haskell.