diff options
Diffstat (limited to 'fp1/week7/camil/BewijsMeppenEnTippen.icl')
| -rw-r--r-- | fp1/week7/camil/BewijsMeppenEnTippen.icl | 82 |
1 files changed, 0 insertions, 82 deletions
diff --git a/fp1/week7/camil/BewijsMeppenEnTippen.icl b/fp1/week7/camil/BewijsMeppenEnTippen.icl deleted file mode 100644 index ca5e396..0000000 --- a/fp1/week7/camil/BewijsMeppenEnTippen.icl +++ /dev/null @@ -1,82 +0,0 @@ -// Mart Lubbers, s4109503
-// Camil Staps, s4498062
-
-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.
\ No newline at end of file |