Package: ghc6
Version: 6.4-4
I was experimenting with writing a functional heap when I got the following
error from ghc:
ghc-6.4: panic! (the `impossible' happened, GHC version 6.4):
ds_app_type PriorityQueue.PriorityQueue{tc r1qv} [k{tv a1vx}]
This seems to be tracable to a confusion of thought on my part about what I
was doing with a typeclass declaration, but I believe it's also a bug in ghc.
I've attached the file I was trying to compile; please don't laugh too hard
at the silly Haskell mistake I made ;-).
Daniel
--
/------------------- Daniel Burrows <[EMAIL PROTECTED]> ------------------\
| You are standing west of a white house. There is a mailbox here. |
\- Does your computer have Super Cow Powers? ------- http://www.debian.org -/
module PriorityQueue(
Heap,
PriorityQueue(..)
) where
import qualified Data.Set as Set
-- Implements Ye Olde Priority Queue. You probably want to import
-- this qualified.
-- A priority queue lets you create a set of objects and extract
-- the minimum element at any time.
class (Ord k) => PriorityQueue k where
empty :: PriorityQueue k
null :: PriorityQueue k -> Bool
insert :: k -> PriorityQueue k -> PriorityQueue k
-- Return the least queue element:
getMin :: PriorityQueue k -> k
-- Remove and discard the least queue element:
pop :: PriorityQueue k -> PriorityQueue k
-- Remove the least queue element and return it:
dequeue :: PriorityQueue k -> (k, PriorityQueue k)
dequeue pq = (getMin pq, pop pq)
contents :: PriorityQueue k -> [k]
contents pq = if (PriorityQueue.null pq) then []
else k:(contents pq') where (k, pq') = dequeue pq
instance (Ord k) => PriorityQueue (Set.Set k) where
empty = Set.empty
null = Set.null
insert = Set.insert
getMin = Set.findMin
pop = Set.deleteMin
dequeue = Set.deleteFindMin
contents = Set.toAscList
-- NB: should I use Int instead of Integer?
data (Ord k) => Heap k = EmptyHeap |
Heap {size :: !Integer,
key :: k,
left, right :: (Heap k)}
instance (Ord k) => PriorityQueue (Heap k) where
empty = EmptyHeap
null EmptyHeap = True
null _ = False
insert = insertHeap
getMin = minHeap
pop = popHeap
heapSize :: (Ord k) => Heap k -> Integer
heapSize EmptyHeap = 0
heapSize Heap {size = s} = s
insertHeap :: (Ord k) => Heap k -> k -> Heap k
insertHeap k EmptyHeap = Heap k EmptyHeap EmptyHeap
insertHeap k h@(Heap {key = k', size = s, left = h1', right = h2'}) =
if heapSize h1' < heapSize h2' then
Heap {key = minK, size = s+1, left = (recur h1'), right = h2'}
else
Heap {key = minK, size = s+1, left = h1', right = (recur h2')}
where recur h' = insertHeap maxK h'
minK = min k k'
maxK = max k k'
-- Empty heaps have no minimum (it's an error to even try to find one)
minHeap :: (Ord k) => Heap k -> k
minHeap (Heap {key = k}) = k
-- Note that this may unbalance the heap...but if you work out some
-- cases you'll see that the worst-case depth is still logarithmic in
-- the total number of operations, and that moreover if you are hit
-- with the worst-case cost, you always decrease the "badness" of the
-- tree. Another way of looking at it is that trying to rebalance the
-- tree up-front would (I believe) incur about as much cost as just
-- accepting that the tree might become temporarily unbalanced.
-- The key to the comment above is the observation that the tree never
-- increases in depth unless it is fully balanced...so if you have an
-- unbalanced tree and hit the worst-case, it must be because you
-- deleted an element on the longest path in the tree. Think
-- amortized analysis.
popHeap :: (Ord k) => Heap k -> Heap k
popHeap Heap {left = EmptyHeap, right = h'} = h'
popHeap Heap {right = EmptyHeap, left = h'} = h'
popHeap [EMAIL PROTECTED] {left = [EMAIL PROTECTED] {key = lk}, right = [EMAIL PROTECTED] {key = rk}} =
if lk < rk then
h {key = lk, size = (size h)-1, left=popHeap l}
else
h {key = rk, size = (size h)-1, right=popHeap r}
