heaps 0.3.6.1 → 0.4
raw patch · 8 files changed
+100/−241 lines, 8 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
+ Data.Heap: adjustMin :: (a -> a) -> Heap a -> Heap a
- Data.Heap: null :: Foldable t => t a -> Bool
+ Data.Heap: null :: Heap a -> Bool
Files
- .hlint.yaml +4/−0
- .travis.yml +0/−169
- CHANGELOG.markdown +17/−2
- HLint.hs +0/−2
- README.markdown +1/−1
- Warning.hs +0/−5
- heaps.cabal +8/−7
- src/Data/Heap.hs +70/−55
+ .hlint.yaml view
@@ -0,0 +1,4 @@+- arguments: [--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,20 @@-0.3.6.1--------+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 license: BSD3 license-file: LICENSE author: Edward A. Kmett@@ -20,14 +20,14 @@ , GHC == 8.0.2 , GHC == 8.2.2 , GHC == 8.4.4- , GHC == 8.6.3+ , GHC == 8.6.5+ , GHC == 8.8.3+ , GHC == 8.10.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 @@ -40,4 +40,5 @@ build-depends: base >= 4 && < 6 hs-source-dirs: src- ghc-options: -O2+ ghc-options: -O2 -Wall+ default-language: Haskell2010
src/Data/Heap.hs view
@@ -43,6 +43,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 +82,49 @@ ( map , span, dropWhile, takeWhile, break, filter, take, drop, splitAt , foldr, minimum, replicate, mapM- , concatMap-#if __GLASGOW_HASKELL__ < 710- , null-#else+ , concatMap, null+#if MIN_VERSION_base(4,8,0) , traverse #endif )-#if MIN_VERSION_base(4,8,0)-import Data.Bifunctor-#endif-import qualified Data.List as L-import Control.Applicative (Applicative(pure)) import Control.Monad (liftM)-#if MIN_VERSION_base(4,9,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 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-import Text.Show-import qualified Data.Traversable as Traversable++#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))+import Data.Semigroup (Semigroup(..))+#endif++-- $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')@@ -125,7 +143,7 @@ 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 +168,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 +178,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 +186,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 +313,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 +340,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@@ -368,16 +387,16 @@ -- >>> 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)@@ -402,18 +421,16 @@ -- @'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)+#if MIN_VERSION_base(4,8,0)+ null = null length = size-#else+#endif -- | /O(1)/. Is the heap empty? --@@ -427,8 +444,6 @@ null _ = False {-# INLINE null #-} -#endif- -- | /O(1)/. The number of elements in the heap. -- -- >>> size empty@@ -448,7 +463,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 +490,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 +502,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 +513,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 +602,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 +616,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 +628,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 +644,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 +659,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)@@ -676,11 +691,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 +766,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