/usr/lib/hugs/packages/fgl/Data/Graph/Inductive/Internal/Heap.hs is in libhugs-fgl-bundled 98.200609.21-5.3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | -- | Pairing heap implementation of dictionary
module Data.Graph.Inductive.Internal.Heap(
-- * Type
Heap(..),
-- * Operations
empty,unit,insert,merge,mergeAll,
isEmpty,findMin,deleteMin,splitMin,
build, toList, heapsort
) where
data Ord a => Heap a b = Empty | Node a b [Heap a b]
deriving Eq
showsHeap :: (Show a,Ord a,Show b) => Heap a b -> ShowS
showsHeap Empty = id
showsHeap (Node key val []) = shows key . (": "++) . shows val
showsHeap (Node key val hs) = shows key . (": "++) . shows val . (' ':) . shows hs
instance (Show a,Ord a,Show b) => Show (Heap a b) where
showsPrec _ d = showsHeap d
----------------------------------------------------------------------
-- MAIN FUNCTIONS
----------------------------------------------------------------------
empty :: Ord a => Heap a b
empty = Empty
unit :: Ord a => a -> b -> Heap a b
unit key val = Node key val []
insert :: Ord a => (a, b) -> Heap a b -> Heap a b
insert (key, val) h = merge (unit key val) h
merge :: Ord a => Heap a b -> Heap a b -> Heap a b
merge h Empty = h
merge Empty h = h
merge h@(Node key1 val1 hs) h'@(Node key2 val2 hs')
| key1<key2 = Node key1 val1 (h':hs)
| otherwise = Node key2 val2 (h:hs')
mergeAll:: Ord a => [Heap a b] -> Heap a b
mergeAll [] = Empty
mergeAll [h] = h
mergeAll (h:h':hs) = merge (merge h h') (mergeAll hs)
isEmpty :: Ord a => Heap a b -> Bool
isEmpty Empty = True
isEmpty _ = False
findMin :: Ord a => Heap a b -> (a, b)
findMin Empty = error "Heap.findMin: empty heap"
findMin (Node key val _) = (key, val)
deleteMin :: Ord a => Heap a b -> Heap a b
deleteMin Empty = Empty
deleteMin (Node _ _ hs) = mergeAll hs
splitMin :: Ord a => Heap a b -> (a,b,Heap a b)
splitMin Empty = error "Heap.splitMin: empty heap"
splitMin (Node key val hs) = (key,val,mergeAll hs)
----------------------------------------------------------------------
-- APPLICATION FUNCTIONS, EXAMPLES
----------------------------------------------------------------------
build :: Ord a => [(a,b)] -> Heap a b
build = foldr insert Empty
toList :: Ord a => Heap a b -> [(a,b)]
toList Empty = []
toList h = x:toList r
where (x,r) = (findMin h,deleteMin h)
heapsort :: Ord a => [a] -> [a]
heapsort = (map fst) . toList . build . map (\x->(x,x))
{-
l :: (Num a) => [a]
l = [6,9,2,13,6,8,14,9,10,7,5]
l' = reverse l
h1 = build $ map (\x->(x,x)) l
h1' = build $ map (\x->(x,x)) l'
s1 = heapsort l
s1' = heapsort l'
-}
|