Ein zentrales Prinzip der Programmierung ist das Abstraktionsprinzip -- das man auch verwendet, ohne es zu kennen.
Abstraktion, 1. Verallgemeinerung. 2. auf zufällige Einzelheiten verzichtende, begrifflich zusammengefaßte Darstellung.
Beispiel: Eine `Funktion', die das Kugelvolumen zu einem speziellen Radius berechnet, ist fast nutzlos.
---------------------------------------------------------------------- > r = 5 > volume_of_r = 3/4 * pi * r^3 ----------------------------------------------------------------------
Wird von dem speziellen Radius abstrahiert -- indem der Radius zum Parameter gemacht wird -- so erhält man eine Definition, die sehr viel nützlicher ist.
---------------------------------------------------------------------- > volume r = 3/4 * pi * r^3 > volume_of_r = volume r ----------------------------------------------------------------------
Diesem Prinzip folgend kann z.B. eine Sortierfunktion mit der zugrundeliegenden Vergleichsfunktion parametrisiert werden.
---------------------------------------------------------------------- > qsortBy :: (a -> a -> Bool) -> [a] -> [a] > qsortBy (<=) [] = [] > qsortBy (<=) (a:x) = qsortBy (<=) l ++ a : qsortBy (<=) r > where (l, r) = partition (<= a) x > > qsort :: Ord a => [a] -> [a] > qsort = qsortBy (<=) ----------------------------------------------------------------------
`qsort' ist eine sogenannte Funktion höherer Ordnung. [`f :: t1->t2' heißt Funktion höherer Ordnung, wenn `t1' oder `t2' ein funktionaler Typ ist.]
Funktionen höherer Ordnung werden unter anderem (und gerne) verwendet, um Rekursionsmuster `einzufangen'. Beispiel: Den Funktionen `inclist' und `strupr' liegt ein gemeinsames Rekursionsmuster zugrunde.
---------------------------------------------------------------------- > inclist [] = [] > inclist (a:x) = a + 1 : inclist x > > strupr [] = [] > strupr (a:x) = toUpper a : strupr x ----------------------------------------------------------------------
Der Mathematiker würde sagen: Hier wird eine Funktion auf eine Liste fortgesetzt. Die Funktion `map' implementiert dieses Muster. Graphische Darstellung:
----------------------------------------------------------------------
[x1, x2, ..., x{n-1}, xn]
|
| map f
v
[f x1, f x2, ..., f x{n-1}, f xn]
----------------------------------------------------------------------
Realisierung der Funktion `map':
---------------------------------------------------------------------- > map :: (a -> b) -> [a] -> [b] > map f [] = [] > map f (a:x) = f a : map f x ----------------------------------------------------------------------
Spezialisierung der `map'-Funktion:
---------------------------------------------------------------------- > inclist = map (+ 1) > strupr = map toUpper ----------------------------------------------------------------------
Beachte: `map' läßt sich einfacher mit Hilfe von Listenbeschreibungen definieren.
---------------------------------------------------------------------- > map f x = [ f a | a <- x ] ----------------------------------------------------------------------
Auf jedem (polymorphen) Datentyp läßt sich sinnvoll eine ``map''-Funktion definieren.
---------------------------------------------------------------------- > mapMaybe :: (a -> b) -> Maybe a -> Maybe b > mapMaybe f Nothing = Nothing > mapMaybe f (Just a) = Just (f a) > > data Tree lab = Node lab [Tree lab] > > mapTree :: (a -> b) -> Tree a -> Tree b > mapTree f (Node a ts) = Node (f a) (map (mapTree f) ts) ----------------------------------------------------------------------
Mathematiker: Sei `T' ein einstelliger Typkonstruktor, dann hat die zugehörige ``map''-Funktion den Typ `(a -> b) -> (T a -> T b)'. Mit einigen zusätzlichen Bedingungen bildet `T, map)' einen Funktor.
Ein anderes Rekursionsmuster liegt den folgenden Funktionen zugrunde.
---------------------------------------------------------------------- > sum [] = 0 > sum (a:x) = a + sum x > > sequence [] = done > sequence (a:as) = a >> sequence as ----------------------------------------------------------------------
Die Funktion `foldr' (rechtsassoziative Auffaltung) implementiert dieses Muster. Graphische Darstellung:
----------------------------------------------------------------------
x1 : x2 : ... : x{n-1} : xn : []
|
| foldr (*) e
v
x1 * (x2 * ... * (x{n-1} * (xn * e)) ... )
----------------------------------------------------------------------
Realisierung der Funktion `foldr':
---------------------------------------------------------------------- > foldr :: (a -> b -> b) -> b -> [a] -> b > foldr (*) e [] = e > foldr (*) e (a:x) = a * foldr (*) e x ----------------------------------------------------------------------
Spezialisierung der `foldr'-Funktion:
---------------------------------------------------------------------- > sum = foldr (+) 0 > sequence = foldr (>>) done ----------------------------------------------------------------------
Aufgabe 1. Definiere `product', `or', `concat', `isort' (Sortieren durch Einfügen) und `accumulate' mit Hilfe von `foldr'!
Auf vielen (polymorphen) Typen läßt sich sinnvoll eine `fold'-Funktion definieren.
---------------------------------------------------------------------- > data Tree lab = Node lab [Tree lab] > > fold :: (a -> [b] -> b) -> Tree a -> b > fold f (Node a ts) = f a (map (fold f) ts) ----------------------------------------------------------------------
Spezialisierung von `fold':
---------------------------------------------------------------------- > sumup = fold (\a ns -> a + sum ns) > size = fold (\_ ns -> 1 + sum ns) > height = fold (\_ ns -> 1 + maximum ns) > inorder = fold (\a xs -> a : concat xs) ----------------------------------------------------------------------
Aufgabe 2. Bestimme die Typen der obigen Funktionen!
Zur Erinnerung: Das Motto von Lazy Evaluation lautet:
Berechne einen Ausdruck bzw. einen Teilausdruck nur, wenn es unbedingt nötig ist und dann auch nur einmal.
`Lazy evaluation' erlaubt einen sehr modularen Programmaufbau. Was wir damit meinen, läßt sich am besten anhand von Beispielen verdeutlichen ...
Beispiel: Wir programmieren eine Funktion, die eine Liste in Teillisten der Länge `n' unterteilt. Folgende Funktionen aus der Standardumgebung sind nützlich.
---------------------------------------------------------------------- > iterate :: (a -> a) -> a -> [a] > takeWhile :: (a -> Bool) -> [a] -> [a] ----------------------------------------------------------------------
Die Funktion `group :: Int -> [a] -> [[a]]' läßt sich als Komposition von drei Standardfunktionen definieren.
---------------------------------------------------------------------- > group n = iterate (drop n) > # takeWhile (/= []) > # map (take n) > > f # g = g . f ----------------------------------------------------------------------
Fazit: keine Scheu vor großen Zwischenlisten.
Beispiel: Realisierung des UNIX-Kommandos `cat'.
NAME
cat - concatenate files and print on the standard output
SYNOPSIS
cat [-benstv] [file...]
DESCRIPTION
This manual page documents the GNU version of cat. cat
writes the contents of each given file, or the standard
input if none are given or when a file named `-' is given,
to the standard output.
OPTIONS
-b Number all nonblank output lines, starting with 1.
-e Display a `$' after the end of each line.
-n Number all output lines, starting with 1.
-s Replace multiple adjacent blank lines with a single
blank line.
-t Display TAB characters as `^I'.
-v Display control characters except for LFD and TAB using
`^' notation and precede characters that have the high
bit set with `M-'.
Der Vollständigkeit halber das Hauptprogramm.
----------------------------------------------------------------------
> import Support
> import IOSupport
> import LibSystem
>
> main = getArgs >>= \args ->
> case args of
> ('-':opts):args' ->
> sequence [ copy opts f | f<-args' ]
> _ -> sequence [ copy "" f | f<-args ]
>
> type Options = [Char]
>
> copy :: Options -> FilePath -> IO ()
> copy opts f = readFile f >>= \cnts ->
> let str = process opts cnts in
> putStr str
----------------------------------------------------------------------
Für das `squeezen' von Leerzeilen führen wir einen neuen Datentyp ein, der es erlaubt zwischen normalen und Leerzeilen zu unterscheiden.
---------------------------------------------------------------------- > data Line = Blank String > | Line String > > classify :: String -> Line > classify s | all isSpace s = Blank s > | otherwise = Line s > > unclassify :: Line -> String > unclassify (Blank s) = s > unclassify (Line s) = s > > squeeze :: [Line] -> [Line] > squeeze [] = [] > squeeze (Blank _:x@(Blank _:_)) = squeeze x > squeeze (a:x) = a:squeeze x ----------------------------------------------------------------------
Die Numerierung von Zeilen bzw. von nicht-leeren Zeilen übernehmen die Funktionen `number' bzw. `bnumber'.
---------------------------------------------------------------------- > number :: Int -> [String] -> [String] > number n = zip [ n .. ] # map lineno > > bnumber :: Int -> [Line] -> [Line] > bnumber n [] = [] > bnumber n (Blank s:x) = Blank (indent s) :bnumber n x > bnumber n (Line s :x) = Line (lineno (n, s)):bnumber (n + 1) x > > indent :: String -> String > indent s = replicate 8 ' ' ++ s > > lineno :: (Int, String) -> String > lineno (n, s) = rjustify 6 (show n) ++ " " ++ s ----------------------------------------------------------------------
Die Hauptarbeit erledigt `process'.
---------------------------------------------------------------------- > process :: Options -> String -> String > process opts = lines > # map classify > # when 's' squeeze > # when 'b' (bnumber 1) > # map unclassify > # when 'n' (number 1) > # when 'e' (map (++ "$")) > # unlines > # when 't' (map showTab # concat) > # when 'v' (map showNonPrinting # concat) > where when c f = if c `elem` opts then f else id > > showTab :: Char -> String > showTab c | c == '\t' = "^I" > | otherwise = [c] ----------------------------------------------------------------------
Zu den zentralen Eigenschaften `rein' funktionaler Sprachen gehören:
Die Schnittstelle einer Funktion ist manifest.
Vor -und Nachteile:
Im Vergleich dazu haben Prozeduren imperativer Sprachen sowohl explizite als auch implizite Parameter (globale Variablen). Die oben genannten Vor- und Nachteile verkehren sich.
Betrachten wir das Problem der Erweiterbarkeit, mit dem funktionale Programmierer kämpfen, an einem Beispiel. Ausgangspunkt: gegeben ist ein einfacher Auswerter für arithmetische Ausdrücke (4 Zeilen). Dieser soll um folgende Funktionalitäten erweitert werden:
Repräsentation von arithmetischen Ausdrücken (im Prinzip: Binärbäume):
---------------------------------------------------------------------- > data Term = Con Integer > | Bin Term Op Term > deriving (Eq, Text) > > data Op = Add | Sub | Mul | Div > deriving (Eq, Text) ----------------------------------------------------------------------
Ein einfacher Auswerter für arithmetische Ausdrücke:
---------------------------------------------------------------------- > sys Add = (+); sys Sub = (-) > sys Mul = (*); sys Div = div > > eval :: Term -> Integer > eval (Con n) = n > eval (Bin t op u) = sys op (eval t) (eval u) ----------------------------------------------------------------------
Erweiterung 1: wir fügen eine Fehlerbehandlung (Division durch `0') hinzu.
---------------------------------------------------------------------- > data Exception a = Raise String > | Return a > > eval :: Term -> Exception Integer > eval (Con n) = Return n > eval (Bin t op u) = case eval t of > Raise s -> Raise s > Return v -> case eval u of > Raise s -> Raise s > Return w -> > if (op == Div && w == 0) then > Raise "div by zero" > else > Return (sys op v w) ----------------------------------------------------------------------
Beobachtung: der Auswerter ist nicht erweitert sondern umgeschrieben worden.
Erweiterung 2: wir zählen die durchgeführten Reduktionen (vielleicht um eine Tiefenschranke zu realisieren).
---------------------------------------------------------------------- > type Count a = Int -> (a, Int) > > eval :: Term -> Count Integer > eval (Con n) = \i -> (n, i) > eval (Bin t op u) = \i -> let (v, j) = eval t i in > let (w, k) = eval u j in > (sys op v w, k + 1) ----------------------------------------------------------------------
Beobachtung: der Auswerter ist nicht erweitert sondern umgeschrieben worden.
Erweiterung 3: wir protokollieren die durchgeführten Operationen.
----------------------------------------------------------------------
> type Trace a = (a, String)
>
> eval :: Term -> Trace Integer
> eval e@(Con n) = (n, trace e n)
> eval e@(Bin t op u) = let (v, x) = eval t in
> let (w, y) = eval u in
> let r = sys op v w in
> (r, x ++ y ++ trace e r)
>
> trace t n = "eval (" ++ show t ++ ") = "
> ++ show n ++ "\n"
----------------------------------------------------------------------
Beobachtung: der Auswerter ist nicht erweitert sondern umgeschrieben worden.
Erweiterung 4: die Reduktionen werden ausgegeben.
----------------------------------------------------------------------
> eval :: Term -> IO Integer
> eval e@(Con n) = putStr (trace e n) >>
> return n
> eval e@(Bin t op u) = eval t >>= \v ->
> eval u >>= \w ->
> let r = sys op v w in
> putStr (trace e r) >>
> return r
>
> trace t n = "eval (" ++ show t ++ ") = "
> ++ show n ++ "\n"
----------------------------------------------------------------------
Beobachtung: der Auswerter ist nicht erweitert sondern umgeschrieben worden.
Beobachtung: Es gibt jeweils zwei getrennte `Berechnungsebenen':
Die Ebenen haben einen unterschiedlichen Stellenwert: Die Berechnung im Vordergrund ist abhängig von der Anwendung, die Berechnung im Hintergrund ist weitgehend unabhängig davon.
Diese Trennung wird bei den EA-Aktionen deutlich: die Berechnung im Hintergrund (Kommunikation mit dem Betriebssystem) ist für den Programmierer nicht sichtbar. Er arbeitet nur mit `return', `(>>=)' und den primitiven EA-Aktionen `putChar' usw.
Was wir bisher verschwiegen haben: `IO' ist ein Beispiel für eine Monade `;-)'.
Eine Monade besteht aus
---------------------------------------------------------------------- > return :: a -> M a > (>>=) :: M a -> (a -> M b) -> M b ----------------------------------------------------------------------Die Operation `(>>)' ist abgeleitet:
---------------------------------------------------------------------- > (>>) :: M a -> M b -> M b > m >> n = m >>= \_ -> n ----------------------------------------------------------------------
Beachte: In Haskell 1.2 sind `return', `(>>=)' für die `IO'-Monade reserviert. Wir verwenden stattdessen `unit', `(&=)' und `(&)'.
Der einfache Auswerter in monadischer Notation:
---------------------------------------------------------------------- > type Id a = a > > eval :: Term -> Id Integer > eval (Con n) = unit n > eval (Bin t op u) = eval t &= \v -> > eval u &= \w -> > unit (sys op v w) > > unit :: a -> Id a > unit a = a > (&=) :: Id a -> (a -> Id b) -> Id b > m &= f = f m ----------------------------------------------------------------------
Die Identitätsmonade führt keine Berechnung im Hintergrund aus.
Erweiterung 1: wir fügen eine Fehlerbehandlung (Division durch `0') hinzu.
---------------------------------------------------------------------- > eval :: Term -> Exception Integer > eval (Con n) = unit n > eval (Bin t op u) = eval t &= \v -> > eval u &= \w -> > if (op == Div && w == 0) then > raise "div by zero" > else > unit (sys op v w) > > unit a = Return a > m &= f = case m of Raise s -> Raise s > Return v -> f v > raise :: String -> Exception a > raise s = Raise s ----------------------------------------------------------------------
Anmerkung: der Auswerter ist wirklich erweitert worden.
Erweiterung 2: wir zählen die durchgeführten Reduktionen (vielleicht um eine Tiefenschranke zu realisieren).
---------------------------------------------------------------------- > type Count a = Int -> (a, Int) > > eval :: Term -> Count Integer > eval (Con n) = unit n > eval (Bin t op u) = eval t &= \v -> > eval u &= \w -> > incr & > unit (sys op v w) > > unit a = \i -> (a, i) > m &= f = \i -> let (a, j) = m i in f a j > incr :: Count () > incr = \i -> ((), i + 1) ----------------------------------------------------------------------
Anmerkung: der Auswerter ist wirklich erweitert worden.
Erweiterung 3: wir protokollieren die durchgeführten Operationen.
---------------------------------------------------------------------- > eval :: Term -> Trace Integer > eval e@(Con n) = output (trace e n) & > unit n > eval e@(Bin t op u) = eval t &= \v -> > eval u &= \w -> > let r = sys op v w in > output (trace e r) & > unit r > > unit a = (a, "") > m &= f = let (a, x) = m in > let (b, y) = f a in > (b, x ++ y) > output :: String -> Trace () > output s = ((), s) ----------------------------------------------------------------------
Anmerkung: der Auswerter ist wirklich erweitert worden.
Also: Monaden erlauben es, `imperative Effekte' in einem rein funktionalen Programm zu erzielen. Ein `monadisches' Programm kann leicht durch Änderung der Monade erweitert werden.
Mathematiker: Damit `M', `return' und `(>>=)' im mathematischen Sinn eine Monade bilden, müssen folgende Eigenschaften erfüllt sein.
----------------------------------------------------------------------
return a >>= k = k a
m >>= return = m
m >>= (\a -> k a >>= h) = (m >>= k) >>= h
----------------------------------------------------------------------
Aufgabe 3. Definiere Monaden, die verschiedene imperative Effekte kombinieren: Ausgabe mit Fehlerbehandlung usw.
In Haskell 1.3 sind Monaden als Typklassen definiert.
---------------------------------------------------------------------- > class Monad m where > (>>=) :: m a -> (a -> m b) -> m b > (>>) :: m a -> m b -> m b > return :: a -> m a > > m >> k = m >>= \_ -> k ----------------------------------------------------------------------
Beispiel: `Exception' als Instanz der Typklasse `Monad'.
---------------------------------------------------------------------- > data Exception a = Raise String | Return a > > instance Monad Exception where > return a = Return a > m >>= f = case m of Raise s -> Raise s > Return v -> f v ----------------------------------------------------------------------
In Haskell 1.3 kann alternativ zu den überladenen Operationen `return' und `(>>=)' die sogenannte `do'-Syntax verwendet werden.
----------------------------------------------------------------------
> eval :: Term -> Exception Integer
> eval (Con n) = return n
> eval (Bin t op u) = do {v <- eval t;
> w <- eval u;
> if (op == Div && w == 0) then
> raise "div by zero"
> else
> return (sys op v w)}
----------------------------------------------------------------------
Aufgabe 4. Welcher Zusammenhang besteht zwischen Listenbeschreibungen und der `do'-Syntax?
Go to the first, previous, next, last section, table of contents.