17

Not sure what exactly to google for this question, so I'll post it directly to SO:

  1. Variables in Haskell are immutable
  2. Pure functions should result in same values for same arguments

From these two points it's possible to deduce that if you call somePureFunc somevar1 somevar2 in your code twice, it only makes sense to compute the value during the first call. The resulting value can be stored in some sort of a giant hash table (or something like that) and looked up during subsequent calls to the function. I have two questions:

  1. Does GHC actually do this kind of optimization?
  2. If it does, what is the behaviour in the case when it's actually cheaper to repeat the computation than to look up the results?

Thanks.

Volker Stolz
  • 7,274
  • 1
  • 32
  • 50
  • I doubt you need a "giant hash table" unless you want to optimize situations where two independent variables happen two have the same values - but that's propably not worth the effort and made even less useful by the fact that function arguments won't be fully evaluated frequently (i.e. you can't check if they're actually the same, at least not without wasting that precious computation time you want to use). –  May 22 '11 at 08:46
  • 1
    See this not-a-faq http://stackoverflow.com/questions/5898162/what-is-the-lifetime-of-a-memoized-value-in-a-functional-language-like-haskell – Don Stewart May 22 '11 at 16:10

2 Answers2

17

GHC doesn't do automatic memoization. See the GHC FAQ on Common Subexpression Elimination (not exactly the same thing, but my guess is that the reasoning is the same) and the answer to this question.

If you want to do memoization yourself, then have a look at Data.MemoCombinators.

Another way of looking at memoization is to use laziness to take advantage of memoization. For example, you can define a list in terms of itself. The definition below is an infinite list of all the Fibonacci numbers (taken from the Haskell Wiki)

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Because the list is realized lazily it's similar to having precomputed (memoized) previous values. e.g. fibs !! 10 will create the first ten elements such that fibs 11 is much faster.

Community
  • 1
  • 1
Jeff Foster
  • 43,770
  • 11
  • 86
  • 103
6

Saving every function call result (cf. hash consing) is valid but can be a giant space leak and in general also slows your program down a lot. It often costs more to check if you have something in the table than to actually compute it.

augustss
  • 22,884
  • 5
  • 56
  • 93