summaryrefslogtreecommitdiff
path: root/fp1/week7/camil
diff options
context:
space:
mode:
Diffstat (limited to 'fp1/week7/camil')
-rw-r--r--fp1/week7/camil/BewijsMeppenEnTippen.icl82
-rw-r--r--fp1/week7/camil/BinSearchTree.dcl7
-rw-r--r--fp1/week7/camil/BinSearchTree.icl177
-rw-r--r--fp1/week7/camil/BinTree.dcl16
-rw-r--r--fp1/week7/camil/BinTree.icl38
5 files changed, 0 insertions, 320 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
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]
generated by cgit v1.2.3 (git 2.39.1) at 2025-03-15 12:20:05 +0000