fp1/week3/camil/StdSortList.icl

   1 // Ik kreeg het alleen werkend door de .dcl ook aan te passen.
   2 // Met een record dat het maximum bijhoudt moet je er namelijk vanuit kunnen gaan dat zero gedefinieerd is voor type a.
   3
   4 implementation module StdSortList
   5
   6 import StdEnv
   7
   8 ::  SortList a = {list :: [a], max :: a}
   9
  10 newSortList   :: (SortList a) | zero a
  11 newSortList = {list=[], max=zero}
  12
  13 memberSort    :: a (SortList a) -> Bool       | Eq, Ord a      // is element van
  14 memberSort _ {list=[],max=_} = False
  15 memberSort m l
  16     | minimum l == m = True
  17     | minimum l > m = False
  18     | otherwise = memberSort m {list=(tl l.list),max=l.max}
  19
  20 insertSort    :: a (SortList a) -> SortList a | Ord a          // voeg element toe
  21 insertSort m l = insertSort` {list=[],max=l.max} m l
  22 where
  23     insertSort` :: (SortList a) a (SortList a) -> (SortList a) | Ord a
  24     insertSort` l1 m l2
  25         | count l2 == 0 = {list=l1.list ++ [m], max=m}
  26         | minimum l2 >= m = {list=l1.list ++ [m] ++ l2.list, max=l2.max}
  27         | otherwise = insertSort` {list=l1.list ++ [hd l2.list], max=hd l2.list} m {list=(tl l2.list), max=l2.max}
  28
  29 removeFirst   :: a (SortList a) -> SortList a | Eq, Ord, zero a      // verwijder eerste voorkomen
  30 removeFirst m l = removeFirst` newSortList m l
  31 where
  32     removeFirst` :: (SortList a) a (SortList a) -> (SortList a) | Eq, Ord a
  33     removeFirst` l1 m l2
  34         | count l2 == 0 = l1
  35         | minimum l2 > m = {list=l1.list ++ l2.list, max=l2.max}
  36         | minimum l2 == m && count l2 == 1 = {list=l1.list ++ tl l2.list, max=l1.max}
  37         | minimum l2 == m = {list=l1.list ++ tl l2.list, max=l2.max}
  38         | otherwise = removeFirst` {list=(l1.list ++ [hd l2.list]),max=hd l2.list} m {list=(tl l2.list), max=l2.max}
  39
  40 removeAll     :: a (SortList a) -> SortList a | Eq, Ord, zero a      // verwijder alle voorkomens
  41 removeAll m l = removeAll` newSortList m l
  42 where
  43     removeAll` :: (SortList a) a (SortList a) -> (SortList a) | Eq, Ord a
  44     removeAll` l1 m l2
  45         | count l2 == 0 = l1
  46         | minimum l2 > m = {list=l1.list ++ l2.list, max=l2.max}
  47         | minimum l2 == m = removeAll` l1 m {list=tl l2.list, max=l2.max}
  48         | otherwise = removeAll` {list=l1.list ++ [hd l2.list], max=hd l2.list} m {list=tl l2.list,max=l2.max}
  49
  50 elements      ::   (SortList a) -> [a]                         // geef alle elementen
  51 elements l = l.list
  52
  53 count         ::   (SortList a) -> Int                         // aantal elementen
  54 count l = length l.list
  55
  56 minimum       ::   (SortList a) -> a                           // huidige minimum waarde
  57 minimum l = hd l.list
  58
  59 maximum       ::   (SortList a) -> a                           // huidige maximum waarde
  60 maximum l = l.max
  61
  62 mergeSortList :: (SortList a) (SortList a) -> SortList a | Eq, Ord, zero a // meng gesorteerde lijsten
  63 mergeSortList l1 {list=[],max=_} = l1
  64 mergeSortList l1 l2 = mergeSortList (insertSort (hd l2.list) l1) {list=tl l2.list,max=l2.max}