Funktionale Programmierung: Haskell Charakteristika

Bestandteile	eines Haskell-Programms
	Definitionen von Konstanten und Funktionen
Beispiel	Quicksort
	qsort :: [a] -> [a] qsort [] = [] qsort (x : xs) = qsort lessX ++ [x] ++ qsort greaterX where lessX = [ y \| y <- xs, y < x ] greaterX = [ y \| y <- xs, y >= x ]

Definition	Jeder Bezeichner steht an jedem angewandten Vorkommen für den gleichen Wert.
Konsequenzen
	Keine Zuweisungen, keine Schleifen
	Programme können wie mathematische Formeln manipuliert weden
	Gleiches kann überall durch gleiches ersetzt werden
	Math. Gesetze können zum Argumentieren, zum Optimieren, zur Wiederverwendung und zum automatischen Testen genutzt werden.
Beispiel	Konkatenation auf Listen
	xs ++ [] = xs [] ++ ys = ys (xs ++ ys) ++ zs = xs ++ (ys ++ zs)
	Keine Zeiger, referenzielle Transparenz
	Funktionen mit I/O müssen anders behandelt werden als reine Funktionen
I/O	getChar: Funktion ohne Parameter?
	getChar :: Char let c1 = getChar in let c2 = getChar in c1 == c2 <==> getChar == getChar <==> True
Lösung	Monaden
Idee	Der Rest der Welt wird als eine Variable aufgefasst. Diese wird bei I/O-behafteten Berechnungen durch die Funktionen durchgefädelt
Ansatz
	data World = ... -- abstrakt type IO a = World -> (a, World) getChar :: IO Char getChar :: World -> (Char, World)
do-Notation	für I/O-behaftete Berechnungen
	get2chars :: IO (Char, Char) get2chars = do c1 <- getChar c2 <- getChar return (c1, c2)
2.Beispiel	getLine
	getLine :: IO String -- = [Char] getLine = do c <- getChar if c == '\n' then return "" else do l <- getLine return (c : l)
main	Transformation des Weltzustands
	main :: IO () -- also main :: World -> ((), World) -- also main :: World -> World

Typen	von Ausdrücken werden vollständig zur Übersetzungszeit ausgewertet
Konsequenzen
	Keine cast-exceptions
	Es wird statisch bewiesen, dass gewisse Fehlerklassen nicht vorhanden sind
	Dynamisches Binden muss explizit gemacht werden
Ausdrucksstarkes Typsystem
Parametrische Polymorphie	Generics
Beispiel	length
	length :: [a] -> Int length [1,2,3] length ['a','b','c'] length "abc" length [(+),(-),(*)]
ad-hoc-Polymorphie	Typklassen
Beispiel	Gleichheitstest (vordefinierte Klasse)
	class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool x /= y = ! (x == y) instance Eq a => Eq [a] where [] == [] = True [] == _ = False _ == [] = False (x:xs) == (y:ys) = x == y && xs == ys
	Typklassen über Typkonstruktoren: Funktor, Monade, Arrow, ...
Konsequenzen
	Viele Eigenschaften können mit dem Typsystem beschrieben werden und deren Einhaltung so statisch garantiert werden

Definition	Ein Ausdruck wird erst dann ausgewertet, wenn sein Wert benötigt wird.
?	call by name
?	call by need (lazy evaluation)
Beispiel	infinity
	infinity :: Integer infinity = 1 + infinity mult x y \| x == 0 = 0 \| otherwise = x * y z = mult 0 infinity o = mult 1 infinity ones :: [Int] ones = 1 : ones l = length ones l100 = take 100 ones
Nutzen?
	Allgemeiner als call by value
	Unendliche Strukturen (Listen, Bäume, Datenströme, ...)
	l :: [Int] l = [0,1,2,3,...]
	Modularität, Wiederverwendung (Trainingslager Listen)
Gefahr?
	Performanz, Speicherlecks

Funktionen	sind first class citizens
	Parameter
	Funktionsresultat
	Komponente in strukturierten Daten
