-- 
-- (c) Susumu Katayama
--
{-# LANGUAGE CPP, RankNTypes #-}
module Data.Memo where
import Data.Char(ord,chr)
import Data.Bits
import Data.Array

import Data.List(sort) -- just for testing the efficiency

import Language.Haskell.TH

-- This could be a separate module.
#if QUICKCHECK>=2
import Test.QuickCheck.Function
#endif
#ifdef QUICKCHECK
import Test.QuickCheck
#else
infixr 0 ==>
type Property = Bool
==> :: Bool -> Bool -> Bool
(==>) = Bool -> Bool -> Bool
forall a. Ord a => a -> a -> Bool
(<=)
#endif
#if QUICKCHECK>=2
#else
type Function = (->)
getFunction :: a -> a
getFunction = a -> a
forall a. a -> a
id
#endif

newtype MapUnit a = MU a -- equivalent to Control.Monad.Identity.Identity
memoUnit :: (() -> a) -> MapUnit a
memoUnit :: (() -> a) -> MapUnit a
memoUnit () -> a
f = a -> MapUnit a
forall a. a -> MapUnit a
MU (() -> a
f ())
appUnit  :: MapUnit a -> (()->a)
appUnit :: MapUnit a -> () -> a
appUnit (MU a
x) ()
_ = a
x -- Should I write () instead of _ to make it strict?

data MapBool a = MB a a
memoBool :: (Bool->a) -> MapBool a
memoBool :: (Bool -> a) -> MapBool a
memoBool Bool -> a
f = a -> a -> MapBool a
forall a. a -> a -> MapBool a
MB (Bool -> a
f Bool
False) (Bool -> a
f Bool
True)
appBool  :: MapBool a -> (Bool -> a)
appBool :: MapBool a -> Bool -> a
appBool  (MB a
f a
t) Bool
False = a
f
appBool  (MB a
f a
t) Bool
True  = a
t

prop_inverseBool :: Bool -> Function Bool Int -> Bool
prop_inverseBool :: Bool -> Function Bool Int -> Bool
prop_inverseBool Bool
b Function Bool Int
f = MapBool Int -> Function Bool Int
forall a. MapBool a -> Bool -> a
appBool (Function Bool Int -> MapBool Int
forall a. (Bool -> a) -> MapBool a
memoBool (Function Bool Int -> Function Bool Int
forall a. a -> a
getFunction Function Bool Int
f)) Bool
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Function Bool Int -> Function Bool Int
forall a. a -> a
getFunction Function Bool Int
f Bool
b

data MapOrdering a = MO a a a
memoOrdering :: (Ordering->a) -> MapOrdering a
memoOrdering :: (Ordering -> a) -> MapOrdering a
memoOrdering Ordering -> a
f = a -> a -> a -> MapOrdering a
forall a. a -> a -> a -> MapOrdering a
MO (Ordering -> a
f Ordering
LT) (Ordering -> a
f Ordering
EQ) (Ordering -> a
f Ordering
GT)
appOrdering  :: MapOrdering a -> Ordering->a
appOrdering :: MapOrdering a -> Ordering -> a
appOrdering  (MO a
l a
e a
g) Ordering
LT = a
l
appOrdering  (MO a
l a
e a
g) Ordering
EQ = a
e
appOrdering  (MO a
l a
e a
g) Ordering
GT = a
g

data MapMaybe m a = MM a (m a)
memoMaybe :: ((b->a)->m a) -> (Maybe b -> a) -> MapMaybe m a
memoMaybe :: ((b -> a) -> m a) -> (Maybe b -> a) -> MapMaybe m a
memoMaybe (b -> a) -> m a
g Maybe b -> a
f = a -> m a -> MapMaybe m a
forall (m :: * -> *) a. a -> m a -> MapMaybe m a
MM (Maybe b -> a
f Maybe b
forall a. Maybe a
Nothing) ((b -> a) -> m a
g (\b
b -> Maybe b -> a
f (b -> Maybe b
forall a. a -> Maybe a
Just b
b)))
appMaybe  :: (m a->(b->a)) -> MapMaybe m a -> (Maybe b -> a)
appMaybe :: (m a -> b -> a) -> MapMaybe m a -> Maybe b -> a
appMaybe  m a -> b -> a
_ (MM a
n m a
_) Maybe b
Nothing  = a
n
appMaybe  m a -> b -> a
g (MM a
_ m a
j) (Just b
x) = m a -> b -> a
g m a
j b
x
prop_inverseMaybe :: Maybe Ordering -> (Maybe Ordering -> Integer) -> Bool
prop_inverseMaybe :: Maybe Ordering -> (Maybe Ordering -> Integer) -> Bool
prop_inverseMaybe Maybe Ordering
mb Maybe Ordering -> Integer
f = (MapOrdering Integer -> Ordering -> Integer)
-> MapMaybe MapOrdering Integer -> Maybe Ordering -> Integer
forall (m :: * -> *) a b.
(m a -> b -> a) -> MapMaybe m a -> Maybe b -> a
appMaybe MapOrdering Integer -> Ordering -> Integer
forall a. MapOrdering a -> Ordering -> a
appOrdering (((Ordering -> Integer) -> MapOrdering Integer)
-> (Maybe Ordering -> Integer) -> MapMaybe MapOrdering Integer
forall b a (m :: * -> *).
((b -> a) -> m a) -> (Maybe b -> a) -> MapMaybe m a
memoMaybe (Ordering -> Integer) -> MapOrdering Integer
forall a. (Ordering -> a) -> MapOrdering a
memoOrdering Maybe Ordering -> Integer
f) Maybe Ordering
mb Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Maybe Ordering -> Integer
f Maybe Ordering
mb

data MapEither m n a = ME (m a) (n a)
memoEither :: ((b->a) -> m a) -> ((d->a) -> n a) -> (Either b d -> a) -> MapEither m n a
memoEither :: ((b -> a) -> m a)
-> ((d -> a) -> n a) -> (Either b d -> a) -> MapEither m n a
memoEither (b -> a) -> m a
g (d -> a) -> n a
h Either b d -> a
f = m a -> n a -> MapEither m n a
forall (m :: * -> *) (n :: * -> *) a. m a -> n a -> MapEither m n a
ME ((b -> a) -> m a
g (\b
b -> Either b d -> a
f (b -> Either b d
forall a b. a -> Either a b
Left b
b))) ((d -> a) -> n a
h (\d
d -> Either b d -> a
f (d -> Either b d
forall a b. b -> Either a b
Right d
d)))
appEither  :: (m a -> (b->a)) -> (n a -> (d->a)) -> MapEither m n a -> (Either b d -> a)
appEither :: (m a -> b -> a)
-> (n a -> d -> a) -> MapEither m n a -> Either b d -> a
appEither  m a -> b -> a
g n a -> d -> a
_ (ME m a
l n a
_) (Left  b
x) = m a -> b -> a
g m a
l b
x
appEither  m a -> b -> a
_ n a -> d -> a
h (ME m a
_ n a
r) (Right d
x) = n a -> d -> a
h n a
r d
x
prop_inverseEither :: Either Int [Bool] -> (Either Int [Bool] -> Integer) -> Bool
prop_inverseEither :: Either Int [Bool] -> (Either Int [Bool] -> Integer) -> Bool
prop_inverseEither Either Int [Bool]
e Either Int [Bool] -> Integer
f = (MapIntegral Integer -> Int -> Integer)
-> (MapFiniteList MapBool Integer -> [Bool] -> Integer)
-> MapEither MapIntegral (MapFiniteList MapBool) Integer
-> Either Int [Bool]
-> Integer
forall (m :: * -> *) a b (n :: * -> *) d.
(m a -> b -> a)
-> (n a -> d -> a) -> MapEither m n a -> Either b d -> a
appEither MapIntegral Integer -> Int -> Integer
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral ((forall a. MapBool a -> Bool -> a)
-> MapFiniteList MapBool Integer -> [Bool] -> Integer
forall (m :: * -> *) b a.
(forall c. m c -> b -> c) -> MapFiniteList m a -> [b] -> a
appFiniteList forall a. MapBool a -> Bool -> a
appBool) (((Int -> Integer) -> MapIntegral Integer)
-> (([Bool] -> Integer) -> MapFiniteList MapBool Integer)
-> (Either Int [Bool] -> Integer)
-> MapEither MapIntegral (MapFiniteList MapBool) Integer
forall b a (m :: * -> *) d (n :: * -> *).
((b -> a) -> m a)
-> ((d -> a) -> n a) -> (Either b d -> a) -> MapEither m n a
memoEither (Int -> Integer) -> MapIntegral Integer
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral ((forall a. (Bool -> a) -> MapBool a)
-> ([Bool] -> Integer) -> MapFiniteList MapBool Integer
forall b (m :: * -> *) a.
(forall c. (b -> c) -> m c) -> ([b] -> a) -> MapFiniteList m a
memoFiniteList forall a. (Bool -> a) -> MapBool a
memoBool) Either Int [Bool] -> Integer
f) Either Int [Bool]
e Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Either Int [Bool] -> Integer
f Either Int [Bool]
e

newtype MapPair m n a = MP (m (n a))
memoPair   :: (forall e. (b->e) -> m e) -> (forall f. (d->f) -> n f) -> ((b,d) -> a) -> MapPair m n a
memoPair :: (forall e. (b -> e) -> m e)
-> (forall f. (d -> f) -> n f) -> ((b, d) -> a) -> MapPair m n a
memoPair   forall e. (b -> e) -> m e
g forall f. (d -> f) -> n f
h (b, d) -> a
f = m (n a) -> MapPair m n a
forall (m :: * -> *) (n :: * -> *) a. m (n a) -> MapPair m n a
MP (m (n a) -> MapPair m n a) -> m (n a) -> MapPair m n a
forall a b. (a -> b) -> a -> b
$ (b -> n a) -> m (n a)
forall e. (b -> e) -> m e
g (\b
b -> (d -> a) -> n a
forall f. (d -> f) -> n f
h (\d
d -> (b, d) -> a
f (b
b,d
d)))
appPair    :: (forall e. m e -> (b->e)) -> (forall f. n f -> (d->f)) -> MapPair m n a -> ((b,d) -> a)
appPair :: (forall e. m e -> b -> e)
-> (forall f. n f -> d -> f) -> MapPair m n a -> (b, d) -> a
appPair    forall e. m e -> b -> e
g forall f. n f -> d -> f
h (MP m (n a)
m) (b
x,d
y) = n a -> d -> a
forall f. n f -> d -> f
h (m (n a) -> b -> n a
forall e. m e -> b -> e
g m (n a)
m b
x) d
y

type MapTriplet l m n = MapPair (MapPair l m) n
memoTriplet :: (forall e. (b->e) -> l e) ->
               (forall e. (c->e) -> m e) ->
               (forall e. (d->e) -> n e) -> ((b,c,d) -> a) -> MapTriplet l m n a
memoTriplet :: (forall e. (b -> e) -> l e)
-> (forall e. (c -> e) -> m e)
-> (forall e. (d -> e) -> n e)
-> ((b, c, d) -> a)
-> MapTriplet l m n a
memoTriplet forall e. (b -> e) -> l e
g forall e. (c -> e) -> m e
h forall e. (d -> e) -> n e
i (b, c, d) -> a
f = (forall e. ((b, c) -> e) -> MapPair l m e)
-> (forall e. (d -> e) -> n e)
-> (((b, c), d) -> a)
-> MapTriplet l m n a
forall b (m :: * -> *) d (n :: * -> *) a.
(forall e. (b -> e) -> m e)
-> (forall f. (d -> f) -> n f) -> ((b, d) -> a) -> MapPair m n a
memoPair ((forall e. (b -> e) -> l e)
-> (forall e. (c -> e) -> m e) -> ((b, c) -> e) -> MapPair l m e
forall b (m :: * -> *) d (n :: * -> *) a.
(forall e. (b -> e) -> m e)
-> (forall f. (d -> f) -> n f) -> ((b, d) -> a) -> MapPair m n a
memoPair forall e. (b -> e) -> l e
g forall e. (c -> e) -> m e
h) forall e. (d -> e) -> n e
i (\((b
x,c
y),d
z) -> (b, c, d) -> a
f (b
x,c
y,d
z))
appTriplet  ::  (forall e. l e -> (b->e)) -> (forall e. m e -> (c->e)) -> (forall e. n e -> (d->e)) -> MapTriplet l m n a -> ((b,c,d) -> a)
appTriplet :: (forall e. l e -> b -> e)
-> (forall e. m e -> c -> e)
-> (forall e. n e -> d -> e)
-> MapTriplet l m n a
-> (b, c, d)
-> a
appTriplet  forall e. l e -> b -> e
g forall e. m e -> c -> e
h forall e. n e -> d -> e
i MapTriplet l m n a
m (b
x,c
y,d
z) = (forall e. MapPair l m e -> (b, c) -> e)
-> (forall e. n e -> d -> e)
-> MapTriplet l m n a
-> ((b, c), d)
-> a
forall (m :: * -> *) b (n :: * -> *) d a.
(forall e. m e -> b -> e)
-> (forall f. n f -> d -> f) -> MapPair m n a -> (b, d) -> a
appPair ((forall e. l e -> b -> e)
-> (forall e. m e -> c -> e) -> MapPair l m e -> (b, c) -> e
forall (m :: * -> *) b (n :: * -> *) d a.
(forall e. m e -> b -> e)
-> (forall f. n f -> d -> f) -> MapPair m n a -> (b, d) -> a
appPair forall e. l e -> b -> e
g forall e. m e -> c -> e
h) forall e. n e -> d -> e
i MapTriplet l m n a
m ((b
x,c
y),d
z)
prop_inverseTriplet :: (Int,[Bool],[Int]) -> ((Int,[Bool],[Int]) -> Integer) -> Bool
prop_inverseTriplet :: (Int, [Bool], [Int]) -> ((Int, [Bool], [Int]) -> Integer) -> Bool
prop_inverseTriplet (Int, [Bool], [Int])
t (Int, [Bool], [Int]) -> Integer
f = (forall e. MapIntegral e -> Int -> e)
-> (forall e. MapList MapBool Bool e -> [Bool] -> e)
-> (forall e. MapList MapIntegral Int e -> [Int] -> e)
-> MapTriplet
     MapIntegral
     (MapList MapBool Bool)
     (MapList MapIntegral Int)
     Integer
-> (Int, [Bool], [Int])
-> Integer
forall (l :: * -> *) b (m :: * -> *) c (n :: * -> *) d a.
(forall e. l e -> b -> e)
-> (forall e. m e -> c -> e)
-> (forall e. n e -> d -> e)
-> MapTriplet l m n a
-> (b, c, d)
-> a
appTriplet forall e. MapIntegral e -> Int -> e
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral (Int
-> (forall a. MapBool a -> Bool -> a)
-> MapList MapBool Bool e
-> [Bool]
-> e
forall (m :: * -> *) b a.
Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList Int
5 forall a. MapBool a -> Bool -> a
appBool) (Int
-> (forall e. MapIntegral e -> Int -> e)
-> MapList MapIntegral Int e
-> [Int]
-> e
forall (m :: * -> *) b a.
Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList Int
5 forall e. MapIntegral e -> Int -> e
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral) ((forall e. (Int -> e) -> MapIntegral e)
-> (forall e. ([Bool] -> e) -> MapList MapBool Bool e)
-> (forall e. ([Int] -> e) -> MapList MapIntegral Int e)
-> ((Int, [Bool], [Int]) -> Integer)
-> MapTriplet
     MapIntegral
     (MapList MapBool Bool)
     (MapList MapIntegral Int)
     Integer
forall b (l :: * -> *) c (m :: * -> *) d (n :: * -> *) a.
(forall e. (b -> e) -> l e)
-> (forall e. (c -> e) -> m e)
-> (forall e. (d -> e) -> n e)
-> ((b, c, d) -> a)
-> MapTriplet l m n a
memoTriplet forall e. (Int -> e) -> MapIntegral e
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral ((forall a. (Bool -> a) -> MapBool a)
-> ([Bool] -> e) -> MapList MapBool Bool e
forall b (m :: * -> *) a.
(forall c. (b -> c) -> m c) -> ([b] -> a) -> MapList m b a
memoList forall a. (Bool -> a) -> MapBool a
memoBool) ((forall e. (Int -> e) -> MapIntegral e)
-> ([Int] -> e) -> MapList MapIntegral Int e
forall b (m :: * -> *) a.
(forall c. (b -> c) -> m c) -> ([b] -> a) -> MapList m b a
memoList forall e. (Int -> e) -> MapIntegral e
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral) (Int, [Bool], [Int]) -> Integer
f) (Int, [Bool], [Int])
t Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== (Int, [Bool], [Int]) -> Integer
f (Int, [Bool], [Int])
t

-- | MapList m a is a memoization of |[b]->a|, where m c is the memoization of b->c. Because we cannot memoize functions taking infinite lists (and long lists practically), functions are silently recomputed if the length if its argument list is more than the length limit.
data MapList m b a = ML (MapFiniteList m a) ([b]->a)
data MapFiniteList m a = MFL {
      MapFiniteList m a -> a
nilArrow  :: a,
      MapFiniteList m a -> m (MapFiniteList m a)
consArrow :: m (MapFiniteList m a)
    }
memoList   :: (forall c. (b->c) -> m c) -> ([b] -> a) -> MapList m b a
memoList :: (forall c. (b -> c) -> m c) -> ([b] -> a) -> MapList m b a
memoList   forall c. (b -> c) -> m c
g [b] -> a
f = MapFiniteList m a -> ([b] -> a) -> MapList m b a
forall (m :: * -> *) b a.
MapFiniteList m a -> ([b] -> a) -> MapList m b a
ML ((forall c. (b -> c) -> m c) -> ([b] -> a) -> MapFiniteList m a
forall b (m :: * -> *) a.
(forall c. (b -> c) -> m c) -> ([b] -> a) -> MapFiniteList m a
memoFiniteList forall c. (b -> c) -> m c
g [b] -> a
f) [b] -> a
f
appList10 :: (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList10 = Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
forall (m :: * -> *) b a.
Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList Int
10
appList5 :: (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList5  = Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
forall (m :: * -> *) b a.
Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList Int
5
appList3 :: (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList3  = Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
forall (m :: * -> *) b a.
Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList Int
3
appList1 :: (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList1  = Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
forall (m :: * -> *) b a.
Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList Int
1
appList    :: Int -- ^ length limit
              -> (forall c. m c -> (b->c)) -> MapList m b a -> ([b]->a)
appList :: Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList    Int
lenlim forall c. m c -> b -> c
g (ML MapFiniteList m a
m [b] -> a
f) [b]
xs | [b]
xs [b] -> Int -> Bool
forall t a. (Ord t, Num t) => [a] -> t -> Bool
`isLongerThan` Int
lenlim = [b] -> a
f [b]
xs
                                | Bool
otherwise                = (forall c. m c -> b -> c) -> MapFiniteList m a -> [b] -> a
forall (m :: * -> *) b a.
(forall c. m c -> b -> c) -> MapFiniteList m a -> [b] -> a
appFiniteList forall c. m c -> b -> c
g MapFiniteList m a
m [b]
xs
memoFiniteList   :: (forall c. (b->c) -> m c) -> ([b] -> a) -> MapFiniteList m a
memoFiniteList :: (forall c. (b -> c) -> m c) -> ([b] -> a) -> MapFiniteList m a
memoFiniteList   forall c. (b -> c) -> m c
g [b] -> a
f = a -> m (MapFiniteList m a) -> MapFiniteList m a
forall (m :: * -> *) a.
a -> m (MapFiniteList m a) -> MapFiniteList m a
MFL ([b] -> a
f []) ((b -> MapFiniteList m a) -> m (MapFiniteList m a)
forall c. (b -> c) -> m c
g (\b
b -> (forall c. (b -> c) -> m c) -> ([b] -> a) -> MapFiniteList m a
forall b (m :: * -> *) a.
(forall c. (b -> c) -> m c) -> ([b] -> a) -> MapFiniteList m a
memoFiniteList forall c. (b -> c) -> m c
g (\[b]
bs -> [b] -> a
f (b
bb -> [b] -> [b]
forall a. a -> [a] -> [a]
:[b]
bs))))
appFiniteList    :: (forall c. m c -> (b->c)) -> MapFiniteList m a -> ([b]->a)
appFiniteList :: (forall c. m c -> b -> c) -> MapFiniteList m a -> [b] -> a
appFiniteList    forall c. m c -> b -> c
_ (MFL a
n m (MapFiniteList m a)
_) []     = a
n
appFiniteList    forall c. m c -> b -> c
g (MFL a
_ m (MapFiniteList m a)
c) (b
x:[b]
xs) = (forall c. m c -> b -> c) -> MapFiniteList m a -> [b] -> a
forall (m :: * -> *) b a.
(forall c. m c -> b -> c) -> MapFiniteList m a -> [b] -> a
appFiniteList forall c. m c -> b -> c
g (m (MapFiniteList m a) -> b -> MapFiniteList m a
forall c. m c -> b -> c
g m (MapFiniteList m a)
c b
x) [b]
xs

[a]
xs     isLongerThan :: [a] -> t -> Bool
`isLongerThan` t
n | t
nt -> t -> Bool
forall a. Ord a => a -> a -> Bool
<t
0 = Bool
True
[]     `isLongerThan` t
n = Bool
False
(a
x:[a]
xs) `isLongerThan` t
n = [a]
xs [a] -> t -> Bool
`isLongerThan` (t
nt -> t -> t
forall a. Num a => a -> a -> a
-t
1)

prop_inverseList :: [Int] -> (Function [Int] Integer) -> Bool
prop_inverseList :: [Int] -> Function [Int] Integer -> Bool
prop_inverseList [Int]
xs Function [Int] Integer
f = Int
-> (forall e. MapIntegral e -> Int -> e)
-> MapList MapIntegral Int Integer
-> Function [Int] Integer
forall (m :: * -> *) b a.
Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList Int
5 forall e. MapIntegral e -> Int -> e
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral ((forall e. (Int -> e) -> MapIntegral e)
-> Function [Int] Integer -> MapList MapIntegral Int Integer
forall b (m :: * -> *) a.
(forall c. (b -> c) -> m c) -> ([b] -> a) -> MapList m b a
memoList forall e. (Int -> e) -> MapIntegral e
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral (Function [Int] Integer -> Function [Int] Integer
forall a. a -> a
getFunction Function [Int] Integer
f)) [Int]
xs Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Function [Int] Integer -> Function [Int] Integer
forall a. a -> a
getFunction Function [Int] Integer
f [Int]
xs
prop_inverseListB :: [Bool] -> (Function [Bool] Integer) -> Bool
prop_inverseListB :: [Bool] -> ([Bool] -> Integer) -> Bool
prop_inverseListB [Bool]
xs [Bool] -> Integer
f = Int
-> (forall a. MapBool a -> Bool -> a)
-> MapList MapBool Bool Integer
-> [Bool]
-> Integer
forall (m :: * -> *) b a.
Int -> (forall c. m c -> b -> c) -> MapList m b a -> [b] -> a
appList Int
5 forall a. MapBool a -> Bool -> a
appBool ((forall a. (Bool -> a) -> MapBool a)
-> ([Bool] -> Integer) -> MapList MapBool Bool Integer
forall b (m :: * -> *) a.
(forall c. (b -> c) -> m c) -> ([b] -> a) -> MapList m b a
memoList forall a. (Bool -> a) -> MapBool a
memoBool (([Bool] -> Integer) -> [Bool] -> Integer
forall a. a -> a
getFunction [Bool] -> Integer
f)) [Bool]
xs Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== ([Bool] -> Integer) -> [Bool] -> Integer
forall a. a -> a
getFunction [Bool] -> Integer
f [Bool]
xs

type MapInteger = MapLargeIntegral Integer
memoInteger :: (Integer->a) -> MapInteger a
memoInteger :: (Integer -> a) -> MapInteger a
memoInteger = (Integer -> a) -> MapInteger a
forall i a. (Bits i, Num i) => (i -> a) -> MapLargeIntegral i a
memoLargeIntegral
appInteger  :: MapInteger a -> Integer->a
appInteger :: MapInteger a -> Integer -> a
appInteger  = (Integer, Integer) -> MapInteger a -> Integer -> a
forall i a.
(Bits i, Ord i, Num i) =>
(i, i) -> MapLargeIntegral i a -> i -> a
appLargeIntegral (Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
forall a. Bounded a => a
minBound::Int), Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
forall a. Bounded a => a
maxBound::Int))
data MapLargeIntegral i a = MLI (MapIntegral a) (i->a)
memoLargeIntegral :: (Bits i, Num i) => (i->a) -> MapLargeIntegral i a
memoLargeIntegral :: (i -> a) -> MapLargeIntegral i a
memoLargeIntegral i -> a
f = MapIntegral a -> (i -> a) -> MapLargeIntegral i a
forall i a. MapIntegral a -> (i -> a) -> MapLargeIntegral i a
MLI ((i -> a) -> MapIntegral a
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral i -> a
f) i -> a
f
appLargeIntegral  :: (Bits i, Ord i, Num i) => (i,i) -- ^ range
                                   -> MapLargeIntegral i a -> i->a
appLargeIntegral :: (i, i) -> MapLargeIntegral i a -> i -> a
appLargeIntegral (i
minb,i
maxb) (MLI MapIntegral a
mi i -> a
f) i
i | i
minb i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= i
i Bool -> Bool -> Bool
&& i
i i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= i
maxb = MapIntegral a -> i -> a
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral MapIntegral a
mi i
i
                                          | Bool
otherwise              = i -> a
f i
i
type MapInt = MapIntegral
memoInt :: (Int->a) -> MapInt a
memoInt :: (Int -> a) -> MapInt a
memoInt = (Int -> a) -> MapInt a
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral
appInt  :: MapInt a -> Int->a
appInt :: MapInt a -> Int -> a
appInt  = MapInt a -> Int -> a
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral
data MapIntegral a = MI {
      MapIntegral a -> MapNat a
negArrow    :: MapNat a,
      MapIntegral a -> MapNat a
nonnegArrow :: MapNat a
    }
type MapNat = MapFiniteList MapBool
memoIntegral :: (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral :: (i -> a) -> MapIntegral a
memoIntegral i -> a
f = MapNat a -> MapNat a -> MapIntegral a
forall a. MapNat a -> MapNat a -> MapIntegral a
MI ((i -> a) -> MapNat a
forall t a. (Num t, Bits t) => (t -> a) -> MapFiniteList MapBool a
memoPosNat (\i
n -> i -> a
f (-i
n))) ((i -> a) -> MapNat a
forall t a. (Num t, Bits t) => (t -> a) -> MapFiniteList MapBool a
memoPosNat (\i
n -> i -> a
f (i
ni -> i -> i
forall a. Num a => a -> a -> a
-i
1)))
memoPosNat :: (t -> a) -> MapFiniteList MapBool a
memoPosNat t -> a
f = (forall a. (Bool -> a) -> MapBool a)
-> ([Bool] -> a) -> MapFiniteList MapBool a
forall b (m :: * -> *) a.
(forall c. (b -> c) -> m c) -> ([b] -> a) -> MapFiniteList m a
memoFiniteList forall a. (Bool -> a) -> MapBool a
memoBool (\[Bool]
bs -> t -> a
f ([Bool] -> t
forall p. (Num p, Bits p) => [Bool] -> p
bitsToPosNat [Bool]
bs))
bitsToPosNat :: [Bool] -> p
bitsToPosNat [] = p
1
bitsToPosNat (Bool
b:[Bool]
bs) | Bool
b         = p
gbs p -> p -> p
forall a. Bits a => a -> a -> a
.|. p
1
                    | Bool
otherwise = p
gbs
                    where gbs :: p
gbs = [Bool] -> p
bitsToPosNat [Bool]
bs p -> Int -> p
forall a. Bits a => a -> Int -> a
`shiftL` Int
1
appIntegral :: (Bits i, Num i) => MapIntegral a -> (i->a)
appIntegral :: MapIntegral a -> i -> a
appIntegral (MI MapNat a
n MapNat a
nn) i
i | i -> i
forall a. Num a => a -> a
signum i
i i -> i -> Bool
forall a. Eq a => a -> a -> Bool
== -i
1 = MapNat a -> i -> a
forall t a. (Num t, Bits t) => MapFiniteList MapBool a -> t -> a
appPosNat MapNat a
n  (-i
i)
                        | Bool
otherwise      = MapNat a -> i -> a
forall t a. (Num t, Bits t) => MapFiniteList MapBool a -> t -> a
appPosNat MapNat a
nn (i
ii -> i -> i
forall a. Num a => a -> a -> a
+i
1)
appPosNat :: MapFiniteList MapBool a -> t -> a
appPosNat MapFiniteList MapBool a
m t
i = (forall a. MapBool a -> Bool -> a)
-> MapFiniteList MapBool a -> [Bool] -> a
forall (m :: * -> *) b a.
(forall c. m c -> b -> c) -> MapFiniteList m a -> [b] -> a
appFiniteList forall a. MapBool a -> Bool -> a
appBool MapFiniteList MapBool a
m (t -> [Bool]
forall t. (Num t, Bits t) => t -> [Bool]
posNatToBits t
i)
posNatToBits :: t -> [Bool]
posNatToBits t
1 = []
posNatToBits t
n = (t
n t -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
`testBit` Int
0) Bool -> [Bool] -> [Bool]
forall a. a -> [a] -> [a]
: t -> [Bool]
posNatToBits (t
n t -> Int -> t
forall a. Bits a => a -> Int -> a
`shiftR` Int
1)
-- Another option is just to use a list as MapNat, and not to memoize when the argument is huge. This might be better if it is unlikely such large keys are visited again.
-- Patricia tree cannot be used for building an infinite tree.
prop_inverseIntegral :: Integer -> (Function Integer Integer) -> Bool
prop_inverseIntegral :: Integer -> Function Integer Integer -> Bool
prop_inverseIntegral Integer
i Function Integer Integer
f = (Integer, Integer)
-> MapLargeIntegral Integer Integer -> Function Integer Integer
forall i a.
(Bits i, Ord i, Num i) =>
(i, i) -> MapLargeIntegral i a -> i -> a
appLargeIntegral (-Integer
2Integer -> Function Integer Integer
forall a b. (Num a, Integral b) => a -> b -> a
^Integer
28,Integer
2Integer -> Function Integer Integer
forall a b. (Num a, Integral b) => a -> b -> a
^Integer
28) (Function Integer Integer -> MapLargeIntegral Integer Integer
forall i a. (Bits i, Num i) => (i -> a) -> MapLargeIntegral i a
memoLargeIntegral (Function Integer Integer -> Function Integer Integer
forall a. a -> a
getFunction Function Integer Integer
f)) Integer
i Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Function Integer Integer -> Function Integer Integer
forall a. a -> a
getFunction Function Integer Integer
f Integer
i
prop_inversePosNat :: Int -> Function Int Int -> Property
prop_inversePosNat :: Int -> Function Int Int -> Bool
prop_inversePosNat Int
n Function Int Int
f = Int
nInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
0 Bool -> Bool -> Bool
==> MapFiniteList MapBool Int -> Function Int Int
forall t a. (Num t, Bits t) => MapFiniteList MapBool a -> t -> a
appPosNat (Function Int Int -> MapFiniteList MapBool Int
forall t a. (Num t, Bits t) => (t -> a) -> MapFiniteList MapBool a
memoPosNat (Function Int Int -> Function Int Int
forall a. a -> a
getFunction Function Int Int
f)) Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Function Int Int -> Function Int Int
forall a. a -> a
getFunction Function Int Int
f Int
n
prop_bitsToFromPosNat :: [Bool]->Bool
prop_bitsToFromPosNat :: [Bool] -> Bool
prop_bitsToFromPosNat [Bool]
is = Integer -> [Bool]
forall t. (Num t, Bits t) => t -> [Bool]
posNatToBits ([Bool] -> Integer
forall p. (Num p, Bits p) => [Bool] -> p
bitsToPosNat [Bool]
is::Integer) [Bool] -> [Bool] -> Bool
forall a. Eq a => a -> a -> Bool
== [Bool]
is -- IntegerでなくIntにすると通らない．

memoIx10, memoIx3 :: (Integral i, Ix i) => (i->a) -> MapIx i a
memoIx10 :: (i -> a) -> MapIx i a
memoIx10 = (i, i) -> (i -> a) -> MapIx i a
forall i a. Ix i => (i, i) -> (i -> a) -> MapIx i a
memoIx (i
0,i
10)
memoIx3 :: (i -> a) -> MapIx i a
memoIx3  = (i, i) -> (i -> a) -> MapIx i a
forall i a. Ix i => (i, i) -> (i -> a) -> MapIx i a
memoIx (i
0,i
3)

data MapIx i a = MIx (Array i a) (i->a)
memoIx :: (Ix i) => (i,i) -> (i->a) -> MapIx i a
memoIx :: (i, i) -> (i -> a) -> MapIx i a
memoIx (i, i)
bnds i -> a
f = Array i a -> (i -> a) -> MapIx i a
forall i a. Array i a -> (i -> a) -> MapIx i a
MIx ((i, i) -> [a] -> Array i a
forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (i, i)
bnds ((i -> a) -> [i] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map i -> a
f ((i, i) -> [i]
forall a. Ix a => (a, a) -> [a]
range (i, i)
bnds))) i -> a
f
appIx  :: (Ix i) => MapIx i a -> i->a
appIx :: MapIx i a -> i -> a
appIx  (MIx Array i a
ar i -> a
f) i
i | Array i a -> (i, i)
forall i e. Array i e -> (i, i)
bounds Array i a
ar (i, i) -> i -> Bool
forall a. Ix a => (a, a) -> a -> Bool
`inRange` i
i = Array i a
arArray i a -> i -> a
forall i e. Ix i => Array i e -> i -> e
!i
i
                    | Bool
otherwise             = i -> a
f i
i

type MapChar = MapIntegral
memoChar :: (Char->a) -> MapChar a
memoChar :: (Char -> a) -> MapChar a
memoChar Char -> a
f = (Int -> a) -> MapChar a
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral (\Int
i -> Char -> a
f (Char -> a) -> Char -> a
forall a b. (a -> b) -> a -> b
$ Int -> Char
chr Int
i)
appChar :: MapChar a -> (Char->a)
appChar :: MapChar a -> Char -> a
appChar MapChar a
mi Char
c = MapChar a -> Int -> a
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral MapChar a
mi (Char -> Int
ord Char
c)
prp_inverseChar :: Char -> (Char -> Int) -> Bool
prp_inverseChar Char
c Char -> Int
f = MapChar Int -> Char -> Int
forall a. MapChar a -> Char -> a
appChar ((Char -> Int) -> MapChar Int
forall a. (Char -> a) -> MapChar a
memoChar Char -> Int
f) Char
c Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (Char -> Int
f Char
c::Int)

type MapReal = MapPair MapIntegral MapIntegral
memoReal :: RealFloat r => (r -> a) -> MapReal a
memoReal :: (r -> a) -> MapReal a
memoReal r -> a
f = (forall e. (Integer -> e) -> MapIntegral e)
-> (forall e. (Int -> e) -> MapIntegral e)
-> ((Integer, Int) -> a)
-> MapReal a
forall b (m :: * -> *) d (n :: * -> *) a.
(forall e. (b -> e) -> m e)
-> (forall f. (d -> f) -> n f) -> ((b, d) -> a) -> MapPair m n a
memoPair forall e. (Integer -> e) -> MapIntegral e
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral forall e. (Int -> e) -> MapIntegral e
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral (r -> a
f (r -> a) -> ((Integer, Int) -> r) -> (Integer, Int) -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Integer -> Int -> r) -> (Integer, Int) -> r
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Integer -> Int -> r
forall a. RealFloat a => Integer -> Int -> a
encodeFloat)
appReal  :: RealFloat r => MapReal a -> r -> a
appReal :: MapReal a -> r -> a
appReal MapReal a
mt r
r = (forall e. MapIntegral e -> Integer -> e)
-> (forall e. MapIntegral e -> Int -> e)
-> MapReal a
-> (Integer, Int)
-> a
forall (m :: * -> *) b (n :: * -> *) d a.
(forall e. m e -> b -> e)
-> (forall f. n f -> d -> f) -> MapPair m n a -> (b, d) -> a
appPair forall e. MapIntegral e -> Integer -> e
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral forall e. MapIntegral e -> Int -> e
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral MapReal a
mt (r -> (Integer, Int)
forall a. RealFloat a => a -> (Integer, Int)
decodeFloat r
r)

prop_inverseReal :: Double -> (Double->Int) -> Bool
prop_inverseReal :: Double -> (Double -> Int) -> Bool
prop_inverseReal Double
r Double -> Int
f = MapReal Int -> Double -> Int
forall r a. RealFloat r => MapReal a -> r -> a
appReal ((Double -> Int) -> MapReal Int
forall r a. RealFloat r => (r -> a) -> MapReal a
memoReal Double -> Int
f) Double
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Double -> Int
f Double
r


-- test code for seeing if memoization really works
heavy, memoizedHeavy :: Integer -> Integer
heavy :: Function Integer Integer
heavy Integer
n = Integer
3Integer -> Function Integer Integer
forall a b. (Num a, Integral b) => a -> b -> a
^Integer
n Integer -> Function Integer Integer
forall a. Integral a => a -> a -> a
`div` Integer
3Integer -> Function Integer Integer
forall a b. (Num a, Integral b) => a -> b -> a
^(Integer
nInteger -> Function Integer Integer
forall a. Num a => a -> a -> a
-Integer
1)
memoHeavy :: MapIntegral Integer
memoHeavy = Function Integer Integer -> MapIntegral Integer
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral Function Integer Integer
heavy
memoizedHeavy :: Function Integer Integer
memoizedHeavy = MapIntegral Integer -> Function Integer Integer
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral MapIntegral Integer
memoHeavy

heavy2, memoizedHeavy2 :: Integer -> Integer -> Integer
heavy2 :: Integer -> Function Integer Integer
heavy2 Integer
m Integer
n = Integer
mInteger -> Function Integer Integer
forall a b. (Num a, Integral b) => a -> b -> a
^Integer
n Integer -> Function Integer Integer
forall a. Integral a => a -> a -> a
`div` Integer
mInteger -> Function Integer Integer
forall a b. (Num a, Integral b) => a -> b -> a
^(Integer
nInteger -> Function Integer Integer
forall a. Num a => a -> a -> a
-Integer
1)
memoHeavy2 :: MapIntegral (MapIntegral Integer)
memoHeavy2 = (Integer -> MapIntegral Integer)
-> MapIntegral (MapIntegral Integer)
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral ((Function Integer Integer -> MapIntegral Integer)
-> (Integer -> Function Integer Integer)
-> Integer
-> MapIntegral Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) Function Integer Integer -> MapIntegral Integer
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral Integer -> Function Integer Integer
heavy2)
memoizedHeavy2 :: Integer -> Function Integer Integer
memoizedHeavy2 = (MapIntegral Integer -> Function Integer Integer)
-> (Integer -> MapIntegral Integer)
-> Integer
-> Function Integer Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) MapIntegral Integer -> Function Integer Integer
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral (MapIntegral (MapIntegral Integer) -> Integer -> MapIntegral Integer
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral MapIntegral (MapIntegral Integer)
memoHeavy2)

memoizedHeavy2' :: Integer -> Integer -> Integer
memoHeavy2' :: MapPair MapIntegral MapIntegral Integer
memoHeavy2' = (forall e. (Integer -> e) -> MapIntegral e)
-> (forall e. (Integer -> e) -> MapIntegral e)
-> ((Integer, Integer) -> Integer)
-> MapPair MapIntegral MapIntegral Integer
forall b (m :: * -> *) d (n :: * -> *) a.
(forall e. (b -> e) -> m e)
-> (forall f. (d -> f) -> n f) -> ((b, d) -> a) -> MapPair m n a
memoPair forall e. (Integer -> e) -> MapIntegral e
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral forall e. (Integer -> e) -> MapIntegral e
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral ((Integer -> Function Integer Integer)
-> (Integer, Integer) -> Integer
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Integer -> Function Integer Integer
heavy2)
memoizedHeavy2' :: Integer -> Function Integer Integer
memoizedHeavy2' = ((Integer, Integer) -> Integer)
-> Integer -> Function Integer Integer
forall a b c. ((a, b) -> c) -> a -> b -> c
curry (((Integer, Integer) -> Integer)
 -> Integer -> Function Integer Integer)
-> ((Integer, Integer) -> Integer)
-> Integer
-> Function Integer Integer
forall a b. (a -> b) -> a -> b
$ (forall e. MapIntegral e -> Integer -> e)
-> (forall e. MapIntegral e -> Integer -> e)
-> MapPair MapIntegral MapIntegral Integer
-> (Integer, Integer)
-> Integer
forall (m :: * -> *) b (n :: * -> *) d a.
(forall e. m e -> b -> e)
-> (forall f. n f -> d -> f) -> MapPair m n a -> (b, d) -> a
appPair forall e. MapIntegral e -> Integer -> e
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral forall e. MapIntegral e -> Integer -> e
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral MapPair MapIntegral MapIntegral Integer
memoHeavy2'

heavy3, memoizedHeavy3 :: Integer -> Integer -> Integer -> Integer
heavy3 :: Integer -> Integer -> Function Integer Integer
heavy3 Integer
l Integer
m Integer
n = Integer
lInteger -> Function Integer Integer
forall a b. (Num a, Integral b) => a -> b -> a
^Integer
n Integer -> Function Integer Integer
forall a. Integral a => a -> a -> a
`div` Integer
mInteger -> Function Integer Integer
forall a b. (Num a, Integral b) => a -> b -> a
^(Integer
nInteger -> Function Integer Integer
forall a. Num a => a -> a -> a
-Integer
1)
-- memoHeavy3 = memoIntegral ((.) memoIntegral ((.) ((.) memoIntegral) heavy3))
memoHeavy3 :: MapIntegral (MapIntegral (MapIntegral Integer))
memoHeavy3 = ((Integer -> MapIntegral (MapIntegral Integer))
-> MapIntegral (MapIntegral (MapIntegral Integer))
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral ((Integer -> MapIntegral (MapIntegral Integer))
 -> MapIntegral (MapIntegral (MapIntegral Integer)))
-> ((Integer -> Integer -> Function Integer Integer)
    -> Integer -> MapIntegral (MapIntegral Integer))
-> (Integer -> Integer -> Function Integer Integer)
-> MapIntegral (MapIntegral (MapIntegral Integer))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Integer -> Function Integer Integer)
 -> MapIntegral (MapIntegral Integer))
