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/mart/BewijsMeppenEnTippen.icl |  29 ++++++
 1415/fp1/week7/mart/BinSearchTree.dcl        |   7 ++
 1415/fp1/week7/mart/BinSearchTree.icl        | 141 +++++++++++++++++++++++++++
 3 files changed, 177 insertions(+)
 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/mart')

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