From 2f6221e339c428cc01528e5419f8e1d2457b2421 Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Sat, 28 Mar 2015 12:55:38 +0100 Subject: [PATCH] 9.5 camil --- week7/camil/BewijsMeppenEnTippen.icl | 79 ++++++++++++++++++++++++++++ 1 file changed, 79 insertions(+) create mode 100644 week7/camil/BewijsMeppenEnTippen.icl diff --git a/week7/camil/BewijsMeppenEnTippen.icl b/week7/camil/BewijsMeppenEnTippen.icl new file mode 100644 index 0000000..1e8d91c --- /dev/null +++ b/week7/camil/BewijsMeppenEnTippen.icl @@ -0,0 +1,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. \ No newline at end of file -- 2.20.1