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 --- 1415/fp1/week7/camil/BewijsMeppenEnTippen.icl | 82 ++++++++++++ 1415/fp1/week7/camil/BinSearchTree.dcl | 7 + 1415/fp1/week7/camil/BinSearchTree.icl | 177 ++++++++++++++++++++++++++ 1415/fp1/week7/camil/BinTree.dcl | 16 +++ 1415/fp1/week7/camil/BinTree.icl | 38 ++++++ 1415/fp1/week7/mart/BewijsMeppenEnTippen.icl | 29 +++++ 1415/fp1/week7/mart/BinSearchTree.dcl | 7 + 1415/fp1/week7/mart/BinSearchTree.icl | 141 ++++++++++++++++++++ 8 files changed, 497 insertions(+) create mode 100644 1415/fp1/week7/camil/BewijsMeppenEnTippen.icl create mode 100644 1415/fp1/week7/camil/BinSearchTree.dcl create mode 100644 1415/fp1/week7/camil/BinSearchTree.icl create mode 100644 1415/fp1/week7/camil/BinTree.dcl create mode 100644 1415/fp1/week7/camil/BinTree.icl create mode 100644 1415/fp1/week7/mart/BewijsMeppenEnTippen.icl create mode 100644 1415/fp1/week7/mart/BinSearchTree.dcl create mode 100644 1415/fp1/week7/mart/BinSearchTree.icl (limited to '1415/fp1/week7') diff --git a/1415/fp1/week7/camil/BewijsMeppenEnTippen.icl b/1415/fp1/week7/camil/BewijsMeppenEnTippen.icl new file mode 100644 index 0000000..ca5e396 --- /dev/null +++ b/1415/fp1/week7/camil/BewijsMeppenEnTippen.icl @@ -0,0 +1,82 @@ +// 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/1415/fp1/week7/camil/BinSearchTree.dcl b/1415/fp1/week7/camil/BinSearchTree.dcl new file mode 100644 index 0000000..696b065 --- /dev/null +++ b/1415/fp1/week7/camil/BinSearchTree.dcl @@ -0,0 +1,7 @@ +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/1415/fp1/week7/camil/BinSearchTree.icl b/1415/fp1/week7/camil/BinSearchTree.icl new file mode 100644 index 0000000..559846b --- /dev/null +++ b/1415/fp1/week7/camil/BinSearchTree.icl @@ -0,0 +1,177 @@ +// 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/1415/fp1/week7/camil/BinTree.dcl b/1415/fp1/week7/camil/BinTree.dcl new file mode 100644 index 0000000..7774ece --- /dev/null +++ b/1415/fp1/week7/camil/BinTree.dcl @@ -0,0 +1,16 @@ +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/1415/fp1/week7/camil/BinTree.icl b/1415/fp1/week7/camil/BinTree.icl new file mode 100644 index 0000000..601efcc --- /dev/null +++ b/1415/fp1/week7/camil/BinTree.icl @@ -0,0 +1,38 @@ +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/1415/fp1/week7/mart/BewijsMeppenEnTippen.icl b/1415/fp1/week7/mart/BewijsMeppenEnTippen.icl new file mode 100644 index 0000000..720ff4d --- /dev/null +++ b/1415/fp1/week7/mart/BewijsMeppenEnTippen.icl @@ -0,0 +1,29 @@ +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/1415/fp1/week7/mart/BinSearchTree.dcl b/1415/fp1/week7/mart/BinSearchTree.dcl new file mode 100644 index 0000000..2e480bb --- /dev/null +++ b/1415/fp1/week7/mart/BinSearchTree.dcl @@ -0,0 +1,7 @@ +definition module BinSearchTree + +import StdClass +import BinTree + +is_geordend :: // meest algemene type +is_gebalanceerd :: // meest algemene type diff --git a/1415/fp1/week7/mart/BinSearchTree.icl b/1415/fp1/week7/mart/BinSearchTree.icl new file mode 100644 index 0000000..8f9f05c --- /dev/null +++ b/1415/fp1/week7/mart/BinSearchTree.icl @@ -0,0 +1,141 @@ +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