diff options
| author | Camil Staps | 2015-02-26 18:25:02 +0100 |
|---|---|---|
| committer | Camil Staps | 2015-02-26 18:25:02 +0100 |
| commit | 7c2b6a59cda7801fcf142bd1a7d4627595f8e5bf (patch) | |
| tree | e6ce3ae143234967e25bc5a24861ac9831e478d2 | |
| parent | 6.5 working (diff) | |
Added sorted list
| -rw-r--r-- | week3/camil/StdSortList.dcl | 18 | ||||
| -rw-r--r-- | week3/camil/StdSortList.icl | 60 | ||||
| -rw-r--r-- | week3/camil/StdSortListTest.icl | 107 |
3 files changed, 185 insertions, 0 deletions
diff --git a/week3/camil/StdSortList.dcl b/week3/camil/StdSortList.dcl new file mode 100644 index 0000000..46bd238 --- /dev/null +++ b/week3/camil/StdSortList.dcl @@ -0,0 +1,18 @@ +definition module StdSortList
+
+import StdClass
+
+:: SortList a
+
+newSortList :: SortList a // lege gesorteerde lijst
+memberSort :: a (SortList a) -> Bool | Eq, Ord a // is element van
+insertSort :: a (SortList a) -> SortList a | Ord a // voeg element toe
+removeFirst :: a (SortList a) -> SortList a | Eq, Ord a // verwijder eerste voorkomen
+removeAll :: a (SortList a) -> SortList a | Eq, Ord a // verwijder alle voorkomens
+elements :: (SortList a) -> [a] // geef alle elementen
+count :: (SortList a) -> Int // aantal elementen
+
+minimum :: (SortList a) -> a // huidige minimum waarde
+maximum :: (SortList a) -> a // huidige maximum waarde
+
+mergeSortList :: (SortList a) (SortList a) -> SortList a | Eq, Ord a // meng gesorteerde lijsten
diff --git a/week3/camil/StdSortList.icl b/week3/camil/StdSortList.icl new file mode 100644 index 0000000..759e915 --- /dev/null +++ b/week3/camil/StdSortList.icl @@ -0,0 +1,60 @@ +implementation module StdSortList
+
+import StdEnv
+
+:: SortList a :== [a]
+
+newSortList :: (SortList a)
+newSortList = []
+
+memberSort :: a (SortList a) -> Bool | Eq, Ord a // is element van
+memberSort _ [] = False
+memberSort m l
+ | hd l == m = True
+ | hd l > m = False
+ | otherwise = memberSort m (tl l)
+
+insertSort :: a (SortList a) -> SortList a | Ord a // voeg element toe
+insertSort m l = insertSort` newSortList m l
+where
+ insertSort` :: (SortList a) a (SortList a) -> (SortList a) | Ord a
+ insertSort` l1 m l2
+ | count l2 == 0 = l1 ++ [m]
+ | minimum l2 >= m = l1 ++ [m] ++ l2
+ | otherwise = insertSort` (l1 ++ [hd l2]) m (tl l2)
+
+removeFirst :: a (SortList a) -> SortList a | Eq, Ord a // verwijder eerste voorkomen
+removeFirst m l = removeFirst` newSortList m l
+where
+ removeFirst` :: (SortList a) a (SortList a) -> (SortList a) | Eq, Ord a
+ removeFirst` l1 m l2
+ | count l2 == 0 = l1
+ | minimum l2 > m = l1 ++ l2
+ | minimum l2 == m = l1 ++ tl l2
+ | otherwise = removeFirst` (l1 ++ [hd l2]) m (tl l2)
+
+removeAll :: a (SortList a) -> SortList a | Eq, Ord a // verwijder alle voorkomens
+removeAll m l = removeAll` newSortList m l
+where
+ removeAll` :: (SortList a) a (SortList a) -> (SortList a) | Eq, Ord a
+ removeAll` l1 m l2
+ | count l2 == 0 = l1
+ | minimum l2 > m = l1 ++ l2
+ | minimum l2 == m = removeAll` l1 m (tl l2)
+ | otherwise = removeAll` (l1 ++ [hd l2]) m (tl l2)
+
+elements :: (SortList a) -> [a] // geef alle elementen
+elements l = l
+
+count :: (SortList a) -> Int // aantal elementen
+count l = length l
+
+minimum :: (SortList a) -> a // huidige minimum waarde
+minimum l = hd l
+
+maximum :: (SortList a) -> a // huidige maximum waarde
+maximum l = last l
+
+mergeSortList :: (SortList a) (SortList a) -> SortList a | Eq, Ord a // meng gesorteerde lijsten
+mergeSortList l1 [] = l1
+mergeSortList l1 l2 = mergeSortList (insertSort (hd l2) l1) (tl l2)
diff --git a/week3/camil/StdSortListTest.icl b/week3/camil/StdSortListTest.icl new file mode 100644 index 0000000..411f7ca --- /dev/null +++ b/week3/camil/StdSortListTest.icl @@ -0,0 +1,107 @@ +module StdSortListTest
+
+/* Test module StdSortList
+ Voor werken met Gast:
+ (*) gebruik Environment 'Gast'
+ (*) zet Project Options op 'Basic Values Only' en '16M' Maximum Heap Size.
+*/
+
+import gast
+import GenLexOrd
+import StdSortList
+
+Start = testn 10000
+ (\n` n2` m -> let n = lst2slst (cast [A,B,C] n` )
+ n2 = lst2slst (cast [A,B,C] n2`)
+ in
+ leeg_is_leeg /\
+ count_matches_elems n /\
+ is_sorted_elems n /\
+ member_is_member n m /\
+ member_na_insert n m /\
+ member_na_remove n m /\
+ insert_remove_invariant n m /\
+ minimum_property n /\
+ maximum_property n /\
+ merge_additive n n2 /\
+ merge_member n n2 m /\
+ True
+ )
+
+:: Enum = A | B | C
+
+derive bimap []
+derive ggen Enum
+derive genShow Enum
+derive gEq Enum
+derive gLexOrd Enum
+instance == Enum where (==) x y = gEq{|*|} x y
+instance < Enum where (<) x y = gEq{|*|} (gLexOrd{|*|} x y) LT
+
+// clean should have something like this!
+cast :: a a -> a
+cast _ x = x
+
+leeg_is_leeg :: Property
+leeg_is_leeg
+ = name "leeg_is_leeg"
+ (count newSortList == 0)
+
+count_matches_elems :: (SortList a) -> Property | Eq, Ord a
+count_matches_elems n
+ = name "count_matches_elems"
+ (length (elements n) == count n)
+
+is_sorted_elems :: (SortList a) -> Property | Eq, Ord a
+is_sorted_elems n
+ = name "is_sorted_elems"
+ (isSorted (elements n))
+ where isSorted lst = and [ x<=y \\ x<-lst & y<-tl lst ]
+
+member_is_member :: (SortList a) a -> Property | Eq, Ord a
+member_is_member lst e
+ = name "member_is_member"
+ ((isMember e (elements lst)) <==> (memberSort e lst))
+
+member_na_insert :: (SortList a) a -> Property | Eq, Ord a
+member_na_insert lst e
+ = name "member_na_insert"
+ (memberSort e (insertSort e lst))
+
+member_na_remove :: (SortList a) a -> Property | Eq, Ord a
+member_na_remove lst e
+ = name "member_na_remove"
+ (not (memberSort e (removeAll e lst)))
+
+insert_remove_invariant :: (SortList a) a -> Property | Eq, Ord a
+insert_remove_invariant lst e
+ = name "insert_remove_invariant"
+ (memberSort e lst <==> memberSort e lst`)
+ where lst` = removeFirst e (insertSort e lst)
+
+minimum_property :: (SortList a) -> Property | Eq,Ord a
+minimum_property n
+ = name "minimum_property"
+ (count n > 0 ==> (memberSort min n /\ all ((<=) min) (elements n)))
+ where min = minimum n
+
+maximum_property :: (SortList a) -> Property | Eq,Ord a
+maximum_property n
+ = name "maximum_property"
+ (count n > 0 ==> (memberSort max n /\ all ((>=) max) (elements n)))
+ where max = maximum n
+
+merge_member :: (SortList a) (SortList a) a -> Property | Eq,Ord a
+merge_member n m e
+ = name "merge_member"
+ (memberSort e nm <==> (memberSort e n \/ memberSort e m))
+ where nm = mergeSortList n m
+
+merge_additive :: (SortList a) (SortList a) -> Property | Eq,Ord a
+merge_additive n m
+ = name "merge_additive"
+ (count n + count m == count nm)
+ where nm = mergeSortList n m
+
+lst2slst :: [a] -> SortList a | Eq,Ord a
+lst2slst xs = seq (map insertSort xs) newSortList
|