diff options
| -rw-r--r-- | week7/mart/BewijsMeppenEnTippen.icl | 29 | ||||
| -rw-r--r-- | week7/mart/BinSearchTree.dcl | 7 | ||||
| -rw-r--r-- | week7/mart/BinSearchTree.icl | 52 |
3 files changed, 88 insertions, 0 deletions
diff --git a/week7/mart/BewijsMeppenEnTippen.icl b/week7/mart/BewijsMeppenEnTippen.icl new file mode 100644 index 0000000..720ff4d --- /dev/null +++ b/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/week7/mart/BinSearchTree.dcl b/week7/mart/BinSearchTree.dcl new file mode 100644 index 0000000..2e480bb --- /dev/null +++ b/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/week7/mart/BinSearchTree.icl b/week7/mart/BinSearchTree.icl new file mode 100644 index 0000000..92e7548 --- /dev/null +++ b/week7/mart/BinSearchTree.icl @@ -0,0 +1,52 @@ +implementation module BinSearchTree
+
+import StdEnv
+import BinTree
+
+z0 = Leaf
+z1 = insertTree 50 z0
+z2 = insertTree 10 z1
+z3 = insertTree 75 z2
+z4 = insertTree 80 z3
+z5 = insertTree 77 z4
+z6 = insertTree 10 z5
+z7 = insertTree 75 z6
+z8 = deleteTree 50 z7
+
+// 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]
|