CODEWITHSUNDEEP
haskellmemoization
Franky
Franky

Reputation: 2421

Memoizing arguments independently

I have a simulation with lots of calls to functions of the type F = A -> B -> C -> D, where A..D are concrete types.

The objects of type A have a medium lifetime. (It is the genome of codegolf's ratrace.)

The most expensive computation arises from parameter A. I can easily memoize like this:

f1 :: F
f1 a = let expensive = trace "expensive computation!" $ expensiveComputation a
        in \b c -> expensive

and hold some pre-processed expensive values via partial application:

preProz :: [B -> C -> D]
preProz = [f1 [], f1 [False], f2 []]

The traces indicate that preProz <*> [[],[[]]] <*> [1,2] does not recompute the values to my delight.

Now I found out that some of my Fs would benefit from pre-processing B, too. This pre-processing is independent from A, and, in fact, memoizing like this has no benefit

f2 a = let expensive = trace "expensive computation!" $ expensiveComputation a
        in \b -> let dear = trace "expensive computation!" $ expensiveComputation b
                  in expensive + dear

because dear is recomputed, even is the bs equal.

What I need is something like:

(B -> e) -> A -> e -> C -> D

where e should be memoized. The type of e is sort-of-existential here. But this forces me to recompute all values A for every B, which is just as bad, and I cannot save the es, which are private to the function.

How can I memoize along 2 parameters independently?

Upvotes: 6

Views: 165

Answers (1)

Neil Mayhew
Neil Mayhew

Reputation: 14958

You need a function that memoizes both a and b together:

f12 a b = ...
    in \c -> ...

When you want to memoize a but not b, you use f1 a and when you want to memoize both you use f12 a b.

It would of course be nice to share some implementation between f1 and f12. However, you can do that only by having private functions that take the precomputed results in place of the original values:

f1 a = privateA (precomputeA a)
f12 a b = privateAB (precomputeA a) (precomputeB b)
privateA a' b = privateAB a' (precomputeB b)
private AB a' b' c = ...

If the precomputation of b depends on the precomputation of a, then:

f1 a = privateA (precomputeA a)
f12 a b = let a' = precomputeA a in privateAB a' (precomputeB a' b)
privateA a' b = privateAB a' (precomputeB a' b)
private AB a' b' c = ...

I've purposely not used function composition and eta-reduction, to make things clearer. I've also left out any strictness annotations that you might want to use to control times of evaluation.

Perhaps memoizing isn't quite the right term here. You mean something like "partial application with some precomputation as well."

Upvotes: 1

Related Questions