Stellen wir uns doch mal vor, wir hätten folgendes Problem
zu lösen: Zu einer gegebenen Menge von Punkten (wobei es
keinen Unterschied macht, ob es sich um 2D- oder 3D-Punkte
handelt) soll die maximale Entfernung zwischen zwei Punkten
ermittelt werden. Wir brauchen also zunächst eine Art
Entfernungstabelle, wie wir sie z.B. aus dem Autoatlas
kennen. Aus all diesen Entfernungen können wir dann mit
(max ...) die grösste herausziehen.
Aber wie kommt man zu so einer Entfernungstabelle? Wir erinnern
uns an die dreieckige Form solcher Tabellen: Wenn wir die
Entfernung eines jeden Punktes nach jedem anderen ermitteln,
dann machen wir etwas falsch - das wären doppelt so viele
Berechnungen und Ergebnisse wie wir brauchen. Das liegt einfach
in der Tatsache begründet, dass es von A nach B genauso weit
ist wie von B nach A!
Denken wir mal in Ruhe nach. Angenommen, wir benennen alle
Punkte (in der Reihenfolge, wie sie in der Liste vorliegen)
einfach A, B, C usw., dann können wir doch mal anfangen,
indem wir die Entfernungen von A nach allen anderen Punkten
berechnen. Wenn wir das haben, können wir A anschliessend
abhaken: Keiner der restlichen Punkte muss noch einmal mit
A verglichen werden - dann hätten wir ja doppelte Daten.
Wozu haben wir denn in Lisp die Funktion
(cdr ...), wenn
nicht, um dieses Problem anzugehen? Nachdem wir A erledigt
haben, trennen wir den Rest der Liste mit
cdr ab, sie
fängt nun mit B an. Und was ist jetzt anders? Gar nichts, wir
wissen doch schon, wie das geht: Wir berechnen die Entfernungen
zwischen B und allen anderen Punkten ab C - und dann wird wieder
abgetrennt. Jetzt ist B erledigt und abgehakt. Dieses Spiel
können wir anschliessend mit C, D, E usw. weiter fortsetzen.
Ist die Anzahl der Punkte bekannt und nicht zu groß, könnte
man jetzt auf die Idee kommen, das alles so zu codieren, wie
wir es uns soeben vorgestellt haben. Hier soll es aber darum
gehen, einen allgemeinen und universell verwendbaren Ansatz
vorzustellen. Was wir brauchen, ist eine Funktion, die analog
zu
(mapcar ...) arbeitet, aber nicht wie mapcar jeweils
den
car einer Liste bearbeitet, sondern den
cdr,
also genau das, was bei
mapcar jeweils ausgeblendet
wird.
Wegen der Einschränkungen, die für benutzerdefinierte Funktionen
nun mal in AutoLisp bestehen, ist es mit dem 'analog' nicht weit
her, aber wir sind doch zufrieden, wenn sie ähnlich ist: Wir
beschränken uns hier auf das Bearbeiten einer einzigen Liste,
und den
body der Funktion müssen wir natürlich - wie
immer - als lambda-ausdruck übergeben. Wenn man erst einmal
weiss, was man will, ist die Implementierung der Funktion gar
nicht mehr schwierig:
(defun mapcdr(expr liste / retl)
(repeat(1-(length liste))
(setq retl
(cons (apply expr(list liste)) retl)
)
(setq liste(cdr liste))
)
(reverse retl)
)
Noch eines fällt auf, wenn man die Funktion betrachtet: Ich
habe die Anzahl der Durchgänge um 1 vermindert. Würde unsere
Punkteliste bis Z gehen, wäre der Listenrest (Y Z) also der
letzte Rest, auf den die lambda-expression angewendet wird.
Dies macht die Handhabung für unser Beispiel einfacher, da
für Z allein keine Entfernung mehr berechnet werden muss und
kann. Das gilt auch für andere Beispiele, aber nicht immer:
Wer eine Funktion braucht, die auch den allerletzten Rest
anzeigt, sollte eine Version ohne das
(1- ...) benutzen.
Wir können jetzt unser Problem mit dem Maximalwert in einer
Entfernungstabelle folgendermassen lösen:
(apply'max
(apply'append
(mapcdr
'(lambda(rest / )
(mapcar
'(lambda(car-von-rest / )
(distance(car rest)car-von-rest)
)
(cdr rest)
)
)
punkteliste
)
)
)
Lisp ist doch immer wieder erstaunlich: Ein stets neues Abmischen
der Zutaten
mapcar,
lambda,
apply usw., und
schon haben wir wieder eine neue Lösung für ein neues Problem.
Aber wie funktioniert das denn jetzt? Fangen wir mit den Erklärungen
mal beim ersten (also äusseren)
lambda an: Dieser
lambda-expression wird von
(mapcdr ...) der jeweilige
Listenrest zur Bearbeitung übergeben. Darin eingebettet finden wir
ein
(mapcar ...), das den Rest wiederum in einen
car
und den dazugehörenden Rest vom Rest aufteilt. Die Entfernungen
zwischen dem
car und allen Elementen aus dem
cdr
werden berechnet.
Das entspricht genau dem, was wir in den Vorüberlegungen gefordert
haben.
(mapcdr ...) übergibt uns sukzessive die Listenreste,
auf die der lambda-Ausdruck angewendet wird. Das Ergebnis von
(mapcdr ...) ist also eine Liste mit lauter Unterlisten,
die von links nach rechts immer kürzer werden. Mit
(apply'append ...) wird diese Liste anschliessend
eingeebnet, d.h. alle Entfernungen liegen nun in einer Liste der
Tiefe 1 vor. Zum Schluss wird noch mit
(apply'max ...) der
grösste Wert extrahiert.