Sprache Haskell / Skripte
 
StartSeite | SpracheHaskell/ | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern

Von Nicht-Mathematikern wird die SpracheHaskell schnell als "zu mathematisch" abgetan. Mathematiker wiederum interessieren sich gar nicht so sehr dafür, wie man zunächst erwartet. Auf jeden Fall bringt man Haskell sicher nicht mit typischen Skriptsprachenanwendungen in Verbindung. Warum eigentlich nicht? Als Hochsprache mit wirklich hohem Abstraktionsgrad sollte hier doch einiges zu holen sein.

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:
module EqualFiles where

import System.Directory (getDirectoryContents)
import Data.List (groupBy, sort, (\\))


groupEqualElems :: (Ord key, Ord elem) => [(elem, key)] -> [[key]]
groupEqualElems xs =
   map (map snd) (groupBy (\x y -> fst x == fst y) (sort xs))

{- | Only return sub-lists with more than one element. -}
clusterEqualElems :: (Ord key, Ord elem) => [(elem, key)] -> [[key]]
clusterEqualElems xs =
   filter (not . null . tail) (groupEqualElems xs)

clusterEqualFiles :: [FilePath] -> IO [[FilePath]]
clusterEqualFiles fileNames =
   do files <- mapM readFile fileNames
      return (clusterEqualElems (zip files fileNames))

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:
*EqualFiles> files <- getDirectoryContents "."
*EqualFiles> let filesNoDot = files \\ [".", ".."]
*EqualFiles> clusterEqualFiles filesNoDot >>= print
Man kann das Ergebnis auch noch netter formatieren:
*EqualFiles> clusterEqualFiles filesNoDot >>= (putStr . unlines . map unwords)


Nicht der dümmste Ansatz, Henning. Haskell bräuchte bloß eine kleine Bibliothek von Kombinatoren, um externe Programme aufzurufen und deren Ergebnisse zu bearbeiten. Dann würde ich sehr gerne meine Bash entsorgen und Hugs stattdessen benutzen. Mindestens für Skripte: man könnte viele häßliche Quote-Symbole ersparen.

Wie müßte so eine Bibliothek aussehen? Hm... keine Ahnung. Bestimmt monadisch, aber genauere Gedanken hab ich mir noch nicht gemacht ;-)


StartSeite | SpracheHaskell/ | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern
Text dieser Seite ändern (zuletzt geändert: 6. Dezember 2005 19:10 (diff))
Suchbegriff: gesucht wird
im Titel
im Text