-> (Integer -> Integer -> Function Integer Integer)
-> Integer
-> MapIntegral (MapIntegral Integer)
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) ((Integer -> MapIntegral Integer)
-> MapIntegral (MapIntegral Integer)
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral ((Integer -> MapIntegral Integer)
 -> MapIntegral (MapIntegral Integer))
-> ((Integer -> Function Integer Integer)
    -> Integer -> MapIntegral Integer)
-> (Integer -> Function Integer Integer)
-> MapIntegral (MapIntegral Integer)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Function Integer Integer -> MapIntegral Integer)
-> (Integer -> Function Integer Integer)
-> Integer
-> MapIntegral Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) Function Integer Integer -> MapIntegral Integer
forall i a. (Bits i, Num i) => (i -> a) -> MapIntegral a
memoIntegral)) Integer -> Integer -> Function Integer Integer
heavy3
-- memoizedHeavy3 = (.) ((.) appIntegral) ((.) appIntegral (appIntegral memoHeavy3))
memoizedHeavy3 :: Integer -> Integer -> Function Integer Integer
memoizedHeavy3 = ((MapIntegral (MapIntegral Integer)
 -> Integer -> Function Integer Integer)
-> (Integer -> MapIntegral (MapIntegral Integer))
-> Integer
-> Integer
-> Function Integer Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) ((MapIntegral Integer -> Function Integer Integer)
-> (Integer -> MapIntegral Integer)
-> Integer
-> Function Integer Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) MapIntegral Integer -> Function Integer Integer
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral ((Integer -> MapIntegral Integer)
 -> Integer -> Function Integer Integer)
