Mit dem heutigen Blogartikel möchte ich eine kleine Artikelserie mit dem Titel „Haskell für Einsteiger“ beginnen. Die Serie richtet sich an Leser mit Programmiererfahrung, die Lust auf Haskell haben, bisher aber den Einstieg in die Sprache nicht richtig geschafft haben.

Ich werde versuchen, Ihnen durch praxisnahe Beispiel und direkt lauffähigem Code den Einstieg zu erleichtern. Um loszulegen benötigen Sie lediglich eine Installation der Haskell Platform sowie ein Checkout des git Repositories zu dieser Artikelserie. Wir werden hin und wieder auch ausgewählte Paket über hackage, dem Haskell-Paket-Repository, installieren.

Ich werde mir Mühe geben, viele Dinge detailliert zu erklären. Allerdings würde es den Rahmen dieses Blogs sprengen, auf jedes Detail einzugehen. Hierzu sei das Studium des einen oder anderen Haskell Tutorials oder Buchs empfohlen. Natürlich können Sie Rückfragen auch als Kommentar zu diesem Artikel stellen.

Im heutigen Artikel implementieren wir eine abgespeckte Version des Unix-Tools tail. Dieses Kommandozeilenprogramm zeigt die letzten Zeilen einer Datei an; per Default werden die letzten 10 Zeilen angezeigt, über die Kommandozeilenoption -n N kann die Zeilenanzahl aber auch auf die Zahl N gesetzt werden.

Um zu schauen, ob Ihre Haskell Installation funktioniert, sollten Sie spätestens jetzt ein Checkout des git Repositories machen. Dann führen Sie im Verzeichnis haskell-for-beginners folgende Befehle aus:

$ cabal install --only-dependencies  # installiert zusätzliche Pakete
$ cabal build                        # baut das Programm

Wenn alles gut geht, finden Sie jetzt das kompilierte Programm unter dist/build/tail/tail. Wenn Sie nun dieses Programm mit der Option --help aufrufen, sollten Sie folgende Ausfgabe sehen:

$ dist/build/tail/tail --help
USAGE: tail [-n N] [FILE ...]

So, jetzt schauen wir uns aber den Code unserer tail-Implementierung an. Sie finden den Code in src/Tail.hs. Wir starten zunächst mit den Imports für eine Datenstruktur für Sequenzen. Das Besondere an dieser Datenstrukturen ist, dass man ein neues Element links oder rechts an eine Sequenz in Zeit O(1) anhängen kann. (Wir könnten auch normale Listen verwenden. Allerdings hat hier das Anhängen an das rechte Ende einer Liste lineare Laufzeit.)

import qualified Data.Sequence as Seq 
import qualified Data.Foldable as F -- nötig für toList auf Sequenzen

Das Modul Safe benötigen wir, um beim Parsen der Kommandozeilenargument das Argument der Option -n in eine Zahl zu konvertieren. Haskell hat zwar standardmäßig eine read-Funktion für diesen Zweck, aber hierbei führt das Fehlschlagen der Konvertierung direkt zu einem Programmabsturz. Das Safe-Modul stellt eine bessere Variante der read-Funktion zur Verfügung.

import Safe

Als nächstes folgen Module, die uns Zugriff auf die Kommandozeilenargumente, auf Funktionen zum Beenden des Programms sowie auf Funktionalität zur Ein-/Ausgabe bieten.

import System.Environment 
import System.Exit        
import System.IO

Das ByteString-Modul schließlich stellt Operation für den Umgang mit Byte-Arrays zur Verfügung.

import qualified Data.ByteString as BS

Wenn Sie selbst ein Haskell Programm schreiben, aber nicht wissen welche Funktionen in welchen Modulen zu finden sind, gibt es mindestens drei Möglichkeiten, dies herauszufinden:

  • Sie benutzen hoogle oder hayoo, zwei Suchmaschine für Haskell-API-Dokumentation.
  • Sie studieren die Übersicht der gängigen Haskell Module.
  • Sie schauen sich auf hackage um.

Jetzt können wir mit der eigentlichen Implementierung loslegen. Wir starten mit der Funktion printTail, welche die letzten lines Zeile einer Datei file ausgibt.

printTail :: Int -> FilePath -> IO ()
printTail lines file =
    if file == "-"
    then doWork stdin
    else withFile file ReadMode doWork
    where
      doWork :: Handle -> IO ()
      doWork h =
          do list <- collectLines lines h
             mapM_ printLine list
      printLine bs =
          do BS.hPut stdout bs
             BS.hPut stdout newline
      newline = BS.pack [10]