Beispiel	Funktionen als Implementierung für Container
	type Set a = a -> Bool emptySet :: Set a emptySet = \ e -> False emptySet' :: Set a emptySet' = const False isIn :: a -> Set a -> Bool isIn x s = s x insert :: Eq a => a -> Set a -> Set a insert x s = \ e -> e == x \|\| s e insert' :: Eq a => a -> Set a -> Set a insert' x s = let s' e = e == x \|\| s e in s' remove :: Eq a => a -> Set a -> Set a remove x s = \ e -> e /= x && s e s1 :: Set Int s1 = insert 3 $ insert 1 $ insert 42 $ emptySet

Kombinatoren	Operatoren zur Verknüpfung von Funktionen
Extensionalitätzprinzip	zwei Funktionen sind gleich, wenn sie für alle Argumente das gleiche Resultat liefern
Komposition	von Funktionen
	(.) :: (b -> c) -> (a -> b) -> (a -> c) g . f = \ x -> g (f x)
Beispiel
	h :: a -> c h x = g (f x) h x = (g . f) x h = g . f
Identität	vordefiniert
	id :: a -> a id x = x f . id = f id . f = f f . (g . h) = (f . g) .h
konstante Funktion	vordefiniert
	const :: a -> b -> a const x y = x
Vertauschen der Parameter	vordefiniert
	flip :: (a -> b -> c) -> (b -> a -> c) flip f = \ x y -> f y x
Funktionsanwendung	vordefiniert
	($) :: (a -> b) -> a -> b f $ x = f x
	Weitere Kombinatoren werden folgen

Definition	Alle Funktionen werden auf einstellige Funktionen zurückgeführt
Beispiel
	add :: Int -> Int -> Int add x y = x + y add x = \ y -> x + y add = \ x -> (\ y -> x + y) five :: Int five = add 2 3 incr :: Int -> Int incr = add 1 decr = add (-1) decr' = flip (-) 1
Kombinatoren	für Currying
	uncurry :: (a -> b -> c) -> ((a, b) -> c) uncurry f = \ (x, y) -> f x y curry :: ((a, b) -> c) -> (a -> b -> c) curry f = \ x y -> f (x, y) -- Gesetze curry . uncurry = id uncurry . curry = id
Nutzen
	Parameter können zu unterschiedlichen Zeitpunkten übergeben werden
	Kombinierbarkeit der Funktionen wird verbessert

Selbstdefinierte Datentypen	auch generisch
Listen	von Zahlen
	data IntList = Nil \| Cons Int IntList
Listen	generisch, vordefiniert mit eigener Listensyntax
	data List a = Nil \| Cons a (List a)
Bäume	zweistellig, mit Information an den inneren Knoten
	data Tree1 a = Empty \| Node a (Tree1 a) (Tree1 a)
Bäume	zweistellig, mit Information an den Blättern
	data Tree2 a = Leaf a \| Fork (Tree2 a) (Tree2 a)
Bäume	zweistellig, mit Information an den inneren Knoten und den Blättern
	data Tree3 a b = Leaf a \| Fork b (Tree3 a b) (Tree3 a b)
Option	vordefiniert
	data Maybe a = Nothing \| Just a
Summe	vordefiniert
	data Either a b = Left a \| Right b
Produkt	in Tupelschreibweise vordefiniert
	data Pair a b = Pair a b

