Mercurial > 12ws.info2

annotate exercises/src/Exercise_5.hs @ 12:8496af3b866b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add G5.3 and G5.4 definitions
author Markus Kaiser <markus.kaiser@in.tum.de>
date Wed, 14 Nov 2012 19:13:22 +0100
parents a721abd5a135
children 8cc37c82619c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
11
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
1 module Exercise_5 where
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
2 import Data.Maybe
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
3
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
4 {- Library DO NOT CHANGE -}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
5 type State = Integer
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
6 type DA = (State, State -> Char -> State, State -> Bool)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
7 type ListDA = (State, [((State, Char), State)], [State])
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
8
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
9 a :: DA
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
10 a = (0, delta, (==1))
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
11 where
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
12 delta 0 'a' = 1
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
13 delta 1 'a' = 1
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
14 delta 2 'a' = 1
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
15 delta 0 'b' = 2
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
16 delta 1 'b' = 2
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
17 delta 2 'b' = 2
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
18
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
19 toDA :: ListDA -> DA
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
20 toDA (start, delta, final) = (start, deltaFun delta, (`elem` final))
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
21 where deltaFun dl = curry (fromMaybe 0 . flip lookup dl)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
22 {- End Library -}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
23
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
24
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
25 {---------------------------------------------------------------------}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
26 {- Aufgabe G5.1 -}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
27
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
28 iter :: Int -> (a -> a) -> a -> a
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
29 iter n f x = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
30
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
31
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
32 pow :: Int -> Int -> Int
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
33 pow n k = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
34
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
35
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
36 drop' :: Int -> [a] -> [a]
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
37 drop' n xs = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
38
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
39
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
40 replicate' :: Int -> a -> [a]
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
41 replicate' n x = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
42
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
43
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
44
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
45 {---------------------------------------------------------------------}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
46 {- Aufgabe G5.2 -}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
47
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
48 partition_rec :: (a -> Bool) -> [a] -> ([a], [a])
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
49 partition_rec p xs = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
50
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
51
12
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
52 partition_foldr :: (a -> Bool) -> [a] -> ([a], [a])
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
53 partition_foldr p xs = undefined
11
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
54
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
55
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
56 partition_filter :: (a -> Bool) -> [a] -> ([a], [a])
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
57 partition_filter p xs = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
58
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
59
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
60 zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
61 zipWith' f xs ys = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
62
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
63
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
64
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
65 {---------------------------------------------------------------------}
12
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
66 {- Aufgabe G5.3 -}
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
67
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
68 lambda_1 = (\xs -> foldr (++) [] (map (\x -> [x]) xs))
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
69 lambda_2 = (\gg xx yy -> head (tail (zipWith gg [ xx , xx ] [ yy , yy ])))
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
70
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
71
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
72
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
73 {---------------------------------------------------------------------}
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
74 {- Aufgabe G5.4 -}
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
75
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
76 zeros :: [Int]
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
77 zeros = 0 : zeros
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
78
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
79
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
80 length' :: [a] -> Int
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
81 length' [] = 0
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
82 length' (_:xs) = 1 + length' xs
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
83
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
84
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
85 h :: Integer -> Integer -> Integer
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
86 h m n
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
87 | m == n = 0
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
88 | m < n = h m (n - 1)
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
89 | m >= n = h n m + 1
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
90
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
91
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
92
8496af3b866b add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents: 11
diff changeset
93 {---------------------------------------------------------------------}
11
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
94 {- Aufgabe H5.1 -}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
95
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
96 fixpoint :: (a -> a -> Bool) -> (a -> a) -> a -> a
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
97 fixpoint = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
98
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
99
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
100 cents :: [Integer] -> [Integer]
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
101 cents = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
102
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
103
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
104 trancl :: [(Integer, Integer)] -> [(Integer, Integer)]
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
105 trancl = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
106
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
107
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
108
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
109 {---------------------------------------------------------------------}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
110 {- Aufgabe H5.2 -}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
111
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
112 advance :: DA -> State -> String -> State
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
113 advance = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
114
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
115
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
116 prop_advance_empty :: ListDA -> State -> Bool
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
117 prop_advance_empty = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
118
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
119
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
120 prop_advance_single :: ListDA -> State -> Char -> Bool
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
121 prop_advance_single = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
122
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
123
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
124 prop_advance_concat :: ListDA -> State -> String -> String -> Bool
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
125 prop_advance_concat = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
126
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
127
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
128 accept :: DA -> String -> Bool
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
129 accept = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
130
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
131
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
132 reachableStates :: DA -> State -> [Char] -> [State]
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
133 reachableStates = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
134
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
135
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
136
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
137 {---------------------------------------------------------------------}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
138 {- Aufgabe H5.3 -}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
139
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
140 {-WETT-}
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
141 quasiSubseq :: Eq a => [a] -> [a] -> Bool
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
142 quasiSubseq xs ys = undefined
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff changeset
143 {-TTEW-}