Deswegen fange ich jetzt mal mit einem Beispiel an: Wie finde ich in einer Menge von Dateien diejenigen heraus, die den gleichen Inhalt besitzen? Wir werden sehen, dass uns die verzögerte Auswertung (LazyEvaluation?) hierbei eine große Hilfe leistet. Aufgrund dieser Technik können wir Dateien so behandeln, als wären sie komplett in den Speicher geladen, was sie aber nicht sind. Der Algorithmus wird dadurch ziemlich einfach: Wir laden scheinbar alle Dateien ein und sortieren sie lexikografisch nach ihrem Inhalt. Die Dateien gleichen Inhalts sind dann aufeinanderfolgende Elemente in der sortierten Liste. Zum Sortieren wird immer nur soviel eingeladen, wie zum Sortieren nötig ist. Eine Datei, die sich bereits relativ weit am Anfang von allen anderen Dateien unterscheidet, wird nie vollständig eingelesen. Nur Dateien, die vollständig mit anderen Dateien übereinstimmen, müssen komplett gelesen werden.
Hier mein Haskell-Programm:
|
Das eigentliche Auffinden gleicher Daten ist in die Funktionen 'groupEqualElems' und 'clusterEqualElems' ausgelagert. Beide sind so allgemein gehalten, dass sie weder auf Dateien beschränkt sind, noch auf bestimmte Typen. 'groupEqualElems' erwartet eine Liste von Paaren der Form (Dateiinhalt, Dateiname). Diese Liste wird sortiert, wobei zuerst nach Dateiinhalt und dann nach Dateiname sortiert wird. Mit 'groupBy' werden die Dateien gleichen Inhalts in Unterlisten zusammengefasst. Zuletzt wirft 'map (map snd)' die Dateiinhalte weg und lässt die Dateinamen übrig. 'clusterEqualElems' entfernt alle Unterlisten der Länge 1. Das sind die Unikate unter den Dateien. 'clusterEqualFiles' ist die einzige Funktion, die Ein- und Ausgaben tätigt. Mit 'mapM readFile fileNames' werden alle Dateien (scheinbar komplett) eingelesen und deren Inhalte in der Liste 'files' gespeichert. Dann werden die Dateiinhalte mit 'zip' mit den zugehörigen Dateinamen verbunden.
Wie verwendet man das Programm? Ich habe mir eine Shell-Schnittstelle geschenkt und einfach alles von einer interaktiven Haskell-Umgebung aus gestartet. Nachfolgend eine Sitzung mit dem GHCi, in der ich alle Dateien des aktuellen Verzeichnisses vergleiche:
|
|
Wie müßte so eine Bibliothek aussehen? Hm... keine Ahnung. Bestimmt monadisch, aber genauere Gedanken hab ich mir noch nicht gemacht ;-)