|
38
|
1 module Exercise_15 where |
|
|
2 |
|
|
3 {- |
|
|
4 Wichtiges: |
|
|
5 - Syntax: Typannotation, Assoziativität, Pattern Matching, Guards, Currying, List Comprehensions |
|
|
6 - Typisierung: Typvariablen, Typklassen, Typbestimmung |
|
|
7 - QuickCheck |
|
|
8 - Induktionsbeweise: Schema!, Fallunterscheidung, Generalisierung, Strukturelle Induktion |
|
|
9 - Higher Order Functions: map, filter, fold, Lambdas, (.) |
|
|
10 - Pointfree Notation |
|
|
11 - Module, Typlassen, Instanzen |
|
|
12 - Datentypen: data vs. type vs. newtype, Abstraktionsfunktionen |
|
|
13 - (Huffman, Parser) |
|
|
14 - Lazy Evaluation: Redexes, Outside In, Unendliche Datenstrukturen |
|
|
15 - IO: do-Notation, warum die Sonderbehandlung? |
|
39
|
16 - Endrekursion und Akkumulatoren |
|
38
|
17 -} |
|
39
|
18 |
|
|
19 |
|
|
20 -- $ |
|
|
21 -- f (g x) == f $ g x |
|
|
22 -- f $ g $ h $ i x == f . g . h $ i x == (f . g . h . i) x |
|
|
23 |
|
|
24 doubleAllEven xs = map (*2) (filter even xs) |
|
|
25 doubleAllEven' xs = map (*2) $ filter even xs |
|
|
26 |
|
|
27 |
|
|
28 |
|
|
29 -- Unendliche Datenstrukturen |
|
|
30 nats = [1..] |
|
|
31 nats' = 1 : map (+1) nats' |
|
|
32 |
|
|
33 fibs = 0 : 1 : zipWith (+) fibs (tail fibs) |
|
|
34 |
|
|
35 |
|
|
36 |
|
|
37 -- (.).(.) |
|
|
38 -- f (g x y) == (f ((.).(.)) g) x y |
|
|
39 oo :: (c -> d) -> (a -> b -> c) -> a -> b -> d |
|
|
40 oo = (.).(.) |
|
|
41 oo' w = ((.) . (.)) w |
|
|
42 oo'' w = (.) ((.) w) |
|
|
43 oo''' w x = (.) ((.) w) x |
|
|
44 oo'''' w x = ((.) w) . x |
|
|
45 oo''''' w x y = (((.) w) . x) y |
|
|
46 oo'''''' w x y = w . (x y) |
|
|
47 oo''''''' w x y z = (w . (x y)) z |
|
|
48 oo'''''''' w x y z = w (x y z) |
|
|
49 |
|
|
50 |
|
|
51 |
|
|
52 -- map, fold |
|
|
53 -- [f x y | x <- xs, y <- ys, p y] |
|
|
54 -- == concatMap (\x -> map (\y -> f x y) (filter p ys)) xs |
|
|
55 |
|
|
56 map' :: (a -> b) -> [a] -> [b] |
|
|
57 map' f xs = [f x | x <- xs] |
|
|
58 |
|
|
59 map'' f = foldr g [] |
|
|
60 where |
|
|
61 g x xs = (f x) : xs |
|
|
62 -- == (:) (f x)-} |
|
|
63 -- == ((:) . f)-} |
|
|
64 |
|
|
65 map''' f = foldl (\xs x -> xs ++ [f x]) [] |
|
|
66 |
|
|
67 foldl' :: (a -> b -> a) -> a -> [b] -> a |
|
|
68 foldl' _ acc [] = acc |
|
|
69 foldl' f acc (x : xs) = foldl' f (f acc x) xs |
|
|
70 |
|
|
71 foldr' _ acc [] = acc |
|
|
72 foldr' f acc (x : xs) = f x (foldr' f acc xs) |
|
|
73 |
|
|
74 filterMap :: (a -> Maybe b) -> [a] -> [b] |
|
|
75 filterMap _ [] = [] |
|
|
76 filterMap f (x:xs) = |
|
|
77 case (f x) of |
|
|
78 Nothing -> filterMap f xs |
|
|
79 Just y -> y : filterMap f xs |
|
|
80 |
|
|
81 |
|
|
82 |
|
|
83 -- type vs. newtype vs. data |
|
|
84 type Name = String |
|
|
85 greet :: Name -> String |
|
|
86 greet n = "Hallo, " ++ n ++ "!" |
|
|
87 |
|
|
88 newtype Address = Address String |
|
|
89 askForTheWay (Address a) = "How do I get to " ++ a ++ "?" |
|
|
90 |
|
|
91 data MyList a = Empty | Element a (MyList a) deriving (Eq) |
|
|
92 instance Show a => Show (MyList a) where |
|
|
93 show Empty = "[]" |
|
|
94 show (Element a xs) = show a ++ ":" ++ show xs |
|
|
95 |
|
|
96 myLength :: (MyList a) -> Int |
|
|
97 myLength Empty = 0 |
|
|
98 myLength (Element _ xs) = 1 + myLength xs |
|
|
99 |
|
|
100 |
|
|
101 |
|
|
102 -- Baumdefinitionen |
|
|
103 data BinaryTree a = Empty | Node a (BinaryTree a) (BinaryTree a) |
|
|
104 |
|
|
105 data ArbitraryTree a = Empty | Node a [ArbitraryTree a] |
