Mercurial > 12ws.info2

comparison exercises/src/Exercise_5.hs @ 13:8cc37c82619c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
week 5 tutorial
author Markus Kaiser <markus.kaiser@in.tum.de>
date Wed, 21 Nov 2012 19:28:26 +0100
parents 8496af3b866b
children
comparison
equal deleted inserted replaced
12:8496af3b866b 13:8cc37c82619c
1 module Exercise_5 where 1 module Exercise_5 where
2 import Data.Maybe 2 import Data.Maybe
3 import Data.List
4 import Test.QuickCheck
3 5
4 {- Library DO NOT CHANGE -} 6 {- Library DO NOT CHANGE -}
5 type State = Integer 7 type State = Integer
6 type DA = (State, State -> Char -> State, State -> Bool) 8 type DA = (State, State -> Char -> State, State -> Bool)
7 type ListDA = (State, [((State, Char), State)], [State]) 9 type ListDA = (State, [((State, Char), State)], [State])
24 26
25 {---------------------------------------------------------------------} 27 {---------------------------------------------------------------------}
26 {- Aufgabe G5.1 -} 28 {- Aufgabe G5.1 -}
27 29
28 iter :: Int -> (a -> a) -> a -> a 30 iter :: Int -> (a -> a) -> a -> a
29 iter n f x = undefined 31 iter n f x
32 | n <= 0 = x
33 | otherwise = iter (n - 1) f (f x)
30 34
31 35
32 pow :: Int -> Int -> Int 36 pow :: Int -> Int -> Int
33 pow n k = undefined 37 pow n k = iter k (\x -> x*n) 1
34 38
35 39
36 drop' :: Int -> [a] -> [a] 40 drop' :: Int -> [a] -> [a]
37 drop' n xs = undefined 41 drop' n xs = iter n tail xs
38 42
39 43
40 replicate' :: Int -> a -> [a] 44 replicate' :: Int -> a -> [a]
41 replicate' n x = undefined 45 replicate' n x = iter n (x:) []
42 46
43 47
44 48
45 {---------------------------------------------------------------------} 49 {---------------------------------------------------------------------}
46 {- Aufgabe G5.2 -} 50 {- Aufgabe G5.2 -}
47 51
52 {- Fold-Beispiel anhand der Summenfunktion -}
53
54 sum' :: [Integer] -> Integer
55 sum' [] = 0
56 sum' (x:xs) = x + sum' xs
57
58
59 sum'' :: [Integer] -> Integer
60 sum'' xs = sum_acc xs 0
61 where
62 sum_acc :: [Integer] -> Integer -> Integer
63 sum_acc [] acc = acc
64 sum_acc (x:xs) acc = sum_acc xs (x+acc)
65
66 sum_fold :: [Integer] -> Integer
67 --sum_fold xs = foldr (\x acc -> x + acc) 0 xs
68 sum_fold xs = foldr (+) 0 xs
69
70 {-----}
71
48 partition_rec :: (a -> Bool) -> [a] -> ([a], [a]) 72 partition_rec :: (a -> Bool) -> [a] -> ([a], [a])
49 partition_rec p xs = undefined 73 partition_rec p xs = partition_rec' xs ([], [])
74 where
75 partition_rec' [] (ts, fs) = (reverse ts, reverse fs)
76 partition_rec' (x:xs) (ts, fs) =
77 if p x then partition_rec' xs (x:ts, fs)
78 else partition_rec' xs (ts, x:fs)
50 79
51 80
52 partition_foldr :: (a -> Bool) -> [a] -> ([a], [a]) 81 partition_foldr :: (a -> Bool) -> [a] -> ([a], [a])
53 partition_foldr p xs = undefined 82 partition_foldr p xs = foldr partition_foldr' ([], []) xs
83 where
84 partition_foldr' x (ts, fs) =
85 if p x then (x:ts, fs)
86 else (ts, x:fs)
54 87
55 88
56 partition_filter :: (a -> Bool) -> [a] -> ([a], [a]) 89 partition_filter :: (a -> Bool) -> [a] -> ([a], [a])
57 partition_filter p xs = undefined 90 --partition_filter p xs = (filter p xs, filter (\x -> not(p(x))) xs)
91 partition_filter p xs = (filter p xs, filter (not . p) xs)
92
93
94 prop_partition_foldr_even xs =
95 partition_foldr even xs == partition even xs
96
97
98 prop_partition_distrib_even xs ys =
99 partition even (xs ++ ys) == (ts ++ ts', fs ++ fs')
100 where
101 (ts, fs) = partition even xs
102 (ts', fs') = partition even ys
58 103
59 104
60 zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c] 105 zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
61 zipWith' f xs ys = undefined 106 zipWith' _ [] [] = []
107 zipWith' f (x:xs) (y:ys) = (f x y) : zipWith' f xs ys
62 108
63 109
64 110
65 {---------------------------------------------------------------------} 111 {---------------------------------------------------------------------}
66 {- Aufgabe G5.3 -} 112 {- Aufgabe G5.3 -}
67 113
114 -- Beide Identitäten
68 lambda_1 = (\xs -> foldr (++) [] (map (\x -> [x]) xs)) 115 lambda_1 = (\xs -> foldr (++) [] (map (\x -> [x]) xs))
69 lambda_2 = (\gg xx yy -> head (tail (zipWith gg [ xx , xx ] [ yy , yy ]))) 116 lambda_2 = (\gg xx yy -> head (tail (zipWith gg [ xx , xx ] [ yy , yy ])))
70 117
71 118
72 119
73 {---------------------------------------------------------------------} 120 {---------------------------------------------------------------------}
74 {- Aufgabe G5.4 -} 121 {- Aufgabe G5.4 -}
75 122
123 -- Unendliche Liste mit Nullen
76 zeros :: [Int] 124 zeros :: [Int]
77 zeros = 0 : zeros 125 zeros = 0 : zeros
78 126
79 127
80 length' :: [a] -> Int 128 length' :: [a] -> Int
81 length' [] = 0 129 length' [] = 0
82 length' (_:xs) = 1 + length' xs 130 length' (_:xs) = 1 + length' xs
83 131
84 132
133 -- Terminiert immer.
134 -- m <= n: 0
135 -- m > n: 1
85 h :: Integer -> Integer -> Integer 136 h :: Integer -> Integer -> Integer
86 h m n 137 h m n
87 | m == n = 0 138 | m == n = 0
88 | m < n = h m (n - 1) 139 | m < n = h m (n - 1)
89 | m >= n = h n m + 1 140 | m >= n = h n m + 1