heaps 0.3.6.1 → 0.4.1
raw patch · 8 files changed
Files
- .hlint.yaml +4/−0
- .travis.yml +0/−169
- CHANGELOG.markdown +21/−2
- HLint.hs +0/−2
- README.markdown +1/−1
- Warning.hs +0/−5
- heaps.cabal +17/−15
- src/Data/Heap.hs +69/−74
+ .hlint.yaml view
@@ -0,0 +1,4 @@+- arguments: [-XCPP, --cpp-define=HLINT, --cpp-ansi]++- ignore: {name: Use infix}+- ignore: {name: Use fmap}
− .travis.yml
@@ -1,169 +0,0 @@-# This Travis job script has been generated by a script via-#-# runghc make_travis_yml_2.hs '-o' '.travis.yml' '--ghc-head' '--irc-channel=irc.freenode.org#haskell-lens' '--no-no-tests-no-bench' '--no-unconstrained' '--allow-failure=7.0.4' '--allow-failure=7.2.2' '--doctest' 'cabal.project'-#-# For more information, see https://github.com/haskell-CI/haskell-ci-#-language: c-sudo: false--git:- submodules: false # whether to recursively clone submodules--notifications:- irc:- channels:- - "irc.freenode.org#haskell-lens"- skip_join: true- template:- - "\x0313heaps\x03/\x0306%{branch}\x03 \x0314%{commit}\x03 %{build_url} %{message}"--cache:- directories:- - $HOME/.cabal/packages- - $HOME/.cabal/store--before_cache:- - rm -fv $HOME/.cabal/packages/hackage.haskell.org/build-reports.log- # remove files that are regenerated by 'cabal update'- - rm -fv $HOME/.cabal/packages/hackage.haskell.org/00-index.*- - rm -fv $HOME/.cabal/packages/hackage.haskell.org/*.json- - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.cache- - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.tar- - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.tar.idx-- - rm -rfv $HOME/.cabal/packages/head.hackage--matrix:- include:- - compiler: "ghc-8.6.3"- # env: TEST=--disable-tests BENCH=--disable-benchmarks- addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.4,ghc-8.6.3], sources: [hvr-ghc]}}- - compiler: "ghc-8.4.4"- # env: TEST=--disable-tests BENCH=--disable-benchmarks- addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.4,ghc-8.4.4], sources: [hvr-ghc]}}- - compiler: "ghc-8.2.2"- # env: TEST=--disable-tests BENCH=--disable-benchmarks- addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.4,ghc-8.2.2], sources: [hvr-ghc]}}- - compiler: "ghc-8.0.2"- # env: TEST=--disable-tests BENCH=--disable-benchmarks- addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.4,ghc-8.0.2], sources: [hvr-ghc]}}- - compiler: "ghc-7.10.3"- # env: TEST=--disable-tests BENCH=--disable-benchmarks- addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.4,ghc-7.10.3], sources: [hvr-ghc]}}- - compiler: "ghc-7.8.4"- # env: TEST=--disable-tests BENCH=--disable-benchmarks- addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.4,ghc-7.8.4], sources: [hvr-ghc]}}- - compiler: "ghc-7.6.3"- # env: TEST=--disable-tests BENCH=--disable-benchmarks- addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.4,ghc-7.6.3], sources: [hvr-ghc]}}- - compiler: "ghc-7.4.2"- # env: TEST=--disable-tests BENCH=--disable-benchmarks- addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.4,ghc-7.4.2], sources: [hvr-ghc]}}- - compiler: "ghc-7.2.2"- # env: TEST=--disable-tests BENCH=--disable-benchmarks- addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.4,ghc-7.2.2], sources: [hvr-ghc]}}- - compiler: "ghc-7.0.4"- # env: TEST=--disable-tests BENCH=--disable-benchmarks- addons: {apt: {packages: [ghc-ppa-tools,cabal-install-2.4,ghc-7.0.4], sources: [hvr-ghc]}}- - compiler: "ghc-head"- env: GHCHEAD=true- addons: {apt: {packages: [ghc-ppa-tools,cabal-install-head,ghc-head], sources: [hvr-ghc]}}-- allow_failures:- - compiler: "ghc-head"- - compiler: "ghc-7.0.4"- - compiler: "ghc-7.2.2"--before_install:- - HC=${CC}- - HCPKG=${HC/ghc/ghc-pkg}- - unset CC- - export HLINTVER=2.0.9- - mkdir ~/.hlint- - curl -L https://github.com/ndmitchell/hlint/releases/download/v$HLINTVER/hlint-$HLINTVER-x86_64-linux.tar.gz | tar -xz --strip-components=1 -C ~/.hlint- - ROOTDIR=$(pwd)- - mkdir -p $HOME/.local/bin- - "PATH=~/.hlint:/opt/ghc/bin:/opt/ghc-ppa-tools/bin:$HOME/local/bin:$PATH"- - HCNUMVER=$(( $(${HC} --numeric-version|sed -E 's/([0-9]+)\.([0-9]+)\.([0-9]+).*/\1 * 10000 + \2 * 100 + \3/') ))- - echo $HCNUMVER--install:- - cabal --version- - echo "$(${HC} --version) [$(${HC} --print-project-git-commit-id 2> /dev/null || echo '?')]"- - BENCH=${BENCH---enable-benchmarks}- - TEST=${TEST---enable-tests}- - HADDOCK=${HADDOCK-true}- - UNCONSTRAINED=${UNCONSTRAINED-true}- - NOINSTALLEDCONSTRAINTS=${NOINSTALLEDCONSTRAINTS-false}- - GHCHEAD=${GHCHEAD-false}- - travis_retry cabal update -v- - "sed -i.bak 's/^jobs:/-- jobs:/' ${HOME}/.cabal/config"- - rm -fv cabal.project cabal.project.local- # Overlay Hackage Package Index for GHC HEAD: https://github.com/hvr/head.hackage- - |- if $GHCHEAD; then- sed -i 's/-- allow-newer: .*/allow-newer: *:base/' ${HOME}/.cabal/config- for pkg in $($HCPKG list --simple-output); do pkg=$(echo $pkg | sed 's/-[^-]*$//'); sed -i "s/allow-newer: /allow-newer: *:$pkg, /" ${HOME}/.cabal/config; done-- echo 'repository head.hackage' >> ${HOME}/.cabal/config- echo ' url: http://head.hackage.haskell.org/' >> ${HOME}/.cabal/config- echo ' secure: True' >> ${HOME}/.cabal/config- echo ' root-keys: 07c59cb65787dedfaef5bd5f987ceb5f7e5ebf88b904bbd4c5cbdeb2ff71b740' >> ${HOME}/.cabal/config- echo ' 2e8555dde16ebd8df076f1a8ef13b8f14c66bad8eafefd7d9e37d0ed711821fb' >> ${HOME}/.cabal/config- echo ' 8f79fd2389ab2967354407ec852cbe73f2e8635793ac446d09461ffb99527f6e' >> ${HOME}/.cabal/config- echo ' key-threshold: 3' >> ${HOME}/.cabal.config-- grep -Ev -- '^\s*--' ${HOME}/.cabal/config | grep -Ev '^\s*$'-- cabal new-update head.hackage -v- fi- - grep -Ev -- '^\s*--' ${HOME}/.cabal/config | grep -Ev '^\s*$'- - (cd /tmp && echo '' | cabal new-repl -w ${HC} --build-dep fail)- - if [ $HCNUMVER -ge 80000 ]; then cabal new-install -w ${HC} -j2 --symlink-bindir=$HOME/.local/bin doctest --constraint='doctest ==0.16.*'; fi- - "printf 'packages: \".\"\\n' > cabal.project"- - "printf 'write-ghc-environment-files: always\\n' >> cabal.project"- - touch cabal.project.local- - "if ! $NOINSTALLEDCONSTRAINTS; then for pkg in $($HCPKG list --simple-output); do echo $pkg | grep -vw -- heaps | sed 's/^/constraints: /' | sed 's/-[^-]*$/ installed/' >> cabal.project.local; done; fi"- - cat cabal.project || true- - cat cabal.project.local || true- - if [ -f "./configure.ac" ]; then- (cd "." && autoreconf -i);- fi- - rm -f cabal.project.freeze- - cabal new-build -w ${HC} ${TEST} ${BENCH} --project-file="cabal.project" --dep -j2 all- - rm -rf .ghc.environment.* "."/dist- - DISTDIR=$(mktemp -d /tmp/dist-test.XXXX)--# Here starts the actual work to be performed for the package under test;-# any command which exits with a non-zero exit code causes the build to fail.-script:- # test that source-distributions can be generated- - cabal new-sdist all- - mv dist-newstyle/sdist/*.tar.gz ${DISTDIR}/- - cd ${DISTDIR} || false- - find . -maxdepth 1 -name '*.tar.gz' -exec tar -xvf '{}' \;- - "printf 'packages: heaps-*/*.cabal\\n' > cabal.project"- - "printf 'write-ghc-environment-files: always\\n' >> cabal.project"- - touch cabal.project.local- - "if ! $NOINSTALLEDCONSTRAINTS; then for pkg in $($HCPKG list --simple-output); do echo $pkg | grep -vw -- heaps | sed 's/^/constraints: /' | sed 's/-[^-]*$/ installed/' >> cabal.project.local; done; fi"- - cat cabal.project || true- - cat cabal.project.local || true-- # build & run tests, build benchmarks- - cabal new-build -w ${HC} ${TEST} ${BENCH} all-- # doctest- - if [ $HCNUMVER -ge 80000 ]; then (cd heaps-* && doctest src); fi-- # cabal check- - (cd heaps-* && cabal check)-- # haddock- - if $HADDOCK; then cabal new-haddock -w ${HC} ${TEST} ${BENCH} all; else echo "Skipping haddock generation";fi-- # hlint- - (cd heaps-* && hlint src --cpp-ansi --cpp-define=HLINT)--# REGENDATA ["-o",".travis.yml","--ghc-head","--irc-channel=irc.freenode.org#haskell-lens","--no-no-tests-no-bench","--no-unconstrained","--allow-failure=7.0.4","--allow-failure=7.2.2","--doctest","cabal.project"]-# EOF
CHANGELOG.markdown view
@@ -1,5 +1,24 @@-0.3.6.1--------+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`,+ i.e.,++ ```haskell+ null :: Heap a -> Bool+ ```++ Previously, this specialized versions of `null` was only exported with GHC+ 7.8 or older, and for more recent GHCs, the `Data.Foldable` version was+ exported instead. The exported API is now uniform across all supported+ versions of GHC.+* Export `adjustMin`.++0.3.6.1 [2019.02.05]+-------------------- * Change to `build-type: Simple`, and drop the `doctests` test suite. This was done in an effort to make `heaps`' dependency footprint as minimal as possible, since `heaps` is used to bootstrap `shake`.
− HLint.hs
@@ -1,2 +0,0 @@-ignore "Use infix"-ignore "Use fmap"
README.markdown view
@@ -1,7 +1,7 @@ heaps ====== -[](https://hackage.haskell.org/package/heaps) [](http://travis-ci.org/ekmett/heaps)+[](https://hackage.haskell.org/package/heaps) [](https://github.com/ekmett/heaps/actions?query=workflow%3AHaskell-CI) This package provides Brodal/Okasaki heaps. These are asymptotically optimal purely functional heaps.
− Warning.hs
@@ -1,5 +0,0 @@-module Warning- {-# WARNING ["You are configuring this package without cabal-doctest installed.",- "The doctests test-suite will not work as a result.",- "To fix this, install cabal-doctest before configuring."] #-}- () where
heaps.cabal view
@@ -1,5 +1,5 @@ name: heaps-version: 0.3.6.1+version: 0.4.1 license: BSD3 license-file: LICENSE author: Edward A. Kmett@@ -11,23 +11,24 @@ 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.3+ , GHC == 8.6.5+ , 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.8+cabal-version: >=1.10 extra-source-files:- HLint.hs- Warning.hs .gitignore- .travis.yml+ .hlint.yaml CHANGELOG.markdown README.markdown @@ -38,6 +39,7 @@ library exposed-modules: Data.Heap build-depends:- base >= 4 && < 6+ base >= 4.9 && < 6 hs-source-dirs: src- ghc-options: -O2+ 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@@ -43,6 +41,7 @@ , insert -- O(1) :: Ord a => a -> Heap a -> Heap a , minimum -- O(1) (/partial/) :: Ord a => Heap a -> a , deleteMin -- O(log n) :: Heap a -> Heap a+ , adjustMin -- O(log n) :: (a -> a) -> Heap a -> Heap a , union -- O(1) :: Heap a -> Heap a -> Heap a , uncons, viewMin -- O(1)\/O(log n) :: Heap a -> Maybe (a, Heap a) -- * Transformations@@ -81,32 +80,38 @@ ( map , span, dropWhile, takeWhile, break, filter, take, drop, splitAt , foldr, minimum, replicate, mapM- , concatMap-#if __GLASGOW_HASKELL__ < 710- , null-#else+ , concatMap, null , traverse-#endif )-#if MIN_VERSION_base(4,8,0)+import Control.Monad (liftM) import Data.Bifunctor-#endif+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 Control.Applicative (Applicative(pure))-import Control.Monad (liftM)-#if MIN_VERSION_base(4,9,0)+import qualified Data.Traversable as T+import Text.Read++#if !(MIN_VERSION_base(4,11,0)) import Data.Semigroup (Semigroup(..)) #endif-import Data.Monoid (Monoid(mappend, mempty))-import Data.Foldable hiding (minimum, concatMap)-import Data.Function (on)-import Data.Data (DataType, Constr, mkConstr, mkDataType, Fixity(Prefix), Data(..), constrIndex)-import Data.Typeable (Typeable)-import Text.Read-import Text.Show-import qualified Data.Traversable as Traversable-import Data.Traversable (Traversable) +-- $setup+-- >>> let break = Data.Heap.break+-- >>> let concatMap = Data.Heap.concatMap+-- >>> let dropWhile = Data.Heap.dropWhile+-- >>> let filter = Data.Heap.filter+-- >>> let minimum = Data.Heap.minimum+-- >>> let null = Data.Heap.null+-- >>> let span = Data.Heap.span+-- >>> let take = Data.Heap.take+-- >>> let takeWhile = Data.Heap.takeWhile+--+-- -- GHC 7.0 and 7.2 will default the `Ord` constraints to () in the types of+-- -- the following functions unless we give them explicit type signatures.+-- >>> let { map :: Ord b => (a -> b) -> Heap a -> Heap b; map = Data.Heap.map }+-- >>> let { replicate :: Ord a => a -> Int -> Heap a ; replicate = Data.Heap.replicate }+ -- The implementation of 'Heap' must internally hold onto the dictionary entry for ('<='), -- so that it can be made 'Foldable'. Confluence in the absence of incoherent instances -- is provided by the fact that we only ever build these from instances of 'Ord' a (except in the case of 'groupBy')@@ -115,17 +120,13 @@ -- | 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 []" showsPrec d (Heap _ _ t) = showParen (d > 10) $- showString "fromList " . showsPrec 11 (toList t)+ showString "fromList " . showsPrec 11 (F.toList t) instance (Ord a, Read a) => Read (Heap a) where readPrec = parens $ prec 10 $ do@@ -150,7 +151,7 @@ Empty == Empty = True Empty == Heap{} = False Heap{} == Empty = False- a@(Heap s1 leq _) == b@(Heap s2 _ _) = s1 == s2 && go leq (toList a) (toList b)+ a@(Heap s1 leq _) == b@(Heap s2 _ _) = s1 == s2 && go leq (F.toList a) (F.toList b) where go f (x:xs) (y:ys) = f x y && f y x && go f xs ys go _ [] [] = True@@ -160,7 +161,7 @@ Empty `compare` Empty = EQ Empty `compare` Heap{} = LT Heap{} `compare` Empty = GT- a@(Heap _ leq _) `compare` b = go leq (toList a) (toList b)+ a@(Heap _ leq _) `compare` b = go leq (F.toList a) (F.toList b) where go f (x:xs) (y:ys) = if f x y@@ -168,9 +169,9 @@ then go f xs ys else LT else GT- go f [] [] = EQ- go f [] (_:_) = LT- go f (_:_) [] = GT+ go _ [] [] = EQ+ go _ [] (_:_) = LT+ go _ (_:_) [] = GT @@ -295,7 +296,7 @@ (Node r x cf, ts2) = getMin leq f0 (zs, ts1, f1) = splitForest r Nil Nil cf f2 = skewMeld leq (skewMeld leq ts1 ts2) f1- f3 = foldr (skewInsert leq) f2 (trees zs)+ f3 = F.foldr (skewInsert leq) f2 (trees zs) {-# INLINE deleteMin #-} -- | /O(log n)/. Adjust the minimum key in the heap and return the resulting heap.@@ -322,12 +323,13 @@ rightZ :: ForestZipper a -> ForestZipper a rightZ (path, x `Cons` xs) = (x `Cons` path, xs)+rightZ _ = error "Heap.rightZ: empty zipper" {-# INLINE rightZ #-} -adjustZ :: (Tree a -> Tree a) -> ForestZipper a -> ForestZipper a-adjustZ f (path, x `Cons` xs) = (path, f x `Cons` xs)-adjustZ _ z = z-{-# INLINE adjustZ #-}+-- adjustZ :: (Tree a -> Tree a) -> ForestZipper a -> ForestZipper a+-- adjustZ f (path, x `Cons` xs) = (path, f x `Cons` xs)+-- adjustZ _ z = z+-- {-# INLINE adjustZ #-} rezip :: ForestZipper a -> Forest a rezip (Nil, xs) = xs@@ -355,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.@@ -368,23 +373,21 @@ -- >>> size (fromList [1,5,3]) -- 3 fromList :: Ord a => [a] -> Heap a-fromList = foldr insert mempty+fromList = F.foldr insert mempty {-# INLINE fromList #-} fromListWith :: (a -> a -> Bool) -> [a] -> Heap a-fromListWith f = foldr (insertWith f) mempty+fromListWith f = F.foldr (insertWith f) mempty {-# INLINE fromListWith #-} -- | /O(n log n)/. Perform a heap sort sort :: Ord a => [a] -> [a]-sort = toList . fromList+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@@ -402,18 +405,14 @@ -- @'fromList' '.' 'toUnsortedList' ≡ 'id'@ toUnsortedList :: Heap a -> [a] toUnsortedList Empty = []-toUnsortedList (Heap _ _ t) = foldMap return t+toUnsortedList (Heap _ _ t) = F.foldMap return t {-# INLINE toUnsortedList #-} instance Foldable Heap where foldMap _ Empty = mempty- foldMap f l@(Heap _ _ t) = f (root t) `mappend` foldMap f (deleteMin l)-#if __GLASGOW_HASKELL__ >= 710- null Empty = True- null _ = False-+ foldMap f l@(Heap _ _ t) = f (root t) `mappend` F.foldMap f (deleteMin l)+ null = null length = size-#else -- | /O(1)/. Is the heap empty? --@@ -427,8 +426,6 @@ null _ = False {-# INLINE null #-} -#endif- -- | /O(1)/. The number of elements in the heap. -- -- >>> size empty@@ -448,7 +445,7 @@ -- fromList [-3,-1,-2] map :: Ord b => (a -> b) -> Heap a -> Heap b map _ Empty = Empty-map f (Heap _ _ t) = foldMap (singleton . f) t+map f (Heap _ _ t) = F.foldMap (singleton . f) t {-# INLINE map #-} -- | /O(n)/. Map a monotone increasing function over the heap.@@ -475,7 +472,7 @@ -- fromList [] filter :: (a -> Bool) -> Heap a -> Heap a filter _ Empty = Empty-filter p (Heap _ leq t) = foldMap f t+filter p (Heap _ leq t) = F.foldMap f t where f x | p x = singletonWith leq x | otherwise = Empty@@ -487,7 +484,7 @@ -- (fromList "b",fromList "a") partition :: (a -> Bool) -> Heap a -> (Heap a, Heap a) partition _ Empty = (Empty, Empty)-partition p (Heap _ leq t) = foldMap f t+partition p (Heap _ leq t) = F.foldMap f t where f x | p x = (singletonWith leq x, mempty) | otherwise = (mempty, singletonWith leq x)@@ -498,8 +495,8 @@ -- >>> split 'h' (fromList "hello") -- (fromList "e",fromList "h",fromList "llo") split :: a -> Heap a -> (Heap a, Heap a, Heap a)-split a Empty = (Empty, Empty, Empty)-split a (Heap s leq t) = foldMap f t+split _ Empty = (Empty, Empty, Empty)+split a (Heap _ leq t) = F.foldMap f t where f x = if leq x a then if leq a x@@ -587,7 +584,7 @@ -- fromList [1,4,5,2] concatMap :: (a -> Heap b) -> Heap a -> Heap b concatMap _ Empty = Empty-concatMap f h@(Heap _ _ t) = foldMap f t+concatMap f (Heap _ _ t) = F.foldMap f t {-# INLINE concatMap #-} -- | /O(n log n)/. Group a heap into a heap of heaps, by unioning together duplicates.@@ -601,7 +598,7 @@ -- | /O(n log n)/. Group using a user supplied function. groupBy :: (a -> a -> Bool) -> Heap a -> Heap (Heap a)-groupBy f Empty = Empty+groupBy _ Empty = Empty groupBy f h@(Heap _ leq t) = insert (insertWith leq x ys) (groupBy f zs) where x = root t@@ -613,7 +610,7 @@ intersect :: Heap a -> Heap a -> Heap a intersect Empty _ = Empty intersect _ Empty = Empty-intersect a@(Heap _ leq _) b = go leq (toList a) (toList b)+intersect a@(Heap _ leq _) b = go leq (F.toList a) (F.toList b) where go leq' xxs@(x:xs) yys@(y:ys) = if leq' x y@@ -629,7 +626,7 @@ intersectWith :: Ord b => (a -> a -> b) -> Heap a -> Heap a -> Heap b intersectWith _ Empty _ = Empty intersectWith _ _ Empty = Empty-intersectWith f a@(Heap _ leq _) b = go leq f (toList a) (toList b)+intersectWith f a@(Heap _ leq _) b = go leq f (F.toList a) (F.toList b) where go :: Ord b => (a -> a -> Bool) -> (a -> a -> b) -> [a] -> [a] -> Heap b go leq' f' xxs@(x:xs) yys@(y:ys)@@ -644,12 +641,12 @@ -- | /O(n log n)/. Traverse the elements of the heap in sorted order and produce a new heap using 'Applicative' side-effects. traverse :: (Applicative t, Ord b) => (a -> t b) -> Heap a -> t (Heap b)-traverse f = fmap fromList . Traversable.traverse f . toList+traverse f = fmap fromList . T.traverse f . F.toList {-# INLINE traverse #-} -- | /O(n log n)/. Traverse the elements of the heap in sorted order and produce a new heap using 'Monad'ic side-effects. mapM :: (Monad m, Ord b) => (a -> m b) -> Heap a -> m (Heap b)-mapM f = liftM fromList . Traversable.mapM f . toList+mapM f = liftM fromList . T.mapM f . F.toList {-# INLINE mapM #-} both :: (a -> b) -> (a, a) -> (b, b)@@ -661,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@@ -676,11 +673,11 @@ -- internal foldable instances that should only be used over commutative monoids instance Foldable Tree where- foldMap f (Node _ a as) = f a `mappend` foldMap f as+ foldMap f (Node _ a as) = f a `mappend` F.foldMap f as -- internal foldable instances that should only be used over commutative monoids instance Foldable Forest where- foldMap f (a `Cons` as) = foldMap f a `mappend` foldMap f as+ foldMap f (a `Cons` as) = F.foldMap f a `mappend` F.foldMap f as foldMap _ Nil = mempty link :: (a -> a -> Bool) -> Tree a -> Tree a -> Tree a@@ -751,12 +748,12 @@ withList :: ([a] -> [a]) -> Heap a -> Heap a withList _ Empty = Empty-withList f hp@(Heap _ leq _) = fromListWith leq (f (toList hp))+withList f hp@(Heap _ leq _) = fromListWith leq (f (F.toList hp)) {-# INLINE withList #-} splitWithList :: ([a] -> ([a],[a])) -> Heap a -> (Heap a, Heap a) splitWithList _ Empty = (Empty, Empty)-splitWithList f hp@(Heap _ leq _) = both (fromListWith leq) (f (toList hp))+splitWithList f hp@(Heap _ leq _) = both (fromListWith leq) (f (F.toList hp)) {-# INLINE splitWithList #-} -- | Explicit priority/payload tuples. Useful to build a priority queue using@@ -768,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