How to use a vector to cache results within a Haskell function?-CodePudding

I have a computationally expensive vector I want to index into inside a function, but since the table is never used anywhere else, I don't want to pass the vector around, but access the precomputed values like a memoized function.

The idea is:

cachedFunction :: Int -> Int
cachedFunction ix = table ! ix
    where table = <vector creation>

One aspect I've noticed is that all memoization examples I've seen deal with recursion, where even if a table is used to memoize, values in the table depend on other values in the table. This is not in my case, where computed values are found using a trial-and-error approach but each element is independent from another.

How do I achieve the cached table in the function?

CodePudding user response：

According to this answer, GHC will never recompute values declared at the top-level of a module. So by moving your table up to the top-level of your module, it will be evaluated lazily (once) the first time it's ever needed, and then it will never be requested again. We can see the behavior directly with Debug.Trace (example uses a simple integer rather than a vector, for simplicity)


import Debug.Trace

cachedFunction :: Int -> Int
cachedFunction ix = table   ix

table = traceShow "Computed" 0

main :: IO ()
main = do
  print 0
  print $ cachedFunction 1
  print $ cachedFunction 2

Outputs:

0
"Computed"
1
2

We see that table is not computed until cachedFunction is called, and it's only computed once, even though we call cachedFunction twice.

CodePudding user response：

You had it almost right. The problem is, your example basically scoped like this:

                    ┌────────────────────────────────┐
cachedFunction ix = │ table ! ix                     │
                    │where table = <vector creation> │
                    └────────────────────────────────┘

i.e. table is not shared between different ix. This is regardless of the fact that it happens to not depend on ix (which is obvious in this example, but not in general). Therefore it would not be useful to keep it in memory, and Haskell doesn't do it.

But you can change that by pulling the ix argument into the result with its associated where-block:

cachedFunction = \ix -> table ! ix
 where table = <vector creation>

i.e.

                 ┌────────────────────────────────┐
cachedFunction = │ \ix -> table ! ix              │
                 │where table = <vector creation> │
                 └────────────────────────────────┘

or shorter,

cachedFunction = (<vector creation> !)

In this form, cachedFunction is a constant applicative form, i.e. despite having a function type it is treated by the compiler as a constant value. It's not a value you could ever evaluate to normal form, but it will keep the same table around (which can't depend on ix; it doesn't have it in scope) when using it for evaluating the lambda function inside.