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])