Die printTail-Funktion öffnet erst die zu lesende Datei, dabei wird - als Standard-Input interpretiert (wie üblich). Für echte Dateien benutzten wir die Funktion withFile. Diese Funktion öffnet eine Datei, führt mit der geöffneten Datei die übergebenen Aktion aus (hier: doWork) und stellt dann sicher, dass die Datei nach Abschluss der Aktion oder im Fehlerfall geschlossen wird.

Die Funktion doWork nimmt dann eine Handle, welches in Haskell eine geöffnete Datei repräsentiert. Mittels der noch zu implementierenden Funktion collectLines werden die letzten lines Zeilen aus der Datei extrahiert und anschließend mit der Hilfsfunktion printLine ausgegeben. Der Aufruf mapM_ printLine list ruft dabei die printLine-Funktion für jedes Element der Liste list auf.

Noch ein Wort zum Typ von printTail: in der Typsignatur zu Beginn der Funktion legen wir diesen auf Int -> FilePath -> IO () zurück, die Funktion nimmt also zwei Argumente vom Typ Int und FilePath und hat als Rückgabetyp IO (). Der Rückgabetyp bedeutet, dass die Funktion Seiteneffekte hat (der IO Teil des Typs) und kein Ergebnis liefert (der () Teil des Typs, gesprochen „Unit“).

In der collectLines-Funktion sammeln wir nun die richtigen Zeilen aus der Datei auf. Dazu benutzen wir die Datenstruktur aus Data.Sequence. Zu Anfang ist die Sequenz leer (Seq.empty). Dann hängen wir jede Zeile der Datei rechts an die Sequenz mittels Seq.|> an, und sorgen anschließend dafür, dass überschüssige Zeilen am linken Ende entfernt werden. Dazu benutzen wir Seq.viewl, um einen „View“ auf das linke Ende zu bekommen. Wenn das linke Ende leer ist (Seq.EmptyL) ist das ein Bug, anderenfalls matchen wir mittels _ Seq.:< rest auf das erste Element _ und den rest.

collectLines :: Int -> Handle -> IO [BS.ByteString]
collectLines lines handle = loop Seq.empty
    where
      loop acc =
          do isEof <- hIsEOF handle
             if isEof
             then return (F.toList acc)
             else do l <- BS.hGetLine handle
                     loop (trim (acc Seq.|> l))
      trim seq =
          if Seq.length seq <= lines
          then seq
          else case Seq.viewl seq of
                 Seq.EmptyL -> error ("Bug in tail: argument to -n should not be negative")
                 _ Seq.:< rest -> rest

Da wir keine Annahme über das Encoding der zu lesenden Daten machen wollen, lesen wir rohe Byte-Arrays (Type BS.ByteString) aus der Datei und verzichten auf eine Konvertierung nach String.

Die hier vorgestellte Implementierung von collectLines ist sicher nicht die effizienteste, da wir immer die komplette Datei lesen. Die C-Implementierung von tail unter BSD ist hier z.B. wesentlich schlauer, denn hier wird mit Memory-Mapped IO vom Ende der Datei her immer mehr Zeilen in den Speicher geladen, bis die gewünschte Anzahl Zeilen erreicht ist. So etwas ist natürlich auch mit Haskell möglich, es gibt z.B. auf Hackage einen Wrapper für den mmap-Systemcall. Falls ein Leser es wünscht, liefere ich gerne eine effizientere Implementierung von collectLines mittels mmap nach, in diesem Falle bitte einen entsprechenden Kommentar schreiben.

Als nächstes widmen wir uns dem Parsen der Kommandozeilenargumente. Dazu definieren wir zunächste einen Datentyp für die Optionen, die wir erwarten:

data TailOpts
    = TailOpts
      { to_files :: [FilePath]
      , to_lines :: Int
      }

Das Parsen der Kommandzeilenargument funktioniert über Pattern-Matching auf der Liste der Argumente:

parseArgs :: [String] -> IO TailOpts
parseArgs args =
    if "-h" `elem` args || "--help" `elem` args
    then usage
    else
        case args of
          ("-n" : nStr : rest) ->
              case readMay nStr of
                Just n | n >= 0 ->
                    return (TailOpts { to_files = rest, to_lines = n })
                _ ->
                    abort "Argument to -n must be a non-negative int."
          [] -> return (TailOpts { to_files = ["-"], to_lines = defaultLines })
          _ -> return (TailOpts { to_files = args, to_lines = defaultLines })
    where
      usage = abort "USAGE: tail [-n N] [FILE ...]"
      defaultLines = 10
      abort msg =
          do hPutStrLn stderr msg
             exitWith (ExitFailure 1)

In der main-Funktion bauen wir schließlich alles zusammen:

main =
    do args <- getArgs
       opts <- parseArgs args
       mapM_ (printTail (to_lines opts)) (to_files opts)

Damit haben wir unsere abgespeckte Version des Unix-Tools tail abgeschlossen. Ich freue mich auf Ihr Feedback!