Debian Codegraph @

Control/Monad/Memo/Vector/Expandable.hs

raw
1 {- |
2 Module : Control.Monad.Trans.Memo.Vector
3 Copyright : (c) Eduard Sergeev 2013
4 License : BSD-style (see the file LICENSE)
5
6 Maintainer : [email protected]
7 Stability : experimental
8 Portability : non-portable (multi-param classes, flexible instances)
9
10 Vector-based `MonadCache` implementation which dynamically expands the vector during the computation to accomodate all requested keys.
11 This implementation does not require to specify the length of the vector up front, but may be slower than "Control.Monad.Memo.Vector".
12
13 -}
14
15 {-# LANGUAGE NoImplicitPrelude,
16 MultiParamTypeClasses, FunctionalDependencies,
17 FlexibleInstances, FlexibleContexts, TypeSynonymInstances,
18 UndecidableInstances, TypeFamilies #-}
19
20 module Control.Monad.Memo.Vector.Expandable
21 (
22
23 -- * VectorCache for boxed types
24 VectorCache,
25 VectorMemo,
26 startEvalVectorMemo,
27 startRunVectorMemo,
28 -- * UVectorCache for unboxed types
29 UVectorCache,
30 UVectorMemo,
31 startEvalUVectorMemo,
32 startRunUVectorMemo,
33 -- * Generic functions for VectorCache
34 Container(..),
35 Cache,
36 genericStartEvalVectorMemo,
37 genericStartRunVectorMemo
38
39 ) where
40
41 import Data.Int
42 import Data.Eq
43 import Data.Ord
44 import Data.Function
45 import Prelude (Num(..))
46 import Data.Maybe (Maybe(..))
47 import Data.Vector.Generic.Mutable
48 import qualified Data.Vector.Mutable as M
49 import qualified Data.Vector.Unboxed.Mutable as UM
50 import Control.Monad
51 import Control.Monad.Trans.Class
52 import Control.Monad.Primitive
53
54 import Data.MaybeLike
55 import Control.Monad.Memo.Class
56 import Control.Monad.Trans.Memo.StateCache
57
58
59 newtype Container vec = Container { toVector :: vec }
60
61 -- | Generic Vector-based memo cache
62 type Cache vec k e = StateCache (Container (vec k e))
63
64 instance (PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) =>
65 MonadCache Int v (Cache c s e m) where
66 {-# INLINE lookup #-}
67 lookup k = do
68 c <- container
69 e <- lift $ cacheRead (toVector c) k
70 return (if isNothing e then Nothing else Just (fromJust e))
71 {-# INLINE add #-}
72 add k v = do
73 c <- container
74 v' <- lift $ cacheWrite (toVector c) k (just v)
75 setContainer (Container v')
76
77 instance (PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) =>
78 MonadMemo Int v (Cache c s e m) where
79 {-# INLINE memo #-}
80 memo f k = do
81 Container vec <- container
82 let l = length vec
83 d = k + 1 - l
84 if d > 0
85 then do
86 vec' <- lift $ expand vec l d
87 setContainer (Container vec')
88 v <- f k
89 Container vec'' <- container
90 lift $ unsafeWrite vec'' k (just v)
91 return v
92 else do
93 e <- lift $ cacheRead vec k
94 if isNothing e
95 then do
96 v <- f k
97 Container vec' <- container
98 lift $ unsafeWrite vec' k (just v)
99 return v
100 else return (fromJust e)
101
102
103 -- VectorCache for boxed types
104 -- --------------------------
105
106 -- | Boxed vector
107 type Vector = M.MVector
108
109 -- | `MonadCache` based on boxed vector
110 type VectorCache s e = Cache Vector s e
111
112 -- | This is just to be able to infer the type of the `VectorCache` element.
113 class MaybeLike e v => VectorMemo v e | v -> e
114
115 -- | Evaluate computation using mutable boxed vector which dynamically grows to accomodate all requested keys
116 startEvalVectorMemo :: (PrimMonad m, VectorMemo v e) =>
117 VectorCache (PrimState m) e m a -> m a
118 {-# INLINE startEvalVectorMemo #-}
119 startEvalVectorMemo = genericStartEvalVectorMemo
120
121 -- | Evaluate computation using mutable boxed vector
122 -- which dynamically grows to accomodate all requested keys.
123 -- This function also returns the final content of the vector cache
124 startRunVectorMemo :: (PrimMonad m, VectorMemo v e) =>
125 VectorCache (PrimState m) e m a -> m (a, Vector (PrimState m) e)
126 {-# INLINE startRunVectorMemo #-}
127 startRunVectorMemo = genericStartRunVectorMemo
128
129
130 -- VectorCache for unboxed types
131 -- ----------------------------
132
133 -- | Unboxed vector
134 type UVector = UM.MVector
135
136 -- | `MonadCache` based on unboxed vector
137 type UVectorCache s e = Cache UVector s e
138
139 -- | This is just to be able to infer the type of the `UVectorCache` element.
140 class MaybeLike e v => UVectorMemo v e | v -> e
141
142 -- | Evaluate computation using mutable unboxed vector
143 -- which dynamically grows to accomodate all requested keys
144 startEvalUVectorMemo :: (PrimMonad m, UVectorMemo v e, MVector UVector e) =>
145 UVectorCache (PrimState m) e m a -> m a
146 {-# INLINE startEvalUVectorMemo #-}
147 startEvalUVectorMemo = genericStartEvalVectorMemo
148
149 -- | Evaluate computation using mutable unboxed vector
150 -- which dynamically grows to accomodate all requested keys.
151 -- This function also returns the final content of the vector cache
152 startRunUVectorMemo :: (PrimMonad m, UVectorMemo v e, MVector UVector e) =>
153 UVectorCache (PrimState m) e m a -> m (a, UVector (PrimState m) e)
154 {-# INLINE startRunUVectorMemo #-}
155 startRunUVectorMemo = genericStartRunVectorMemo
156
157
158 genericStartEvalVectorMemo :: (MaybeLike e v, PrimMonad m, MVector vec e) =>
159 Cache vec (PrimState m) e m a -> m a
160 {-# INLINE genericStartEvalVectorMemo #-}
161 genericStartEvalVectorMemo m = do
162 (a,_) <- genericStartRunVectorMemo m
163 return a
164
165 genericStartRunVectorMemo :: (MaybeLike e v, PrimMonad m, MVector vec e) =>
166 Cache vec (PrimState m) e m a -> m (a, vec (PrimState m) e)
167 {-# INLINE genericStartRunVectorMemo #-}
168 genericStartRunVectorMemo m = do
169 vec <- replicate 0 nothing
170 (a, c) <- runStateCache m (Container vec)
171 return (a, toVector c)
172
173 {-# INLINE cacheRead #-}
174 cacheRead c k =
175 if k >= length c
176 then return nothing
177 else unsafeRead c k
178
179 {-# INLINE cacheWrite #-}
180 cacheWrite c k e = do
181 c' <- if d > 0
182 then expand c l d
183 else return c
184 unsafeWrite c' k e
185 return c'
186 where
187 l = length c
188 d = k + 1 - l
189
190 {-# INLINE expand #-}
191 expand c l d = do
192 uc <- unsafeGrow c toGrow
193 unsafeWrite uc l nothing
194 initialise uc 1
195 where
196 toGrow = d `max` (l * 2)
197 {-# INLINE initialise #-}
198 initialise c i | i == toGrow = return c
199 initialise c i = do
200 let n = i `min` (toGrow-i)
201 t = unsafeSlice (l+i) n c
202 s = unsafeSlice l n c
203 unsafeCopy t s
204 initialise c (i+n)