--- a/exercises/src/Exercise_12.hs	Wed Jan 16 19:21:23 2013 +0100
+++ b/exercises/src/Exercise_12.hs	Sat Jan 19 18:33:53 2013 +0100
@@ -7,21 +7,35 @@
 {-
 
 Ausdruck: 1 + (2 * 3)
+(2 * 3)                         Innermost
+1 + (2 * 3)                     Outermost
 
 
 Ausdruck: (1 + 2) * (2 + 3)
+(1 + 2)                         Innermost
+(2 + 3)                         Innermost
+(1 + 2) * (2 + 3)               Outermost
 
 
 Ausdruck: fst (1 + 2, 2 + 3)
+(1 + 2)                         Innermost
+(2 + 3)                         Innermost
+fst (1 + 2, 2 + 3)              Outermost
 
 
 Ausdruck: fst (snd (1, 2 + 3), 4)
+(2 + 3)                         Innermost
+snd (1, 2 + 3)
+fst (snd (1, 2 + 3), 4)         Outermost
 
 
-Ausdruck: (\x. 1 + x) (2 * 3)
+Ausdruck: (\x -> 1 + x) (2 * 3)
+(2 * 3)                         Innermost
+(\x -> 1 + x) (2 * 3)           Outermost
+
+-}
 
 
--}
 
 {---------------------------------------------------------------------}
 {- Aufgabe G12.2 -}
@@ -34,25 +48,147 @@
 f (x1:x2:xs) ys (z:zs) = x1
 
 a = f (inf (1+0)) (inf (1+1)) (inf (1+2))
+{-
+f (inf (1+0)) (inf (1+1)) (inf (1+2))
+-> f ((1+0) : inf (1+0)) ((1+1) : inf (1+1)) (inf (1+2))
+-> f (1 : inf 1) (2 : inf 2) (inf (1+2))
+-> f (1 : 1 : inf 1) (2 : inf 2) ((1+2) : inf (1+2))
+-> 1
+-}
+
 b = f (inf (1+2)) (inf (1+1)) (inf (1+0))
+{-
+f (inf (1+2)) (inf (1+1)) (inf (1+0))
+-> f ((1+2) : inf (1+2)) ((1+1) : inf (1+1)) (inf (1+0))
+-> f (3 : inf 3) (2 : inf 2) (inf (1+0))
+-> 2
+-}
+
 c = f (inf (1+0)) [] (inf (1+1))
+{-
+f (inf (1+0)) [] (inf (1+1))
+-> f ((1+0) : inf (1+0)) [] (inf (1+1))
+-> f ((1+0) : (1+0) : inf (1+0)) [] ((1+1) : inf (1+1))
+-> (1+0)
+-> 1
+-}
+
+{- Musterlösung -}
+{- Aufruf:
+ -    f (inf (1+0)) (inf (1+1)) (inf (1+2))
+ - Argumente
+ -   inf (1+0) ~~> 1 : 1: inf 1
+ -   inf (1+1) ~~> 2 : inf 2
+ -   inf (1+2) ~~> (1+2) : inf (1+2)
+ - Warum?
+ -  Zur Auswertung von f wird zunächst Pattern Matching gemacht gegen die erste
+ -  Regel gemacht. Haskell muss also feststellen, ob das erste und zweite
+ -  Argument die Form _:_ (statt []) hat. Das dritte Argument ist nur eine
+ -  Variable, hier muss also noch nichts ausgewertet werden.
+ -    inf (1+0) ~> (1+0) : inf (1+0)
+ -    inf (1+1) ~> (1+1) : inf (1+1)
+ -    inf (1+2) ~> inf(1+2)
+ -  Jetzt wird (unter anderem) x = 1+0 und y = 1+1 gebunden.
+ -  In einem zweiten Schritt muss "x > y" getestet werden, dazu müssen x und y
+ -  ausgewertet werden:
+ -    (1+0) : inf (1+0) ~> 1 : inf 1
+ -    (1+1) : inf (1+1) ~> 2 : inf 2
+ -    inf (1+2) ~> inf(1+2)
+ -  Warum wurden jetzt beide 1+0 zu 1 (bzw. beide 1+1 zu 2 ausgewertet)? Weil es
+ -  jeweils der selbe (nicht nur der gleiche Ausdruck war).
+ -
+ -  "x > y" ist False, deswegen muss jetzt noch die zweite Regel getestet werden.
+ -  Dafür ist es notwendig, das erste Argument zu der Form _:_:_ und das dritte
+ -  Argument zu der Form _:_ auszuwerten:
+ -    1 : inf 1 ~> 1 : 1 : inf 1
+ -    2 : inf 2 ~> 2 : inf 2
+ -    inf (1+2) ~> (1+2) : inf (1+2)
+ -  Der Rückgabewert ist jetzt 1, was schon vollständig ausgewertet ist und daher
+ -  für die Anzeige nicht weiter ausgewertet werden muss.
+ -}
+
+{- Aufruf:
+ -   f (inf(1+2)) (inf(1+1)) (inf(1+0))
+ - Argumente:
+ -   inf (1+2) ~> 3 : inf 3
+ -   inf (1+2) ~> 2 : inf 2
+ -   inf (1+0) ~> inf (1+0)
+ - Ähnlich wie oben, nur schlägt hier der Test "x > y" nicht fehl, daher wird das
+ - dritte Argument nie ausgewertet.
+ -}
+
+{- Aufruf
+ -   f (inf (1+0)) [] (inf 0)
+ - Argumente:
+ -   inf (1+0) ~> 1 : inf 1
+ -   inf 0 ~> 0 : inf 0
+ - Hier wird der Test "x > y" nie erreicht (denn das zweite Argument hat die Form []).
+ - 1+0 wird dennoch zu 1 ausgewertet, da es der Rückgabewert der Funktion ist und daher
+ - ausgewertet werden muss, um angezeigt zu werden.
+ -}
+
 
 
 {---------------------------------------------------------------------}
 {- Aufgabe G12.3 -}
 
