Literatur
|
LYAH:
Only folds and horses
|
| |
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?
|
|
reverse [] = []
reverse (x : xs) = (flip (++)) [x] (reverse xs)
|
| |
Verarbeitung
|
|
|
wird transformiert in
|
|---|
|
x1 `op` (x2 `op` (x3 `op` e))
|
|---|
| |
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?
|
|
Lineare Rekursion
|
| |
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?
|
|
length = sum . map (const 1)
|
| |
?
|
reverse mit foldr?
|
|
reverse = foldr snoc []
where
snoc x xs = xs ++ [x]
reverse = foldr (\ x -> (++ [x])) []
reverse = foldr (flip (++) . (:[])) []
|
| |
?
|
Laufzeit von reverse mit foldr?
|
|
O(n2)
|
| |
?
|
Identität für Listen mit foldr?
|
|
id' :: [a] -> [a]
id' = foldr (:) []
|
| |
?
|
map mit foldr?
|
|
map f = foldr ((:) . f) []
|
| |
|
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?
|
|
Endrekursion
|
| |
Beispiel
|
reverse = foldl snoc []
where
snoc xs x = x : xs
reverse = foldl (flip (:)) []
|
| |
?
|
Laufzeit von reverse mit foldl?
|
|
O(n)
reverse [1, 2, 3]
=
(([] `snoc` 1) `snoc` 2) `snoc` 3
where
snoc xs x = x : xs
=
([1] `snoc` 2) `snoc` 3
=
[2, 1] `snoc` 3
=
[3, 2, 1]
|
| |
?
|
concat mit foldl?
|
|
|
| |
?
|
Laufzeit von concat mit foldl?
|
|
O(n2)
concat [l1, l2, l3]
=
(([] ++ l1) ++ l2) ++ l3
|
| |
? |
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?
|
|
etwas ineffizient
scanl op e = map (foldl op e) . inits
inits :: [a] -> [[a]]
inits [] = []
inits (x : xs) = [] : map (x:) (inits xs)
inits = foldr op [[]]
where
x `op` xss = [] : map (x:) xss
|
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?
|
|
Induktionsanfang
| |
foldr (:) [] []
|
| = | { Def. foldr für [] } |
| |
[]
|
Induktionsschritt
| |
foldr (:) [] (x:xs)
|
| = | { Def. foldr für (x:xs) } |
| |
x : foldr (:) [] xs
|
| = | { Induktionsbehauptung } |
| |
x : xs
|
|
| |
?
|
foldl und foldr auf unendlichen Listen?
|
|
foldr (+) 0 [0..] = undefined
foldl (+) 0 [0..] = undefined
foldr (&&) True (repeat False) = False
foldl (&&) True (repeat False) = undefined
|
Funktionale Programmierung: Fold-Funktionen
