packages feed

fastmemo (empty) → 0.1.0.0

raw patch · 18 files changed

+659/−0 lines, 18 filesdep +QuickCheckdep +basedep +bytestringsetup-changed

Dependencies added: QuickCheck, base, bytestring, fastmemo, utf8-string, vector

Files

+ LICENSE view
@@ -0,0 +1,30 @@+Copyright David Spies (c) 2022++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of David Spies nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,5 @@+# FastMemo++Memoization with Generics++[Examples](test/Examples.hs)
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ fastmemo.cabal view
@@ -0,0 +1,69 @@+cabal-version: 1.12++-- This file has been generated from package.yaml by hpack version 0.34.4.+--+-- see: https://github.com/sol/hpack++name:           fastmemo+version:        0.1.0.0+synopsis:       Memoize functions on Generic types+description:    Please see the README on GitHub at <https://github.com/davidspies/fastmemo#readme>+category:       Memoization+homepage:       https://github.com/davidspies/fastmemo#readme+bug-reports:    https://github.com/davidspies/fastmemo/issues+author:         David Spies+maintainer:     dnspies@gmail.com+copyright:      2022 David Spies+license:        BSD3+license-file:   LICENSE+build-type:     Simple+extra-source-files:+    README.md++source-repository head+  type: git+  location: https://github.com/davidspies/fastmemo++library+  exposed-modules:+      Data.Function.FastMemo+  other-modules:+      Data.Function.FastMemo.ByteString+      Data.Function.FastMemo.Char+      Data.Function.FastMemo.Class+      Data.Function.FastMemo.Instances+      Data.Function.FastMemo.Int+      Data.Function.FastMemo.Integer+      Data.Function.FastMemo.Natural+      Data.Function.FastMemo.Ratio+      Data.Function.FastMemo.Util+      Data.Function.FastMemo.Vector+      Data.Function.FastMemo.Word+      Paths_fastmemo+  hs-source-dirs:+      src+  ghc-options: -Wall+  build-depends:+      base >=4.7 && <4.15+    , bytestring ==0.10.*+    , utf8-string ==1.0.*+    , vector ==0.12.*+  default-language: Haskell2010++test-suite fastmemo-test+  type: exitcode-stdio-1.0+  main-is: Spec.hs+  other-modules:+      Examples+      Paths_fastmemo+  hs-source-dirs:+      test+  ghc-options: -Wall -threaded -rtsopts -with-rtsopts=-N+  build-depends:+      QuickCheck+    , base >=4.7 && <4.15+    , bytestring ==0.10.*+    , fastmemo+    , utf8-string ==1.0.*+    , vector ==0.12.*+  default-language: Haskell2010
+ src/Data/Function/FastMemo.hs view
@@ -0,0 +1,42 @@+{-# OPTIONS_GHC -Wno-orphans #-}++-- |+-- Straightforward function memoization library;+-- see [Examples](https://github.com/davidspies/fastmemo/blob/master/test/Examples.hs) for example usage+module Data.Function.FastMemo (Memoizable (..), memoizeFixedLen, memo1, memo2, memo3, memo4, memo5, memo6, memo7) where++import Data.Function.FastMemo.ByteString ()+import Data.Function.FastMemo.Char ()+import Data.Function.FastMemo.Class (Memoizable (..))+import Data.Function.FastMemo.Instances ()+import Data.Function.FastMemo.Int ()+import Data.Function.FastMemo.Integer ()+import Data.Function.FastMemo.Natural ()+import Data.Function.FastMemo.Ratio ()+import Data.Function.FastMemo.Util (memoizeFixedLen)+import Data.Function.FastMemo.Vector ()+import Data.Function.FastMemo.Word ()++memo1 :: Memoizable a => (a -> b) -> a -> b+memo1 = memoize++liftMemo :: Memoizable a => (b -> b) -> (a -> b) -> a -> b+liftMemo m f = memoize $ m . f++memo2 :: (Memoizable a, Memoizable b) => (a -> b -> c) -> a -> b -> c+memo2 = liftMemo memo1++memo3 :: (Memoizable a, Memoizable b, Memoizable c) => (a -> b -> c -> d) -> a -> b -> c -> d+memo3 = liftMemo memo2++memo4 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d) => (a -> b -> c -> d -> e) -> a -> b -> c -> d -> e+memo4 = liftMemo memo3++memo5 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e) => (a -> b -> c -> d -> e -> f) -> a -> b -> c -> d -> e -> f+memo5 = liftMemo memo4++memo6 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f) => (a -> b -> c -> d -> e -> f -> g) -> a -> b -> c -> d -> e -> f -> g+memo6 = liftMemo memo5++memo7 :: (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f, Memoizable g) => (a -> b -> c -> d -> e -> f -> g -> h) -> a -> b -> c -> d -> e -> f -> g -> h+memo7 = liftMemo memo6
+ src/Data/Function/FastMemo/ByteString.hs view
@@ -0,0 +1,14 @@+{-# OPTIONS_GHC -Wno-orphans #-}++module Data.Function.FastMemo.ByteString () where++import qualified Data.ByteString as SBS+import qualified Data.ByteString.Lazy as LBS+import Data.Function.FastMemo.Class (Memoizable (..))+import Data.Function.FastMemo.Word ()++instance Memoizable SBS.ByteString where+  memoize f = memoize (f . SBS.pack) . SBS.unpack++instance Memoizable LBS.ByteString where+  memoize f = memoize (f . LBS.pack) . LBS.unpack
+ src/Data/Function/FastMemo/Char.hs view
@@ -0,0 +1,40 @@+{-# OPTIONS_GHC -Wno-orphans #-}++module Data.Function.FastMemo.Char () where++import Data.Bits (complement, countLeadingZeros)+import qualified Data.ByteString as ByteString+import qualified Data.ByteString.UTF8 as UTF8+import Data.Function.FastMemo.Class (Memoizable (..))+import Data.Function.FastMemo.Util (memoizeFixedLen)+import Data.Function.FastMemo.Word ()+import Data.List.NonEmpty (NonEmpty (..))+import qualified Data.List.NonEmpty as NonEmpty+import Data.Word (Word8)++-- We want ASCII Chars to require only a single Vector lookup, so let's encode as UTF-8+instance Memoizable Char where+  memoize f = memoize (f . codePointToChar) . charToCodePoint++newtype CodePoint = CodePoint {getCodePoint :: NonEmpty Word8}++-- In UTF-8, the first byte of a codepoint tells us how many more bytes that codepoint contains.+-- We can use this fact to reduce lookups.+instance Memoizable CodePoint where+  memoize f =+    let f' = memoize (\w -> memoizeFixedLen (extraBytes w) (f . CodePoint . (w :|)))+     in \(CodePoint (w :| ws)) -> f' w ws++extraBytes :: Word8 -> Int+extraBytes x = case countLeadingOnes x of+  0 -> 0+  n -> n - 1++countLeadingOnes :: Word8 -> Int+countLeadingOnes = countLeadingZeros . complement++charToCodePoint :: Char -> CodePoint+charToCodePoint = CodePoint . NonEmpty.fromList . ByteString.unpack . UTF8.fromString . (: [])++codePointToChar :: CodePoint -> Char+codePointToChar = head . UTF8.toString . ByteString.pack . NonEmpty.toList . getCodePoint
+ src/Data/Function/FastMemo/Class.hs view
@@ -0,0 +1,49 @@+{-# LANGUAGE DefaultSignatures #-}+{-# LANGUAGE EmptyCase #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE LambdaCase #-}+{-# LANGUAGE TypeOperators #-}++module Data.Function.FastMemo.Class (Memoizable (..)) where++import Data.List.NonEmpty (NonEmpty)+import GHC.Generics++class Memoizable a where+  memoize :: (a -> b) -> a -> b+  default memoize :: (Generic a, GMemoize (Rep a)) => (a -> b) -> a -> b+  memoize f = gMemoize (f . to) . from++class GMemoize a where+  gMemoize :: (a p -> b) -> a p -> b++instance GMemoize f => GMemoize (M1 i c f) where+  gMemoize f = gMemoize (f . M1) . unM1++instance GMemoize V1 where+  gMemoize _f = \case++instance GMemoize U1 where+  gMemoize f = let fu = f U1 in \U1 -> fu++instance Memoizable c => GMemoize (K1 i c) where+  gMemoize f = memoize (f . K1) . unK1++instance (GMemoize a, GMemoize b) => GMemoize (a :*: b) where+  gMemoize f =+    let f' = gMemoize (\x -> gMemoize (\y -> f (x :*: y)))+     in \(x :*: y) -> f' x y++instance (GMemoize a, GMemoize b) => GMemoize (a :+: b) where+  gMemoize f =+    let fL = gMemoize (f . L1)+        fR = gMemoize (f . R1)+     in \case+          L1 x -> fL x+          R1 x -> fR x++instance (Memoizable a, Memoizable b) => Memoizable (a, b)++instance Memoizable a => Memoizable [a]++instance Memoizable a => Memoizable (NonEmpty a)
+ src/Data/Function/FastMemo/Instances.hs view
@@ -0,0 +1,42 @@+{-# OPTIONS_GHC -Wno-orphans #-}++module Data.Function.FastMemo.Instances () where++import Data.Complex (Complex)+import Data.Function.FastMemo.Char ()+import Data.Function.FastMemo.Class (Memoizable)+import Data.Function.FastMemo.Int ()+import Data.Functor.Identity (Identity)+import Data.Proxy (Proxy)+import Data.Version (Version)+import Data.Void (Void)++instance Memoizable Bool++instance Memoizable a => Memoizable (Maybe a)++instance (Memoizable a, Memoizable b) => Memoizable (Either a b)++instance Memoizable Void++instance Memoizable ()++instance Memoizable (Proxy a)++instance Memoizable Ordering++instance Memoizable a => Memoizable (Complex a)++instance Memoizable Version++instance Memoizable a => Memoizable (Identity a)++instance (Memoizable a, Memoizable b, Memoizable c) => Memoizable (a, b, c)++instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d) => Memoizable (a, b, c, d)++instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e) => Memoizable (a, b, c, d, e)++instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f) => Memoizable (a, b, c, d, e, f)++instance (Memoizable a, Memoizable b, Memoizable c, Memoizable d, Memoizable e, Memoizable f, Memoizable g) => Memoizable (a, b, c, d, e, f, g)
+ src/Data/Function/FastMemo/Int.hs view
@@ -0,0 +1,29 @@+{-# LANGUAGE DerivingVia #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE StandaloneDeriving #-}+{-# OPTIONS_GHC -Wno-orphans #-}++module Data.Function.FastMemo.Int () where++import Data.Function.FastMemo.Class (Memoizable (..))+import Data.Function.FastMemo.Word ()+import Data.Int+import Data.Word++deriving via IntegralConversion Int Word instance Memoizable Int++deriving via IntegralConversion Int8 Word8 instance Memoizable Int8++deriving via IntegralConversion Int16 Word16 instance Memoizable Int16++deriving via IntegralConversion Int32 Word32 instance Memoizable Int32++deriving via IntegralConversion Int64 Word64 instance Memoizable Int64++newtype IntegralConversion a b = IntegralConversion {getIntegralConversion :: a}++instance (Integral a, Integral b, Memoizable b) => Memoizable (IntegralConversion a b) where+  memoize f =+    memoize (f . IntegralConversion . fromIntegral)+      . (fromIntegral :: a -> b)+      . getIntegralConversion
+ src/Data/Function/FastMemo/Integer.hs view
@@ -0,0 +1,27 @@+{-# LANGUAGE DeriveAnyClass #-}+{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE LambdaCase #-}+{-# OPTIONS_GHC -Wno-orphans #-}++module Data.Function.FastMemo.Integer () where++import Data.Function.FastMemo.Class (Memoizable (..))+import Data.Function.FastMemo.Natural ()+import GHC.Generics (Generic)+import Numeric.Natural (Natural)++instance Memoizable Integer where+  memoize f = memoize (f . signedNatToInteger) . integerToSignedNat++data Sign = NegativePlus1 | NonNegative+  deriving (Generic, Memoizable)++integerToSignedNat :: Integer -> (Sign, Natural)+integerToSignedNat i+  | i < 0 = (NegativePlus1, fromInteger (- (i + 1)))+  | otherwise = (NonNegative, fromInteger i)++signedNatToInteger :: (Sign, Natural) -> Integer+signedNatToInteger = \case+  (NegativePlus1, n) -> - (toInteger n + 1)+  (NonNegative, n) -> toInteger n
+ src/Data/Function/FastMemo/Natural.hs view
@@ -0,0 +1,28 @@+{-# OPTIONS_GHC -Wno-orphans #-}++module Data.Function.FastMemo.Natural () where++import Data.Bits (shiftL, shiftR, (.|.))+import Data.Foldable (foldl')+import Data.Function.FastMemo.Class (Memoizable (..))+import Data.Function.FastMemo.Word ()+import Data.List.NonEmpty (NonEmpty (..))+import Data.Word (Word8)+import Numeric.Natural (Natural)++instance Memoizable Natural where+  memoize f = memoize (f . wordsToNat) . natToWords++-- A slightly weird encoding that assigns unique values to each of [0], [0,0], [0,0,0]...+natToWords :: Natural -> NonEmpty Word8+natToWords = go []+  where+    go acc n =+      if n <= 0xff+        then w :| acc+        else go (w : acc) (n `shiftR` 8 - 1)+      where+        w = fromIntegral n++wordsToNat :: NonEmpty Word8 -> Natural+wordsToNat (w0 :| ws0) = foldl' (\acc w -> (acc + 1) `shiftL` 8 .|. fromIntegral w) (fromIntegral w0) ws0
+ src/Data/Function/FastMemo/Ratio.hs view
@@ -0,0 +1,9 @@+{-# OPTIONS_GHC -Wno-orphans #-}++module Data.Function.FastMemo.Ratio () where++import Data.Function.FastMemo.Class (Memoizable (..))+import Data.Ratio (Ratio, denominator, numerator, (%))++instance (Integral a, Memoizable a) => Memoizable (Ratio a) where+  memoize f = memoize (f . uncurry (%)) . (\x -> (numerator x, denominator x))
+ src/Data/Function/FastMemo/Util.hs view
@@ -0,0 +1,18 @@+{-# LANGUAGE LambdaCase #-}++module Data.Function.FastMemo.Util (memoizeFixedLen) where++import Data.Function.FastMemo.Class (Memoizable, memoize)+import GHC.Stack (HasCallStack)++-- | Memoize a function on a list whose length is predetermined.+--+-- If called on a larger list, it will truncate; on a smaller list, it will throw an error+memoizeFixedLen :: (HasCallStack, Memoizable a) => Int -> ([a] -> b) -> [a] -> b+memoizeFixedLen n f+  | n <= 0 = const (f [])+  | otherwise =+    let f' = memoize $ \x -> memoizeFixedLen (n - 1) (f . (x :))+     in \case+          [] -> error "List too short"+          x : xs -> f' x xs
+ src/Data/Function/FastMemo/Vector.hs view
@@ -0,0 +1,17 @@+{-# OPTIONS_GHC -Wno-orphans #-}++module Data.Function.FastMemo.Vector () where++import Data.Function.FastMemo.Class (Memoizable (..))+import qualified Data.Vector as V+import qualified Data.Vector.Storable as SV+import qualified Data.Vector.Unboxed as UV++instance Memoizable a => Memoizable (V.Vector a) where+  memoize f = memoize (f . V.fromList) . V.toList++instance (SV.Storable a, Memoizable a) => Memoizable (SV.Vector a) where+  memoize f = memoize (f . SV.fromList) . SV.toList++instance (UV.Unbox a, Memoizable a) => Memoizable (UV.Vector a) where+  memoize f = memoize (f . UV.fromList) . UV.toList
+ src/Data/Function/FastMemo/Word.hs view
@@ -0,0 +1,43 @@+{-# LANGUAGE DerivingVia #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE StandaloneDeriving #-}+{-# OPTIONS_GHC -Wno-orphans #-}++module Data.Function.FastMemo.Word () where++import Data.Bits+import Data.Foldable (foldl')+import Data.Function.FastMemo.Class (Memoizable (..))+import Data.Function.FastMemo.Util (memoizeFixedLen)+import qualified Data.Vector as V+import Data.Word++instance Memoizable Word8 where+  memoize f =+    let values = f <$> V.fromList [0x00 .. 0xff]+     in \i -> values V.! fromIntegral i++deriving via MemoWord Word instance Memoizable Word++deriving via MemoWord Word16 instance Memoizable Word16++deriving via MemoWord Word32 instance Memoizable Word32++deriving via MemoWord Word64 instance Memoizable Word64++newtype MemoWord a = MemoWord {getMemoWord :: a}++instance (FiniteBits a, Integral a) => Memoizable (MemoWord a) where+  memoize f =+    memoizeFixedLen (byteLen (0 :: a)) (f . MemoWord . fromBytes) . toBytes . getMemoWord++byteLen :: FiniteBits a => a -> Int+byteLen x = (finiteBitSize x + 7) `quot` 8++toBytes :: (FiniteBits a, Integral a) => a -> [Word8]+toBytes x = [fromIntegral (x `shiftR` i) | i <- [s0, s0 - 8 .. 0]]+  where+    s0 = (byteLen x - 1) * 8++fromBytes :: (Bits a, Num a) => [Word8] -> a+fromBytes = foldl' (\acc x -> acc `shiftL` 8 .|. fromIntegral x) 0
+ test/Examples.hs view
@@ -0,0 +1,21 @@+{-# LANGUAGE DeriveAnyClass #-}+{-# LANGUAGE DeriveGeneric #-}++module Examples where++import Data.Function.FastMemo (Memoizable, memoize)+import Data.Word (Word8)+import GHC.Generics (Generic)+import Numeric.Natural (Natural)++data Color = Color {red :: Word8, green :: Word8, blue :: Word8}+  deriving (Generic, Memoizable)++data Tree a = Leaf a | Node (Tree a) (Tree a)+  deriving (Generic, Memoizable)++fibonacci :: Natural -> Natural+fibonacci = memoize $ \i -> case i of+  0 -> 0+  1 -> 1+  _ -> fibonacci (i - 1) + fibonacci (i - 2)
+ test/Spec.hs view
@@ -0,0 +1,174 @@+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE StandaloneDeriving #-}+{-# LANGUAGE TemplateHaskell #-}+{-# OPTIONS_GHC -Wno-orphans #-}++import Control.Exception (ErrorCall (..), catch, evaluate)+import Data.Function.FastMemo+import Data.Functor (($>))+import Data.Int (Int16, Int32, Int64, Int8)+import Data.Proxy (Proxy (Proxy))+import Data.Ratio (Ratio)+import Data.Word (Word16, Word32, Word64, Word8)+import Examples (Color (Color), Tree (Leaf, Node), fibonacci)+import Numeric.Natural (Natural)+import Test.QuickCheck++prop_memoizesFib :: Property+prop_memoizesFib = forAllShrink (sized $ \size -> choose (0, size)) shrink $+  \i -> fibonacci (fromIntegral i) === allFibs !! i++allFibs :: [Natural]+allFibs = 0 : 1 : zipWith (+) allFibs (tail allFibs)++instance Arbitrary Natural where+  arbitrary = fromInteger . getNonNegative <$> arbitrary+  shrink = map (fromInteger . getNonNegative) . shrink . NonNegative . toInteger++instance Arbitrary (Proxy a) where+  arbitrary = return Proxy++prop_memoizesId :: (Eq a, Show a, Memoizable a) => a -> Property+prop_memoizesId = let m = memoize id in \x -> m x === x++prop_memoizeFixedLenFixesLen :: (Eq a, Show a, Memoizable a) => Int -> [a] -> Property+prop_memoizeFixedLenFixesLen n =+  let m = memoizeFixedLen n id+   in \xs ->+        if length xs < n+          then expectErrorCall (Just "List too short") (m xs)+          else m xs === take n xs++expectErrorCall :: Maybe String -> a -> Property+expectErrorCall expected x =+  ioProperty $+    (evaluate x $> property False)+      `catch` \(ErrorCall msg) -> return $ maybe (property True) (msg ===) expected++prop_boolMemoizesId :: Bool -> Property+prop_boolMemoizesId = prop_memoizesId++prop_charMemoizesId :: Char -> Property+prop_charMemoizesId = prop_memoizesId++prop_stringMemoizesId :: String -> Property+prop_stringMemoizesId = prop_memoizesId++prop_integerMemoizesId :: Integer -> Property+prop_integerMemoizesId = prop_memoizesId++prop_bigIntegerMemoizesId :: Property+prop_bigIntegerMemoizesId =+  forAllShrink+    (genBigBound >>= \b -> choose (- b, b))+    shrink+    prop_memoizesId++genBigBound :: Gen Integer+genBigBound = sized $ \n -> return $ 256 ^ n++prop_naturalMemoizesId :: Natural -> Property+prop_naturalMemoizesId = prop_memoizesId++prop_bigNaturalMemoizesId :: Property+prop_bigNaturalMemoizesId =+  forAllShrink+    (genBigBound >>= \b -> (fromInteger :: Integer -> Natural) <$> choose (0, b))+    shrink+    prop_memoizesId++prop_unitMemoizesId :: () -> Property+prop_unitMemoizesId = prop_memoizesId++prop_eitherMemoizesId ::+  (Eq a, Show a, Memoizable a, Eq b, Show b, Memoizable b) => Either a b -> Property+prop_eitherMemoizesId = prop_memoizesId++prop_pairMemoizesId :: (Eq a, Show a, Memoizable a, Eq b, Show b, Memoizable b) => (a, b) -> Property+prop_pairMemoizesId = prop_memoizesId++prop_tripletMemoizesId ::+  (Eq a, Show a, Memoizable a, Eq b, Show b, Memoizable b, Eq c, Show c, Memoizable c) =>+  (a, b, c) ->+  Property+prop_tripletMemoizesId = prop_memoizesId++prop_maybeMemoizesId :: (Eq a, Show a, Memoizable a) => Maybe a -> Property+prop_maybeMemoizesId = prop_memoizesId++prop_listMemoizesId :: (Eq a, Show a, Memoizable a) => [a] -> Property+prop_listMemoizesId = prop_memoizesId++prop_intMemoizesId :: Int -> Property+prop_intMemoizesId = prop_memoizesId++prop_largeIntMemoizesId :: Large Int -> Property+prop_largeIntMemoizesId (Large i) = prop_memoizesId i++prop_int8MemoizesId :: Int8 -> Property+prop_int8MemoizesId = prop_memoizesId++prop_int16MemoizesId :: Int16 -> Property+prop_int16MemoizesId = prop_memoizesId++prop_int32MemoizesId :: Int32 -> Property+prop_int32MemoizesId = prop_memoizesId++prop_int64MemoizesId :: Int64 -> Property+prop_int64MemoizesId = prop_memoizesId++prop_wordMemoizesId :: Word -> Property+prop_wordMemoizesId = prop_memoizesId++prop_largeWordMemoizesId :: Large Word -> Property+prop_largeWordMemoizesId (Large w) = prop_memoizesId w++prop_word8MemoizesId :: Word8 -> Property+prop_word8MemoizesId = prop_memoizesId++prop_word16MemoizesId :: Word16 -> Property+prop_word16MemoizesId = prop_memoizesId++prop_word32MemoizesId :: Word32 -> Property+prop_word32MemoizesId = prop_memoizesId++prop_word64MemoizesId :: Word64 -> Property+prop_word64MemoizesId = prop_memoizesId++prop_ratioMemoizesId :: (Integral a, Memoizable a, Show a) => Ratio a -> Property+prop_ratioMemoizesId = prop_memoizesId++deriving instance Eq Color++deriving instance Show Color++instance Arbitrary Color where+  arbitrary = Color <$> arbitrary <*> arbitrary <*> arbitrary+  shrink = genericShrink++prop_colorMemoizesId :: Color -> Property+prop_colorMemoizesId = prop_memoizesId++deriving instance Eq a => Eq (Tree a)++deriving instance Show a => Show (Tree a)++instance Arbitrary a => Arbitrary (Tree a) where+  arbitrary = sized $ \n -> do+    let h = (n - 1) `quot` 2+        h' = n - 1 - h+    frequency+      [ (1, Leaf <$> arbitrary),+        (max (n - 1) 0, Node <$> resize h arbitrary <*> resize h' arbitrary)+      ]+  shrink = genericShrink++prop_treeMemoizesId :: (Eq a, Show a, Memoizable a) => Tree a -> Property+prop_treeMemoizesId = prop_memoizesId++return []++main :: IO ()+main = do+  True <- $quickCheckAll+  return ()