| Copyright | (c) Eduard Sergeev 2013 |
|---|---|
| License | BSD-style (see the file LICENSE) |
| Maintainer | eduard.sergeev@gmail.com |
| Stability | experimental |
| Portability | non-portable (multi-param classes, flexible instances) |
| Safe Haskell | None |
| Language | Haskell2010 |
Control.Monad.Memo.Array
Description
ArrayCache - mutable-array-based (IO and ST hosted) MonadCache
Very fast memoization cache. Unfortunatelly it cannot suit every case (see limitations), but if you can use it, please do: it is generally an order of magnitude faster than Map-based Memo, especially unboxed version - try to use it whenever you can.
Limitations: Since MArray is used as MonadCache the key range must be known beforehand and the array is allocated before the first call.
It is therefore most suitable for the cases when the distribution of possible key values is within reasonable range and is rather dense (the best case: all values withing some range will be used). If this is the case then MArray has O(1) for both lookup and update operations.
In addition unboxed UArrayCache can only store unboxed types (but it does it very efficiently).
Synopsis
- type family Array (m :: * -> *) :: * -> * -> *
- type ArrayCache k e m = Cache (Array m) k e m
- class MaybeLike e v => ArrayMemo v e | v -> e
- evalArrayMemo :: (Ix k, MArray (Array m) e m, ArrayMemo v e) => ArrayCache k e m a -> (k, k) -> m a
- runArrayMemo :: (Ix k, MArray (Array m) e m, ArrayMemo v e) => ArrayCache k e m a -> (k, k) -> m (a, Array m k e)
- type family UArray (m :: * -> *) :: * -> * -> *
- type UArrayCache k e m = Cache (UArray m) k e m
- class MaybeLike e v => UArrayMemo v e | v -> e
- evalUArrayMemo :: (Ix k, MArray (UArray m) e m, UArrayMemo v e) => UArrayCache k e m a -> (k, k) -> m a
- runUArrayMemo :: (Ix k, MArray (UArray m) e m, UArrayMemo v e) => UArrayCache k e m a -> (k, k) -> m (a, UArray m k e)
- newtype Container arr = Container {
- toArray :: arr
- type Cache arr k e = ReaderCache (Container (arr k e))
- genericEvalArrayMemo :: (Ix k, MaybeLike e v, MArray arr e m) => Cache arr k e m a -> (k, k) -> m a
- genericRunArrayMemo :: (Ix k, MaybeLike e v, MArray arr e m) => Cache arr k e m a -> (k, k) -> m (a, arr k e)
ArrayCache for boxed types
type family Array (m :: * -> *) :: * -> * -> * Source #
A family of boxed arrays
Instances
| type Array IO Source # | |
Defined in Control.Monad.Memo.Array | |
| type Array (ST s) Source # | |
Defined in Control.Monad.Memo.Array | |
| type Array (ReaderCache c IO) Source # | |
Defined in Control.Monad.Memo.Array | |
| type Array (ReaderCache c (ST s)) Source # | |
Defined in Control.Monad.Memo.Array | |
type ArrayCache k e m = Cache (Array m) k e m Source #
Memoization monad based on mutable boxed array
class MaybeLike e v => ArrayMemo v e | v -> e Source #
This is just to be able to infer the type of the ArrayCache element
Type families could be used instead but due to the bug in 7.4.* we cannot use them here
Arguments
| :: (Ix k, MArray (Array m) e m, ArrayMemo v e) | |
| => ArrayCache k e m a | memoized computation to be evaluated |
| -> (k, k) | array key range |
| -> m a | computation result |
Evaluate computation using boxed array
Key range should cover all possible keys used in computation otherwise not in range error is generated by array
Arguments
| :: (Ix k, MArray (Array m) e m, ArrayMemo v e) | |
| => ArrayCache k e m a | memoized computation to be evaluated |
| -> (k, k) | array key range |
| -> m (a, Array m k e) | computation result and final array cache |
Evaluate computation and the final content of array cache using boxed array
Key range should cover all possible keys used in computation otherwise not in range error is generated by array
ArrayCache for unboxed types
type family UArray (m :: * -> *) :: * -> * -> * Source #
A family of unboxed arrays
Instances
| type UArray IO Source # | |
Defined in Control.Monad.Memo.Array | |
| type UArray (ST s) Source # | |
Defined in Control.Monad.Memo.Array | |
| type UArray (ReaderCache c IO) Source # | |
Defined in Control.Monad.Memo.Array | |
| type UArray (ReaderCache c (ST s)) Source # | |
Defined in Control.Monad.Memo.Array | |
type UArrayCache k e m = Cache (UArray m) k e m Source #
Memoization monad based on mutable unboxed array
class MaybeLike e v => UArrayMemo v e | v -> e Source #
This is just to be able to infer the type of the UArrayCache element
Type families could be used instead but due to the bug in 7.4.* we cannot use them here
Instances
| MaybeLike v v => UArrayMemo v v Source # | |
Defined in Control.Monad.Memo.Array.Instances | |
Arguments
| :: (Ix k, MArray (UArray m) e m, UArrayMemo v e) | |
| => UArrayCache k e m a | memoized computation to be evaluated |
| -> (k, k) | array key range |
| -> m a | computation result |
Evaluate computation using unboxed array
Key range should cover all possible keys used in computation otherwise not in range error is generated by array
Arguments
| :: (Ix k, MArray (UArray m) e m, UArrayMemo v e) | |
| => UArrayCache k e m a | memoized computation to be evaluated |
| -> (k, k) | array key range |
| -> m (a, UArray m k e) | computation result and final array cache |
Evaluate computation and the final content of array cache using unboxed array
Key range should cover all possible keys used in computation otherwise not in range error is generated by array
Generic function for ArrayCache
type Cache arr k e = ReaderCache (Container (arr k e)) Source #
Generic Array-based memo cache