-> (MapIntegral (MapIntegral Integer)
    -> Integer -> MapIntegral Integer)
-> MapIntegral (MapIntegral Integer)
-> Integer
-> Function Integer Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MapIntegral (MapIntegral Integer) -> Integer -> MapIntegral Integer
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral) ((Integer -> MapIntegral (MapIntegral Integer))
 -> Integer -> Integer -> Function Integer Integer)
-> (MapIntegral (MapIntegral (MapIntegral Integer))
    -> Integer -> MapIntegral (MapIntegral Integer))
-> MapIntegral (MapIntegral (MapIntegral Integer))
-> Integer
-> Integer
-> Function Integer Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MapIntegral (MapIntegral (MapIntegral Integer))
-> Integer -> MapIntegral (MapIntegral Integer)
forall i a. (Bits i, Num i) => MapIntegral a -> i -> a
appIntegral) MapIntegral (MapIntegral (MapIntegral Integer))
memoHeavy3


heavyList, memoizedHeavyList :: String -> String
heavyList :: String -> String
heavyList String
xs = Int -> String -> String
forall a. Int -> [a] -> [a]
take Int
10 (String -> String) -> String -> String
forall a b. (a -> b) -> a -> b
$ String -> String
forall a. [a] -> [a]
reverse (String -> String) -> String -> String
forall a b. (a -> b) -> a -> b
$ String -> String
forall a. Ord a => [a] -> [a]
sort (String -> String) -> String -> String
forall a b. (a -> b) -> a -> b
$ Int -> String -> String
forall a. Int -> [a] -> [a]
take Int
1000000 (String -> String) -> String -> String
forall a b. (a -> b) -> a -> b
$ String -> String
forall a. [a] -> [a]
cycle String
xs
memoHeavyList :: MapFiniteList MapIntegral String
memoHeavyList = (forall a. (Char -> a) -> MapChar a)
-> (String -> String) -> MapFiniteList MapIntegral String
forall b (m :: * -> *) a.
(forall c. (b -> c) -> m c) -> ([b] -> a) -> MapFiniteList m a
memoFiniteList forall a. (Char -> a) -> MapChar a
memoChar String -> String
heavyList
memoizedHeavyList :: String -> String
memoizedHeavyList = (forall a. MapChar a -> Char -> a)
-> MapFiniteList MapIntegral String -> String -> String
forall (m :: * -> *) b a.
(forall c. m c -> b -> c) -> MapFiniteList m a -> [b] -> a
appFiniteList forall a. MapChar a -> Char -> a
appChar MapFiniteList MapIntegral String
memoHeavyList