Mercurial > 12ws.info2
changeset 37:15e527f4b92e
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 | a10156e1609a |
| files | exercises/src/Exercise_14.hs |
| diffstat | 1 files changed, 45 insertions(+), 4 deletions(-) [+] |
line wrap: on
line diff
--- a/exercises/src/Exercise_14.hs Tue Feb 05 22:12:07 2013 +0100 +++ b/exercises/src/Exercise_14.hs Wed Feb 06 21:48:45 2013 +0100 @@ -56,20 +56,61 @@ {---------------------------------------------------------------------} {- Aufgabe G14.2 -} +-- Beispiele zur Endrekursion +sum1 :: Int -> Int +sum1 0 = 0 +sum1 n = n + sum1 (n - 1) +{- +sum1 3 = 3 + sum1 2 + sum1 2 = 2 + sum1 1 + sum1 1 = 1 + sum1 0 + sum1 0 = 0 + sum1 1 = 1 + 0 + = 1 + sum1 2 = 2 + 1 + = 3 +sum1 3 = 3 + 3 + = 6 +-} + +sum2 :: Int -> Int +sum2 = sum2_end 0 + where + sum2_end acc 0 = acc + sum2_end acc n = sum2_end (acc + n) (n - 1) +{- +sum2 3 = sum2_end 0 3 + = sum2_end 3 2 + = sum2_end 5 1 + = sum2_end 6 0 + = 6 + +-} + + +-- Concats +-- Nicht Endrekursiv concat' :: [[a]] -> [a] concat' [] = [] concat' (xs:xss) = xs ++ concat' xss - +-- O(n) concat'' :: [[a]] -> [a] -concat'' xss = go [] (reverse xss) +concat'' yss = go [] (reverse yss) where go acc [] = acc go acc (xs:xss) = go (xs ++ acc) xss - +-- O(n^2) concat''' :: [[a]] -> [a] -concat''' = foldr (++) [] +concat''' = go [] + where + go acc [] = acc + go acc (xs:xss) = go (acc ++ xs) xss + +-- Mit Fold +concat'''' :: [[a]] -> [a] +concat'''' = foldr (++) []