Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- {-# LANGUAGE RankNTypes #-}
- module Main where
- import qualified Data.List as List
- import qualified Data.Set as Set
- {- TYPES: -}
- -- PQ new push pop
- -- by intention there is no build-in way to tell if the queue is empty
- data PriorityQueue q t = PQ (q t) (t -> q t -> q t) (q t -> (t, q t))
- -- there is a concrete way for a particular queue, e.g. List.null
- type ListPriorityQueue t = PriorityQueue [] t
- -- but there is no method in the abstract setting
- newtype AbstractPriorityQueue q = APQ (forall t. Ord t => PriorityQueue q t)
- {- SOLUTIONS: -}
- -- the basic version
- list_selection_sort :: ListPriorityQueue t -> [t] -> [t]
- list_selection_sort (PQ new push pop) list = List.unfoldr mypop (List.foldr push new list)
- where
- mypop [] = Nothing -- this is possible because we know that the queue is represented by a list
- mypop ls = Just (pop ls)
- -- here we abstract the queue, so we need to keep the queue size ourselves
- abstract_selection_sort :: Ord t => AbstractPriorityQueue q -> [t] -> [t]
- abstract_selection_sort (APQ (PQ new push pop)) list = List.unfoldr mypop (List.foldr mypush (0,new) list)
- where
- mypush t (n, q) = (n+1, push t q)
- mypop (0, q) = Nothing
- mypop (n, q) = let (t, q') = pop q in Just (t, (n-1, q'))
- -- here we generalize the first solution to all the queues that allow checking if the queue is empty
- class EmptyCheckable q where
- is_empty :: q -> Bool
- generalized_selection_sort :: EmptyCheckable (q t) => PriorityQueue q t -> [t] -> [t]
- generalized_selection_sort (PQ new push pop) list = List.unfoldr mypop (List.foldr push new list)
- where
- mypop q | is_empty q = Nothing
- mypop q | otherwise = Just (pop q)
- {- EXAMPLES: -}
- -- priority queue based on lists
- priority_queue_1 :: Ord t => ListPriorityQueue t
- priority_queue_1 = PQ [] List.insert (\ls -> (head ls, tail ls))
- instance EmptyCheckable [t] where
- is_empty = List.null
- -- priority queue based on sets
- priority_queue_2 :: Ord t => PriorityQueue Set.Set t
- priority_queue_2 = PQ Set.empty Set.insert Set.deleteFindMin
- instance EmptyCheckable (Set.Set t) where
- is_empty = Set.null
- -- an arbitrary type and a queue specially designed for it
- data ABC = A | B | C deriving (Eq, Ord, Show)
- -- priority queue based on counting
- data PQ3 t = PQ3 Integer Integer Integer
- priority_queue_3 :: PriorityQueue PQ3 ABC
- priority_queue_3 = PQ new push pop
- where
- new = (PQ3 0 0 0)
- push A (PQ3 a b c) = (PQ3 (a+1) b c)
- push B (PQ3 a b c) = (PQ3 a (b+1) c)
- push C (PQ3 a b c) = (PQ3 a b (c+1))
- pop (PQ3 0 0 0) = undefined
- pop (PQ3 0 0 c) = (C, (PQ3 0 0 (c-1)))
- pop (PQ3 0 b c) = (B, (PQ3 0 (b-1) c))
- pop (PQ3 a b c) = (A, (PQ3 (a-1) b c))
- instance EmptyCheckable (PQ3 t) where
- is_empty (PQ3 0 0 0) = True
- is_empty _ = False
- {- MAIN: -}
- main :: IO ()
- main = do
- print $ list_selection_sort priority_queue_1 [2, 3, 1]
- -- print $ list_selection_sort priority_queue_2 [2, 3, 1] -- fail
- -- print $ list_selection_sort priority_queue_3 [B, C, A] -- fail
- print $ abstract_selection_sort (APQ priority_queue_1) [B, C, A] -- APQ hides the queue
- print $ abstract_selection_sort (APQ priority_queue_2) [B, C, A] -- behind the layer of abstraction
- -- print $ abstract_selection_sort (APQ priority_queue_3) [B, C, A] -- fail
- print $ generalized_selection_sort priority_queue_1 [2, 3, 1]
- print $ generalized_selection_sort priority_queue_2 [B, C, A]
- print $ generalized_selection_sort priority_queue_3 [B, C, A]-- power of generalization
- -- fail
- -- print $ let f q = (list_selection_sort q [2,3,1], list_selection_sort q [B,C,A])
- -- in f priority_queue_1
- -- power of abstraction (rank-n-types actually, but never mind)
- print $ let f q = (abstract_selection_sort q [2,3,1], abstract_selection_sort q [B,C,A])
- in f (APQ priority_queue_1)
- -- fail
- -- print $ let f q = (generalized_selection_sort q [2,3,1], generalized_selection_sort q [B,C,A])
- -- in f priority_queue_1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement