week3/camil/StdSortList.icl

   1 implementation module StdSortList
   2
   3 import StdEnv
   4
   5 ::  SortList a :== [a]
   6
   7 newSortList   :: (SortList a)
   8 newSortList = []
   9
  10 memberSort    :: a (SortList a) -> Bool       | Eq, Ord a      // is element van
  11 memberSort _ [] = False
  12 memberSort m l
  13     | hd l == m = True
  14     | hd l > m = False
  15     | otherwise = memberSort m (tl l)
  16
  17 insertSort    :: a (SortList a) -> SortList a | Ord a          // voeg element toe
  18 insertSort m l = insertSort` newSortList m l
  19 where
  20     insertSort` :: (SortList a) a (SortList a) -> (SortList a) | Ord a
  21     insertSort` l1 m l2
  22         | count l2 == 0 = l1 ++ [m]
  23         | minimum l2 >= m = l1 ++ [m] ++ l2
  24         | otherwise = insertSort` (l1 ++ [hd l2]) m (tl l2)
  25
  26 removeFirst   :: a (SortList a) -> SortList a | Eq, Ord a      // verwijder eerste voorkomen
  27 removeFirst m l = removeFirst` newSortList m l
  28 where
  29     removeFirst` :: (SortList a) a (SortList a) -> (SortList a) | Eq, Ord a
  30     removeFirst` l1 m l2
  31         | count l2 == 0 = l1
  32         | minimum l2 > m = l1 ++ l2
  33         | minimum l2 == m = l1 ++ tl l2
  34         | otherwise = removeFirst` (l1 ++ [hd l2]) m (tl l2)
  35
  36 removeAll     :: a (SortList a) -> SortList a | Eq, Ord a      // verwijder alle voorkomens
  37 removeAll m l = removeAll` newSortList m l
  38 where
  39     removeAll` :: (SortList a) a (SortList a) -> (SortList a) | Eq, Ord a
  40     removeAll` l1 m l2
  41         | count l2 == 0 = l1
  42         | minimum l2 > m = l1 ++ l2
  43         | minimum l2 == m = removeAll` l1 m (tl l2)
  44         | otherwise = removeAll` (l1 ++ [hd l2]) m (tl l2)
  45
  46 elements      ::   (SortList a) -> [a]                         // geef alle elementen
  47 elements l = l
  48
  49 count         ::   (SortList a) -> Int                         // aantal elementen
  50 count l = length l
  51
  52 minimum       ::   (SortList a) -> a                           // huidige minimum waarde
  53 minimum l = hd l
  54
  55 maximum       ::   (SortList a) -> a                           // huidige maximum waarde
  56 maximum l = last l
  57
  58 mergeSortList :: (SortList a) (SortList a) -> SortList a | Eq, Ord a // meng gesorteerde lijsten
  59 mergeSortList l1 [] = l1
  60 mergeSortList l1 l2 = mergeSortList (insertSort (hd l2) l1) (tl l2)