>>8427I think you are asking two different things but not too sure.
I will answer the memoization first a la
f(x) { if (f[x] == null) {f[x] = f(x)} return f[x];}
Haskell is semantically non-strict and the GHC compiler is lazy by default. This allows you to pretend like there exist an infinitely large data structure (list for single valued functions, map for multiple valued functions et cetra) that is populated with values you (will) need. When your program actually executes in hardware and needs that value, it will either utilize the contents of list / map / data structure or calculate (recursively or not) the value it need, store it into list / map / data structure and use it (transparently). There is no practical difference (as in how rough assembly language output would be generated) between your 'procedural' pseudo code and
memoize f = (map f [0 ..] !!)
fx = fix(memoize . f)
after all, turing machine and lambda expression should be equivalent right?
Now about the second part of the question regarding 'global' immutable, as you could readily understand the infinitely large data structure caching f's value is indeed immutable from programmer's perspective. Its contents are initally not 'realized' but it can, and it will be realized when you actually need it on runtime. You might be confusing not relying on mutability (side effect) while writing program and how haskell's compiler and runtime actually evaluates the code. If no side effect of any kind is not allowed while realizing computation, haskell or purely functional codes will not be able to do anything inside physical processor and that is not the point of 'purely' functional languages.
Post too long. Click here to view the full text.