haskell - Memoization in recursive expressions using a Map -
i'm calculating recursive expressions of form,
now, let suppose have list of indexes t,u,v ([t,u,v]::int)
simplicity can represent [[int]]
, , want calculate r function each index [t,u,v]
using similar following code:
import qualified data.vector.unboxed u import qualified data.map.strict m data hermitestateintegral = hermitestateintegral { getmapi :: m.map [int] double ,getkeyi :: [[int]] } deriving show calcintegrals :: [double] ->[[int]] -> double -> vector double calcintegrals vs listindex f0 = u.unfoldr (calcrecexpr vs) seedi seedi = hermitestateintegral mapi0 listindex mapi0 = m.insert [0,0,0] f0 m.empty calcrecexpr :: [double] -> hermitestateintegral -> maybe (double,hermitestateintegral) calcrecexpr vs hs@(hermitestateintegral m is)= <- safehead -- safehead :: [a] -> maybe -- if value associated indexes t,u,v not in map -- calculate using recursive equations let (val,newmap) = (lookupm m) `mplus` (fun vs m) newst = hs{getmapi = newmap,getkeyi = tail is} return (val,newst) lookupm :: ord k => k -> m.map k -> maybe (a , m.map k a) lookupm k m = val <- m.lookup k m return (val,m) fun :: [double] -> [int] -> m.map [int] double -> maybe (double, m.map [int] double) fun vs m = -- fun computes value associated index [t,u,v] -- not in map, using recursive equations. , -- insert value on map.
so, using map
explicitly store r subexpressions. if want calculate example index [1,1,1] map store indexes [0,1,1],[0,0,1],[0,0,0] can use in future calculations.
my questions there: efficient implementation explicitly caching subexpression of r ? there more efficient way express memoization using lazy evaluation?
Comments
Post a Comment