summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--week3/mart/StdSortList.icl41
-rw-r--r--week4/mart/StdSet.dcl25
-rw-r--r--week4/mart/StdSet.icl56
3 files changed, 105 insertions, 17 deletions
diff --git a/week3/mart/StdSortList.icl b/week3/mart/StdSortList.icl
index 2c8ad3f..db71a36 100644
--- a/week3/mart/StdSortList.icl
+++ b/week3/mart/StdSortList.icl
@@ -2,42 +2,49 @@ implementation module StdSortList
import StdEnv
-:: SortList a = SortList (SortList a, a, SortList a) | Empty
+:: SortList a :== ([a], a)
newSortList :: SortList a
-newSortList = Empty
+newSortList = ([], abort "Empty list")
memberSort :: a (SortList a) -> Bool | Eq, Ord a
-memberSort x Empty = False
-memberSort x (le, el, gr)
-| x == e = True
-| x < el = memberSort x le
-| otherwise = memberSort x gr
+memberSort e ([], y) = y
+memberSort e ([x:xs], y)
+| e == x = True
+| e > x = False
+| otherwise = memberSort e (xs, y)
insertSort :: a (SortList a) -> SortList a | Ord a
-memberSort x Empty = Sortlist (Empty, x, Empty)
-memberSort x (le, el, gr)
+insertSort e ([], y) = ([e], e)
+insertSort e ([x:xs], y)
+| e <= x = ([e:x:xs], y)
+| otherwise = ([x:fst result], snd result)
+ where result = insertSort e (xs, y)
removeFirst :: a (SortList a) -> SortList a | Eq, Ord a
-removeFirst e ([], _)_ = ([], _)
+removeFirst e ([], y) = y
+removeFirst e ([e], e) = newSortList
+removeFirst e ([x:xs], y)
+| e == x = ([xs], y)
+removeFirst _ _ = abort ""
-removeAll :: a (SortList a) -> SortList a
-removeAll _ _ = Empty
+removeAll :: a (SortList a) -> SortList a | Eq, Ord a
+removeAll _ _ = abort ""
elements :: (SortList a) -> [a]
-elements _ = []
+elements _ = abort ""
count :: (SortList a) -> Int
-count _ = 0
+count _ = abort ""
minimum :: (SortList a) -> a
-minimum _ = 0
+minimum _ = abort ""
maximum :: (SortList a) -> a
-maximum _ = 0
+maximum _ = abort ""
mergeSortList :: (SortList a) (SortList b) -> (SortList a)
-mergeSortList _ _ = Empty
+mergeSortList _ _ = abort ""
Start :: String
Start = newSortList
diff --git a/week4/mart/StdSet.dcl b/week4/mart/StdSet.dcl
new file mode 100644
index 0000000..6cad7f1
--- /dev/null
+++ b/week4/mart/StdSet.dcl
@@ -0,0 +1,25 @@
+definition module StdSet
+
+import StdClass
+
+:: Set a
+
+toSet :: [a] -> Set a | Eq a
+fromSet :: (Set a) -> [a]
+
+isEmptySet :: (Set a) -> Bool
+isDisjoint :: (Set a) (Set a) -> Bool | Eq a
+isSubset :: (Set a) (Set a) -> Bool | Eq a
+isStrictSubset :: (Set a) (Set a) -> Bool | Eq a
+memberOfSet :: a (Set a) -> Bool | Eq a
+union :: (Set a) (Set a) -> Set a | Eq a
+intersection :: (Set a) (Set a) -> Set a | Eq a
+nrOfElements :: (Set a) -> Int
+without :: (Set a) (Set a) -> Set a | Eq a
+
+product :: (Set a) (Set b) -> Set (a,b)
+
+instance zero (Set a)
+instance == (Set a) | Eq a
+
+powerSet :: (Set a) -> Set (Set a)
diff --git a/week4/mart/StdSet.icl b/week4/mart/StdSet.icl
new file mode 100644
index 0000000..a14e6ba
--- /dev/null
+++ b/week4/mart/StdSet.icl
@@ -0,0 +1,56 @@
+implementation module StdSet
+
+import StdEnv
+import StdClass
+
+:: Set a = Set [a]
+
+toSet :: [a] -> Set a | Eq a
+toSet s = Set (removeDup s)
+
+fromSet :: (Set a) -> [a]
+fromSet (Set s) = s
+
+isEmptySet :: (Set a) -> Bool
+isEmptySet s = isEmpty (fromSet s)
+
+isDisjoint :: (Set a) (Set a) -> Bool | Eq a
+isDisjoint s1 s2 = nrOfElements (intersection s1 s2) == 0
+
+isSubset :: (Set a) (Set a) -> Bool | Eq a
+isSubset s1 s2 = nrOfElements s1 == nrOfElements (intersection s1 s2)
+
+isStrictSubset :: (Set a) (Set a) -> Bool | Eq a
+isStrictSubset s1 s2 = isSubset s1 s2 && nrOfElements s1 < nrOfElements s2
+
+memberOfSet :: a (Set a) -> Bool | Eq a
+memberOfSet a (Set []) = False
+memberOfSet a (Set [x:xs]) = a == x || memberOfSet a (Set xs)
+
+union :: (Set a) (Set a) -> Set a | Eq a
+union (Set s1) (Set s2) = toSet (s1 ++ s2)
+
+intersection :: (Set a) (Set a) -> Set a | Eq a
+intersection (Set s1) s2 = Set [e \\ e <- s1 | memberOfSet e s2]
+
+nrOfElements :: (Set a) -> Int
+nrOfElements s = length (fromSet s)
+
+without :: (Set a) (Set a) -> Set a | Eq a
+without (Set s1) s2 = Set [e \\ e <- s1 | not (memberOfSet e s2)]
+
+product :: (Set a) (Set b) -> Set (a,b)
+product (Set s1) (Set s2) = Set [(e1, e2) \\ e1 <- s1, e2 <- s2]
+
+instance zero (Set a)
+where zero = Set []
+
+instance == (Set a) | Eq a
+where (==) s1 s2 = isSubset s1 s2 && isSubset s2 s1
+
+powerSet :: (Set a) -> Set (Set a)
+powerSet (Set a) = Set [(Set x) \\ x <- powerSet2 a]
+where
+ powerSet2 :: [a] -> [[a]]
+ powerSet2 [] = [[]]
+ powerSet2 [e:xs] = (powerSet2 xs) ++ [[e:x] \\ x <- powerSet2 xs]