packages feed

heap 0.3 → 0.3.1

raw patch · 4 files changed

+231/−255 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

Data/Heap.hs view
@@ -12,29 +12,28 @@ -- This module is best imported @qualified@ in order to prevent name clashes -- with other modules. module Data.Heap-	(-	-- * Heap type-	  Heap, MinHeap, MaxHeap-	, HeapPolicy(..), MinPolicy, MaxPolicy-	-- * Query-	, null, isEmpty, size, head, tail, extractHead-	-- * Construction-	, empty, singleton, insert-	-- * Union-	, union, unions-	-- * Filter-	, filter, partition-	-- * Subranges-	, take, drop, splitAt-	, takeWhile, span, break-	-- * Conversion-	-- ** List-	, fromList, toList, elems-	-- ** Ordered list-	, fromAscList, toAscList-	-- * Debugging-	, check-	) where+  ( -- * Heap type+    Heap, MinHeap, MaxHeap+  , HeapPolicy(..), MinPolicy, MaxPolicy+    -- * Query+  , null, isEmpty, size, head, tail, extractHead+    -- * Construction+  , empty, singleton, insert+    -- * Union+  , union, unions+    -- * Filter+  , filter, partition+    -- * Subranges+  , take, drop, splitAt+  , takeWhile, span, break+    -- * Conversion+    -- ** List+  , fromList, toList, elems+    -- ** Ordered list+  , fromAscList, toAscList+    -- * Debugging+  , check+  ) where  import Data.Foldable (Foldable(foldMap)) import Data.List (foldl')@@ -42,262 +41,232 @@ import Prelude hiding (break, drop, filter, head, null, tail, span, splitAt, take, takeWhile) import Text.Read --- |--- The basic 'Heap' type.+-- | The basic 'Heap' type. data Heap p a-	= Empty-	| Tree {-# UNPACK #-} !Int a !(Heap p a) !(Heap p a)+  = Empty+  | Tree {-# UNPACK #-} !Int a !(Heap p a) !(Heap p a) --- |--- A 'Heap' which will always extract the minimum first.+-- | A 'Heap' which will always extract the minimum first. type MinHeap a = Heap MinPolicy a --- |--- A 'Heap' with inverted order: The maximum will be extracted first.+-- | A 'Heap' with inverted order: The maximum will be extracted first. type MaxHeap a = Heap MaxPolicy a  instance (Show a) => Show (Heap p a) where-	show h = "fromList " ++ (show . toList) h+  show h = "fromList " ++ (show . toList) h  instance (HeapPolicy p a) => Eq (Heap p a) where-	h1 == h2 = EQ == compare h1 h2+  h1 == h2 = EQ == compare h1 h2  instance (HeapPolicy p a) => Ord (Heap p a) where-	compare h1 h2 = compare' (toAscList h1) (toAscList h2)-		where-		compare' [] [] = EQ-		compare' [] _  = LT-		compare' _  [] = GT-		compare' (x:xs) (y:ys) = case heapCompare (policy h1) x y of-			EQ -> compare' xs ys-			c  -> c+  compare h1 h2 = compare' (toAscList h1) (toAscList h2)+    where+    compare' [] [] = EQ+    compare' [] _  = LT+    compare' _  [] = GT+    compare' (x:xs) (y:ys) = case heapCompare (policy h1) x y of+      EQ -> compare' xs ys+      c  -> c  instance (HeapPolicy p a) => Monoid (Heap p a) where-	mempty  = empty-	mappend = union-	mconcat = unions+  mempty  = empty+  mappend = union+  mconcat = unions  instance Foldable (Heap p) where-	foldMap _ Empty          = mempty-	foldMap f (Tree _ x l r) = foldMap f l `mappend` f x `mappend` foldMap f r+  foldMap _ Empty          = mempty+  foldMap f (Tree _ x l r) = foldMap f l `mappend` f x `mappend` foldMap f r  instance (HeapPolicy p a, Read a) => Read (Heap p a) where #ifdef __GLASGOW_HASKELL__-	readPrec = parens $ prec 10 $ do-		Ident "fromList" <- lexP-		xs <- readPrec-		return (fromList xs)-	readListPrec = readListPrecDefault+  readPrec = parens $ prec 10 $ do+    Ident "fromList" <- lexP+    xs               <- readPrec+    return (fromList xs)+  readListPrec = readListPrecDefault #else-	readsPrec p = readParen (p > 10) $ \r -> do-		("fromList", s) <- lex r-		(xs, t) <- reads s-		return (fromList xs, t)+  readsPrec p = readParen (p > 10) $ \r -> do+    ("fromList", s) <- lex r+    (xs, t)         <- reads s+    return (fromList xs, t) #endif --- |--- The 'HeapPolicy' class defines an order on the elements contained within+-- | The 'HeapPolicy' class defines an order on the elements contained within -- a 'Heap'. class HeapPolicy p a where-	-- |-	-- Compare two elements, just like 'compare' of the 'Ord' class,-	-- so this function has to define a mathematical ordering.-	-- When using a 'HeapPolicy' for a 'Heap', the minimal value-	-- (defined by this order) will be the 'head' of the 'Heap'.-	heapCompare :: p    -- ^ /Must not be evaluated/.-		-> a        -- ^ Must be compared to 3rd parameter.-		-> a        -- ^ Must be compared to 2nd parameter.-		-> Ordering -- ^ Result of the comparison.+  -- |+  -- Compare two elements, just like 'compare' of the 'Ord' class,+  -- so this function has to define a mathematical ordering.+  -- When using a 'HeapPolicy' for a 'Heap', the minimal value+  -- (defined by this order) will be the 'head' of the 'Heap'.+  heapCompare :: p    -- ^ /Must not be evaluated/.+    -> a        -- ^ Must be compared to 3rd parameter.+    -> a        -- ^ Must be compared to 2nd parameter.+    -> Ordering -- ^ Result of the comparison. --- |--- Policy type for a 'MinHeap'.+-- | Policy type for a 'MinHeap'. data MinPolicy  instance (Ord a) => HeapPolicy MinPolicy a where-	heapCompare = const compare+  heapCompare = const compare --- |--- Policy type for a 'MaxHeap'+-- | Policy type for a 'MaxHeap' data MaxPolicy  instance (Ord a) => HeapPolicy MaxPolicy a where-	heapCompare = const (flip compare)+  heapCompare = const (flip compare) --- |--- /O(1)/. Is the 'Heap' empty?+-- | /O(1)/. Is the 'Heap' empty? null :: Heap p a -> Bool null Empty = True null _     = False --- |--- /O(1)/. Is the 'Heap' empty?+-- | /O(1)/. Is the 'Heap' empty? isEmpty :: Heap p a -> Bool isEmpty = null --- |--- /O(1)/. Calculate the rank of a 'Heap'.+-- | /O(1)/. Calculate the rank of a 'Heap'. rank :: Heap p a -> Int rank Empty          = 0 rank (Tree r _ _ _) = r --- |--- Gets the default policy instance for a 'Heap' that can be the first+-- | Gets the default policy instance for a 'Heap' that can be the first -- parameter of 'heapCompare'. This function always returns 'undefined'. policy :: Heap p a -> p policy = const undefined --- |--- /O(n)/. The number of elements in the 'Heap'.+-- | /O(n)/. The number of elements in the 'Heap'. size :: (Num n) => Heap p a -> n size Empty          = 0 size (Tree _ _ l r) = 1 + size l + size r --- |--- /O(1)/. Finds the minimum (depending on the 'HeapPolicy') of the 'Heap'.+-- | /O(1)/. Finds the minimum (depending on the 'HeapPolicy') of the 'Heap'. head :: (HeapPolicy p a) => Heap p a -> a head = fst . extractHead --- |--- /O(log n)/. Delete the minimum (depending on the 'HeapPolicy')+-- | /O(log n)/. Delete the minimum (depending on the 'HeapPolicy') -- from the 'Heap'. tail :: (HeapPolicy p a) => Heap p a -> Heap p a tail = snd . extractHead --- |--- /O(log n)/. Find the minimum (depending on the 'HeapPolicy') and+-- | /O(log n)/. Find the minimum (depending on the 'HeapPolicy') and -- delete it from the 'Heap'. This function is undefined for an -- empty 'Heap'. extractHead :: (HeapPolicy p a) => Heap p a -> (a, Heap p a) extractHead Empty          = error "empty Heap" extractHead (Tree _ x l r) = (x, union l r) --- |--- /O(1)/. Constructs an empty 'Heap'.+-- | /O(1)/. Constructs an empty 'Heap'. empty :: Heap p a empty = Empty --- |--- /O(1)/. Create a singleton 'Heap'.+-- | /O(1)/. Create a singleton 'Heap'. singleton :: a -> Heap p a singleton x = Tree 1 x empty empty --- |--- /O(log n)/. Insert an element in the 'Heap'.+-- | /O(log n)/. Insert an element in the 'Heap'. insert :: (HeapPolicy p a) => a -> Heap p a -> Heap p a insert x h = union h (singleton x) --- |--- Take the lowest @n@ elements in ascending order of the--- 'Heap' (according to the 'HeapPolicy').+-- | Take the lowest @n@ elements in ascending order of the 'Heap'+-- (according to the 'HeapPolicy'). take :: (HeapPolicy p a) => Int -> Heap p a -> [a] take n = fst . (splitAt n) --- |--- Remove the lowest (according to the 'HeapPolicy') @n@ elements+-- | Remove the lowest (according to the 'HeapPolicy') @n@ elements -- from the 'Heap'. drop :: (HeapPolicy p a) => Int -> Heap p a -> Heap p a drop n = snd . (splitAt n) --- |--- @'splitAt' n h@ returns an ascending list of the lowest @n@+-- | @'splitAt' n h@ returns an ascending list of the lowest @n@ -- elements of @h@ (according to its 'HeapPolicy') and a 'Heap' -- like @h@, lacking those elements. splitAt :: (HeapPolicy p a) => Int -> Heap p a -> ([a], Heap p a) splitAt _ Empty     = ([], empty) splitAt n heap@(Tree _ x l r)-	| n > 0     = let (xs, heap') = splitAt (n-1) (union l r) in (x:xs, heap')-	| otherwise = ([], heap)+  | n > 0     = let (xs, heap') = splitAt (n-1) (union l r) in (x:xs, heap')+  | otherwise = ([], heap) --- |--- @'takeWhile' p h@ lists the longest prefix of elements in ascending+-- | @'takeWhile' p h@ lists the longest prefix of elements in ascending -- order (according to its 'HeapPolicy') of @h@ that satisfy @p@. takeWhile :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> [a] takeWhile p = fst . (span p) --- |--- @'span' p h@ returns the longest prefix of elements in ascending+-- | @'span' p h@ returns the longest prefix of elements in ascending -- order (according to its 'HeapPolicy') of @h@ that satisfy @p@ and -- a 'Heap' like @h@, lacking those elements. span :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> ([a], Heap p a) span _ Empty        = ([], empty) span p heap@(Tree _ x l r)-	| p x       = let (xs, heap') = span p (union l r) in (x:xs, heap')-	| otherwise = ([], heap)--- |--- @'break' p h@ returns the longest prefix of elements in ascending+  | p x       = let (xs, heap') = span p (union l r) in (x:xs, heap')+  | otherwise = ([], heap)++-- | @'break' p h@ returns the longest prefix of elements in ascending -- order (according to its 'HeapPolicy') of @h@ that do /not/ satisfy @p@ -- and a 'Heap' like @h@, lacking those elements. break :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> ([a], Heap p a) break p = span (not . p) --- |--- /O(log max(n, m))/. The union of two 'Heap's.+-- | /O(log max(n, m))/. The union of two 'Heap's. union :: (HeapPolicy p a) => Heap p a -> Heap p a -> Heap p a union h Empty = h union Empty h = h-union heap1@(Tree _ x l1 r1) heap2@(Tree _ y l2 r2) = if LT == heapCompare (policy heap1) x y-	then makeT x l1 (union r1 heap2) -- keep smallest number on top and merge the other-	else makeT y l2 (union r2 heap1) -- heap into the right branch, it's shorter+union heap1@(Tree _ x l1 r1) heap2@(Tree _ y l2 r2) =+  if LT == heapCompare (policy heap1) x y+    then makeT x l1 (union r1 heap2) -- keep smallest number on top and merge the other+    else makeT y l2 (union r2 heap1) -- heap into the right branch, it's shorter --- |--- Combines a value @x@ and two 'Heap's to one 'Heap'. Therefore, @x@ has to+-- | Combines a value @x@ and two 'Heap's to one 'Heap'. Therefore, @x@ has to -- be less or equal the minima (depending on the 'HeapPolicy') of both -- 'Heap' parameters. /The precondition is not checked/. makeT :: a -> Heap p a -> Heap p a -> Heap p a makeT x a b = let-	ra = rank a-	rb = rank b-	in if ra > rb-		then Tree (rb + 1) x a b-		else Tree (ra + 1) x b a+  ra = rank a+  rb = rank b+  in if ra > rb+    then Tree (rb + 1) x a b+    else Tree (ra + 1) x b a --- |--- Builds the union over all given 'Heap's.+-- | Builds the union over all given 'Heap's. unions :: (HeapPolicy p a) => [Heap p a] -> Heap p a unions = foldl' union empty --- |--- Removes all elements from a given 'Heap' that do not fulfil the+-- | Removes all elements from a given 'Heap' that do not fulfil the -- predicate. filter :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> Heap p a filter p = fst . (partition p)  {-# RULES-	"filter/filter" forall p1 p2 h. filter p2 (filter p1 h) = filter (\x -> p1 x && p2 x) h+  "filter/filter" forall p1 p2 h. filter p2 (filter p1 h) = filter (\x -> p1 x && p2 x) h   #-} --- |--- Partition the 'Heap' into two. @'partition' p h = (h1, h2)@:+-- | Partition the 'Heap' into two. @'partition' p h = (h1, h2)@: -- All elements in @h1@ fulfil the predicate @p@, those in @h2@ don't. -- @'union' h1 h2 = h@. partition :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> (Heap p a, Heap p a)-partition _ Empty   = (empty, empty)+partition _ Empty = (empty, empty) partition p (Tree _ x l r)-	| p x       = (makeT x l1 r1, union l2 r2)-	| otherwise = (union l1 r1, makeT x l2 r2)-	where-	(l1, l2) = partition p l-	(r1, r2) = partition p r+  | p x       = (makeT x l1 r1, union l2 r2)+  | otherwise = (union l1 r1, makeT x l2 r2)+  where+  (l1, l2) = partition p l+  (r1, r2) = partition p r --- |--- Builds a 'Heap' from the given elements.+-- | Builds a 'Heap' from the given elements. -- You may want to use 'fromAscList', if you have a sorted list. fromList :: (HeapPolicy p a) => [a] -> Heap p a fromList = unions . (map singleton) --- |--- /O(n)/. Lists elements of the 'Heap' in no specific order.+-- | /O(n)/. Lists elements of the 'Heap' in no specific order. toList :: Heap p a -> [a] toList Empty          = [] toList (Tree _ x l r) = x : toList l ++ toList r --- |--- /O(n)/. Lists elements of the 'Heap' in no specific order.+-- | /O(n)/. Lists elements of the 'Heap' in no specific order. elems :: Heap p a -> [a] elems = toList --- |--- /O(n)/. Creates a 'Heap' from an ascending list. Note that the list+-- | /O(n)/. Creates a 'Heap' from an ascending list. Note that the list -- has to be ascending corresponding to the 'HeapPolicy', not to its -- 'Ord' instance declaration (if there is one). -- /The precondition is not checked/.@@ -306,31 +275,30 @@ --fromAscList (x:xs) = Tree 1 x (fromAscList xs) empty fromAscList = fromList -- Just as fast, but needs less memory. Why? --- |--- /O(n)/. Lists elements of the 'Heap' in ascending order (corresponding+-- | /O(n)/. Lists elements of the 'Heap' in ascending order (corresponding -- to the 'HeapPolicy'). toAscList :: (HeapPolicy p a) => Heap p a -> [a] toAscList Empty            = [] toAscList h@(Tree _ e l r) = e : mergeLists (toAscList l) (toAscList r)-	where-	mergeLists [] ys = ys-	mergeLists xs [] = xs-	mergeLists xs@(x:xs') ys@(y:ys') = if LT == heapCompare (policy h) x y-		then x : mergeLists xs' ys-		else y : mergeLists xs  ys'+  where+  mergeLists [] ys = ys+  mergeLists xs [] = xs+  mergeLists xs@(x:xs') ys@(y:ys') = if LT == heapCompare (policy h) x y+    then x : mergeLists xs' ys+    else y : mergeLists xs  ys' --- |--- Sanity checks for debugging. This includes checking the ranks and+-- | Sanity checks for debugging. This includes checking the ranks and -- the heap and leftist (the left rank is at least the right rank) properties. check :: (HeapPolicy p a) => Heap p a -> Bool-check Empty = True+check Empty                   = True check h@(Tree r x left right) = let-	leftRank  = rank left-	rightRank = rank right-	in (null left || LT /= heapCompare (policy h) (head left) x) -- heap property-		&& (null right || LT /= heapCompare (policy h) (head right) x) -- dito-		&& r == 1 + rightRank    -- rank == length of right spine-		&& leftRank >= rightRank -- leftist property-		&& check left-		&& check right+  leftRank  = rank left+  rightRank = rank right+  in+  (null left || LT /= heapCompare (policy h) (head left) x) -- heap property+    && (null right || LT /= heapCompare (policy h) (head right) x) -- dito+    && r == 1 + rightRank    -- rank == length of right spine+    && leftRank >= rightRank -- leftist property+    && check left+    && check right
Test/Heap.hs view
@@ -1,6 +1,6 @@-module Test.Heap (-	testHeap-) where+module Test.Heap+  ( testHeap+  ) where  import Data.Foldable (foldl) import Data.Heap as Heap@@ -10,59 +10,61 @@  testHeap :: IO () testHeap = do-	putStr "Leftist property of MinHeap Int: "-	quickCheck (leftistHeapProperty :: MinHeap Int -> Bool)-	putStr "Leftist property of MaxHeap Int: "-	quickCheck (leftistHeapProperty :: MaxHeap Int -> Bool)-	putStr "Size property:                   "-	quickCheck sizeProperty-	putStr "Order property:                  "-	quickCheck orderProperty-	putStr "head/tail property:              "-	quickCheck headTailProperty-	putStr "take/drop/splitAt                "-	quickCheck (takeDropSplitAtProperty :: Int -> MinHeap Int -> Bool)-	putStr "takeWhile/span/break             "-	quickCheck takeWhileSpanBreakProperty-	putStr "read . show === id               "-	quickCheck (readShowProperty :: MinHeap Int -> Bool)-	putStr "fold                             "-	quickCheck (foldProperty :: MaxHeap Int -> Bool)-	putStr "fromList vs. fromAscList         "-	quickCheck (fromListProperty :: [Int] -> Bool)-	putStr "toList === elems                 "-	quickCheck (toListProperty :: MaxHeap Int -> Bool)-	putStr "partition and filter             "-	quickCheck (partitionFilterProperty (\x -> x `mod` 2 == 0) :: MinHeap Int -> Bool)-	putStr "ordering property                "-	quickCheck (orderingProperty :: MinHeap Int -> MinHeap Int -> Bool)+  putStr "Leftist property of MinHeap Int: "+  quickCheck (leftistHeapProperty :: MinHeap Int -> Bool)+  putStr "Leftist property of MaxHeap Int: "+  quickCheck (leftistHeapProperty :: MaxHeap Int -> Bool)+  putStr "Size property:                   "+  quickCheck sizeProperty+  putStr "Order property:                  "+  quickCheck orderProperty+  putStr "head/tail property:              "+  quickCheck headTailProperty+  putStr "take/drop/splitAt                "+  quickCheck (takeDropSplitAtProperty :: Int -> MinHeap Int -> Bool)+  putStr "takeWhile/span/break             "+  quickCheck takeWhileSpanBreakProperty+  putStr "read . show === id               "+  quickCheck (readShowProperty :: MinHeap Int -> Bool)+  putStr "fold                             "+  quickCheck (foldProperty :: MaxHeap Int -> Bool)+  putStr "fromList vs. fromAscList         "+  quickCheck (fromListProperty :: [Int] -> Bool)+  putStr "toList === elems                 "+  quickCheck (toListProperty :: MaxHeap Int -> Bool)+  putStr "partition and filter             "+  quickCheck (partitionFilterProperty (\x -> x `mod` 2 == 0) :: MinHeap Int -> Bool)+  putStr "ordering property                "+  quickCheck (orderingProperty :: MinHeap Int -> MinHeap Int -> Bool)  instance (Arbitrary a, HeapPolicy p a) => Arbitrary (Heap p a) where-	arbitrary = do-		length <- choose (0, 100)-		list   <- vector length-		return (Heap.fromList list)-	coarbitrary heap = variant (Heap.size heap)+  arbitrary = do+    length <- choose (0, 100)+    list   <- vector length+    return (Heap.fromList list)  leftistHeapProperty :: (HeapPolicy p a) => Heap p a -> Bool leftistHeapProperty = Heap.check  sizeProperty :: Int -> Bool sizeProperty n = let-	n' = abs n-	h  = Heap.fromList [1..n'] :: MaxHeap Int-	in Heap.size h == n' && (if n' == 0 then Heap.isEmpty h && Heap.null h else True)+  n' = abs n+  h  = Heap.fromList [1..n'] :: MaxHeap Int+  in+  Heap.size h == n' && (if n' == 0 then Heap.isEmpty h && Heap.null h else True)  orderProperty :: Int -> [Int] -> Bool orderProperty n xs = let-		heap        = Heap.fromList xs :: MaxHeap Int-		(a,  b)     = List.splitAt n (sortBy (heapCompare (policy heap)) xs)-		(a', heap') = Heap.splitAt n heap-	in (Heap.fromList b == heap') && equal heap a a'-	where	equal _ [] [] = True-		equal _ _  [] = False-		equal _ [] _  = False-		equal h (x:xs) (y:ys) = EQ == heapCompare (policy h) x y+  heap        = Heap.fromList xs :: MaxHeap Int+  (a,  b)     = List.splitAt n (sortBy (heapCompare (policy heap)) xs)+  (a', heap') = Heap.splitAt n heap+  in+  (Heap.fromList b == heap') && equal heap a a'+  where+  equal _ [] [] = True+  equal _ _  [] = False+  equal _ [] _  = False+  equal h (x:xs) (y:ys) = EQ == heapCompare (policy h) x y  policy :: Heap p a -> p policy = const undefined@@ -70,31 +72,32 @@ headTailProperty :: [Int] -> Bool headTailProperty [] = True headTailProperty xs = let-		heap = fromList xs :: MaxHeap Int-		xs'  = sortBy (heapCompare (policy heap)) xs-	in Heap.head heap == List.head xs' && Heap.tail heap == (fromAscList (List.tail xs'))+  heap = fromList xs :: MaxHeap Int+  xs'  = sortBy (heapCompare (policy heap)) xs+  in+  Heap.head heap == List.head xs'+    && Heap.tail heap == (fromAscList (List.tail xs'))  takeDropSplitAtProperty :: (Ord a) => Int -> MinHeap a -> Bool takeDropSplitAtProperty n heap = let-	(begin, end) = Heap.splitAt n heap-	begin'       = Heap.take n heap-	end'         = Heap.drop n heap-	in-	begin == begin' && end == end'+  (begin, end) = Heap.splitAt n heap+  begin'       = Heap.take n heap+  end'         = Heap.drop n heap+  in+  begin == begin' && end == end'  takeWhileSpanBreakProperty :: Int -> Int -> Bool takeWhileSpanBreakProperty length index = let-	length'      = abs length-	index'       = abs index-	xs           = [1..(max length' index')]-	heap         = Heap.fromAscList xs :: MinHeap Int-	p1 x         = x <= index'-	p2 x         = x > index'-	(xs', heap') = Heap.span p1 heap-	in-	xs' == Heap.takeWhile p1 heap-		&& (xs', heap') == Heap.break p2 heap---		&& ([1..(min length' index')], Heap.fromAscList [(min index' length')..(max length' index')]) == (xs', heap')+  length'      = abs length+  index'       = abs index+  xs           = [1..(max length' index')]+  heap         = Heap.fromAscList xs :: MinHeap Int+  p1 x         = x <= index'+  p2 x         = x > index'+  (xs', heap') = Heap.span p1 heap+  in+  xs' == Heap.takeWhile p1 heap+    && (xs', heap') == Heap.break p2 heap  readShowProperty :: (HeapPolicy p a, Show a, Read a) => Heap p a -> Bool readShowProperty heap = heap == read (show heap)@@ -103,21 +106,27 @@ foldProperty heap = foldl (+) 0 heap == foldl (+) 0 (toList heap)  fromListProperty :: [Int] -> Bool-fromListProperty xs = let xs' = sort xs in (fromList xs' :: MinHeap Int) == (fromAscList xs' :: MinHeap Int)+fromListProperty xs = let+  xs' = sort xs+  in+  (fromList xs' :: MinHeap Int) == (fromAscList xs' :: MinHeap Int)  toListProperty :: (HeapPolicy p a, Eq a) => Heap p a -> Bool toListProperty heap = toList heap == elems heap  partitionFilterProperty :: (HeapPolicy p a) => (a -> Bool) -> Heap p a -> Bool partitionFilterProperty p heap = let-		(yes,  no)  = Heap.partition p heap-		(yes', no') = List.partition p (toList heap)-	in yes == fromList yes' && no == fromList no' && (Heap.filter p heap) == fromList yes'+  (yes,  no)  = Heap.partition p heap+  (yes', no') = List.partition p (toList heap)+  in+  yes == fromList yes'+    && no == fromList no'+    && (Heap.filter p heap) == fromList yes'  orderingProperty :: (Ord a) => MinHeap a -> MinHeap a -> Bool orderingProperty heap1 heap2 = let-	list1 = toAscList heap1-	list2 = toAscList heap2-	in-	compare heap1 heap2 == compare list1 list2+  list1 = toAscList heap1+  list2 = toAscList heap2+  in+  compare heap1 heap2 == compare list1 list2
Tests.lhs view
@@ -6,7 +6,6 @@ > import Test.Heap > > main :: IO ()-> main = do->	testHeap+> main = testHeap >
heap.cabal view
@@ -1,26 +1,26 @@ -Name:               heap-Version:            0.3-Stability:          beta+Name:                heap+Version:             0.3.1+Stability:           beta -Category:           Data Structures-Synopsis:           Heaps in Haskell-Description:        A flexible Haskell heap implementation+Category:            Data Structures+Synopsis:            Heaps in Haskell+Description:         A flexible Haskell heap implementation -License:            BSD3-License-File:       LICENSE-Copyright:          (c) 2008, Stephan Friedrichs+License:             BSD3+License-File:        LICENSE+Copyright:           (c) 2008, Stephan Friedrichs -Author:             Stephan Friedrichs-Maintainer:         Stephan Friedrichs (deduktionstheorem at web dot de)+Author:              Stephan Friedrichs+Maintainer:          Stephan Friedrichs (deduktionstheorem at web dot de) -Build-Type:         Custom-Cabal-Version:      >=1.2-Extra-Source-Files: Tests.lhs, Test/Heap.hs+Build-Type:          Simple+Cabal-Version:       >= 1.2+Extra-Source-Files:  Tests.lhs, Test/Heap.hs  Library-  Build-Depends:   base-  Exposed-Modules: Data.Heap-  ghc-options:     -Wall-  Extensions:      CPP+  Build-Depends:     base+  Exposed-Modules:   Data.Heap+  ghc-options:       -Wall+  Extensions:        CPP