monad-memo-0.5.4: Memoization monad transformer

Copyright | (c) Eduard Sergeev 2011
License | BSD-style (see the file LICENSE)
Maintainer | eduard.sergeev@gmail.com
Stability | experimental
Portability | non-portable (multi-param classes, functional dependencies)
Safe Haskell | None
Language | Haskell2010

Control.Monad.Memo

Contents

- MonadMemo class
- Generalized Memo monad
- Generalized MemoStateT monad transformer
- Map-based Memo monad
- Map-based MemoT monad transformer
- Array-based Memo monad
  - ArrayCache for boxed types
  - ArrayCache for unboxed types
- Vector-based Memo monad
  - VectorCache for boxed types
  - VectorCache for unboxed types
- Adapter for memoization of multi-argument functions
- Memoization cache level access functions
- Example 1: Fibonacci numbers
- Example 2: Mutualy recursive definition with memoization
- Example 3: Combining Memo with other transformers
- Example 4: Memoization of multi-argument function
- Example 5: Alternative memo caches

Description

Importing just this module is sufficient for most cases of the package usage

Synopsis

- module Control.Monad
- module Control.Monad.Trans.Class
- module Data.MapLike
- module Data.MaybeLike
- class Monad m => MonadMemo k v (m :: Type -> Type) | m -> k, m -> v where
  - memo :: (k -> m v) -> k -> m v
