| 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 |
VectorCache - mutable-vector-based `MonadCache` with unsafe operations. |
| 11 |
|
| 12 |
This is a version of "Control.Monad.Memo.Mutable.Vector" but implemented using /unsafe*/ vector operations. |
| 13 |
Faster than default implementation but you must be sure that your code doesn't try to read/write outside vector boundaries. |
| 14 |
|
| 15 |
-} |
| 16 |
|
| 17 |
{-# LANGUAGE NoImplicitPrelude, |
| 18 |
MultiParamTypeClasses, FunctionalDependencies, |
| 19 |
FlexibleInstances, FlexibleContexts, TypeFamilies, |
| 20 |
UndecidableInstances, TypeSynonymInstances #-} |
| 21 |
|
| 22 |
module Control.Monad.Memo.Vector.Unsafe |
| 23 |
( |
| 24 |
|
| 25 |
-- * VectorCache for boxed types |
| 26 |
VectorCache, |
| 27 |
VectorMemo, |
| 28 |
unsafeEvalVectorMemo, |
| 29 |
unsafeRunVectorMemo, |
| 30 |
-- * UVectorCache for unboxed types |
| 31 |
UVectorCache, |
| 32 |
UVectorMemo, |
| 33 |
unsafeEvalUVectorMemo, |
| 34 |
unsafeRunUVectorMemo, |
| 35 |
-- * Generic functions for VectorCache |
| 36 |
Container(..), |
| 37 |
Cache, |
| 38 |
genericUnsafeEvalVectorMemo, |
| 39 |
genericUnsafeRunVectorMemo |
| 40 |
|
| 41 |
|
| 42 |
) where |
| 43 |
|
| 44 |
import Data.Function |
| 45 |
import Data.Int |
| 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.Applicative |
| 51 |
import Control.Monad |
| 52 |
import Control.Monad.Fix |
| 53 |
import Control.Monad.Trans.Class |
| 54 |
import Control.Monad.Primitive |
| 55 |
|
| 56 |
import Data.MaybeLike |
| 57 |
import Control.Monad.Memo.Class |
| 58 |
import Control.Monad.Trans.Memo.ReaderCache |
| 59 |
|
| 60 |
|
| 61 |
newtype Container vec = Container { toVector :: vec } |
| 62 |
|
| 63 |
-- | Generic Vector-based memo cache |
| 64 |
type Cache vec k e = ReaderCache (Container (vec k e)) |
| 65 |
|
| 66 |
instance (PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) => |
| 67 |
MonadCache Int v (Cache c s e m) where |
| 68 |
{-# INLINE lookup #-} |
| 69 |
lookup k = do |
| 70 |
c <- container |
| 71 |
e <- lift $ unsafeRead (toVector c) k |
| 72 |
return (if isNothing e then Nothing else Just (fromJust e)) |
| 73 |
{-# INLINE add #-} |
| 74 |
add k v = do |
| 75 |
c <- container |
| 76 |
lift $ unsafeWrite (toVector c) k (just v) |
| 77 |
|
| 78 |
instance (PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) => |
| 79 |
MonadMemo Int v (Cache c s e m) where |
| 80 |
{-# INLINE memo #-} |
| 81 |
memo f k = do |
| 82 |
c <- container |
| 83 |
e <- lift $ unsafeRead (toVector c) k |
| 84 |
if isNothing e |
| 85 |
then do |
| 86 |
v <- f k |
| 87 |
lift $ unsafeWrite (toVector c) k (just v) |
| 88 |
return v |
| 89 |
else return (fromJust e) |
| 90 |
|
| 91 |
|
| 92 |
-- VectorCache for boxed types |
| 93 |
-- -------------------------- |
| 94 |
|
| 95 |
-- | Boxed vector |
| 96 |
type Vector = M.MVector |
| 97 |
|
| 98 |
-- | `MonadCache` based on boxed vector |
| 99 |
type VectorCache s e = Cache Vector s e |
| 100 |
|
| 101 |
-- | This is just to be able to infer the type of the `VectorCache` element. |
| 102 |
class MaybeLike e v => VectorMemo v e | v -> e |
| 103 |
|
| 104 |
-- | Evaluate computation using mutable boxed vector and unsafe operations |
| 105 |
-- |
| 106 |
-- Vector length must covers all possible keys used in computation |
| 107 |
-- otherwise the behaviour is undefined (i.e. segfault) |
| 108 |
unsafeEvalVectorMemo :: (PrimMonad m, VectorMemo v e) => |
| 109 |
VectorCache (PrimState m) e m a -- ^memoized computation |
| 110 |
-> Int -- ^vector length |
| 111 |
-> m a -- ^result |
| 112 |
{-# INLINE unsafeEvalVectorMemo #-} |
| 113 |
unsafeEvalVectorMemo = genericUnsafeEvalVectorMemo |
| 114 |
|
| 115 |
-- | Evaluate computation using mutable boxed vector and unsafe operations. |
| 116 |
-- It also returns the final content of the vector cache |
| 117 |
-- |
| 118 |
-- Vector length must covers all possible keys used in computation |
| 119 |
-- otherwise the behaviour is undefined (i.e. segfault) |
| 120 |
unsafeRunVectorMemo :: (PrimMonad m, VectorMemo v e) => |
| 121 |
VectorCache (PrimState m) e m a -- ^memoized computation |
| 122 |
-> Int -- ^vector length |
| 123 |
-> m (a, Vector (PrimState m) e) -- ^result and final vector cache |
| 124 |
{-# INLINE unsafeRunVectorMemo #-} |
| 125 |
unsafeRunVectorMemo = genericUnsafeRunVectorMemo |
| 126 |
|
| 127 |
|
| 128 |
-- VectorCache for unboxed types |
| 129 |
-- ---------------------------- |
| 130 |
|
| 131 |
-- | Unboxed vector |
| 132 |
type UVector = UM.MVector |
| 133 |
|
| 134 |
-- | `MonadCache` based on unboxed vector |
| 135 |
type UVectorCache s e = Cache UVector s e |
| 136 |
|
| 137 |
-- | This is just to be able to infer the type of the `UVectorCache` element |
| 138 |
class MaybeLike e v => UVectorMemo v e | v -> e |
| 139 |
|
| 140 |
-- | Evaluate computation using mutable unboxed vector and unsafe operations |
| 141 |
-- |
| 142 |
-- Vector length must covers all possible keys used in computation |
| 143 |
-- otherwise the behaviour is undefined (i.e. segfault) |
| 144 |
unsafeEvalUVectorMemo :: (PrimMonad m, UVectorMemo v e, MVector UVector e) => |
| 145 |
UVectorCache (PrimState m) e m a -- ^memoized computation |
| 146 |
-> Int -- ^vector length |
| 147 |
-> m a -- ^result |
| 148 |
{-# INLINE unsafeEvalUVectorMemo #-} |
| 149 |
unsafeEvalUVectorMemo = genericUnsafeEvalVectorMemo |
| 150 |
|
| 151 |
-- | Evaluate computation using mutable boxed vector and unsafe operations. |
| 152 |
-- It also returns the final content of the vector cache |
| 153 |
-- |
| 154 |
-- Vector length must covers all possible keys used in computation |
| 155 |
-- otherwise the behaviour is undefined (i.e. segfault) |
| 156 |
unsafeRunUVectorMemo :: (PrimMonad m, UVectorMemo v e, MVector UVector e) => |
| 157 |
UVectorCache (PrimState m) e m a -- ^memoized computation |
| 158 |
-> Int -- ^vector length |
| 159 |
-> m (a, UVector (PrimState m) e) -- ^result and final vector cache |
| 160 |
{-# INLINE unsafeRunUVectorMemo #-} |
| 161 |
unsafeRunUVectorMemo = genericUnsafeRunVectorMemo |
| 162 |
|
| 163 |
|
| 164 |
genericUnsafeEvalVectorMemo :: (MaybeLike e v, PrimMonad m, MVector c e) => |
| 165 |
Cache c (PrimState m) e m a -> Int -> m a |
| 166 |
{-# INLINE genericUnsafeEvalVectorMemo #-} |
| 167 |
genericUnsafeEvalVectorMemo m n = do |
| 168 |
vec <- replicate n nothing |
| 169 |
evalReaderCache m (Container vec) |
| 170 |
|
| 171 |
genericUnsafeRunVectorMemo :: (MaybeLike e v, PrimMonad m, MVector c e) => |
| 172 |
Cache c (PrimState m) e m a -> Int -> m (a, c (PrimState m) e) |
| 173 |
{-# INLINE genericUnsafeRunVectorMemo #-} |
| 174 |
genericUnsafeRunVectorMemo m n = do |
| 175 |
vec <- replicate n nothing |
| 176 |
a <- evalReaderCache m (Container vec) |
| 177 |
return (a, vec) |