Mercurial > 12ws.info2

comparison exercises/src/Exercise_14.hs @ 37:15e527f4b92e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add some more examples to G14.2 (thanks Tobi)
author Markus Kaiser <markus.kaiser@in.tum.de>
date Wed, 06 Feb 2013 21:48:45 +0100
parents 89feab98266f
children
comparison
equal deleted inserted replaced
36:89feab98266f 37:15e527f4b92e
54 54
55 55
56 {---------------------------------------------------------------------} 56 {---------------------------------------------------------------------}
57 {- Aufgabe G14.2 -} 57 {- Aufgabe G14.2 -}
58 58
59 -- Beispiele zur Endrekursion
60 sum1 :: Int -> Int
61 sum1 0 = 0
62 sum1 n = n + sum1 (n - 1)
63 {-
64 sum1 3 = 3 + sum1 2
65 sum1 2 = 2 + sum1 1
66 sum1 1 = 1 + sum1 0
67 sum1 0 = 0
68 sum1 1 = 1 + 0
69 = 1
70 sum1 2 = 2 + 1
71 = 3
72 sum1 3 = 3 + 3
73 = 6
74 -}
75
76 sum2 :: Int -> Int
77 sum2 = sum2_end 0
78 where
79 sum2_end acc 0 = acc
80 sum2_end acc n = sum2_end (acc + n) (n - 1)
81 {-
82 sum2 3 = sum2_end 0 3
83 = sum2_end 3 2
84 = sum2_end 5 1
85 = sum2_end 6 0
86 = 6
87
88 -}
89
90
91 -- Concats
92 -- Nicht Endrekursiv
59 concat' :: [[a]] -> [a] 93 concat' :: [[a]] -> [a]
60 concat' [] = [] 94 concat' [] = []
61 concat' (xs:xss) = xs ++ concat' xss 95 concat' (xs:xss) = xs ++ concat' xss
62 96
63 97 -- O(n)
64 concat'' :: [[a]] -> [a] 98 concat'' :: [[a]] -> [a]
65 concat'' xss = go [] (reverse xss) 99 concat'' yss = go [] (reverse yss)
66 where 100 where
67 go acc [] = acc 101 go acc [] = acc
68 go acc (xs:xss) = go (xs ++ acc) xss 102 go acc (xs:xss) = go (xs ++ acc) xss
69 103
104 -- O(n^2)
105 concat''' :: [[a]] -> [a]
106 concat''' = go []
107 where
108 go acc [] = acc
109 go acc (xs:xss) = go (acc ++ xs) xss
70 110
71 concat''' :: [[a]] -> [a] 111 -- Mit Fold
72 concat''' = foldr (++) [] 112 concat'''' :: [[a]] -> [a]
113 concat'''' = foldr (++) []
73 114
74 115
75 116
76 {---------------------------------------------------------------------} 117 {---------------------------------------------------------------------}
77 {- Aufgabe G14.3 -} 118 {- Aufgabe G14.3 -}