Control.Monad.Memo.Array

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).

ArrayCache for boxed types

type family Array (m :: * -> *) :: * -> * -> *

A family of boxed arrays

Instances

type Array IO

Defined in Control.Monad.Memo.Array

type Array IO = IOArray

type Array (ST s)

Defined in Control.Monad.Memo.Array

type Array (ST s) = STArray s

type ArrayCache k e m = Cache (Array m) k e m

Memoization monad based on mutable boxed array

class MaybeLike e v => ArrayMemo v e | v -> e

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

MaybeLike (Maybe v) v => ArrayMemo v (Maybe v)

Defined in Control.Monad.Memo.Array.Instances

evalArrayMemo

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

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 :: * -> *) :: * -> * -> *

A family of unboxed arrays

Instances

type UArray IO

Defined in Control.Monad.Memo.Array

type UArray IO = IOUArray

type UArray (ST s)

Defined in Control.Monad.Memo.Array

type UArray (ST s) = STUArray s

type UArrayCache k e m = Cache (UArray m) k e m

Memoization monad based on mutable unboxed array

class MaybeLike e v => UArrayMemo v e | v -> e

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

Defined in Control.Monad.Memo.Array.Instances

evalUArrayMemo

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

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

Constructors

Container

Fields

• toArray :: arr

Instances

(Monad m, Ix k, MaybeLike e v, MArray c e m) => MonadMemo k v (Cache c k e m)

Defined in Control.Monad.Memo.Array

Methods

memo :: (k -> Cache c k e m v) -> k -> Cache c k e m v

(Monad m, Ix k, MaybeLike e v, MArray c e m) => MonadCache k v (Cache c k e m)

Defined in Control.Monad.Memo.Array

Methods

lookup :: k -> Cache c k e m (Maybe v)

add :: k -> v -> Cache c k e m ()

type Cache arr k e = ReaderCache (Container (arr k e))

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

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