hw-fingertree 0.1.2.0 → 0.1.2.1
raw patch · 6 files changed
+50/−52 lines, 6 filesdep ~doctestdep ~hedgehogdep ~hspecPVP ok
version bump matches the API change (PVP)
Dependency ranges changed: doctest, hedgehog, hspec
API changes (from Hackage documentation)
Files
- hw-fingertree.cabal +7/−6
- src/HaskellWorks/Data/FingerTree.hs +11/−9
- src/HaskellWorks/Data/IntervalMap/FingerTree.hs +7/−12
- src/HaskellWorks/Data/PriorityQueue/FingerTree.hs +10/−15
- tests/HaskellWorks/Data/FingerTree/Gen.hs +4/−1
- tests/HaskellWorks/Data/FingerTreeSpec.hs +11/−9
hw-fingertree.cabal view
@@ -1,7 +1,7 @@ cabal-version: 2.2 name: hw-fingertree-version: 0.1.2.0+version: 0.1.2.1 synopsis: Generic finger-tree structure, with example instances description: A general sequence representation with arbitrary annotations, for use as a base for implementations of@@ -20,11 +20,11 @@ homepage: https://github.com/haskell-works/hw-fingertree#readme bug-reports: https://github.com/haskell-works/hw-fingertree/issues maintainer: John Ky <newhoggy@gmail.com>-copyright: (c) 2017-2020 John Ky+copyright: (c) 2017-2022 John Ky (c) 2006 Ross Paterson, Ralf Hinze, license: BSD-3-Clause license-file: LICENSE-tested-with: GHC == 8.10.1, GHC == 8.8.3, GHC == 8.6.5, GHC == 8.4.4+tested-with: GHC == 9.2.2, GHC == 9.0.2, GHC == 8.10.7, GHC == 8.8.4, GHC == 8.6.5 build-type: Simple source-repository head@@ -34,9 +34,9 @@ common base { build-depends: base >= 4.11 && < 5 } common deepseq { build-depends: deepseq >= 1.4 && < 1.5 }-common doctest { build-depends: doctest >= 0.16.2 && < 0.17 }+common doctest { build-depends: doctest >= 0.16.2 && < 0.21 } common doctest-discover { build-depends: doctest-discover >= 0.2 && < 0.3 }-common hedgehog { build-depends: hedgehog >= 0.6 && < 1.1 }+common hedgehog { build-depends: hedgehog >= 0.6 && < 1.2 } common hspec { build-depends: hspec >= 2.4 && < 3.0 } common hw-hspec-hedgehog { build-depends: hw-hspec-hedgehog >= 0.1 && < 0.2 } common hw-prim { build-depends: hw-prim >= 0.6.2.25 && < 0.7 }@@ -67,6 +67,7 @@ , hw-fingertree , hw-hspec-hedgehog type: exitcode-stdio-1.0+ ghc-options: -threaded -rtsopts -with-rtsopts=-N main-is: Spec.hs hs-source-dirs: tests build-tool-depends: hspec-discover:hspec-discover@@ -80,7 +81,7 @@ , hw-fingertree default-language: Haskell2010 type: exitcode-stdio-1.0- ghc-options: -threaded+ ghc-options: -threaded -rtsopts -with-rtsopts=-N main-is: DoctestDriver.hs HS-Source-Dirs: doctest build-tool-depends: doctest-discover:doctest-discover
src/HaskellWorks/Data/FingerTree.hs view
@@ -6,9 +6,7 @@ {-# LANGUAGE FunctionalDependencies #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE TypeFamilies #-}-#if __GLASGOW_HASKELL__ >= 710-{-# LANGUAGE AutoDeriveTypeable #-}-#endif+ ----------------------------------------------------------------------------- -- | -- Module : Data.FingerTree@@ -77,9 +75,8 @@ , (|>) ) where -import Control.Applicative (Applicative (pure, (<*>)), (<$>)) import Control.DeepSeq-import Data.Foldable (Foldable (foldMap), toList)+import Data.Foldable (toList) import GHC.Generics (Generic) import HaskellWorks.Data.Container import HaskellWorks.Data.Cons@@ -89,9 +86,16 @@ import qualified Data.Semigroup as S +#if !MIN_VERSION_base(4,13,0)+import Control.Applicative (Applicative (pure, (<*>)), (<$>))+#endif+ infixr 5 :< infixl 5 :> +{- HLINT ignore "Reduce duplication" -}+{- HLINT ignore "Use record patterns" -}+ -- | View of the left end of a sequence. data ViewL s a = EmptyL -- ^ empty sequence@@ -120,8 +124,6 @@ instance Measured v a => Monoid (FingerTree v a) where mempty = empty {-# INLINE mempty #-}- mappend = append- {-# INLINE mappend #-} instance Container (FingerTree v a) where type Elem (FingerTree v a) = a@@ -366,7 +368,7 @@ -- | /O(1)/. Add an element to the left end of a sequence. -- Mnemonic: a triangle with the single element at the pointy end. instance Measured v a => Cons (FingerTree v a) where- cons a (Empty ) = Single a+ cons a Empty = Single a cons a (Single b ) = deep (One a) Empty (One b) cons a (Deep v (Four b c d e) m sf) = m `seq` Deep (measure a `mappend` v) (Two a b) (node3 c d e <| m) sf cons a (Deep v pr m sf ) = Deep (measure a `mappend` v) (consDigit a pr) m sf@@ -380,7 +382,7 @@ -- | /O(1)/. Add an element to the right end of a sequence. -- Mnemonic: a triangle with the single element at the pointy end. instance Measured v a => Snoc (FingerTree v a) where- snoc (Empty ) a = Single a+ snoc Empty a = Single a snoc (Single a ) b = deep (One a) Empty (One b) snoc (Deep v pr m (Four a b c d)) e = m `seq` Deep (v `mappend` measure e) pr (m |> node3 a b c) (Two d e) snoc (Deep v pr m sf ) x = Deep (v `mappend` measure x) pr m (snocDigit sf x)
src/HaskellWorks/Data/IntervalMap/FingerTree.hs view
@@ -2,9 +2,7 @@ {-# LANGUAGE DeriveAnyClass #-} {-# LANGUAGE DeriveGeneric #-} {-# LANGUAGE MultiParamTypeClasses #-}-#if __GLASGOW_HASKELL__ >= 710-{-# LANGUAGE AutoDeriveTypeable #-}-#endif+ ----------------------------------------------------------------------------- -- | -- Module : Data.PriorityQueue.FingerTree@@ -48,16 +46,17 @@ , dominators ) where -import Control.Applicative ((<$>)) import Control.DeepSeq-import Data.Foldable (Foldable (foldMap))-import Data.Traversable (Traversable (traverse)) import GHC.Generics import HaskellWorks.Data.FingerTree (FingerTree, Measured (..), ViewL (..), (<|), (><)) import qualified Data.Semigroup as S import qualified HaskellWorks.Data.FingerTree as FT +#if !MIN_VERSION_base(4,13,0)+import Control.Applicative ((<$>))+#endif+ ---------------------------------- -- 4.8 Application: interval trees ----------------------------------@@ -86,8 +85,8 @@ data IntInterval v = NoInterval | IntInterval (Interval v) v deriving (Generic, NFData) appendInterval :: Ord v => IntInterval v -> IntInterval v -> IntInterval v-appendInterval (NoInterval ) (i ) = i-appendInterval (i ) (NoInterval ) = i+appendInterval NoInterval i = i+appendInterval i NoInterval = i appendInterval (IntInterval _ hi1) (IntInterval int2 hi2) = IntInterval int2 (max hi1 hi2) {-# INLINE appendInterval #-} @@ -98,8 +97,6 @@ instance Ord v => Monoid (IntInterval v) where mempty = NoInterval {-# INLINE mempty #-}- mappend = appendInterval- {-# INLINE mappend #-} instance (Ord v) => Measured (IntInterval v) (Node v a) where measure (Node i _) = IntInterval i (high i)@@ -129,8 +126,6 @@ instance (Ord v) => Monoid (IntervalMap v a) where mempty = empty {-# INLINE mempty #-}- mappend = union- {-# INLINE mappend #-} -- | /O(1)/. The empty interval map. empty :: (Ord v) => IntervalMap v a
src/HaskellWorks/Data/PriorityQueue/FingerTree.hs view
@@ -1,8 +1,7 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE MultiParamTypeClasses #-}-#if __GLASGOW_HASKELL__ >= 710-{-# LANGUAGE AutoDeriveTypeable #-}-#endif+{-# LANGUAGE TupleSections #-}+ ----------------------------------------------------------------------------- -- | -- Module : Data.PriorityQueue.FingerTree@@ -51,8 +50,7 @@ , minViewWithKey ) where -import Control.Arrow ((***))-import Data.Foldable (Foldable (foldMap))+import Data.Bifunctor (first) import HaskellWorks.Data.FingerTree (FingerTree, Measured (..), ViewL (..), (<|), (><), (|>)) import Prelude hiding (null) @@ -82,8 +80,6 @@ instance Ord k => Monoid (Prio k v) where mempty = NoPrio {-# INLINE mempty #-}- mappend = appendPrio- {-# INLINE mappend #-} instance Ord k => Measured (Prio k v) (Entry k v) where measure (Entry k v) = Prio k v@@ -106,8 +102,6 @@ instance Ord k => Monoid (PQueue k v) where mempty = empty {-# INLINE mempty #-}- mappend = union- {-# INLINE mappend #-} -- | /O(1)/. The empty priority queue. empty :: Ord k => PQueue k v@@ -161,7 +155,7 @@ -- * @'minView' ('singleton' k v) = 'Just' (v, 'empty')@ -- minView :: Ord k => PQueue k v -> Maybe (v, PQueue k v)-minView q = fmap (snd *** id) (minViewWithKey q)+minView q = fmap (first snd) (minViewWithKey q) -- | /O(1)/ for the element, /O(log(n))/ for the reduced queue. -- Returns 'Nothing' for an empty map, or the minimal (priority, value)@@ -180,11 +174,12 @@ minViewWithKey :: Ord k => PQueue k v -> Maybe ((k, v), PQueue k v) minViewWithKey (PQueue q) | FT.null q = Nothing- | otherwise = Just ((k, v), case FT.viewl r of- _ :< r' -> PQueue (l >< r')- _ -> error "can't happen")- where Prio k v = measure q- (l, r) = FT.split (below k) q+ | otherwise = case measure q of+ Prio k v -> case FT.split (below k) q of+ (l, r) -> Just . ((k, v),) $ case FT.viewl r of+ _ :< r' -> PQueue (l >< r')+ _ -> error "can't happen"+ NoPrio -> error "can't happen: queue has no priority" below :: Ord k => k -> Prio k v -> Bool below _ NoPrio = False
tests/HaskellWorks/Data/FingerTree/Gen.hs view
@@ -11,6 +11,9 @@ import qualified Hedgehog.Internal.Shrink as S import qualified Hedgehog.Range as R +{- HLINT ignore "Use <=<" -}+{- HLINT ignore "Use record patterns" -}+ genList :: MonadGen m => Range Int -> m a -> m [a] genList range gen = G.sized $ \size ->@@ -43,7 +46,7 @@ shrinkNode (Node3 _ a b c) = [node2 a b, node2 a c, node2 b c] genSizedNode :: (MonadGen m, Measured v a) => Size -> m a -> m (Node v a)-genSizedNode n gen = G.shrink shrinkNode $ G.choice+genSizedNode _ gen = G.shrink shrinkNode $ G.choice [ node2 <$> gen <*> gen , node3 <$> gen <*> gen <*> gen ]
tests/HaskellWorks/Data/FingerTreeSpec.hs view
@@ -1,15 +1,18 @@+{-# OPTIONS_GHC -fno-warn-orphans #-}+ {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE TupleSections #-} module HaskellWorks.Data.FingerTreeSpec (spec) where -import Control.Applicative (Applicative (..))+-- import Control.Applicative (Applicative (..)) import Control.Monad (ap)-import Data.Foldable (Foldable (foldMap, foldl, foldr), all, toList)-import Data.Functor ((<$>))+import Data.Foldable (toList)+-- import Data.Functor ((<$>)) import Data.List (inits)-import Data.Traversable (traverse)+-- import Data.Traversable (traverse) import HaskellWorks.Data.FingerTree import HaskellWorks.Hspec.Hedgehog import Hedgehog hiding (evalM)@@ -21,9 +24,9 @@ import qualified Hedgehog.Range as R import qualified Prelude as P -{-# ANN module ("HLint: ignore Redundant do" :: String) #-}-{-# ANN module ("HLint: ignore Reduce duplication" :: String) #-}-{-# ANN module ("HLint: ignore Redundant bracket" :: String) #-}+{- HLINT ignore "Redundant do" -}+{- HLINT ignore "Reduce duplication" -}+{- HLINT ignore "Redundant bracket" -} spec :: Spec spec = do@@ -137,14 +140,13 @@ evalM m = snd (runM m 0) instance Monad M where- return x = M $ \ n -> (n, x) M u >>= f = M $ \ m -> let (n, x) = u m in runM (f x) n instance Functor M where fmap f (M u) = M $ \ m -> let (n, x) = u m in (n, f x) instance Applicative M where- pure = return+ pure x = M (, x) (<*>) = ap step :: M Int