Datenstrukturen |
Numbers
Clojure kann mit diversen Zahlen Typen umgehen und wandelt diese in der Regel korrekt ineinander um
; Integer
93
; Float
1.2
; Ratio
1/5
Strings
Strings repräsentieren beliebigen Unicode Text:
"Alice: \"Wer Ä sagt, muss auch 🅱️ sagen\""
Unter der Haube sind das Java Strings.
Keywords
Keywords sind spezielle Symbole, die vor allem anstelle von Strings verwendet werden können.
:a
:rumplestiltsken
:34
Keywords sind oft effizienter als Strings
Lists
Listen sind geordnete Sammlungen von Werten
'(1 2 3 4)
Durch ' verhindern wir, dass die Liste evaluiert wird.
Jedes Programm in Clojure ist eine Liste:
(+ 1 2 3 4)
; => 10
Nicht jede Liste ist auch ein Programm:
(1 2 3 4)
; java.lang.ClassCastException
Eine valide S-Expression muss mit etwas Ausführbarem beginnen.
Dass jedes Programm als Datenstruktur in der Sprache selber dargestellt wird hat einen Namen:
Homoikonizität / Homoiconicity
Diese Eigenschaft werden wir später ausnutzen können.
Wir können eine Liste auch mit der "list" Funktion erstellen:
(list 1 2 3 4)
Mit "nth" können wir auf Elemente zugreifen
(def l (list "a" 2 "c" 4))
(nth l 2)
; => "c"
Clojure ist schwach typisiert - wir können einer Liste beliebige Werte mitgeben.
Mit "conj" können wir ein Element zu einer Liste hinzufügen
(conj '(1 2 3) 4)
; => (4 1 2 3)
Bei Listen werden Elemente per default am Anfang angefügt (mehr dazu später)
Mit "into" können wir einer Liste Elemente aus einer anderen Liste (oder Array oder Set) hinzufügen
(into '(1 2) '(3 4))
; => (4 3 1 2)
Wir können auch wieder Elemente vom Anfang wie von einem Stack entfernen
(pop '(1 2 3))
; => (2 3)
Die Anzahl Elemente einer Datenstruktur bekommen wir mit "count"
(count '(1 2 3))
; => 3
Vectors
Vektoren sind wie Listen, nur in vielen Fällen performanter. Im Zweifel präferieren wir Vektoren.
[3 2 1]
(vector 3 2 1)
(nth [3 2 1] 0)
; => 3
Bei Vektoren gibt es für den Zugriff auch "get"
(get [3 2 1] 1)
; => 2
(get [3 2 1] 5)
; => nil
"conj" schreibt bei Vektoren ans Ende
(conj [1 :zwei :drei] 4)
; => [1 :zwei :drei 4]
"conj" funktioniert auch mit mehr Elementen
(conj [1 2 3] 4 5 6)
; => [1 2 3 4 5 6]
"into" funktioniert analog
(into [1 2] '(3 4))
; => [1 2 3 4]
Sets
Wenn uns die Reihenfolge nicht interessiert und wir vor allem wissen wollen, ob ein Element in einer Sammlung vorkommt, verwenden wir ein "Hash-Set":
#{"abc" 5 :foo}
(hash-set "abc" 5 :foo)
Jeder Wert kann nur einmal in einem Set sein:
(conj #{:a :b} :b)
; => #{:a :b}
Eine andere Collection können wir mit "set" umwandeln:
(set [3 3 4 3 4 3])
; => #{4 3}
Mit "contains?" können wir testen, ob ein Element in einem Set ist
(contains? #{:a :b} :a)
; => true
(contains? #{:a :b} 3)
; => false
(contains? #{:a nil} nil)
; => true
Maps
Um einen Wert (key) mit einem anderen Wert (value) zu verknüpfen, brauchen wir eine "Hash-Map".
{"first-name" "Charlie"
:last-name "Chaplin"
:age 40}
Keys in Maps sind der primäre Use-Case für Keywords
Kommas sind optional:
{"first-name" "Charlie",
:last-name "Chaplin",
:age 40}
Ein Map Value kann alles sein, auch eine Map:
{:name {:first "John"
:middle "Jacob"
:last "Jingleheimerschmidt"}}
Mit der "hash-map" Funktion (und einer geraden Anzahl Parameter) kann eine Map erzeugt werden:
(hash-map 1 2 3 4)
Auch die leere Map ist eine Map:
{}
Mit "get" kommen wir zu einem Key einer Map an dessen Value:
(get {:a 0 :b 1} :a)
; => 0
(get {:a 0 :b {:c "foo"}} :b)
; => {:c "foo"}
Wenn ein Wert nicht vorhanden ist, liefert "get" "nil":
(get {:a 0 :b 1} :c)
; => nil
Wir können einen default Wert definieren, den "get" alternativ zurückgeben soll:
(get {:a 0 :b 1} :c "unicorns?")
; => "unicorns?"
Die Map kann wie eine Funktion verwendet werden und liefert dann die Werte zu dem Parameter:
(def m {:a 0 "b" 1})
(m :a)
; => 0
(m "b")
; => 1
(m :c)
; => nil
(m :c "foo")
; => "foo"
Keywords können auch wie eine Funktion verwendet werden, um aus dem Parameter Values zu holen:
(def m {:a 0 "b" 1})
(:a m)
; => 0
(:b m)
; => nil
(:b m "foo")
; => "foo"
Nested Maps sind so gängig, dass es eine Komfortfunktion gibt, um darin an Werte zu kommen:
(def m {:a 0 :b {:c "bar"}})
(get-in m [:b :c])
; => "bar"
Mit "assoc" fügen wir neue Elemente zu einer Map hinzu:
(assoc {:a 7 :b 5} :c 3)
; => {:a 7, :b 5, :c 3}
(assoc {:a 7 :b 5} :a 3)
; => {:a 3, :b 5}
Mit "dissoc" entfernen wir Keys:
(dissoc {:a 7 :b 5 :c 3} :b)
; => {:a 7, :c 3}
(dissoc {:a 7 :b 5 :c 3} :d)
; => {:a 7 :b 5 :c 3}
Mehr Datenstrukturen brauchen wir in der Regel nicht!
- In OOP definieren wir eigene Klassen für jeden neuen Datentyp.
- In funktionaler Programmierung machen wir viel mehr mit Basis Datentypen.
It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures.
Alan Perlis
In vielen Programmiersprachen kennen wir Variablen, die veränderlich sind.
# Python
l = [1, 1, 2]
l.append(l[2])
l[3] += l[1]
In reiner funktionaler Programmierung gibt es keine veränderlichen Objekte (mutable objects)
Alle* unsere Daten sind konstant (immutable)
*: Natürlich gibt es in Clojure auch Ausnahmen von der Regel.
Wenn wir eine Datenstruktur modifizieren wollen, erzeugen wir eine neue Datentruktur:
(def a [1 2 3])
(def b (conj a 4))
a
; => [1 2 3]
b
; => [1 2 3 4]
Aber warum?
- Veränderlicher Zustand (mutable state) macht Programme komplex.
- Was sind Referenzen und was sind Kopien?
- Was sind unerwartete Seiteneffekte?
- Eine Funktion kann sich unterschiedlich verhalten, wenn sich der Zustand ändert.
- Mutable State macht parallelen Code besonders schwierig.
Referential Transparency
Eine Funktion ist referenziell transparent, wenn man sie durch ihren evaluierten Wert ersetzen kann. Die Funktion hat keine Seiteneffekte.
Gegenbeispiel in Python
def f(l):
l.append(5)
return sum(l)
foo = [1,2,3]
f(foo)
# => 11
- erleichtert die Code Analyse
- ermöglicht mehr Compiler Optimierungen
Referential Transparency
Wenn eine Funktion keine Seiteneffekte hat und ihr Output nur von den übergebenen Parametern abhängt, sprechen wir auch von einer Pure Function
Müssen wir für jede Operation die ganze Datenstruktur kopieren?
Nicht, wenn wir es schlau machen.
Linked List
(def a '(1 :zwei 3))
(def b (conj a :vier))
(def c (pop a))
Daher kommen neue Elemente bei "conj" an den Anfang der Liste.
(def a '(1 2 3))
(def b '(4 5 6))
(def c (concat a b))
Je weiter hinten wir die Liste modifizieren wollen, umso mehr müssen wir kopieren.
Im schlimmsten Fall fassen wir immer das letzte Element an.
Wie sieht es mit Maps aus?
Hier überlegen wir uns, wie wir einen Knoten in einen Suchbaum einfügen können.
Füge "4" in Suchbaum ein.
Wir brauchen $O(\log(n))$ neue Knoten wenn wir ein Element hinzufügen oder entfernen wollen.
Gleiche Größenordnung wie andere Operationen auf Suchbäumen.
- Persistant data structures haben oft ähnliche Komplexität wie ihre mutablen Gegenstücke.
- Leichter Performance Overhead (für modifizierende Operationen).
- Garbage Collection ist wichtig.
Persistent (oder immutable) data structures sind im Detail ein komplexes Thema.
C++Now 2017: Phil Nash “The Holy Grail!? A Persistent Hash-Array-Mapped Trie for C++"