4

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?

Improve this question
3
  • How are you creating the vector? How are you "seeing it repeatedly recreating the table?" Commented Nov 3, 2022 at 15:25
  • @AndrewRay I used Debug.Trace. Commented Nov 3, 2022 at 15:26
  • 1
    You can implement memoization via Representable. See this blog for a good introduction: iagoleal.com/posts/representable-memoize and this question for some additional clarifications: stackoverflow.com/q/73896954/402428 Commented Nov 3, 2022 at 15:33

2 Answers 2

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

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.

Improve this answer

1 Comment

The link contained the insight I needed, and your example highlighted it nicely. Thanks!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.