# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1353522506 -3600
# Node ID 8cc37c82619cf5d2f6dec58c1af9c11f9788c2f8
# Parent  8496af3b866bd15af17246329274788341716f71
week 5 tutorial

diff -r 8496af3b866b -r 8cc37c82619c exercises/src/Exercise_5.hs
--- a/exercises/src/Exercise_5.hs	Wed Nov 14 19:13:22 2012 +0100
+++ b/exercises/src/Exercise_5.hs	Wed Nov 21 19:28:26 2012 +0100
@@ -1,5 +1,7 @@
 module Exercise_5 where
 import Data.Maybe
+import Data.List
+import Test.QuickCheck
 
 {- Library DO NOT CHANGE -}
 type State = Integer
@@ -26,45 +28,90 @@
 {- Aufgabe G5.1 -}
 
 iter :: Int -> (a -> a) -> a -> a
-iter n f x = undefined
+iter n f x
+        | n <= 0 = x
+        | otherwise = iter (n - 1) f (f x)
 
 
 pow :: Int -> Int -> Int
-pow n k = undefined
+pow n k = iter k (\x -> x*n) 1
 
 
 drop' :: Int -> [a] -> [a]
-drop' n xs = undefined
+drop' n xs = iter n tail xs
 
 
 replicate' :: Int -> a -> [a]
-replicate' n x = undefined
+replicate' n x = iter n (x:) []
 
 
 
 {---------------------------------------------------------------------}
 {- Aufgabe G5.2 -}
 
+{- Fold-Beispiel anhand der Summenfunktion -}
+
+sum' :: [Integer] -> Integer
+sum' [] = 0
+sum' (x:xs) = x + sum' xs
+
+
+sum'' :: [Integer] -> Integer
+sum'' xs = sum_acc xs 0
+        where
+        sum_acc :: [Integer] -> Integer -> Integer 
+        sum_acc [] acc = acc
+        sum_acc (x:xs) acc = sum_acc xs (x+acc)
+
+sum_fold :: [Integer] -> Integer
+--sum_fold xs = foldr (\x acc -> x + acc) 0 xs
+sum_fold xs = foldr (+) 0 xs
+
+{-----}
+
 partition_rec :: (a -> Bool) -> [a] -> ([a], [a])
-partition_rec p xs = undefined
+partition_rec p xs = partition_rec' xs ([], [])
+        where
+        partition_rec' [] (ts, fs) = (reverse ts, reverse fs)
+        partition_rec' (x:xs) (ts, fs) =
+                if p x then partition_rec' xs (x:ts, fs)
+                else partition_rec' xs (ts, x:fs)
 
 
 partition_foldr :: (a -> Bool) -> [a] -> ([a], [a])
-partition_foldr p xs = undefined
+partition_foldr p xs = foldr partition_foldr' ([], []) xs
+        where
+        partition_foldr' x (ts, fs) =
+                if p x then (x:ts, fs)
+                else (ts, x:fs)
 
 
 partition_filter :: (a -> Bool) -> [a] -> ([a], [a])
-partition_filter p xs = undefined
+--partition_filter p xs = (filter p xs, filter (\x -> not(p(x))) xs)
+partition_filter p xs = (filter p xs, filter (not . p) xs)
+
+
+prop_partition_foldr_even xs =
+        partition_foldr even xs == partition even xs
+
+
+prop_partition_distrib_even xs ys =
+        partition even (xs ++ ys) == (ts ++ ts', fs ++ fs')
+        where
+        (ts, fs) = partition even xs
+        (ts', fs') = partition even ys
 
 
 zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
-zipWith' f xs ys = undefined
+zipWith' _ [] [] = []
+zipWith' f (x:xs) (y:ys) = (f x y) : zipWith' f xs ys
 
 
 
 {---------------------------------------------------------------------}
 {- Aufgabe G5.3 -}
 
+-- Beide Identitäten
 lambda_1 = (\xs -> foldr (++) [] (map (\x -> [x]) xs))
 lambda_2 = (\gg xx yy -> head (tail (zipWith gg [ xx , xx ] [ yy , yy ])))
 
@@ -73,6 +120,7 @@
 {---------------------------------------------------------------------}
 {- Aufgabe G5.4 -}
 
+-- Unendliche Liste mit Nullen
 zeros :: [Int] 
 zeros = 0 : zeros 
 
@@ -82,6 +130,9 @@
 length' (_:xs) = 1 + length' xs 
 
 
+-- Terminiert immer.
+-- m <= n: 0
+-- m >  n: 1
 h :: Integer -> Integer -> Integer
 h m n
         | m == n = 0