blob: 43329e3986e1697f4b90ffce4e999066cdf780db (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
Zij gegeven de volgende functie-definities:
subs :: [a] -> [[a]]
subs [] = [[]] (1.)
subs [x:xs] = subs xs ++ map (cons x) (subs xs) (2.)
map :: (a -> b) [a] -> [b]
map f [] = [] (3.)
map f [x:xs] = [f x : map f xs] (4.)
(++) :: [a] [a] -> [a]
(++) [] ys = ys (5.)
(++) [x:xs] ys = [x : xs ++ ys] (6.)
cons :: a [a] -> [a]
cons x xs = [x : xs] (7.)
Bewijs de volgende stelling voor alle functies f en eindige lijsten xs:
subs (map f xs) = map (map f) (subs xs).
Je kunt gebruik maken van de volgende hulpstellingen (lemma's) die gelden voor alle
functies f, g en eindige lijsten xs en ys:
map f (xs ++ ys) = map f xs ++ map f ys (8.)
map g (map f xs) = map (g o f) xs (9.)
(cons (f a)) o (map f) = (map f) o (cons a) (10.)
(g o f) x = g (f x) (11.)
Bewijs:
-------
|
