Typische Struktur
|
für einfache Listenfunktionen
|
|
f :: [a] -> b
f [] = e
f (x : xs) = x `op` f xs
|
|---|
|
|
Beispiele
|
sum :: Num a => [a] -> a
sum [] = 0
sum (x : xs) = x + sum xs
|
|
length :: [a] -> Int
length [] = 0
length (x : xs) = 1 + length xs
|
|---|
|
concat :: [[a]] -> [a]
concat [] = []
concat (xs : xss) = xs ++ concat xss
|
|---|
|
and :: [Bool] -> Bool
and [] = True
and (x : xs) = x && and xs
|
|---|
|
fast
|
|---|
|
reverse :: [a] -> [a]
reverse [] = []
reverse (x : xs) = reverse xs ++ [x]
|
|---|
?
|
Transformation in obiges Schema?
|
|
|
Verarbeitung
|
|
|
wird transformiert in
|
|---|
|
x1 `op` (x2 `op` (x3 `op` e))
|
|---|
|
|
?
|
Weitere Beispiele?
|
Abstraktion
|
von der Operation
|
|
Trennung von Kontrollstruktur und Verarbeitung
|
|---|
|
|
Definition: foldr
|
fold right
|
|
`op` bezeichnet eine rechtsassoziative Operation
|
|---|
|
foldr :: (a -> b -> b) -> b ->
[a] -> b
foldr op e [] = e
foldr op e (x : xs) = x `op` (foldr op e xs)
|
|---|
|
|
?
|
Rekursionstyp?
|
|
|
Beispiele
|
sum = foldr (+) 0
concat = foldr (++) []
and = foldr (&&) True
length = foldr oneplus 0
where
oneplus x n = 1 + n
length = foldr (\ x -> (1+)) 0
length = foldr (const (1+)) 0
|
|
|
?
|
length mit sum?
|
|
|
?
|
reverse mit foldr?
|
|
|
?
|
Laufzeit von reverse mit foldr?
|
|
|
?
|
Identität für Listen mit foldr?
|
|
|
?
|
map mit foldr?
|
|
|
|
filter mit map implementiert.
|
|
map mit foldr implementiert.
|
|
Aber: Direkte Implementierung von map kann effizienter sein als foldr.
|
? |
linksassoziative Operationen mit fold?
|
|
|
Beispiel
|
Horner-Schema
|
|
decimal [x0, x1, x2]
=
((0 * 10 + x0) * 10 + x1) * 10 + x2
=
((0 `op` x0) `op` x1) `op` x2
where
n `op` x = n * 10 + x
|
|---|
|
|
foldl
|
fold left
|
|
foldl op e [x0, x1, ..., xn]
=
(...((e `op` x0) `op` x1) ...) `op` xn
|
|---|
|
|
Definition
|
foldl :: (b -> a -> b) -> b ->
[a] -> b
foldl op e [] = e
foldl op e (x : xs) = foldl op (e `op` x) xs
|
|
|
?
|
Rekursionstyp?
|
|
|
Beispiel
|
reverse = foldl snoc []
where
snoc xs x = x : xs
reverse = foldl (flip (:)) []
|
|
|
?
|
Laufzeit von reverse mit foldl?
|
|
|
?
|
concat mit foldl?
|
|
|
?
|
Laufzeit von concat mit foldl?
|
|
|
? |
Maximum und Minimum über Listen mit fold?
|
|
|
Problem
|
Wert der leeren Liste?
|
|
|
Lösung
|
Varianten von fold für nicht leere Listen
|
|
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 op (x : xs)
| null xs = x
| otherwise = x `op` foldr1 op xs
|
|---|
|
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 op (x : xs)
= foldl op x xs
|
|---|
|
|
|
Das letzte (foldr) oder das erste Element (foldl) wird für
das fehlende e verwendet.
|
|
|
Beispiele
|
minimum :: Ord a => [a] -> a
minimum = foldl1 min
maximum :: Ord a => [a] -> a
maximum = foldl1 max
|
|
|
scanl
|
Verarbeiten aller Anfangsstücke einer Liste
|
|
scanl op e [x0, x1, x2, ...]
=
[ e
, e `op` x0
, (e `op` x0) `op` x1
, ((e `op` x0) `op` x1) `op` x2
, ...
]
|
|---|
|
|
Beispiel
|
die zu einer Zahlenfolge gehörige Reihe
|
|
scanl (+) 0
scanl (+) 0 (repeat 1) = ???
scanl (+) 0 [1..] = ???
|
|---|
|
|
Definition
|
scanl :: (a -> b -> b) -> b ->
[a] -> [b]
scanl op e [] = []
scanl op e (x : xs) = e : scanl op (e `op` x) xs
|
|
|
?
|
scanl mit fold?
|
Gesetze
|
für fold Funktionen
|
1. Dualitätsgesetz
|
für assoziative Operationen `op` mit e als neutralem Element und endlichen Listen xs gilt
|
|
foldr op e xs = foldl op e xs
|
|---|
|
|
Beispiele
|
sum = foldl (+) 0
and = foldl (&&) True
or = foldl (||) False
concat = foldl (++) []
|
|
|
2. Dualitätsgesetz
|
Wenn op1, op2 die folgenden Bedingungen erfüllen, dann gilt für endliche Listen xs:
|
|
x `op1` (y `op2` z) = (x `op1` y) `op2` z
x `op1` e = e `op2` x
foldr op1 e xs = foldl op2 e xs
|
|---|
|
|
|
Das erste Gesetz ist Spezialfall des zweiten.
|
|
|
?
|
Beweis?
|
|
|
?
|
foldl und foldr auf unendlichen Listen?
|
Funktionale Programmierung: Fold-Funktionen
