bytestring-trie 0.2.4.1 → 0.2.4.3

raw patch · 5 files changed

+124/−82 lines, 5 filesdep ~basedep ~bytestringnew-uploaderPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: base, bytestring

API changes (from Hackage documentation)

Files

• CHANGELOG +22/−0
• README.md +65/−0
• VERSION +0/−19
• bytestring-trie.cabal +35/−57
• src/Data/Trie/Internal.hs +2/−6

@@ -0,0 +1,22 @@+0.2.4.3 (2019.02.24):+    - Moved VERSION to CHANGELOG+    - Fixing things to compile under GHC 8.0 and 8.2.  N.B., still doesn't compile under 8.4 or 8.6, due to the version limit on `base`.+0.2.4.1 (2015.04.04):+    - Data.Trie.Internal: adjusted imports to compule under GHC 7.10.1+0.2.4 (2014.10.09):+    - added Data.Trie.Internal.{match_,matches_}, Data.Trie.Base.{match,matches}+0.2.3 (2010.02.12):+    - added Data.Trie.Internal.alterBy_+    - added Data.Trie.Internal.{contextualMap, contextualMap', contextualFilterMap, contextualMapBy}+    - added Data.Trie.Convenience.{fromListWith', fromListWithL, fromListWithL'} as suggested by Ian Taylor+    - added Data.Trie.Convenience{insertWith', insertWithKey', unionWith'}+    - converted fmap, foldMap, traverse, and filterMap to worker/wrapper+0.2.2 (2010.06.10):+    - Corrected a major bug in mergeBy, reported by Gregory Crosswhite+0.2.1.1 (2009.12.20):+    - Added a VERSION file+0.2.1 (2009.02.13):+    - Most recent release before adding a VERSION file++0.1.4 (2009.01.11):+    - The only previous tag

@@ -0,0 +1,65 @@+bytestring-trie+===============+[![Hackage version](https://img.shields.io/hackage/v/bytestring-trie.svg?style=flat)](https://hackage.haskell.org/package/bytestring-trie) +[![Hackage-Deps](https://img.shields.io/hackage-deps/v/bytestring-trie.svg?style=flat)](http://packdeps.haskellers.com/specific?package=bytestring-trie)+[![TravisCI Build Status](https://img.shields.io/travis/wrengr/bytestring-trie.svg?style=flat)](https://travis-ci.org/wrengr/bytestring-trie) +[![CircleCI Build Status](https://circleci.com/gh/wrengr/bytestring-trie.svg?style=shield&circle-token=b57517657c556be6fd8fca92b843f9e4cffaf8d1)](https://circleci.com/gh/wrengr/bytestring-trie)++The bytestring-trie package provides an efficient implementation+of tries mapping `ByteString` to values.  The implementation is+based on Okasaki's big-endian patricia trees, à la `IntMap`.  We+first trie on the elements of `ByteString` and then trie on the+big-endian bit representation of those elements.  Patricia trees+have efficient algorithms for union and other merging operations,+but they're also quick for lookups and insertions.++If you are only interested in being able to associate individual+`ByteString`s to values, then you may prefer the `hashmap` package+which is faster for those only needing a map-like structure.  This+package is intended for those who need the extra capabilities that+a trie-like structure can offer (e.g., structure sharing to reduce+memory costs for highly redundant keys, taking the submap of all+keys with a given prefix, contextual mapping, extracting the minimum+and maximum keys, etc.)+++## Install++This is a simple package and should be easy to install.  You should+be able to use one of the following standard methods to install it.++    -- With cabal-install and without the source:+    $> cabal install bytestring-trie+    +    -- With cabal-install and with the source already:+    $> cd bytestring-trie+    $> cabal install+    +    -- Without cabal-install, but with the source already:+    $> cd bytestring-trie+    $> runhaskell Setup.hs configure --user+    $> runhaskell Setup.hs build+    $> runhaskell Setup.hs haddock --hyperlink-source+    $> runhaskell Setup.hs copy+    $> runhaskell Setup.hs register++The Haddock step is optional.+++## Portability++The implementation is quite portable, relying only on a few basic+language extensions. The complete list of extensions used is:++* CPP+* ForeignFunctionInterface+* MagicHash +* NoImplicitPrelude++## Links++* [Website](http://wrengr.org/)+* [Blog](http://winterkoninkje.dreamwidth.org/)+* [Twitter](https://twitter.com/wrengr)+* [Hackage](http://hackage.haskell.org/package/bytestring-trie)+* [GitHub](https://github.com/wrengr/bytestring-trie)

@@ -1,19 +0,0 @@-0.2.4.1 (2015.04.04):-	- Data.Trie.Internal: adjusted imports to compule under GHC 7.10.1-0.2.4 (2014.10.09):-    - added Data.Trie.Internal.{match_,matches_}, Data.Trie.Base.{match,matches}-0.2.3 (2010.02.12):-    - added Data.Trie.Internal.alterBy_-    - added Data.Trie.Internal.{contextualMap, contextualMap', contextualFilterMap, contextualMapBy}-    - added Data.Trie.Convenience.{fromListWith', fromListWithL, fromListWithL'} as suggested by Ian Taylor-    - added Data.Trie.Convenience{insertWith', insertWithKey', unionWith'}-    - converted fmap, foldMap, traverse, and filterMap to worker/wrapper-0.2.2 (2010.06.10):-    - Corrected a major bug in mergeBy, reported by Gregory Crosswhite-0.2.1.1 (2009.12.20):-    - Added a VERSION file-0.2.1 (2009.02.13):-    - Most recent release before adding a VERSION file--0.1.4 (2009.01.11):-	- The only previous tag

@@ -1,19 +1,21 @@-------------------------------------------------------------------- wren gayle romano <wren@community.haskell.org>   ~ 2015.04.04-----------------------------------------------------------------+------------------------------------------------------------+-- wren gayle romano <wren@cpan.org>            ~ 2019.02.23+------------------------------------------------------------ --- By and large Cabal >=1.2 is fine; but >= 1.6 gives tested-with:--- and source-repository:.-Cabal-Version:  >= 1.6+-- By and large Cabal >=1.2 is fine; but+-- * >=1.6 gives tested-with: and source-repository:+-- * >=1.8 allows executables to build-depends: on the library+-- * >=1.9.2 allows Test-Suite+Cabal-Version:  >= 1.9.2 Build-Type:     Simple  Name:           bytestring-trie-Version:        0.2.4.1+Version:        0.2.4.3 Stability:      provisional-Homepage:       http://code.haskell.org/~wren/+Homepage:       http://wrengr.org Author:         wren gayle romano-Maintainer:     wren@community.haskell.org-Copyright:      Copyright (c) 2008--2015 wren gayle romano+Maintainer:     wren@cpan.org+Copyright:      Copyright (c) 2008--2019 wren gayle romano License:        BSD3 License-File:   LICENSE @@ -41,37 +43,32 @@                 maximum keys, etc.)  -Tested-With:-    GHC == 6.12.1, GHC == 7.6.1 Extra-source-files:-    AUTHORS, VERSION-Source-Repository head-    Type:     darcs-    Location: http://community.haskell.org/~wren/bytestring-trie+    AUTHORS, CHANGELOG, README.md ------------------------------------------------------------------Flag base4-    Default:     True-    Description: base-4.0 emits "Prelude deprecated" messages in-                 order to get people to be explicit about which-                 version of base they use.+-- Cf., <https://travis-ci.org/wrengr/bytestring-lexing>+Tested-With:+    GHC ==7.4.1, GHC ==7.4.2,+    GHC ==7.6.1, GHC ==7.6.2, GHC ==7.6.3,+    GHC ==7.8.1, GHC ==7.8.2, GHC ==7.8.3, GHC ==7.8.4,+    GHC ==7.10.1, GHC ==7.10.2, GHC ==7.10.3,+    GHC ==8.0.1, GHC ==8.0.2,+    GHC ==8.2.1, GHC ==8.2.2+    -- TODO: re-enable these and get them to work.+    -- GHC ==8.4.1, GHC ==8.4.2, GHC ==8.4.3,+    -- GHC ==8.6.1, GHC ==8.6.2 +Source-Repository head+    Type:     git+    Location: https://github.com/wrengr/bytestring-trie.git++------------------------------------------------------------ Flag useCinternal     Default:     False     Description: Use optimized C implementation for indexOfDifference.                  See notes in Data.Trie.ByteStringInternal. -Flag applicativeInBase-    Default:     True-    Description: Applicative functors were added in base-2.0--Flag bytestringInBase-    Default:     False-    Description: The bytestring library was included in base-2.0-                 and base-2.1.1, but for base-1.0 and base-3.0 it-                 was a separate package------------------------------------------------------------------+------------------------------------------------------------ Library     Hs-Source-Dirs:  src     Exposed-Modules: Data.Trie@@ -80,28 +77,9 @@     Other-Modules:   Data.Trie.BitTwiddle                    , Data.Trie.ByteStringInternal                    , Data.Trie.Errors-    Build-Depends: binary-    -    -- I think this is all that needs doing to get rid of the warnings?-    -- BUG: looks like it's not enough-    if flag(base4)-        Build-Depends: base >= 4 && < 5-    else-        Build-Depends: base < 4-        -    if flag(bytestringInBase)-        Build-Depends: base >= 2.0 && < 2.2-    else-        Build-Depends: base < 2.0 || >= 3, bytestring-    -    if flag(applicativeInBase)-        Build-Depends: base >= 2.0-        Cpp-Options: -DAPPLICATIVE_IN_BASE-        -- BUG (Cabal 1.2 + Haddock): enable for Haddock, disable-        -- for Hackage. Fixed in Cabal 1.6-        --Ghc-Options: -DAPPLICATIVE_IN_BASE-    else-        Build-Depends: base < 2.0+    Build-Depends: base       >= 4   && < 4.11+                 , bytestring >= 0.9 && < 0.11+                 , binary          if flag(useCinternal)         C-Sources:     src/Data/Trie/ByteStringInternal/indexOfDifference.c@@ -109,5 +87,5 @@         Cpp-Options:   -D__USE_C_INTERNAL__ -- Also need to add stuff to run Configure.hs, FWIW ----------------------------------------------------------------------------------------------------------------------------- fin.+------------------------------------------------------------+------------------------------------------------------- fin.

@@ -70,12 +70,10 @@  import Data.Monoid         (Monoid(..)) import Control.Monad       (liftM, liftM3, liftM4)-#ifdef APPLICATIVE_IN_BASE import Control.Monad       (ap) import Control.Applicative (Applicative(..), (<$>)) import Data.Foldable       (Foldable(foldMap)) import Data.Traversable    (Traversable(traverse))-#endif  #ifdef __GLASGOW_HASKELL__ import GHC.Exts (build)@@ -236,7 +234,6 @@         go (Branch p m l r)   = Branch p m (go l) (go r)  -#ifdef APPLICATIVE_IN_BASE instance Foldable Trie where     -- If our definition of foldr is so much faster than the Endo     -- default, then maybe we should remove this and use the default@@ -247,7 +244,7 @@         go (Arc _ Nothing  t) = go t         go (Arc _ (Just v) t) = f v `mappend` go t         go (Branch _ _ l r)   = go l `mappend` go r-    +     {- This definition is much faster, but it's also wrong     -- (or at least different than foldrWithKey)     foldr f = \z t -> go t id z@@ -256,7 +253,7 @@         go (Branch _ _ l r)   k x = go r (go l k) x         go (Arc _ Nothing t)  k x = go t k x         go (Arc _ (Just v) t) k x = go t k (f v x)-    +     foldl f = \z t -> go t id z         where         go Empty              k x = k x@@ -279,7 +276,6 @@ instance Applicative Trie where     pure  = return     (<*>) = ap-#endif  -- Does this even make sense? It's not nondeterminism like lists -- and sets. If no keys were prefixes of other keys it'd make sense