Advertisement
Guest User

Untitled

a guest
Oct 19th, 2013
584
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. {-# LANGUAGE RankNTypes #-}
  2.  
  3. module Main where
  4.  
  5. import qualified Data.List as List
  6. import qualified Data.Set as Set
  7.  
  8. {- TYPES: -}
  9.  
  10. -- PQ new push pop
  11. -- by intention there is no build-in way to tell if the queue is empty
  12. data PriorityQueue q t = PQ (q t) (t -> q t -> q t) (q t -> (t, q t))
  13. -- there is a concrete way for a particular queue, e.g. List.null
  14. type ListPriorityQueue t = PriorityQueue [] t
  15. -- but there is no method in the abstract setting
  16. newtype AbstractPriorityQueue q = APQ (forall t. Ord t => PriorityQueue q t)
  17.  
  18.  
  19. {- SOLUTIONS: -}
  20.  
  21. -- the basic version
  22. list_selection_sort :: ListPriorityQueue t -> [t] -> [t]
  23. list_selection_sort (PQ new push pop) list = List.unfoldr mypop (List.foldr push new list)
  24.   where
  25.     mypop [] = Nothing -- this is possible because we know that the queue is represented by a list
  26.     mypop ls = Just (pop ls)
  27.  
  28.  
  29. -- here we abstract the queue, so we need to keep the queue size ourselves
  30. abstract_selection_sort :: Ord t => AbstractPriorityQueue q -> [t] -> [t]
  31. abstract_selection_sort (APQ (PQ new push pop)) list = List.unfoldr mypop (List.foldr mypush (0,new) list)
  32.   where
  33.     mypush t (n, q) = (n+1, push t q)
  34.     mypop (0, q) = Nothing
  35.     mypop (n, q) = let (t, q') = pop q in Just (t, (n-1, q'))
  36.  
  37.  
  38. -- here we generalize the first solution to all the queues that allow checking if the queue is empty
  39. class EmptyCheckable q where
  40.   is_empty :: q -> Bool
  41.  
  42. generalized_selection_sort :: EmptyCheckable (q t) => PriorityQueue q t -> [t] -> [t]
  43. generalized_selection_sort (PQ new push pop) list = List.unfoldr mypop (List.foldr push new list)
  44.   where
  45.     mypop q | is_empty q = Nothing
  46.     mypop q | otherwise  = Just (pop q)
  47.  
  48.  
  49. {- EXAMPLES: -}
  50.  
  51. -- priority queue based on lists
  52. priority_queue_1 :: Ord t => ListPriorityQueue t
  53. priority_queue_1 = PQ [] List.insert (\ls -> (head ls, tail ls))
  54. instance EmptyCheckable [t] where
  55.   is_empty = List.null
  56.  
  57. -- priority queue based on sets
  58. priority_queue_2 :: Ord t => PriorityQueue Set.Set t
  59. priority_queue_2 = PQ Set.empty Set.insert Set.deleteFindMin
  60. instance EmptyCheckable (Set.Set t) where
  61.   is_empty = Set.null
  62.  
  63. -- an arbitrary type and a queue specially designed for it
  64. data ABC = A | B | C deriving (Eq, Ord, Show)
  65.  
  66. -- priority queue based on counting
  67. data PQ3 t = PQ3 Integer Integer Integer
  68. priority_queue_3 :: PriorityQueue PQ3 ABC
  69. priority_queue_3 = PQ new push pop
  70.   where
  71.     new = (PQ3 0 0 0)
  72.     push A (PQ3 a b c) = (PQ3 (a+1) b c)
  73.     push B (PQ3 a b c) = (PQ3 a (b+1) c)
  74.     push C (PQ3 a b c) = (PQ3 a b (c+1))
  75.     pop (PQ3 0 0 0) = undefined
  76.     pop (PQ3 0 0 c) = (C, (PQ3 0 0 (c-1)))
  77.     pop (PQ3 0 b c) = (B, (PQ3 0 (b-1) c))
  78.     pop (PQ3 a b c) = (A, (PQ3 (a-1) b c))
  79.  
  80. instance EmptyCheckable (PQ3 t) where
  81.   is_empty (PQ3 0 0 0) = True
  82.   is_empty _ = False
  83.  
  84.  
  85. {- MAIN: -}
  86.  
  87. main :: IO ()
  88. main = do
  89.   print $ list_selection_sort priority_queue_1 [2, 3, 1]
  90.   -- print $ list_selection_sort priority_queue_2 [2, 3, 1] -- fail
  91.   -- print $ list_selection_sort priority_queue_3 [B, C, A] -- fail
  92.   print $ abstract_selection_sort (APQ priority_queue_1) [B, C, A] -- APQ hides the queue
  93.   print $ abstract_selection_sort (APQ priority_queue_2) [B, C, A] -- behind the layer of abstraction
  94.   -- print $ abstract_selection_sort (APQ priority_queue_3) [B, C, A] -- fail
  95.   print $ generalized_selection_sort priority_queue_1 [2, 3, 1]
  96.   print $ generalized_selection_sort priority_queue_2 [B, C, A]
  97.   print $ generalized_selection_sort priority_queue_3 [B, C, A]-- power of generalization
  98.  
  99.   -- fail
  100.   -- print $ let f q = (list_selection_sort q [2,3,1], list_selection_sort q [B,C,A])
  101.   --         in f priority_queue_1
  102.  
  103.   -- power of abstraction (rank-n-types actually, but never mind)
  104.   print $ let f q = (abstract_selection_sort q [2,3,1], abstract_selection_sort q [B,C,A])
  105.           in f (APQ priority_queue_1)
  106.  
  107.   -- fail
  108.   -- print $ let f q = (generalized_selection_sort q [2,3,1], generalized_selection_sort q [B,C,A])
  109.   --         in f priority_queue_1
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement