Is there a way to "preserve" results in Haskell?

Question

I'm new to Haskell and understand that it is (basically) a pure functional language, which has the advantage that results to functions will not change across multiple evaluations. Given this, I'm puzzled by why I can't easily mark a function in such a way that its remembers the results of its first evaluation, and does not have to be evaluated again each time its value is required.

In Mathematica, for example, there is a simple idiom for accomplishing this:

f[x_]:=f[x]= ...

but in Haskell, the closest things I've found is something like

f' = (map f [0 ..] !!)
   where f 0 = ... 
         f n = f' ...

which in addition to being far less clear (and apparently limited to Int arguments?) does not (seem to) preserve results within an interactive session.

Admittedly (and clearly), I don't understand exactly what's going on here; but naively, it seems like Haskel should have some way, at the function definition level, of

• taking advantage of the fact that its functions are functions and skipping re-computation of their results once they have been computed, and
• indicating a desire to do this at the function definition level with a simple and clean idiom.

Is there a way to accomplish this in Haskell that I'm missing? I understand (sort of) that Haskell can't store the evaluations as "state", but why can't it simply (in effect) redefine evaluated functions to be their computed value?

---

This grows out of this question, in which lack of this feature results in terrible performance.

Answer 1

Use a suitable library, such as MemoTrie.

import Data.MemoTrie

f' = memo f
 where f 0 = ... 
       f n = f' ...

That's hardly less nice than the Mathematica version, is it?

---

Regarding

“why can't it simply (in effect) redefine evaluated functions to be their computed value?”

Well, it's not so easy in general. These values have to be stored somewhere. Even for an Int-valued function, you can't just allocate an array with all possible values – it wouldn't fit in memory. The list solution only works because Haskell is lazy and therefore allows infinite lists, but that's not particularly satisfying since lookup is O(n). For other types it's simply hopeless – you'd need to somehow diagonalise an over-countably infinite domain.

You need some cleverer organisation. I don't know how Mathematica does this, but it probably uses a lot of “proprietary magic”. I wouldn't be so sure that it does really work the way you'd like, for any inputs.

Haskell fortunately has type classes, and these allow you to express exactly what a type needs in order to be quickly memoisable. HasTrie is such a class.