memoize 1.1.1 → 1.1.2

raw patch · 4 files changed

+33/−54 lines, 4 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• CHANGELOG.md +4/−0
• LICENSE +1/−1
• memoize.cabal +2/−2
• src/Data/Function/Memoize.hs +26/−51

@@ -1,5 +1,9 @@ # Change Log +## [1.1.2] - 2022-09-16+- fix severe slowness in `Memoizable Integer` instance (h/t @darrenks)+- correct minimum `base` version (h/t @Bodigrim)+ ## [1.1.1] - 2021-10-31 - add this changelog to `memoize.cabal` 

@@ -1,4 +1,4 @@-Copyright (c) 2011–2021, Jesse A. Tov+Copyright (c) 2011–2022, Jesse A. Tov All rights reserved.  Redistribution and use in source and binary forms, with or without

@@ -1,6 +1,6 @@ cabal-version:  2.2 name:           memoize-version:        1.1.1+version:        1.1.2 license:        BSD-3-Clause license-file:   LICENSE stability:      experimental@@ -25,7 +25,7 @@ extra-source-files: README.md CHANGELOG.md  library-  build-depends:        base >=3 && <5,+  build-depends:        base >=4.8 && <5,                         template-haskell >=2 && <3   default-language:     Haskell98 

@@ -46,6 +46,7 @@ import Data.Function.Memoize.Class import Data.Function.Memoize.TH +import           Data.Bits      (shiftL, shiftR, finiteBitSize, (.&.), (.|.)) import qualified Data.Complex   as Complex import qualified Data.Ratio     as Ratio #ifdef COMPAT_HAS_SOLO@@ -146,7 +147,7 @@ --- Binary-tree based memo caches --- --- Used for both 'Integer' and arbitrary 'Int'-like types.+-- Used for arbitrary types that are bounded and enumerable:  data BinaryTreeCache v  = BinaryTreeCache {@@ -156,56 +157,6 @@    deriving Functor  ------- 'Integer' memoization------instance Memoizable Integer where-  memoize f = integerLookup (f <$> theIntegers)---- | An integer cache stores a value for 0 and separate caches for the---   positive and negative integers.-data IntegerCache v-  = IntegerCache {-      icZero                 ∷ v,-      icNegative, icPositive ∷ PosIntCache v-    }-  deriving Functor---- | A positive integer cache is represented as a little-endian bitwise---   trie-type PosIntCache v = BinaryTreeCache v--theIntegers ∷ IntegerCache Integer-theIntegers-  = IntegerCache {-      icZero     = 0,-      icNegative = negate <$> thePosInts,-      icPositive = thePosInts-    }--thePosInts ∷ PosIntCache Integer-thePosInts =-  BinaryTreeCache {-   btValue = 1,-   btLeft  = fmap (* 2) thePosInts,-   btRight = fmap (succ . (* 2)) thePosInts- }--integerLookup ∷ IntegerCache v → Integer → v-integerLookup cache n =-  case n `compare` 0 of-    EQ → icZero cache-    GT → posIntLookup (icPositive cache) n-    LT → posIntLookup (icNegative cache) (negate n)---- PRECONDITION: @n@ is a positive 'Integer'-posIntLookup ∷ PosIntCache v → Integer → v-posIntLookup cache 1 = btValue cache-posIntLookup cache n-  | even n    = posIntLookup (btLeft cache) (n `div` 2)-  | otherwise = posIntLookup (btRight cache) (n `div` 2)----- --- Enumerable types using binary search trees --- @@ -297,6 +248,30 @@ deriveMemoizable ''(,,,,,,,,,) deriveMemoizable ''(,,,,,,,,,,) deriveMemoizable ''(,,,,,,,,,,,)++---+--- 'Integer' memoization+---++instance Memoizable Integer where+  memoize f = memoize (f . decodeInteger) . encodeInteger++encodeInteger :: Integer -> [Int]+encodeInteger 0 = []+encodeInteger i | minInt <= i && i <= maxInt+                = [fromInteger i]+encodeInteger i = fromInteger (i .&. maxInt) : encodeInteger (i `shiftR` intBits)++decodeInteger :: [Int] -> Integer+decodeInteger  = foldr op 0 where+  op i i' = fromIntegral i .|. i' `shiftL` intBits++intBits :: Int+intBits  = finiteBitSize (0 :: Int) - 1++minInt, maxInt :: Integer+minInt = fromIntegral (minBound :: Int)+maxInt = fromIntegral (maxBound :: Int)  --- --- Functions