Euklidischer Abstand in Haskell
Vor 8 Monaten habe ich über verschiedene Algorithmen zur Bestimmung von Ähnlichkeiten geschrieben. Den euklidischen Abstand habe ich kürzlich in Haskell implementiert.
Mathematische Definition
Schauen wir uns zuerst einmal die mathematische Definition an und kommen danach zur Umsetzung in Haskell. Der euklidische Abstand ist wie folgt definiert:
\[d(x,y) = \sqrt{(x_1 - y_1)^2 + \ldots + (x_n - y_n)^2}\]Da für den Vergleich von Ähnlichkeiten die exakte Distanz keine Rolle spielt (sondern nur der Vergleich, ob eine Distanz größer ist als eine andere), wird bei solchen Einsatzzwecken das Wurzel-Ziehen am Ende gerne weggelassen. Man rechnet daher nur:
\[d(x,y) = (x_1 - y_1)^2 + \ldots + (x_n - y_n)^2\]Implementierung in Haskell
In Haskell lässt sich dies dann folgenermaßen umsetzen:
euclidian :: (Num a) => [a] -> [a] -> a
euclidian [] [] = 0
euclidian xs [] = euclidian xs [0]
euclidian [] ys = euclidian [0] ys
euclidian (x:xs) (y:ys) = (x - y) * (x - y) + euclidian xs ysDie erste Zeile definiert die Typendeklaration, wobei wir als Eingabe zwei numerische Listen erwarten und als Ausgabe in numerischer Wert zurückgeliefert wird.
Anschließend definieren wir mehrere Grenzfälle, die bei der Rekursion zum Abbruch führen sollen oder ansonsten zu Problemen führen könnten. In Haskell ist dies besonders schön möglich, weil man einfach nur mehrere Funktionsdefinitionen anlegen muss.
So definieren wir in der zweiten Zeile das Verhalten für zwei leere Listen. In diesem Fall erwarten wir der Rückgabewert 0, denn dies stellt den Abbruch unserer Rekursion dar. In der dritten und vierten Zeile sind Sonderfälle definiert, wenn die Länge einer Liste die andere übersteigt. In solch einem Fall so so getan werden, als stünden in der ersten Liste am Ende noch Nullen.
Und die letzte Zeile stellt schließlich die allgemeine Definition der Funktion dar. Wir extrahieren aus zwei Listen jeweils das erste Element und vergleichen diese miteinander. Die restlichen Werte übergeben wir erneut an die euclidian-Funktion.
Beispieldurchlauf
Wir wollen uns nun noch einen Beispielablauf für folgende Eingabe ansehen:
euclidian [2,1] [1,4,2]- euclidian (x:xs) (y:ys)
\((x-y)*(x-y) = (2-1)(2-1) = 1\)
xs = [1], ys = [4,2]
ruft mit diesen Werten wieder euclidian auf - euclidian (x:xs) (y:ys)
\((x-y)*(x-y) = (1-4)(1-4) = 9\)
xs ist leer und ys = [2]ruft mit diesen Werten wieder euclidian auf - euclidian [] ys
ruft euclidian [0] ys auf - euclidian (x:xs) (y:ys)
\((x-y)*(x-y) = (0-2)(0-2) = 4\)
xs ist leer, ys ist leer
ruft noch einmal euclidian auf - euclidian [] []
gibt 0 zurück und ruft selbst keine Rekursion mehr auf - Da die Rekursion beendet ist, können die Ergebnisse nun aufaddiert werden. Also: \(1 + (9 + (4 + 0)) = 14\)