Listen	als Ersatz für Schleifen
1. Aufgabe	Suche nach einem Wort in einem Text
	import Prelude hiding ( any ) -- ------------------------------ isSubstringOf x y = any (isPrefixOf x) (tails y) -- ------------------------------ tails :: [a] -> [[a]] tails [] = [[]] tails xs@(_:xs') = xs : tails xs' -- ------------------------------ isPrefixOf :: (Eq t) => [t] -> [t] -> Bool isPrefixOf [] _ = True isPrefixOf _ [] = False isPrefixOf (x:xs) (y:ys) \| x == y = isPrefixOf xs ys \| otherwise = False -- ------------------------------ any :: (a -> Bool) -> [a] -> Bool any f [] = False any f (x:xs) = f x \|\| any f xs -- ------------------------------ test1 = "aba" `isSubstringOf` "123ababac" test2 = "aba" `isSubstringOf` "abcabc"
2. Aufgabe	Verallgemeinerung: Position des ersten, des letzten, aller Vorkommen
	import Prelude hiding ( map, filter , zip, zipWith ) import Data.List ( tails , isPrefixOf ) import Data.Maybe ( listToMaybe ) -- ------------------------------ allOcc :: Eq a => [a] -> [a] -> [Int] firstOcc :: Eq a => [a] -> [a] -> Maybe Int lastOcc :: Eq a => [a] -> [a] -> Maybe Int isSubstringOf :: Eq a => [a] -> [a] -> Bool allOcc x = map fst . filter (isPrefixOf x . snd) . zip [0..] . tails firstOcc x = listToMaybe . allOcc x lastOcc x = listToMaybe . reverse . allOcc x isSubstringOf x = not . null . allOcc x -- ------------------------------ map :: (a -> b) -> ([a] -> [b]) map f [] = [] map f (x:xs) = f x : map f xs -- ------------------------------ filter :: (a -> Bool) -> [a] -> [a] filter p [] = [] filter p (x:xs) \| p x = x : filter p xs \| otherwise = filter p xs -- ------------------------------ zip :: [a] -> [b] -> [(a, b)] zip [] _ = [] zip _ [] = [] zip (x:xs) (y:ys) = (x,y) : zip xs ys zipWith :: (a -> b -> c) -> ([a] -> [b] -> [c]) zipWith op [] _ = [] zipWith op _ [] = [] zipWith op (x:xs) (y:ys) = op x y : zipWith op xs ys -- ------------------------------ test1 = allOcc "aba" "123ababac" test2 = firstOcc "aba" "123ababac" test3 = lastOcc "aba" "123ababac" test4 = "aba" `isSubstringOf` "123ababac" test5 = firstOcc "abc" "123ababac"
3. Aufgabe	Besucher für Listen: foldr und foldl
	import Prelude hiding ( map, filter , zip, zipWith , foldr, foldl , reverse , sum , and, or ) import Data.Char ( ord ) -- ------------------------------ foldr :: (a -> b -> b) -> b -> [a] -> b foldr op n [] = n foldr op n (x:xs) = x `op` foldr op n xs foldl :: (b -> a -> b) -> b -> [a] -> b foldl op n [] = n foldl op n (x:xs) = foldl op (n `op` x) xs -- ------------------------------ sum :: Num a => [a] -> a sum' :: Num a => [a] -> a prod :: Num a => [a] -> a prod' :: Num a => [a] -> a and = foldr (&&) True or = foldr (\|\|) False sum' = foldr (+) 0 prod' = foldr () 1 reverse' = foldr (\ x xs -> xs ++ [x]) [] sum = foldl (+) 0 prod = foldl () 1 reverse = foldl (\ xs x -> x : xs) [] hash = foldl (\ x c -> 31 * x + ord c) 0 fac n = prod [1..n]

Binäre Suchbäume
1. Aufgabe	Binärer Suchbaum: Einfügen, Suchen, map und fold
	data Tree a = Empty \| Node a (Tree a) (Tree a) deriving (Show) emptyTree :: Tree a emptyTree = Empty isIn :: Ord a => a -> Tree a -> Bool isIn x Empty = False isIn x (Node e l r) \| x == e = True \| x < e = isIn x l \| x > e = isIn x r insert :: Ord a => a -> Tree a -> Tree a insert x Empty = Node x Empty Empty insert x n@(Node e l r) \| x == e = n \| x < e = Node e (insert x l) r \| x > e = Node e l (insert x r) t1 = insert 7 $ insert 42 $ insert 23 $ Empty -- ------------------------------ -- Besucher mapTree :: (a -> b) -> Tree a -> Tree b mapTree f Empty = Empty mapTree f (Node e l r) = Node (f e) (mapTree f l) (mapTree f r) t2 = mapTree (\ x -> x*x) t1 -- ------------------------------ foldTree :: (a -> b -> b -> b) -> b -> Tree a -> b foldTree op n Empty = n foldTree op n (Node x l r) = op x fl fr where fl = foldTree op n l fr = foldTree op n r sizeTree :: Tree a -> Int sizeTree = foldTree op n where n = 0 op x fl fr = 1 + fl + fr sumTree :: Num a => Tree a -> a sumTree = foldTree (\ x y z -> x + y + z) 0 -- ------------------------------

Haskell Charakteristika

Syntax

Rein funktional

Statische Typisierung

Bedarfsauswertung

Funktionen als Daten

Punktfreier Programmierstil

Currying

Algebraische Datentypen

Trainingslager: Listen und Paare

Trainingslager: Bäume