Script 'mail_helper' called by obssrc Hello community, here is the log from the commit of package ghc-heaps for openSUSE:Factory checked in at 2021-03-10 08:54:51 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/ghc-heaps (Old) and /work/SRC/openSUSE:Factory/.ghc-heaps.new.2378 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "ghc-heaps" Wed Mar 10 08:54:51 2021 rev:4 rq:877630 version:0.4 Changes: -------- --- /work/SRC/openSUSE:Factory/ghc-heaps/ghc-heaps.changes 2020-12-22 11:40:18.329551437 +0100 +++ /work/SRC/openSUSE:Factory/.ghc-heaps.new.2378/ghc-heaps.changes 2021-03-10 08:56:51.994864909 +0100 @@ -1,0 +2,9 @@ +Sat Feb 20 00:08:04 UTC 2021 - psim...@suse.com + +- Update heaps to version 0.4. + Upstream has edited the change log file since the last release in + a non-trivial way, i.e. they did more than just add a new entry + at the top. You can review the file at: + http://hackage.haskell.org/package/heaps-0.4/src/CHANGELOG.markdown + +------------------------------------------------------------------- Old: ---- heaps-0.3.6.1.tar.gz New: ---- heaps-0.4.tar.gz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ ghc-heaps.spec ++++++ --- /var/tmp/diff_new_pack.pvatzM/_old 2021-03-10 08:56:52.642865578 +0100 +++ /var/tmp/diff_new_pack.pvatzM/_new 2021-03-10 08:56:52.646865582 +0100 @@ -1,7 +1,7 @@ # # spec file for package ghc-heaps # -# Copyright (c) 2020 SUSE LLC +# Copyright (c) 2021 SUSE LLC # # All modifications and additions to the file contributed by third parties # remain the property of their copyright owners, unless otherwise agreed @@ -18,7 +18,7 @@ %global pkg_name heaps Name: ghc-%{pkg_name} -Version: 0.3.6.1 +Version: 0.4 Release: 0 Summary: Asymptotically optimal Brodal/Okasaki heaps License: BSD-3-Clause ++++++ heaps-0.3.6.1.tar.gz -> heaps-0.4.tar.gz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/heaps-0.3.6.1/.hlint.yaml new/heaps-0.4/.hlint.yaml --- old/heaps-0.3.6.1/.hlint.yaml 1970-01-01 01:00:00.000000000 +0100 +++ new/heaps-0.4/.hlint.yaml 2001-09-09 03:46:40.000000000 +0200 @@ -0,0 +1,4 @@ +- arguments: [--cpp-define=HLINT, --cpp-ansi] + +- ignore: {name: Use infix} +- ignore: {name: Use fmap} diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/heaps-0.3.6.1/.travis.yml new/heaps-0.4/.travis.yml --- old/heaps-0.3.6.1/.travis.yml 2001-09-09 03:46:40.000000000 +0200 +++ new/heaps-0.4/.travis.yml 1970-01-01 01:00:00.000000000 +0100 @@ -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 diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/heaps-0.3.6.1/CHANGELOG.markdown new/heaps-0.4/CHANGELOG.markdown --- old/heaps-0.3.6.1/CHANGELOG.markdown 2001-09-09 03:46:40.000000000 +0200 +++ new/heaps-0.4/CHANGELOG.markdown 2001-09-09 03:46:40.000000000 +0200 @@ -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`. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/heaps-0.3.6.1/HLint.hs new/heaps-0.4/HLint.hs --- old/heaps-0.3.6.1/HLint.hs 2001-09-09 03:46:40.000000000 +0200 +++ new/heaps-0.4/HLint.hs 1970-01-01 01:00:00.000000000 +0100 @@ -1,2 +0,0 @@ -ignore "Use infix" -ignore "Use fmap" diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/heaps-0.3.6.1/README.markdown new/heaps-0.4/README.markdown --- old/heaps-0.3.6.1/README.markdown 2001-09-09 03:46:40.000000000 +0200 +++ new/heaps-0.4/README.markdown 2001-09-09 03:46:40.000000000 +0200 @@ -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. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/heaps-0.3.6.1/Warning.hs new/heaps-0.4/Warning.hs --- old/heaps-0.3.6.1/Warning.hs 2001-09-09 03:46:40.000000000 +0200 +++ new/heaps-0.4/Warning.hs 1970-01-01 01:00:00.000000000 +0100 @@ -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 diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/heaps-0.3.6.1/heaps.cabal new/heaps-0.4/heaps.cabal --- old/heaps-0.3.6.1/heaps.cabal 2001-09-09 03:46:40.000000000 +0200 +++ new/heaps-0.4/heaps.cabal 2001-09-09 03:46:40.000000000 +0200 @@ -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 diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/heaps-0.3.6.1/src/Data/Heap.hs new/heaps-0.4/src/Data/Heap.hs --- old/heaps-0.3.6.1/src/Data/Heap.hs 2001-09-09 03:46:40.000000000 +0200 +++ new/heaps-0.4/src/Data/Heap.hs 2001-09-09 03:46:40.000000000 +0200 @@ -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,31 +82,48 @@ ( 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 @@ -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
