From a7d7542dc646a5fd124ef71e71ce260889f1701b Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Tue, 2 Feb 2016 19:24:50 +0100 Subject: Moved to 1415 directory --- fp1/week7/camil/BewijsMeppenEnTippen.icl | 82 -------------- fp1/week7/camil/BinSearchTree.dcl | 7 -- fp1/week7/camil/BinSearchTree.icl | 177 ------------------------------- fp1/week7/camil/BinTree.dcl | 16 --- fp1/week7/camil/BinTree.icl | 38 ------- fp1/week7/mart/BewijsMeppenEnTippen.icl | 29 ----- fp1/week7/mart/BinSearchTree.dcl | 7 -- fp1/week7/mart/BinSearchTree.icl | 141 ------------------------ 8 files changed, 497 deletions(-) delete mode 100644 fp1/week7/camil/BewijsMeppenEnTippen.icl delete mode 100644 fp1/week7/camil/BinSearchTree.dcl delete mode 100644 fp1/week7/camil/BinSearchTree.icl delete mode 100644 fp1/week7/camil/BinTree.dcl delete mode 100644 fp1/week7/camil/BinTree.icl delete mode 100644 fp1/week7/mart/BewijsMeppenEnTippen.icl delete mode 100644 fp1/week7/mart/BinSearchTree.dcl delete mode 100644 fp1/week7/mart/BinSearchTree.icl (limited to 'fp1/week7') 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 diff --git a/fp1/week7/camil/BinSearchTree.dcl b/fp1/week7/camil/BinSearchTree.dcl deleted file mode 100644 index 696b065..0000000 --- a/fp1/week7/camil/BinSearchTree.dcl +++ /dev/null @@ -1,7 +0,0 @@ -definition module BinSearchTree - -import StdClass -import BinTree - -is_geordend :: (Tree a) -> Bool | Ord a // meest algemene type -is_gebalanceerd :: (Tree a) -> Bool | Ord a // meest algemene type diff --git a/fp1/week7/camil/BinSearchTree.icl b/fp1/week7/camil/BinSearchTree.icl deleted file mode 100644 index 559846b..0000000 --- a/fp1/week7/camil/BinSearchTree.icl +++ /dev/null @@ -1,177 +0,0 @@ -// Mart Lubbers, s4109503 -// Camil Staps, s4498062 - -implementation module BinSearchTree - -import StdEnv -import BinTree - -z0 = Leaf -// Leaf - -z1 = insertTree 50 z0 -// 50 -// | -// ------------- -// | | -// Leaf Leaf - -z2 = insertTree 10 z1 -// 50 -// | -// ------------- -// | | -// 10 Leaf -// | -// --------- -// | | -// Leaf Leaf - -z3 = insertTree 75 z2 -// 50 -// | -// --------------- -// | | -// 10 75 -// | | -// --------- --------- -// | | | | -// Leaf Leaf Leaf Leaf - -z4 = insertTree 80 z3 -// 50 -// | -// --------------- -// | | -// 10 75 -// | | -// --------- --------- -// | | | | -// Leaf Leaf Leaf 80 -// | -// --------- -// | | -// Leaf Leaf - -z5 = insertTree 77 z4 -// 50 -// | -// --------------- -// | | -// 10 75 -// | | -// --------- --------- -// | | | | -// Leaf Leaf Leaf 77 -// | -// --------- -// | | -// Leaf 80 -// | -// --------- -// | | -// Leaf Leaf - -z6 = insertTree 10 z5 -// 50 -// | -// --------------- -// | | -// 10 75 -// | | -// --------- --------- -// | | | | -// 10 Leaf Leaf 77 -// | | -// --------- --------- -// | | | | -// Leaf Leaf Leaf 80 -// | -// --------- -// | | -// Leaf Leaf - -z7 = insertTree 75 z6 -// 50 -// | -// ---------------- -// | | -// 10 75 -// | | -// --------- ----------- -// | | | | -// 10 Leaf 75 77 -// | | | -// --------- ------ ------- -// | | | | | | -// Leaf Leaf Leaf Leaf Leaf 80 -// | -// --------- -// | | -// Leaf Leaf - -z8 = deleteTree 50 z7 -// 10 -// | -// ---------------- -// | | -// 10 75 -// | | -// --------- ----------- -// | | | | -// Leaf Leaf 75 77 -// | | -// ------ ------- -// | | | | -// Leaf Leaf Leaf 80 -// | -// --------- -// | | -// Leaf Leaf - -// Uit het diktaat, blz. 73: -insertTree :: a (Tree a) -> Tree a | Ord a -insertTree e Leaf = Node e Leaf Leaf -insertTree e (Node x le ri) -| e <= x = Node x (insertTree e le) ri -| e > x = Node x le (insertTree e ri) - -deleteTree :: a (Tree a) -> (Tree a) | Eq, Ord a -deleteTree e Leaf = Leaf -deleteTree e (Node x le ri) -| e < x = Node x (deleteTree e le) ri -| e == x = join le ri -| e > x = Node x le (deleteTree e ri) -where - join :: (Tree a) (Tree a) -> (Tree a) - join Leaf b2 = b2 - join b1 b2 = Node x b1` b2 - where - (x,b1`) = largest b1 - - largest :: (Tree a) -> (a,(Tree a)) - largest (Node x b1 Leaf) = (x,b1) - largest (Node x b1 b2) = (y,Node x b1 b2`) - where - (y,b2`) = largest b2 - - -is_geordend :: (Tree a) -> Bool | Ord a // meest algemene type -is_geordend Leaf = True -is_geordend (Node x le ri) = (foldr (&&) True (map ((>) x) (members le))) && (foldr (&&) True (map ((<=) x) (members ri))) && is_geordend le && is_geordend ri -where - members :: (Tree a) -> [a] - members Leaf = [] - members (Node x le ri) = [x:(members le) ++ (members ri)] - -//Start = map is_geordend [t0,t1,t2,t3,t4,t5,t6,t7] - -is_gebalanceerd :: (Tree a) -> Bool | Ord a // meest algemene type -is_gebalanceerd Leaf = True -is_gebalanceerd (Node x le ri) = abs ((depth le) - (depth ri)) <= 1 && is_gebalanceerd le && is_gebalanceerd ri -where - depth :: (Tree a) -> Int - depth Leaf = 0 - depth (Node x le ri) = max (depth le) (depth ri) + 1 - -//Start = map is_gebalanceerd [t0,t1,t2,t3,t4,t5,t6,t7] diff --git a/fp1/week7/camil/BinTree.dcl b/fp1/week7/camil/BinTree.dcl deleted file mode 100644 index 7774ece..0000000 --- a/fp1/week7/camil/BinTree.dcl +++ /dev/null @@ -1,16 +0,0 @@ -definition module BinTree - -:: Tree a = Node a (Tree a) (Tree a) | Leaf - -t0 :: Tree Int -t1 :: Tree Int -t2 :: Tree Int -t3 :: Tree Int -t4 :: Tree Int -t5 :: Tree Int -t6 :: Tree Int -t7 :: Tree Int - -//nodes :: // meest algemene type -//leaves :: // meest algemene type -//diepte :: // meest algemene type diff --git a/fp1/week7/camil/BinTree.icl b/fp1/week7/camil/BinTree.icl deleted file mode 100644 index 601efcc..0000000 --- a/fp1/week7/camil/BinTree.icl +++ /dev/null @@ -1,38 +0,0 @@ -implementation module BinTree - -import StdEnv - -:: Tree a = Node a (Tree a) (Tree a) | Leaf - -t0 :: Tree Int -t0 = Leaf -t1 :: Tree Int -t1 = Node 4 t0 t0 -t2 :: Tree Int -t2 = Node 2 t0 t1 -t3 :: Tree Int -t3 = Node 5 t2 t0 -t4 :: Tree Int -t4 = Node 5 t2 t2 -t5 :: Tree Int -t5 = Node 1 Leaf (Node 2 Leaf (Node 3 Leaf (Node 4 Leaf Leaf))) -t6 :: Tree Int -t6 = Node 1 (Node 2 (Node 3 (Node 4 Leaf Leaf) Leaf) Leaf) Leaf -t7 :: Tree Int -t7 = Node 4 (Node 1 Leaf Leaf) (Node 5 (Node 2 Leaf Leaf) Leaf) - -// 2. -//nodes :: // meest algemene type -//nodes ... - -//Start = map nodes [t0,t1,t2,t3,t4,t5,t6,t7] - -//leaves :: // meest algemene type -//leaves ... - -//Start = map leaves [t0,t1,t2,t3,t4,t5,t6,t7] - -//diepte :: // meest algemene type -//diepte ... - -//Start = map diepte [t0,t1,t2,t3,t4,t5,t6,t7] diff --git a/fp1/week7/mart/BewijsMeppenEnTippen.icl b/fp1/week7/mart/BewijsMeppenEnTippen.icl deleted file mode 100644 index 720ff4d..0000000 --- a/fp1/week7/mart/BewijsMeppenEnTippen.icl +++ /dev/null @@ -1,29 +0,0 @@ -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: diff --git a/fp1/week7/mart/BinSearchTree.dcl b/fp1/week7/mart/BinSearchTree.dcl deleted file mode 100644 index 2e480bb..0000000 --- a/fp1/week7/mart/BinSearchTree.dcl +++ /dev/null @@ -1,7 +0,0 @@ -definition module BinSearchTree - -import StdClass -import BinTree - -is_geordend :: // meest algemene type -is_gebalanceerd :: // meest algemene type diff --git a/fp1/week7/mart/BinSearchTree.icl b/fp1/week7/mart/BinSearchTree.icl deleted file mode 100644 index 8f9f05c..0000000 --- a/fp1/week7/mart/BinSearchTree.icl +++ /dev/null @@ -1,141 +0,0 @@ -implementation module BinSearchTree - -import StdEnv -import BinTree - - -z0 - Leaf -z1 - 50 - | - ---------- - | | - Leaf Leaf -z2 - 50 - | - ---------- - | | - 10 Leaf - | - ------ - | | - Leaf Leaf -z3 - 50 - | - ---------- - | | - 10 75 - | | - ------ ------ - | | | | - Leaf Leaf Leaf Leaf -z4 - 50 - | - ---------- - | | - 10 75 - | | - ------ ------ - | | | | - Leaf Leaf Leaf 80 - | - ------ - | | - Leaf Leaf -z5 - 50 - | - ---------- - | | - 10 75 - | | - ------ ------ - | | | | - Leaf Leaf Leaf 77 - | - ------ - | | - Leaf 80 - | - ------ - | | - Leaf Leaf -z6 - 50 - | - ---------- - | | - 10 75 - | | - ------ ------ - | | | | - 10 Leaf Leaf 77 - | | - ------ ------ - | | | | -Leaf Leaf Leaf 80 - | - ------ - | | - Leaf Leaf -z7 - 50 - | - ---------- - | | - 10 75 - | | - ------ ----------- - | | | | - 10 Leaf 75 77 - | | | - ------ ------ ------ - | | | | | | -Leaf Leaf Leaf Leaf Leaf 80 - | - ------ - | | - Leaf Leaf -z8 - -// Uit het diktaat, blz. 73: -insertTree :: a (Tree a) -> Tree a | Ord a -insertTree e Leaf = Node e Leaf Leaf -insertTree e (Node x le ri) -| e <= x = Node x (insertTree e le) ri -| e > x = Node x le (insertTree e ri) - -deleteTree :: a (Tree a) -> (Tree a) | Eq, Ord a -deleteTree e Leaf = Leaf -deleteTree e (Node x le ri) -| e < x = Node x (deleteTree e le) ri -| e == x = join le ri -| e > x = Node x le (deleteTree e ri) -where - join :: (Tree a) (Tree a) -> (Tree a) - join Leaf b2 = b2 - join b1 b2 = Node x b1` b2 - where - (x,b1`) = largest b1 - - largest :: (Tree a) -> (a,(Tree a)) - largest (Node x b1 Leaf) = (x,b1) - largest (Node x b1 b2) = (y,Node x b1 b2`) - where - (y,b2`) = largest b2 - - -is_geordend :: // meest algemene type -is_geordend ... - -Start = map is_geordend [t0,t1,t2,t3,t4,t5,t6,t7] - - -is_gebalanceerd :: // meest algemene type -is_gebalanceerd ... - -//Start = map is_gebalanceerd [t0,t1,t2,t3,t4,t5,t6,t7] -- cgit v1.2.3