monad-memo-0.5.4: Memoization monad transformer

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

Contents

- ArrayCache for boxed types
- ArrayCache for unboxed types
- Generic function for ArrayCache

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 -> Type) :: Type -> Type -> Type
- type ArrayCache k e (m :: Type -> Type) = 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 -> Type) :: Type -> Type -> Type
- type UArrayCache k e (m :: Type -> Type) = 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 :: Type -> Type -> Type) 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 :: Type -> Type) :: Type -> Type -> Type Source #

A family of boxed arrays

#### Instances

Instances details

type Array IO Source # |
Instance details Defined in Control.Monad.Memo.Array type Array IO = IOArray
type Array (ST s) Source # |
Instance details Defined in Control.Monad.Memo.Array type Array (ST s) = STArray s
type Array (ReaderCache c (ST s)) Source # |
Instance details Defined in Control.Monad.Memo.Array type Array (ReaderCache c (ST s)) = STArray s
type Array (ReaderCache c IO) Source # |
Instance details Defined in Control.Monad.Memo.Array type Array (ReaderCache c IO) = IOArray

type ArrayCache k e (m :: Type -> Type) = 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

#### Instances

Instances details

MaybeLike (Maybe v) v => ArrayMemo v (Maybe v) Source # |
Instance details Defined in Control.Monad.Memo.Array.Instances

evalArrayMemo Source #

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

runArrayMemo Source #

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 :: Type -> Type) :: Type -> Type -> Type Source #

A family of unboxed arrays

#### Instances

Instances details

type UArray IO Source # |
Instance details Defined in Control.Monad.Memo.Array type UArray IO = IOUArray
type UArray (ST s) Source # |
Instance details Defined in Control.Monad.Memo.Array type UArray (ST s) = STUArray s
type UArray (ReaderCache c (ST s)) Source # |
Instance details Defined in Control.Monad.Memo.Array type UArray (ReaderCache c (ST s)) = STUArray s
type UArray (ReaderCache c IO) Source # |
Instance details Defined in Control.Monad.Memo.Array type UArray (ReaderCache c IO) = IOUArray

type UArrayCache k e (m :: Type -> Type) = 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

Instances details

MaybeLike v v => UArrayMemo v v Source # |
Instance details Defined in Control.Monad.Memo.Array.Instances

evalUArrayMemo Source #

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

runUArrayMemo Source #

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

newtype Container arr Source #

Constructors

Container |

Fields

- toArray :: arr

#### Instances

Instances details

(Monad m, Ix k, MaybeLike e v, MArray c e m) => MonadCache k v (Cache c k e m) Source # |
Instance details Defined in Control.Monad.Memo.Array Methods lookup :: k -> Cache c k e m (Maybe v) Source # add :: k -> v -> Cache c k e m () Source #
(Monad m, Ix k, MaybeLike e v, MArray c e m) => MonadMemo k v (Cache c k e m) Source # |
Instance details Defined in Control.Monad.Memo.Array Methods memo :: (k -> Cache c k e m v) -> k -> Cache c k e m v Source #

type Cache (arr :: Type -> Type -> Type) k e = ReaderCache (Container (arr k e)) Source #

Generic Array-based memo cache

genericEvalArrayMemo :: (Ix k, MaybeLike e v, MArray arr e m) => Cache arr k e m a -> (k, k) -> m a Source #

genericRunArrayMemo :: (Ix k, MaybeLike e v, MArray arr e m) => Cache arr k e m a -> (k, k) -> m (a, arr k e) Source #