Alp Vorl 5.2.07
Verzögerte Auswertung (Lazy Evaluation)
---------------------------------------
square x = x * x
> square (3+4) = (3+4) * (3+4) = 7 * (3+4) = 7*7 = 49 -- leftmost-outermost
> square (3+4) = square 7 = 7 * 7 = 49 -- leftmost-innermost
Church Rosser Theorem: Die Reihenfolge der Auswertung hat keine Auswirkung auf
das Ergebnis, ausser das gegebenfalls eine Auswertung nicht zum Ergebnis führt
Wenn leftmostinnermost zum Ergebnis führt, ist dies i.a. schneller
Normalisierungsrek. Wenn ein Ausdruck A ein Ergebnis hat, dann lässt sich dies durch
leftmostoutermost - Strategie gewinnen
Bsp: one x = 1
y = y -- wenn man reduziert leftmostoutermost, one y und nehmen definition von one
l.o.: one y = 1 -- wird y nicht ausgerechnet, und ergebnis ist 1
l.i.: one y = one y = ... -- leftmostinnermost zwingt das system erst das argument auszurechnen,
-- wird durch rechte seite errechnet, so eine endlose berechnung,
-- zwischenergebnisse sind nicht falsch
Gesucht: Sichere Strategie, die keine unnötigen Reduktionen macht!
Idee: Stelle Ausdrücke nicht durch Bäume sondern Graphen dar
-- (3+4) * (3+4) =
* @ @
/ \ / \ => / \
\ / square x @ |
+ / \ /
/ \ * x
3 4
Definierende Gleichungen werden durch Graphtransformationen ersetzt.
Lazy Evaluation verwendet die lo-Strategie über Graphen, dadurch ist sie sicher.
Wenn ein Argument ausgewertet werden muss, dann ein für alle mal
Bsp: f :: [Int] -> Int
f [] = 0
f (x:xs) = 1
nats = [1..] -- natürliche zahlen, > take n nats
ones = 1:ones
l.i. > f nats
l.i. > f ones = f (1:ones) = f (1:(1:ones)) = ..
lazy > f ones = 1
-- dadurch unendliche listen sinnvoll verwendbar
-- mit l.i. niemals unendliche dynamische datenstrukturen verwenden, terminiert nicht
-- mit l.o., lazyevaluation macht es mehr sinn
Erzeuge Primzahlen:
Eine Zahl p ist primzahl, g.d.w p nur durch 1 + sich selbst teilbar ist
teilbar :: Int -> Int -> Bool
p `teilbar` z = p `mod` z => 0
prim :: Int -> Bool
prim p = not ( or [p `teilbar` z | z <- [2..p-1]])
primes :: [Int]
primes = [p | p <- [2..], prim p]
Sieb des Erastothemes:
2,3,4,5,6,7,8,9,10,11,12,13,...
-- alle vielfachen der ersten gefunden wegwerfen
-- von nächster zahl alle vielfachen weg usw
primes :: [Int]
primes = sieve [2..]
sieve (p:xs) = p:sieve [x|x<-xs, x `mod` p /= 0 ]
> primes = sieve [2..] = 2:sieve [x|x<-[3..], x `mod` 2 /=0 ]
-- lazy evaulation führt dazu das sieve wieder reduziert wird
= 2:sieve (3: [x|x<-[4..], x `mod` 2 /= 0])= 2:3:sieve([y|y<-xs, y `mod` 3 /= 0])