- type MemoState c k v = MemoStateT c k v Identity
- runMemoState :: MemoState c k v a -> c -> (a, c)
- evalMemoState :: MemoState c k v a -> c -> a
- type MemoStateT s k v = StateCache (Container s)
- runMemoStateT :: Monad m => MemoStateT s k v m a -> s -> m (a, s)
- evalMemoStateT :: Monad m => MemoStateT c k v m a -> c -> m a
- type Memo k v = MemoT k v Identity
- runMemo :: Memo k v a -> Map k v -> (a, Map k v)
- evalMemo :: Memo k v a -> Map k v -> a
- startRunMemo :: Memo k v a -> (a, Map k v)
- startEvalMemo :: Memo k v a -> a
- type MemoT k v = MemoStateT (Map k v) k v
- runMemoT :: Monad m => MemoT k v m a -> Map k v -> m (a, Map k v)
- evalMemoT :: Monad m => MemoT k v m a -> Map k v -> m a
- startRunMemoT :: Monad m => MemoT k v m a -> m (a, Map k v)
- startEvalMemoT :: Monad m => MemoT k v m a -> m a
- 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 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)
- type VectorCache s e = Cache Vector s e
- class MaybeLike e v => VectorMemo v e | v -> e
- evalVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> Int -> m a
- runVectorMemo :: (PrimMonad m, VectorMemo v e) => VectorCache (PrimState m) e m a -> Int -> m (a, Vector (PrimState m) e)
- type UVectorCache s e = Cache UVector s e
- class MaybeLike e v => UVectorMemo v e | v -> e
- evalUVectorMemo :: (PrimMonad m, MVector UVector e, UVectorMemo v e) => UVectorCache (PrimState m) e m a -> Int -> m a
- runUVectorMemo :: (PrimMonad m, MVector UVector e, UVectorMemo v e) => UVectorCache (PrimState m) e m a -> Int -> m (a, UVector (PrimState m) e)
- for2 :: (((k1, k2) -> mv) -> (k1, k2) -> mv) -> (k1 -> k2 -> mv) -> k1 -> k2 -> mv
- for3 :: (((k1, k2, k3) -> mv) -> (k1, k2, k3) -> mv) -> (k1 -> k2 -> k3 -> mv) -> k1 -> k2 -> k3 -> mv
- for4 :: (((k1, k2, k3, k4) -> mv) -> (k1, k2, k3, k4) -> mv) -> (k1 -> k2 -> k3 -> k4 -> mv) -> k1 -> k2 -> k3 -> k4 -> mv
- memoln :: (MonadCache k2 v m1, Monad m1, Monad m2) => (forall a. m1 a -> m2 a) -> (k1 -> k2) -> (k1 -> m2 v) -> k1 -> m2 v
- memol0 :: (MonadCache k v m, Monad m) => (k -> m v) -> k -> m v
- memol1 :: forall t1 k v (m :: Type -> Type). (MonadTrans t1, MonadCache k v m, Monad (t1 m)) => (k -> t1 m v) -> k -> t1 m v
- memol2 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (MonadTrans t1, MonadTrans t2, MonadCache k v m, Monad (t2 m), Monad (t1 (t2 m))) => (k -> t1 (t2 m) v) -> k -> t1 (t2 m) v
- memol3 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) (t3 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (MonadTrans t1, MonadTrans t2, MonadTrans t3, MonadCache k v m, Monad (t3 m), Monad (t2 (t3 m)), Monad (t1 (t2 (t3 m)))) => (k -> t1 (t2 (t3 m)) v) -> k -> t1 (t2 (t3 m)) v
- memol4 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) (t3 :: (Type -> Type) -> Type -> Type) (t4 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (MonadTrans t1, MonadTrans t2, MonadTrans t3, MonadTrans t4, MonadCache k v m, Monad (t4 m), Monad (t3 (t4 m)), Monad (t2 (t3 (t4 m))), Monad (t1 (t2 (t3 (t4 m))))) => (k -> t1 (t2 (t3 (t4 m))) v) -> k -> t1 (t2 (t3 (t4 m))) v

# Documentation

module Control.Monad

module Control.Monad.Trans.Class

module Data.MapLike

module Data.MaybeLike

# MonadMemo class

class Monad m => MonadMemo k v (m :: Type -> Type) | m -> k, m -> v where Source #

Memoization interface

Methods

memo :: (k -> m v) -> k -> m v Source #

#### Instances

Instances details

MonadCache k (Maybe v) m => MonadMemo k v (MaybeT m) Source # |
Instance details Defined in Control.Monad.Memo.Class Methods memo :: (k -> MaybeT m v) -> k -> MaybeT m v Source #
MonadCache k (Either e v) m => MonadMemo k v (ExceptT e m) Source # |
Instance details Defined in Control.Monad.Memo.Class Methods memo :: (k -> ExceptT e m v) -> k -> ExceptT e m v Source #
MonadCache k v m => MonadMemo k v (IdentityT m) Source # |
Instance details Defined in Control.Monad.Memo.Class Methods memo :: (k -> IdentityT m v) -> k -> IdentityT m v Source #
MonadCache (r, k) v m => MonadMemo k v (ReaderT r m) Source # |
Instance details Defined in Control.Monad.Memo.Class Methods memo :: (k -> ReaderT r m v) -> k -> ReaderT r m v Source #
MonadCache (s, k) (v, s) m => MonadMemo k v (StateT s m) Source # |
Instance details Defined in Control.Monad.Memo.Class Methods memo :: (k -> StateT s m v) -> k -> StateT s m v Source #
MonadCache (s, k) (v, s) m => MonadMemo k v (StateT s m) Source # |
Instance details Defined in Control.Monad.Memo.Class Methods memo :: (k -> StateT s m v) -> k -> StateT s m v Source #
(Monoid w, MonadCache k (v, w) m) => MonadMemo k v (WriterT w m) Source # |
Instance details Defined in Control.Monad.Memo.Class Methods memo :: (k -> WriterT w m v) -> k -> WriterT w m v Source #
(Monoid w, MonadCache k (v, w) m) => MonadMemo k v (WriterT w m) Source # |
Instance details Defined in Control.Monad.Memo.Class Methods memo :: (k -> WriterT w m v) -> k -> WriterT w m v Source #
MonadCache k v m => MonadMemo k v (ContT r m) Source # |
Instance details Defined in Control.Monad.Memo.Class Methods memo :: (k -> ContT r m v) -> k -> ContT r m v Source #
(PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m) Source # |
Instance details Defined in Control.Monad.Memo.Vector Methods memo :: (Int -> Cache c s e m v) -> Int -> Cache c s e m v Source #
(PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m) Source # |
Instance details Defined in Control.Monad.Memo.Vector.Expandable Methods memo :: (Int -> Cache c s e m v) -> Int -> Cache c s e m v Source #
(PrimMonad m, PrimState m ~ s, MaybeLike e v, MVector c e) => MonadMemo Int v (Cache c s e m) Source # |
Instance details Defined in Control.Monad.Memo.Vector.Unsafe Methods memo :: (Int -> Cache c s e m v) -> Int -> Cache c s e m v 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 #
(Monad m, MapLike c k v) => MonadMemo k v (MemoStateT c k v m) Source # |
Instance details Defined in Control.Monad.Trans.Memo.State Methods memo :: (k -> MemoStateT c k v m v) -> k -> MemoStateT c k v m v Source #
(Monoid w, MonadCache (r, s, k) (v, s, w) m) => MonadMemo k v (RWST r w s m) Source # |
Instance details Defined in Control.Monad.Memo.Class Methods memo :: (k -> RWST r w s m v) -> k -> RWST r w s m v Source #
(Monoid w, MonadCache (r, s, k) (v, s, w) m) => MonadMemo k v (RWST r w s m) Source # |
Instance details Defined in Control.Monad.Memo.Class Methods memo :: (k -> RWST r w s m v) -> k -> RWST r w s m v Source #

# Generalized Memo monad

type MemoState c k v = MemoStateT c k v Identity Source #

Memoization monad based on `StateCache` to be used with pure cache containers which support `MapLike` interface

runMemoState :: MemoState c k v a -> c -> (a, c) Source #

Returns the pair of the result of `MonadMemo` computation along with the final state of the internal pure container

evalMemoState :: MemoState c k v a -> c -> a Source #

Returns the result of `MonadMemo` computation discarding the cache

# Generalized MemoStateT monad transformer

type MemoStateT s k v = StateCache (Container s) Source #

Memoization monad transformer based on `StateCache` to be used with pure cache containers which support `MapLike` interface

runMemoStateT :: Monad m => MemoStateT s k v m a -> s -> m (a, s) Source #

Returns the pair of the result of `MonadMemo` computation along with the final state of the internal pure container wrapped in monad

evalMemoStateT :: Monad m => MemoStateT c k v m a -> c -> m a Source #

Returns the result of `MonadMemo` computation wrapped in monad. This function discards the cache

# Map-based Memo monad

type Memo k v = MemoT k v Identity Source #

Memoization monad which uses `Map` as a cache container

runMemo :: Memo k v a -> Map k v -> (a, Map k v) Source #

Given an initial cache, compute the result of a memoized computation along with the final state of the cache

evalMemo :: Memo k v a -> Map k v -> a Source #

Given an initial state, compute the result of a memoized computation discarding the final state of the cache

startRunMemo :: Memo k v a -> (a, Map k v) Source #

Compute the result of memoized computation along with the final state of the cache. This function uses empty `Map` as an initial state

startEvalMemo :: Memo k v a -> a Source #

Compute the result of a memoized computation discarding the final state of the cache. This function uses empty `Map` as an initial state

# Map-based MemoT monad transformer

type MemoT k v = MemoStateT (Map k v) k v Source #

Memoization monad transformer which uses `Map` as a cache container

runMemoT :: Monad m => MemoT k v m a -> Map k v -> m (a, Map k v) Source #

Given an initial cache, compute the result of a memoized computation along with the final state of the cache

evalMemoT :: Monad m => MemoT k v m a -> Map k v -> m a Source #

Given an initial state, compute the result of a memoized computation discarding the final state of the cache

startRunMemoT :: Monad m => MemoT k v m a -> m (a, Map k v) Source #

Compute the result of memoized computation along with the final state of the cache. This function uses empty `Map` as an initial state

startEvalMemoT :: Monad m => MemoT k v m a -> m a Source #

Compute the result of a memoized computation discarding the final state of the cache. This function uses empty `Map` as an initial state

# Array-based Memo monad

## ArrayCache for boxed types

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

# Vector-based Memo monad

## VectorCache for boxed types

type VectorCache s e = Cache Vector s e Source #

`MonadCache` based on boxed vector

class MaybeLike e v => VectorMemo v e | v -> e Source #

This is just to be able to infer the type of the `VectorCache` element.

#### Instances

Instances details

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

evalVectorMemo Source #

Arguments

:: (PrimMonad m, VectorMemo v e) |
=> VectorCache (PrimState m) e m a | memoized computation
-> Int | vector length
-> m a | result

Evaluate computation using mutable boxed vector

Vector length must covers all possible keys used in computation otherwise index out of bound error is generated by vector code

runVectorMemo Source #

Arguments

:: (PrimMonad m, VectorMemo v e) |
=> VectorCache (PrimState m) e m a | memoized computation
-> Int | vector length
-> m (a, Vector (PrimState m) e) | result and final vector cache

Evaluate computation using mutable boxed vector. It also returns the final content of the vector cache

Vector length must covers all possible keys used in computation otherwise index out of bound error is generated by vector code

## VectorCache for unboxed types

type UVectorCache s e = Cache UVector s e Source #

`MonadCache` based on unboxed vector

class MaybeLike e v => UVectorMemo v e | v -> e Source #

This is just to be able to infer the type of the `UVectorCache` element.

#### Instances

Instances details

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

evalUVectorMemo Source #

Arguments

:: (PrimMonad m, MVector UVector e, UVectorMemo v e) |
=> UVectorCache (PrimState m) e m a | memoized computation
-> Int | vector length
-> m a | result

Evaluate computation using mutable unboxed vector

Vector length must covers all possible keys used in computation otherwise index out of bound error is generated by vector code

runUVectorMemo Source #

Arguments

:: (PrimMonad m, MVector UVector e, UVectorMemo v e) |
=> UVectorCache (PrimState m) e m a | memoized computation
-> Int | vector length
-> m (a, UVector (PrimState m) e) | result and final vector cache

Evaluate computation using mutable unboxed vector. It also returns the final content of the vector cache

Vector length must covers all possible keys used in computation otherwise index out of bound error is generated by vector code

# Adapter for memoization of multi-argument functions

for2 :: (((k1, k2) -> mv) -> (k1, k2) -> mv) -> (k1 -> k2 -> mv) -> k1 -> k2 -> mv Source #

Adapter for memoization of two-argument function

for3 :: (((k1, k2, k3) -> mv) -> (k1, k2, k3) -> mv) -> (k1 -> k2 -> k3 -> mv) -> k1 -> k2 -> k3 -> mv Source #

Adapter for memoization of three-argument function

for4 :: (((k1, k2, k3, k4) -> mv) -> (k1, k2, k3, k4) -> mv) -> (k1 -> k2 -> k3 -> k4 -> mv) -> k1 -> k2 -> k3 -> k4 -> mv Source #

Adapter for memoization of four-argument function

# Memoization cache level access functions

memoln :: (MonadCache k2 v m1, Monad m1, Monad m2) => (forall a. m1 a -> m2 a) -> (k1 -> k2) -> (k1 -> m2 v) -> k1 -> m2 v Source #

Memoization for the current transformer in stack using a cache from an arbitrary transformer down the stack

memol0 :: (MonadCache k v m, Monad m) => (k -> m v) -> k -> m v Source #

Uses current monad's memoization cache

memol1 :: forall t1 k v (m :: Type -> Type). (MonadTrans t1, MonadCache k v m, Monad (t1 m)) => (k -> t1 m v) -> k -> t1 m v Source #

Uses the 1st transformer in stack for memoization cache

memol2 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (MonadTrans t1, MonadTrans t2, MonadCache k v m, Monad (t2 m), Monad (t1 (t2 m))) => (k -> t1 (t2 m) v) -> k -> t1 (t2 m) v Source #

Uses the 2nd transformer in stack for memoization cache

memol3 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) (t3 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (MonadTrans t1, MonadTrans t2, MonadTrans t3, MonadCache k v m, Monad (t3 m), Monad (t2 (t3 m)), Monad (t1 (t2 (t3 m)))) => (k -> t1 (t2 (t3 m)) v) -> k -> t1 (t2 (t3 m)) v Source #

Uses the 3rd transformer in stack for memoization cache

memol4 :: forall t1 (t2 :: (Type -> Type) -> Type -> Type) (t3 :: (Type -> Type) -> Type -> Type) (t4 :: (Type -> Type) -> Type -> Type) k v (m :: Type -> Type). (MonadTrans t1, MonadTrans t2, MonadTrans t3, MonadTrans t4, MonadCache k v m, Monad (t4 m), Monad (t3 (t4 m)), Monad (t2 (t3 (t4 m))), Monad (t1 (t2 (t3 (t4 m))))) => (k -> t1 (t2 (t3 (t4 m))) v) -> k -> t1 (t2 (t3 (t4 m))) v Source #

Uses the 4th transformer in stack for memoization cache

# Example 1: Fibonacci numbers

Memoization can be specified whenever monadic computation is taking place. Including recursive definition. Classic example: Fibonacci number function: Here is simple non-monadic definition of it

    fib :: (Eq n, Num n) => n -> n
    fib 0 = 0
    fib 1 = 1
    fib n = fib (n-1) + fib (n-2)

To use `Memo` monad we need to convert it into monadic form:

    fibm :: (Eq n, Num n, Monad m) => n -> m n
    fibm 0 = return 0
    fibm 1 = return 1
    fibm n = do
      n1 <- fibm (n-1)
      n2 <- fibm (n-2)
      return (n1+n2)

Then we can specify which computation we want to memoize with `memo` (both recursive calls to (n-1) and (n-2)):

    fibm :: (Eq n, Num n, Ord n) => n -> Memo n n n
    fibm 0 = return 0
    fibm 1 = return 1
    fibm n = do
      n1 <- memo fibm (n-1)
      n2 <- memo fibm (n-2)
      return (n1+n2)

NB: `Ord` is required since internaly Memo implementation uses `Map` to store and lookup memoized values

Then it can be run with `startEvalMemo`

    startEvalMemo (fibm 100)

Or using applicative form:

    fibm :: (Eq n, Num n, Ord n) => n -> Memo n n n
    fibm 0 = return 0
    fibm 1 = return 1
    fibm n = (+) <$> memo fibm (n-1) <*> memo fibm (n-2)

# Example 2: Mutualy recursive definition with memoization

In order to use memoization for both mutually recursive function we need to use nested MemoT monad transformers (one for each cache). Let's extend our Fibonacci function with meaningless extra function `boo` which in turn uses `fibm2`.

Memoization cache type for `fibm2` (caches `Integer -> Integer`) will be:

    type MemoFib = MemoT Integer Integer

While cache for `boo` (`Double -> String`):

    type MemoBoo = MemoT Double String

Stacking them together gives us te overall type for our combined memoization monad:

    type MemoFB = MemoFib (MemoBoo Identity)

    boo :: Double -> MemoFB String
    boo 0 = return ""
    boo n = do
      n1 <- memol1 boo (n-1)           -- uses next in stack transformer (memol_1_): MemoBoo is nested in MemoFib
      fn <- memol0 fibm2 (floor (n-1))   -- uses current transformer (memol_0_): MemoFib
      return (show fn ++ n1)

    fibm2 :: Integer -> MemoFB Integer
    fibm2 0 = return 0
    fibm2 1 = return 1
    fibm2 n = do
      l <- memol1 boo (fromInteger n)        -- as in 'boo' we need to use 1st nested transformer here
      f1 <- memol0 fibm2 (n-1)               -- and 0st (the current) for fibm2
      f2 <- memol0 fibm2 (n-2)
      return (f1 + f2 + floor (read l))

    evalFibM2 :: Integer -> Integer
    evalFibM2 = startEvalMemo . startEvalMemoT . fibm2

# Example 3: Combining Memo with other transformers

`MonadMemo` can be combined with other monads and transformers:

With `MonadWriter`:

    fibmw :: (MonadWriter String m, MonadMemo Integer Integer m) => Integer -> m Integer
    fibmw 0 = return 0
    fibmw 1 = return 1
    fibmw n = do
      f1 <- memo fibmw (n-1)
      f2 <- memo fibmw (n-2)
      tell $ show n
      return (f1+f2)

    evalFibmw :: Integer -> (Integer, String)
    evalFibmw = startEvalMemo . runWriterT . fibmw

# Example 4: Memoization of multi-argument function

Functions with more than one argument (in curried form) can also be memoized with a help of `forX` set of function: For two-argument function we can use `for2` function adapter:

    -- Ackerman function classic definition
    ack :: (Eq n, Num n) => n -> n -> n
    ack 0 n = n+1
    ack m 0 = ack (m-1) 1
    ack m n = ack (m-1) (ack m (n-1))

    -- Ackerman function memoized definition
    ackm :: (Num n, Ord n, MonadMemo (n, n) n m) => n -> n -> m n
    ackm 0 n = return (n+1)
    ackm m 0 = for2 memo ackm (m-1) 1
    ackm m n = do
      n1 <- for2 memo ackm m (n-1)
      for2 memo ackm (m-1) n1

    evalAckm :: (Num n, Ord n) => n -> n -> n
    evalAckm n m = startEvalMemo $ ackm n m

# Example 5: Alternative memo caches

Given a monadic function definition it is often possible to execute it using different memo-cache (`MonadCache`) implementations. For example `ArrayCache` when used can dramatically reduce function computation time and memory usage.

For example the same Fibonacci function:

    fibm 0 = return 0
    fibm 1 = return 1
    fibm n = (+) <$> memo fibm (n-1) <*> memo fibm (n-2)

can easily be run using mutable array in `ST` monad:

    evalFibmSTA :: Integer -> Integer
    evalFibmSTA n = runST $ evalArrayMemo (fibm n) (0,n)

or, if we change its return type to a primitive (unboxed) value, we can use even more efficient unboxed array `STUArray`:

    evalFibmSTUA :: Integer -> Double
    evalFibmSTUA n = runST $ evalUArrayMemo (fibm n) (0,n)

Finally if we want to achieve the best performance within monad-memo, we can switch to unboxed `Vector`-based `MemoCache` (vectors support only `Int` as a key so we have to change the type):

    evalFibmSTUV :: Int -> Double
    evalFibmSTUV n = runST $ evalUVectorMemo (fibm n) (n+1)

Note that `IO` monad can be used instead of `ST`:

    evalFibmIOUV :: Int -> IO Double
    evalFibmIOUV n = evalUVectorMemo (fibm n) (n+1)