blob: 1e8d91cd53f567a786baa9a1126a71d87c1594b6 (
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
Zij gegeven:
:: BTree a = Tip a | Bin (BTree a) (BTree a)
map :: (a -> b) [a] -> [b]
map f [] = [] (1.)
map f [x:xs] = [f x : map f xs] (2.)
mapbtree :: (a -> b) (BTree a) -> BTree b
mapbtree f (Tip a) = Tip (f a) (3.)
mapbtree f (Bin t1 t2) = Bin (mapbtree f t1) (mapbtree f t2) (4.)
foldbtree :: (a a -> a) (BTree a) -> a
foldbtree f (Tip x) = x (5.)
foldbtree f (Bin t1 t2) = f (foldbtree f t1) (foldbtree f t2) (6.)
tips :: (BTree a) -> [a]
tips t = foldbtree (++) (mapbtree unit t) (7.)
unit :: a -> [a]
unit x = [x] (8.)
Te bewijzen:
voor alle functies f, voor alle eindige bomen t:
map f (tips t) = tips (mapbtree f t)
Bewijs:
Met inductie over t.
Inductiebasis: stel t = Tip a.
Dan hebben we:
map f (tips t) // definitie tips (7)
= map f (foldbtree (++) (mapbtree unit t)) // aanname t = Tip a
= map f (foldbtree (++) (mapbtree unit (Tip a))) // definitie mapbtree (3)
= map f (foldbtree (++) (Tip unit a)) // definitie foldbtree (5)
= map f (unit a) // definitie unit (8)
= map f [a] // herschrijven lijst
= map f [a:[]] // definitie map (2)
= [f a : map f []] // definitie map (1)
= [f a : []] // herschrijven lijst
= [f a] // definitie unit (8)
= unit (f a) // definitie foldbtree (5)
= foldbtree (++) (Tip (unit (f a))) // definitie mapbtree (3)
= foldbtree (++) (mapbtree unit (Tip (f a))) // definitie tips (7)
= tips (Tip (f a)) // definitie mapbtree (3)
= tips (mapbtree f (Tip a)) // aanname t = Tip a
= tips (mapbtree f t)
Dus de stelling geldt voor t = Tip a.
Inductiestap: laten we aannemen dat
map f (tips t) = tips (mapbtree f t)
voor alle f en zekere t=t1,t=t2 (inductiehypothese).
Dan hebben we:
map f (tips (Bin t1 t2)) // definitie tips (7)
= map f (foldbtree (++) (mapbtree unit (Bin t1 t2))) // definitie mapbtree (4)
= map f (foldbtree (++) (Bin (mapbtree unit t1) (mapbtree unit t2))) // definitie foldbtree (6)
= map f ((++) (foldbtree (++) (mapbtree unit t1)) (foldbtree (++) (mapbtree unit t2))) // definitie tips (7)
= map f ((++) (tips t1) (tips t2)) // 9.4.1
= (map f (tips t1)) ++ (map f (tips t2)) // inductiehypothese
= (tips (mapbtree f t1)) ++ (tips (mapbtree f t2)) // definitie tips (7)
= (foldbtree (++) (mapbtree unit (f t1))) ++ (foldbtree (++) (mapbtree unit (f t2))) // herschrijven infixnotatie
= (++) (foldbtree (++) (mapbtree unit (f t1))) (foldbtree (++) (mapbtree unit (f t2))) // definitie foldbtree (6)
= foldbtree (++) (Bin (mapbtree unit (f t1)) (mapbtree unit (f t2))) // definitie mapbtree (4)
= foldbtree (++) (mapbtree unit (Bin (mapbtree f t1) (mapbtree f t2))) // definitie tips (7)
= tips (Bin (mapbtree f t1) (mapbtree f t2)) // definitie mapbtree (4)
= tips (mapbtree f (Bin t1 t2))
Conclusie:
We hebben laten zien dat de stelling geldt voor elke f met t = Tip a. Vervolgens hebben we laten zien dat als de stelling geldt voor elke f met t=t1 of t=t2, de stelling óók geldt voor elke f met t = Bin t1 t2.
Met het principe van inductie volgt nu
map f (tips t) = tips (mapbtree f t)
voor alle functies f en alle eindige bomen t.
|