+-- Beispiel: Zweierpotenzen
+-- powersOfTwo == [1,2,4,8,16,...]
+powersOfTwo :: [Integer]
+powersOfTwo = 1 : map (*2) powersOfTwo
+
+-- powerSeriers == [x^y, x^(y+1), x^(y+2), x^(y+3),...]
+powerSeries :: Integer -> Integer -> [Integer]
+powerSeries x y = x^y : powerSeries x (y+1)
+
+{-
+powersOfTwo
+-> 1 : map (*2) powersOfTwo
+-> 1 : map (*2) (1 : map (*2) powersOfTwo)
+-> 1 : 2 : map (*2) (map (*2) powersOfTwo)
+-> 1 : 2 : map (*2) (map (*2) (1 : map ...))
+-> 1 : 2 : map (*2) (2 : (map (*2) (map ...)))
+-> 1 : 2 : 4 : map ...
+-}
+
+
+-- Aufgabe
 fib :: Integer -> Integer
 fib 0 = 0
 fib 1 = 1
 fib n = fib (n - 1) + fib (n - 2)
 
+fib1 :: [Integer]
+fib1 = 0 : 1 : zipWith (+) fib1 (tail fib1)
 
-fib1 :: [Integer]
-fib1 = undefined
+fib2 :: Integer -> Integer -> [Integer]
+fib2 x y = x : fib2 y (x+y)
+
+
+{-
+fib1
+-> 0 : 1 : zipWith (+) fib1 (tail fib1)
+-> 0 : 1 : zipWith (+) (0 : 1 : zipWith ...) (1 : zipWith ...)
+-> 0 : 1 : 1 : zipWith (+) (1 : 1 : zipWith ...) (1 : zipWith ...)
+-> 0 : 1 : 1 : 2 : zipWith (+) (1 : 2 : zipWith ...) (2 : zipWith ...)
+-> 0 : 1 : 1 : 2 : 3 : zipWith (+) (2 : 3 : zipWith ...) (3 : zipWith ...)
 
 
-fib2 :: Integer -> Integer -> [Integer]
-fib2 x y = undefined
+fib2 0 1
+-> 0 : fib2 1 (0+1)
+-> 0 : 1 : fib2 (0+1) (1+(0+1))
+-> 0 : 1 : (0+1) : fib2 (1+(0+1)) ((0+1)+((0+1)+1))
+-> 0 : 1 : 1 : fib2 (1+1) (1+(1+1))
+-> 0 : 1 : 1 : (1+1) : fib2 (1+(1+1)) ((1+1)+((1+1)+1))
+-> 0 : 1 : 1 : 2 : fib2 (1+2) (2+(2+1))
+-}
+
+
+{- Um fib n auszuwerten, muss fib (n-1) 2-mal, fib (n - 2) 4-mal, fib (n-3)
+ - 8-mal, ... ausgewertet werden. Zur Auswertung von fib1 !! n müssen nur die
+ - ersten (n+1) Elemente von fib1 jeweils 1-mal ausgewertet werden.
+ - Die Laufzeit ist also linear statt exponentiell.
+ -}
 
 
 
@@ -60,7 +196,27 @@
 {- Aufgabe G12.4 -}
 
 hamming :: [Integer]
-hamming = undefined
+hamming = 1 : sort z (sort x y)
+        where
+        x = map (*2) hamming
+        y = map (*3) hamming
+        z = map (*5) hamming
+
+        sort (x:xs) (y:ys)
+                | x < y = x : sort xs (y:ys)
+                | x > y = y : sort (x:xs) ys
+                | x == y = x : sort xs ys
+
+
+productOf :: [Integer] -> Integer -> Bool
+productOf xs y = go xs y
+  where
+    go _ 1 = True
+    go [] y = False
+    go (z:zs) y = if y `mod` z == 0 then go xs (y `div` z) else go zs y
+
+hamming' :: [Integer]
+hamming' = filter (productOf [2,3,5]) [1 ..]