heaps 0.4 → 0.4.1
raw patch · 4 files changed
+29/−44 lines, 4 filesdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- .hlint.yaml +1/−1
- CHANGELOG.markdown +4/−0
- heaps.cabal +12/−11
- src/Data/Heap.hs +12/−32
.hlint.yaml view
@@ -1,4 +1,4 @@-- arguments: [--cpp-define=HLINT, --cpp-ansi]+- arguments: [-XCPP, --cpp-define=HLINT, --cpp-ansi] - ignore: {name: Use infix} - ignore: {name: Use fmap}
CHANGELOG.markdown view
@@ -1,3 +1,7 @@+0.4.1 [2024.12.04]+------------------+* Drop support for pre-8.0 versions of GHC.+ 0.4 [2021.02.17] ---------------- * `heaps` now always exports a `null` function that is specialized to `Heap`,
heaps.cabal view
@@ -1,5 +1,5 @@ name: heaps-version: 0.4+version: 0.4.1 license: BSD3 license-file: LICENSE author: Edward A. Kmett@@ -11,18 +11,19 @@ synopsis: Asymptotically optimal Brodal/Okasaki heaps. description: Asymptotically optimal Brodal\/Okasaki bootstrapped skew-binomial heaps from the paper <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 "Optimal Purely Functional Priority Queues">, extended with a 'Foldable' interface. copyright: (c) 2010-2015 Edward A. Kmett-tested-with: GHC == 7.0.4- , GHC == 7.2.2- , GHC == 7.4.2- , GHC == 7.6.3- , GHC == 7.8.4- , GHC == 7.10.3- , GHC == 8.0.2+tested-with: GHC == 8.0.2 , GHC == 8.2.2 , GHC == 8.4.4 , GHC == 8.6.5- , GHC == 8.8.3- , GHC == 8.10.1+ , GHC == 8.8.4+ , GHC == 8.10.4+ , GHC == 9.0.2+ , GHC == 9.2.8+ , GHC == 9.4.8+ , GHC == 9.6.6+ , GHC == 9.8.4+ , GHC == 9.10.1+ , GHC == 9.12.1 build-type: Simple cabal-version: >=1.10 extra-source-files:@@ -38,7 +39,7 @@ library exposed-modules: Data.Heap build-depends:- base >= 4 && < 6+ base >= 4.9 && < 6 hs-source-dirs: src ghc-options: -O2 -Wall default-language: Haskell2010
src/Data/Heap.hs view
@@ -1,8 +1,6 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE DeriveDataTypeable #-}-#if __GLASGOW_HASKELL__ >= 707 {-# LANGUAGE RoleAnnotations #-}-#endif ----------------------------------------------------------------------------- -- | -- Copyright : (c) Edward Kmett 2010-2015@@ -32,9 +30,9 @@ module Data.Heap ( -- * Heap Type- Heap -- instance Eq,Ord,Show,Read,Data,Typeable+ Heap -- instance Eq,Ord,Show,Read,Data -- * Entry type- , Entry(..) -- instance Eq,Ord,Show,Read,Data,Typeable+ , Entry(..) -- instance Eq,Ord,Show,Read,Data -- * Basic functions , empty -- O(1) :: Heap a , null -- O(1) :: Heap a -> Bool@@ -83,29 +81,18 @@ , span, dropWhile, takeWhile, break, filter, take, drop, splitAt , foldr, minimum, replicate, mapM , concatMap, null-#if MIN_VERSION_base(4,8,0) , traverse-#endif ) import Control.Monad (liftM)+import Data.Bifunctor import Data.Data (DataType, Constr, mkConstr, mkDataType, Fixity(Prefix), Data(..), constrIndex) import qualified Data.Foldable as F import Data.Function (on) import qualified Data.List as L import qualified Data.Traversable as T-import Data.Typeable (Typeable) import Text.Read -#if MIN_VERSION_base(4,8,0)-import Data.Bifunctor-#else-import Control.Applicative (Applicative)-import Data.Foldable (Foldable)-import Data.Monoid (Monoid(mappend, mempty))-import Data.Traversable (Traversable)-#endif--#if MIN_VERSION_base(4,9,0) && !(MIN_VERSION_base(4,11,0))+#if !(MIN_VERSION_base(4,11,0)) import Data.Semigroup (Semigroup(..)) #endif @@ -133,12 +120,8 @@ -- | A min-heap of values of type @a@. data Heap a = Empty- | Heap {-# UNPACK #-} !Int (a -> a -> Bool) {-# UNPACK #-} !(Tree a)- deriving Typeable--#if __GLASGOW_HASKELL__ >= 707+ | Heap {-# UNPACK #-} !Int (a -> a -> Bool) !(Tree a) type role Heap nominal-#endif instance Show a => Show (Heap a) where showsPrec _ Empty = showString "fromList []"@@ -374,7 +357,10 @@ | leq a a' = n | otherwise = Node r a' (rezip (left, heapify leq (Node r' a as') `Cons` right)) where- (left, Node r' a' as' `Cons` right) = minZ leq as+ -- (left, Node r' a' as' `Cons` right) = minZ leq as+ (left, r', a', as', right) = case minZ leq as of+ (left', Node r'' a'' as'' `Cons` right') -> (left', r'', a'', as'', right')+ _ -> error "Heap.heapify: empty zipper" -- | /O(n)/. Build a heap from a list of values.@@ -399,11 +385,9 @@ sort = F.toList . fromList {-# INLINE sort #-} -#if MIN_VERSION_base(4,9,0) instance Semigroup (Heap a) where (<>) = union {-# INLINE (<>) #-}-#endif instance Monoid (Heap a) where mempty = empty@@ -427,10 +411,8 @@ instance Foldable Heap where foldMap _ Empty = mempty foldMap f l@(Heap _ _ t) = f (root t) `mappend` F.foldMap f (deleteMin l)-#if MIN_VERSION_base(4,8,0) null = null length = size-#endif -- | /O(1)/. Is the heap empty? --@@ -676,10 +658,10 @@ { rank :: {-# UNPACK #-} !Int , root :: a , _forest :: !(Forest a)- } deriving (Show,Read,Typeable)+ } deriving (Show,Read) data Forest a = !(Tree a) `Cons` !(Forest a) | Nil- deriving (Show,Read,Typeable)+ deriving (Show,Read) infixr 5 `Cons` instance Functor Tree where@@ -783,16 +765,14 @@ -- ==> 'foldMap' 'payload' myHeap ≡ "HelloWorld!" -- @ data Entry p a = Entry { priority :: p, payload :: a }- deriving (Read,Show,Data,Typeable)+ deriving (Read,Show,Data) instance Functor (Entry p) where fmap f (Entry p a) = Entry p (f a) {-# INLINE fmap #-} -#if MIN_VERSION_base(4,8,0) instance Bifunctor Entry where bimap f g (Entry p a) = Entry (f p) (g a)-#endif instance Foldable (Entry p) where foldMap f (Entry _ a) = f a