C-Programmierer. Vergeßt! Vergeßt am besten alles, was Ihr über Programmierung und Programmiersprachen wißt.
Haskell ist eine rein funktionale Sprache.
`Funktional' (auch: applikativ, werteorientiert) im Gegensatz zu
`Rein' funktionale Sprache im Gegensatz zu hybriden Sprachen wie
Ein Haskell Programm besteht aus einem oder mehreren Modulen.
Ein Modul besteht aus Definitionen und Deklarationen.
---------------------------------------------------------------------- > date = (18, "April", 1996) ----------------------------------------------------------------------
Definitionen werden im allgemeinen in Form von Gleichungen angegeben: der Bezeichner auf der linken Seite wird durch den Ausdruck auf der rechten Seite definiert.
Jeder Ausdruck besitzt einen Typ. Der Typ von `date' wird wie folgt deklariert:
---------------------------------------------------------------------- > date :: (Int, String, Int) ----------------------------------------------------------------------
Funktionen werden ebenfalls durch Gleichungen definiert. Der oder die formalen Parameter werden nach dem Namen der Funktion aufgeführt.
---------------------------------------------------------------------- > succ :: Int -> Int > succ n = n + 1 > > twice f a = f (f a) ----------------------------------------------------------------------
Aufgabe 1. Rate den Typ von `twice'!
Beachte: Haskell kommt mit wenig Syntax aus; `f a' bezeichnet die Anwendung der Funktion `f' auf das Argument `a'.
Das Berechnungsmodell von Haskell ist denkbar einfach: ein gegebener Ausdruck wird zu einem Wert (auch: Normalform) reduziert.
----------------------------------------------------------------------
succ (succ 5) => succ 5 + 1 (succ.1)
=> (5 + 1) + 1 (succ.1)
=> 7
----------------------------------------------------------------------
Wir sagen: `succ (succ 5)' reduziert zu `7'.
Aufgabe 2. Reduziere `twice succ 0' und `twice twice succ 0'! Beachte: der Ausdruck `twice succ 0' kürzt `(twice succ) 0' ab, da die Funktionsanwendung von links assoziiert.
Eine (Programmier-) Sprache lernt man am besten durch Beispiele. Unser erstes: Binärbäume.
Ein neuer Typ wird mittels einer Datentypdefinition eingeführt.
---------------------------------------------------------------------- data IntTree = Empty | Node IntTree Int IntTree ----------------------------------------------------------------------
Der Bezeichner `IntTree' ist der Typname; `Empty' und `Node' sind Konstruktoren: mit ihrer Hilfe werden Element des Datentyps konstruiert.
---------------------------------------------------------------------- > atree :: IntTree > atree = Node (Node Empty 2 Empty) 5 Empty ----------------------------------------------------------------------
Beachte: nur Bezeichner von Typen und Konstruktoren werden groß geschrieben.
Konstruktoren werden wie `normale Funktionen' verwendet. Zusätzlich - und das unterscheidet sie von Funktionen - dienen sie zur Programmierung von Fallunterscheidungen.
---------------------------------------------------------------------- > insert :: Int -> IntTree -> IntTree > insert a Empty = Node Empty a Empty > insert a (Node l b r) = if a <= b then Node (insert a l) b r > else Node l b (insert a r) ----------------------------------------------------------------------
`Empty' und `Node l b r' sind Beispiele für Muster. Die Variablen `l', `b' und `r' benennen die entsprechenden Komponenten eines Baumsknotens.
Aufgabe 3. Reduziere `insert 7 atree'!
Für Testzwecke ist es nützlich, einen `größeren' Binärbaum zur Hand zu haben.
---------------------------------------------------------------------- > big :: Int -> IntTree > big n = Node (big (2*n)) n (big (2*n+1)) ----------------------------------------------------------------------
Etwas stutzen kann nicht schaden: `prune' verhindert, daß `big 1' in den Himmel wächst.
---------------------------------------------------------------------- > prune :: Int -> IntTree -> IntTree > prune 0 t = Empty > prune (n+1) Empty = Empty > prune (n+1) (Node l a r) = Node (prune n l) a (prune n r) ----------------------------------------------------------------------
Mit `prune n (big 1)' wird ein vollständig ausgeglichener Binärbaum der Tiefe `n' konstruiert.
Aufgabe 4. Reduziere `prune 2 (big 1)'! Worauf muß man achten?
Löschen ist schwieriger als Einfügen.
---------------------------------------------------------------------- > delete :: Int -> IntTree -> IntTree > delete a Empty = Empty > delete a (Node l b r) > | a < b = Node (delete a l) b r > | a == b = join l r > | otherwise = Node l b (delete a r) ----------------------------------------------------------------------
Der senkrechte Strich `|' kennzeichnet einen Wächter: ein boolescher Ausdruck, der über die Anwendung einer Gleichung wacht.
Aufgabe 5. Formuliere `delete' mit Hilfe von `if'!
Die Funktion `join' konkateniert zwei Suchbäume: der am weitesten rechts stehende Knoten des linken Teilbaums wird zur Wurzel.
---------------------------------------------------------------------- > join :: IntTree -> IntTree -> IntTree > join Empty r = r > join (Node ll a lr) r = let (b, t) = split ll a lr > in Node t b r > > split :: IntTree -> Int -> IntTree > -> (Int, IntTree) > split l a Empty = (a, l) > split l a (Node rl b rr) > = let (c, t) = split rl b rr > in (c, Node l a t) ----------------------------------------------------------------------
Wir haben uns bisher auf den Typ `Int' für Knotenmarkierungen festgelegt. Die folgende Datentypdefinition ist bezüglich des `Knotentyps' parametrisiert. Der Bezeichner `lab' ist ein Typparameter.
---------------------------------------------------------------------- > data Tree lab = Empty | Node (Tree lab) lab (Tree lab) ----------------------------------------------------------------------
Der Typ `IntTree' läßt sich als Abkürzung definieren.
---------------------------------------------------------------------- > type IntTree = Tree Int ----------------------------------------------------------------------
Bezüglich dieser Typdefinition lauten die Typen der obigen Funktionen.
---------------------------------------------------------------------- > big :: Int -> Tree Int > insert :: ?? > prune :: Int -> Tree lab -> Tree lab > delete :: ?? > join :: Tree lab -> Tree lab -> Tree lab > split :: Tree lab -> lab -> Tree lab -> (lab, Tree lab) ----------------------------------------------------------------------
Die Funktionen `prune', `join' und `split' sind polymorph; sie arbeiten auf Binärbäumen über beliebigen Grundtypen.
Lies: für alle Typen `lab' ist `Int -> Tree lab -> Tree lab' ein gültiger Typ von `prune'.
Aufgabe 6. Rate den Type von `insert' und `delete'!
Die Funktionen `insert' und `delete' verwenden die Vergleichsfunktionen `<=', `<' und `=='. Diese sind überladen; sie arbeiten je nach Typ unterschiedlich und sind nicht für alle Typen definiert: es ist z.B. nicht möglich, Funktionen zu vergleichen.
---------------------------------------------------------------------- > insert :: (Ord lab) => lab -> Tree lab -> Tree lab > delete :: (Ord lab) => lab -> Tree lab -> Tree lab ----------------------------------------------------------------------
`Ord' ist ein Beispiel für eine Typklasse. Lies: für alle Typen `lab', auf denen eine Ordnung definiert ist, ist `lab -> Tree lab -> Tree lab' ein gültiger Typ von `insert'.
Aufgabe 7. `Mengen' können durch binäre Suchbäume ohne Duplikate repräsentiert werden. Modifiziere `insert' und `delete' entsprechend!
Aufgabe 8. Implementiere den Datentyp `Wörterbuch' unter Verwendung binärer Suchbäume.
----------------------------------------------------------------------
type Dict attr val = Tree (attr, val)
empty :: Dict a b
add :: Ord a => (a,b) -> Dict a b
-> Dict a b
delete :: Ord a => a -> Dict a b -> Dict a b
lookupWithDefault :: Ord a => Dict a b -> b -> a -> b
----------------------------------------------------------------------
Funktionale Programmierer sprechen auch von endlichen Abbildungen.
Zwei von drei Funktionen, die in Haskell geschrieben werden, arbeiten wahrscheinlich mit Listen `;-)'. Für die folgenden Beispiele kommen auch wir nicht ohne aus. Listen könnten wie folgt definiert werden.
---------------------------------------------------------------------- > data List a = Nil | Cons a (List a) ----------------------------------------------------------------------
Haskell verwendet die folgende Notation: `[a]' statt `List a', `[]' statt `Nil' und `:' (Infixoperator) statt `Cons'. Es gibt Myriaden vordefinierter Listenfunktionen.
---------------------------------------------------------------------- (++) :: [a] -> [a] -> [a] ----------------------------------------------------------------------
Aufgabe 9. Definiere Funktionen, die einen Binärbaum in eine Liste und umgekehrt überführen. Beachte: `build' sollte möglichst einen ausgeglichenen Baum erzeugen.
---------------------------------------------------------------------- inorder :: Tree a -> [a] build :: [a] -> Tree a ----------------------------------------------------------------------
Die Idee des `Literate Programming' geht wie so vieles auf Donald E. Knuth zurück. Der übliche Kommentierstil wird auf den Kopf gestellt: alles ist Kommentar, Programmzeilen werden speziell gekennzeichnet.
---------------------------------------------------------------------- Die Funktion `insert' fuegt ein Element zu einen binaeren Suchbaum hinzu. > insert :: Int -> IntTree -> IntTree > insert a Empty = Node Empty a Empty > insert a (Node l b r) = if a <= b then Node (insert a l) b r > else Node l b (insert a r) ----------------------------------------------------------------------
Auf diese Weise läßt sich z.B. ein Haskellprogramm in LaTeX dokumentieren (mit etwas Programmunterstützung).
HUGS ist ein Haskell-Interpreter und somit gut geeignet, kleinere Programme oder Programmfragmente zu erstellen und zu testen. Typische Vorgehensweise:
antimon 1> hugs -l -h50000 BinTree.lhs Hugs, The Haskell User's Gofer System Version 1.0
? insert 7 atree Node (Node Empty 2 Empty) 5 (Node Empty 7 Empty)
Nützliche Kommandos:
Beispiel: Ein- und Ausgabe von Zeichenketten. Die Ausgabe eines Zeichens ist vordefiniert.
---------------------------------------------------------------------- > putChar :: Char -> IO () ----------------------------------------------------------------------
Elemente vom Typ `IO val' beschreiben EA-Aktionen, die ein Element vom Typ `val' zurückgeben (`()' ist der `Dummytyp'). Beachte: die Aktionen werden nicht ausgeführt.
---------------------------------------------------------------------- > putLine :: String -> IO () > putLine [] = putChar '\n' > putLine (c:s) = putChar c >> putLine s ----------------------------------------------------------------------
Der Operator `>>' korrespondiert mit dem Semikolon in Pascal.
---------------------------------------------------------------------- > (>>) :: IO a -> IO b -> IO b ----------------------------------------------------------------------
Jedes Haskell Programm muß den Bezeichner `main :: IO ()' definieren.
---------------------------------------------------------------------- > main = putLine "hello world" ----------------------------------------------------------------------
Beim Programmstart wird die an `main' gebundene Aktion (respektive die Beschreibung der Aktion) ausgeführt.
Warum ist es wichtig, die Beschreibung einer Aktion von deren Ausführung zu trennen? Anderenfalls wären die Ausdrücke
---------------------------------------------------------------------- let a = putLine "ha" in a >> a putLine "ha" >> putLine "ha" ----------------------------------------------------------------------
nicht äquivalent. Das Prinzip der Ersetzung `von Gleichem durch Gleiches' wäre verletzt.
Das Pendant von `putChar' ist `getChar'.
---------------------------------------------------------------------- > getChar :: IO Char ----------------------------------------------------------------------
Mit `getLine' wird entsprechend eine Zeile eingelesen.
---------------------------------------------------------------------- > getLine :: IO String > getLine = getChar >>= \ c -> > if c=='\n' then > return "" > else > getLine >>= \ s -> > return (c:s) ----------------------------------------------------------------------
Der Operator `>>=' erlaubt, auf das Ergebnis einer Aktion zuzugreifen.
---------------------------------------------------------------------- > (>>=) :: IO a -> (a -> IO b) -> IO b ----------------------------------------------------------------------
Der Ausdruck `\x -> e' bezeichnet eine Funktion mit dem formalen Parameter `x' und dem Rumpf `e'.
C-Programmierer. `act1 >>= \x -> act2' läßt sich als `x = act1; act2' lesen. (Haskell 1.3 bietet eine ähnliche Notation an).
Wir verwenden die bisher eingeführten Funktionen (insbesondere aus Aufgabe 6), um ein `interaktives Wörterbuch' zu programmieren. Beispielsitzung:
---------------------------------------------------------------------- antimon 1> db asterix db> lookup key: alea iacta est der Wuerfel ist gefallen db> enter key: acta est fabula value: vorbei ist vorbei db> save db> end ----------------------------------------------------------------------
Beispiel für ein Wörterbuch:
---------------------------------------------------------------------- [(äb imo pectore", "von ganzem Herzen"), (äcta est fabula", "vorbei ist vorbei"), ... ----------------------------------------------------------------------
---------------------------------------------------------------------- > import LibSystem ( getArgs ) > > type State = (String, Dict String String) > > main :: IO () > main = getArgs >>= \args -> > let fname = args!!0 in > readFile fname >>= \cnts -> > loop (fname, read cnts) > > loop :: State -> IO val > loop state = putStr "db> " >> > getLine >>= \line -> > exec state (words line) >>= \state' -> > loop state' > > exec :: State -> [String] -> IO State > exec state [] = return state > exec state@(fname, dict) (cmd:_) = case cmd of > "end" -> exit > "enter" -> askFor "key: " >>= \key -> > askFor "value: " >>= \val -> > let dict' = add (key, val) dict in > return (fname, dict') > "lookup" -> askFor "key: " >>= \key -> > putLine (lookupWithDefault > dict "not found" key) >> > return state > ßave" -> writeFile fname (show dict) >> > return state > _ -> putLine ünknown command" >> > return state ----------------------------------------------------------------------
GHC (Glasgow Haskell Compiler) ist ein Batchcompiler ähnlich wie `cc'. Typische Vorgehensweise:
---------------------------------------------------------------------- antimon 1> ghc -o db Database.lhs ----------------------------------------------------------------------
---------------------------------------------------------------------- antimon 1> db asterix db> ... ----------------------------------------------------------------------
GHC bietet eine Unzahl von Optionen an (siehe Handbuch).
Go to the first, previous, next, last section, table of contents.