Funktionale Linsen
Linsen sind eine funktionale Abstraktion, die sich für uns schon in mehreren Projekten als sehr nützlich erwiesen haben. Mit ihnen kann man sehr gut komplexe Eigenschaften größerer Datenstrukturen definieren, abfragen und insbesondere ändern. Linsen machen aus Eigenschaften first class citizens über die man abstrahieren und die man miteinander kombinieren kann.
Dieser Artikel soll zeigen was Linsen sind, und wie man sie dafür verwenden kann. Die verwendete Programmiersprache ist Clojure, in der wir zur Zeit sehr viel und gerne programmieren. Einige Tutorials zur Sprache finden sich zum Beispiel hier.
Motivation
Als motivierendes Beispiel stellen wir uns vor, wir hätten ein einfaches Telefonbuch als eine Datenstruktur folgender Art vorliegen:
(def book-1
{"Mike" #{[:work "071170709468"] [:home "07071xxx"]}
"David" #{[:home "07121xxx"]}})Das Telefonbuch ist also eine Map mit Namen als Schlüssel, und einem Set von Einträgen als Wert. Jeder Eintrag besteht aus einem Tupel aus der Art des Eintrags und einem String mit der Telefonnummer selbst.
Als Aufgabe stellen wir uns zwei Funktionen: Eine schaut nach, ob zu einem Namen ein bestimmter Eintrag vorhanden ist, die Andere fügt einen Eintrag hinzu. Dabei sollte es keine Rolle spielen ob ein Name überhaupt schon im Telefonbuch vorhanden ist oder nicht:
(defn has-entry? [book name kind number] ...)
(defn add-entry [book name kind number] ...)Was sind Linsen?
Zunächst einmal kommt das Wort vom englischen Lens, es sind also nicht die Linsen zum Essen gemeint, sondern die zum Durchsehen. Und diese Analogie ist recht treffend: man hält eine Linse vor etwas Großes, und sieht einen kleineren Teil davon. Vom Programmieren her geht es also erst einmal darum, dass man mithilfe einer Linse einen Wert aus einer Datenstruktur herausziehen kann. In Clojure könnte man das so definieren:
(defprotocol Lens
(yank [this data]))Dies definiert Linsen als ein Protokoll, das von verschiedenen Typen
implementiert werden kann, indem man eine Funktion yank mit einem
weiteren Parameter data über Werte diesen Typs definiert. Der erste
Parameter von Protokollfunktionen ist in Clojure immer der konkrete
Wert des jeweiligen Typs, und this ein passender Name dafür.
Das allein wäre aber natürlich noch nicht der Rede wert. Entscheind
ist, dass eine Linse ausserdem die Möglichkeit bietet, den Wert, den
sie fokussiert, zu modifizieren! Modifizieren heißt in der
funktionalen Programmierung natürlich, eine neue Datenstruktur zu
erstellen, die an der fokussierten Stelle einen neuen Wert enthält. Es
kommt also noch eine Funktion shove, zum Einschieben eines neuen
Wert dazu:
(defprotocol Lens
(yank [this data])
(shove [this data v]))Eine Möglichkeit konkrete Linsen zu erzeugen ist nun, die beiden
Funktionen yank und shove explizit zu definieren:
(defrecord ExplicitLens
[yanker shover]
Lens
(yank [this data] (yanker data))
(shove [this data v] (shover data v)))
(defn lens
[yanker shover]
(ExplicitLens. yanker shover))Der Recordtyp ExplicitLens hat also die beiden Felder yanker und
shover und implementiert das Protokoll Lens direkt mit diesen
beiden Funktionen. Die Funktion lens konstruiert einen Wert vom Typ
ExplicitLens.
Anwendung
Die richtigen Eigenschaften als Linsen zu definieren, ist manchmal gar
nicht so einfach. Die erste die wir für unser Beispiel brauchen
werden, ist der Wert der in einer Map zu einem bestimmten Schlüssel
hinterlegt ist. Dazu schreiben wir eine Funktion member, die einen
Schlüssel und einen Default-Wert nimmt, und eine Linse erzeugt, die,
über eine konkrete Map gehalten, den zugehörigen Wert fokussiert:
(defn member
[key & [default]]
(lens #(get % key default)
#(if (= %2 default)
(dissoc %1 key)
(assoc %1 key %2))))Member nimmt also einen Parameter key und einen optionalen
Parameter default, und ruft lens mit entsprechenden yanker und
shover Funktionen auf (# zusammen mit % bzw. %1 und %2 ist
Clojure‘s Kurzschreibweise für „Lambda-Ausdrücke“ mit einem bzw.
meheren Parametern.)
Die Funktion yank der member-Linse gibt den zum Schlüssel
passenden Wert zurück (oder den Default-Wert, falls der Schlüssel
nicht in der Map ist); die Funktion shove ändert den Wert zu einem
Schlüssel oder entfernt Schlüssel und Wert aus der Map, wenn wir den
Default-Wert übergeben.
Damit können wir die erste interessante Eigenschaft eines Telefonbuchs als Linse definieren, nämlich das Set der Einträge zu einem Namen, mit einem leeren Set als Default-Wert:
(defn book-entries
[name]
(member name #{}))Wie gesagt können wir mit einer Linse diese Eigenschaft lesen und setzen. Ein Beispiel:
(def my-entries (book-entries "David"))
(yank my-entries book-1)
;; => #{[:home "07121xxx"]}
(shove my-entries book-1 #{})
;; => {"Mike" #{[:work "071170709468"] [:home "07071xxx"]}}Hier sieht man aber auch, dass solche Eigenschaften jetzt
first-class sind: (book-entries "David") erzeugt eine Linse für
meine Einträge in einem Telefonbuch! Diesen Wert kann man an einen
Namen binden wie hier, oder an andere Funktionen übergeben und weiter
verarbeiten - dazu kommen wir noch weiter unten.
Übrigens: Dadurch, dass member einen Map-Eintrag komplett entfernt, der dem
Default-Wert entspricht, enthält das neue Telefonbuch, das der letzte
Ausdruck erzeugt, keinen Schlüssel "David" mehr.
Wir müssen jetzt ausserdem noch in das Set der Einträge einsteigen. Dazu sind Linsen folgender Art hilfreich:
(defn contains
[v]
(lens #(contains? % v)
#(if %2
(conj %1 v)
(disj %1 v))))Die Funktion contains nimmt einen Wert und gibt eine Linse zurück,
die über der boolschen Eigenschaft fokussiert, ob dieser Wert in
einem Set enthalten ist oder nicht. Die yank-Funktion dieser Linse
prüft dazu, ob dieser Wert in einem Set enthalten ist; die
shove-Funktion ergänzt oder löscht einen Wert, abhängig vom zweiten
Argument.
Für unsere Telefonbuch-Einträge könnten wir also zunächst definieren:
(defn entries-contains [kind number]
(contains [kind number]))Und so können wir das direkt auf den Sets verwenden:
(def contains-my-work-number
(entries-contains :work "071170709475"))
(yank contains-my-work-number #{[:home "07121xxx"]})
;; => false
(shove contains-my-work-number #{[:home "07121xxx"]} true)
;; => #{[:home "07121xxx"] [:work "071170709475"]}Jetzt wollen wir noch die Linsen für die
Map-Einträge und die für die Sets kombinieren. In diesem
Fall wollen wir sie aneinander hängen, oder übereinander legen, um
im Bild zu bleiben. Die kombinierte Linse sollte beim Lesen erst die
yank-Funktion der Linse für einen Map-Eintrag anwenden, und dann auf
dem resultieren Set die yank-Funktion einer Linse für den
Set-Eintrag anwenden. Beim Schreiben, der shove-Funktion sollte es
entsprechend andersherum passieren. Wenn wir einmal Wunschdenken
anwenden brauchen wir einen Kombinator, nennen wir ihn >>, der
folgendes kann:
(def contains-my-work-number-for-me
(>> my-entries contains-my-work-number))
(yank contains-my-work-number-for-me book-1)
;; => false
(shove contains-my-work-number-for-me book-1 true)
;; => {"Mike" #{[:work "071170709468"] [:home "07071xxx"]}
;; "David" #{[:home "07121xxx"] [:work "071170709475"]}Und tatsächlich ist es auch gar nicht so schwer, diesen überaus nützlichen Kombinator zu definieren:
(defn >>
[l1 l2]
(lens (fn [data] (yank l2 (yank l1 data)))
(fn [data v] (shove l1 data (shove l2 (yank l1 data) v)))))Der yanker liest zuerst den Wert den die Linse l1 in data
fokussiert, und liest darin dann das was die Linse l2 definiert hat
aus. Der shover liest auch zunächst auch aus was l1 in den
bisherigen Daten zeigt, lässt l2 darin seine Änderungen
machen, und setzt das Ergebnis schließlich an die entsprechende
„Stelle“ zurück, so wie von l1 definiert.
(Die Erweiterung auf mehr als zwei Linsen ist auch nicht schwer.)
Kommen wir zum Schluss nun zu den beiden Funktionen auf Telefonbüchern, die wir uns zu Beginn als Aufgabe gestellt haben:
(defn has-entry? [book name kind number] ...)
(defn add-entry [book name kind number] ...)Wenn wir eine Linse für das Vorhandensein eines Eintrags definieren:
(defn book-contains [name kind number]
(>> (book-entries name)
(entries-contains kind number)))Dann sind die beiden Funktionen einfach die Anwendung dieser Linse:
(defn has-entry? [book name kind number]
(yank (book-contains name kind number) book))
(defn add-entry [book name kind number]
(shove (book-contains name kind number) book true))Wie man jetzt noch ein remove-entry definieren könnte ist sicherlich naheliegend.
Regeln
Nicht alles, was das dem obigen Lens-Protokoll entspricht, sollte man
als Linse betrachten. Folgende Regeln, oder Gesetze, machen Linsen
erst sinnvoll:
-
Man zieht immer das raus was man rein gesteckt hat:
(yank l (shove l d v))==v -
Reinstecken, was man raus gezogen hat, ändert nichts:
(shove l d (yank l d))==d -
Zweimal reinstecken ist das gleiche wie einmal:
(shove l (shove l d v) v)==(shove l d v)
Die Linsen aus diesem Beitrag erfüllen alle Gesetze.
Zusammenfassung
Mit Linsen lassen sich modifizierbare Eigenschaften von Datenstrukturen sehr präzise und mit minimaler Redundanz definieren.
Sehr praktisch ist es zum Beispiel zusammen mit unserer Webclient-Bibliothek reacl, wie bereits in einem früheren Artikel erwähnt. Aber wir haben Linsen auch erfolgreich in Xtend auf einer mutierbaren Java-Datenstruktur eingesetzt.
Nachtrag: Linsen für Clojure und ClojureScript sind, in leicht anderer Form, Teil unserer active-clojure Bibliothek.
