# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1352462497 -3600
# Node ID f4d71c6df64cd748c10f03d1b1221e3b6c9f990c
# Parent  8689a0a4b38ec0008a50285e4d23d8a7eb7a10fd
week 4 tutorial

diff -r 8689a0a4b38e -r f4d71c6df64c exercises/src/Exercise_4.hs
--- a/exercises/src/Exercise_4.hs	Wed Nov 07 22:17:33 2012 +0100
+++ b/exercises/src/Exercise_4.hs	Fri Nov 09 13:01:37 2012 +0100
@@ -5,39 +5,95 @@
 {---------------------------------------------------------------------}
 {- Aufgabe G4.1 -}
 
+{- allEqual ist nicht Teil des Übungsblattes, nur ein Beispiel. -}
+allEqual :: [Integer] -> Bool
+--allEqual [] = True
+--allEqual [x] = True
+allEqual (x : y : ys) = x == y && allEqual (y : ys)
+allEqual _ = True
+
+
 hasFibonacciProperty :: [Integer] -> Bool
-hasFibonacciProperty xs = undefined
+hasFibonacciProperty (x : y : z : zs) = z == x + y && hasFibonacciProperty (y : z : zs)
+hasFibonacciProperty _ = True
 
 
 
 {---------------------------------------------------------------------}
 {- Aufgabe G4.2 -}
+
+-- Beispielschlüssel vom Blatt
 key = [('a','x'),('H','e'),('l','P'),('o','M')]
 
 cryptChar :: [(Char,Char)] -> Char -> Char
 cryptChar [] c = '_'
-cryptChar ((k,v) : ks) c = undefined
+cryptChar ((k,v) : ks) c = if c == k then v else cryptChar ks c
 
 
 crypt :: [(Char,Char)] -> [Char] -> [Char]
-crypt key [] = []
-crypt key (x : xs) = undefined
+crypt key xs = [cryptChar key x | x <- xs]
+
+--Alternativ:
+crypt' key [] = []
+crypt' key (x : xs) = cryptChar key x : crypt' key xs 
 
 
 isKeyReversible :: [(Char,Char)] -> Bool
 isKeyReversible [] = True
-isKeyReversible ((k,v) : ks) = undefined
+isKeyReversible ((k,v) : ks) = null [1 | (k', v') <- ks, v' == v] && isKeyReversible ks
+
+--Alternativ (wird in den QuickCheck Tests verwendet):
+isKeyReversible' ks = nub vs == vs
+        where vs = [v | (_, v) <- ks]
+
 
 {- QuickCheck Tests -}
+-- Wenn kein Value doppelt ist kommt True raus
+prop_isKeyReversible_complete :: [(Char, Char)] -> Property
+prop_isKeyReversible_complete ks = vs == nub vs ==> isKeyReversible ks
+        where vs = [v | (_, v) <- ks]
+
+-- Wenn ein Value doppelt ist kommt False raus
+prop_isKeyReversible_sound :: Char -> Char-> Char -> [(Char, Char)] -> [(Char, Char)] -> [(Char, Char)] -> Bool
+prop_isKeyReversible_sound v k1 k2 ks1 ks2 ks3 =
+        not(isKeyReversible (ks1 ++ [(k1, v)] ++ ks2 ++ [(k2, v)] ++ ks3))
 
 
 
 {---------------------------------------------------------------------}
 {- Aufgabe G4.3 -}
 
+
+-- Englisch, da schamlos aus der Musterlösung geklaut.
 {-
- - Proof me!
- -}
+ - Note: [x] is just a syntactic abbreviation for (x : [])
+ - 
+ - Lemma reverse (snoc xs x) = x : reverse xs
+ - Proof by structural induction on xs
+ - 
+ - Base case:
+ - To show: reverse (snoc [] x) = x : reverse []
+ - reverse (snoc [] x)
+ - == reverse [x]                 (by snoc_Nil)
+ - == reverse [] ++ [x]           (by reverse_Cons)
+ - == [] ++ [x]                   (by reverse_Nil)
+ - == [x]                         (by append_Nil)
+ -
+ - x : reverse []
+ - == [x]                         (by reverse_Nil)
+ - 
+ - Induction step:
+ - IH: reverse (snoc ys x) = x : reverse ys
+ - To show: reverse (snoc (y : ys) x) = x : reverse (y : ys)
+ - reverse (snoc (y : ys) x)
+ - == reverse (y : snoc ys x)     (by snoc_Cons)
+ - == reverse (snoc ys x) ++ [y]  (by reverse_Cons)
+ - == (x : reverse ys) ++ [y]     (by IH)
+ - == x : (reverse ys ++ [y])     (by append_Cons)
+ -
+ - x : reverse (y : ys)
+ - == x : (reverse ys ++ [y])     (by reverse_Cons)
+-}
 
 
 
@@ -45,7 +101,12 @@
 {- Aufgabe G4.4 -}
 
 match :: [Char] -> [Char] -> Bool
-match xs ys = undefined
+match [] ys             = null ys
+match ('?':ps) (y:ys)   = match ps ys
+match ('*':ps) []       = match ps []
+match ('*':ps) (y:ys)   = match ps (y:ys) || match ('*':ps) ys
+match (p:ps) (y:ys)     = p == y && match ps ys
+match ps []             = False