Non-strict memoization
I’ve written a few posts about functional memoization. In one of them, Luke Palmer commented that the memoization methods are correct only for strict functions, which I had not noticed before. In this note, I correct this flaw, extending correct memoization to non-strict functions as well. The semantic notion of least upper bound (which can be built of unambiguous choice) plays a crucial role.
Edits:
- 2010-07-13: Fixed the non-strict memoization example to use an argument of
undefined(⊥) as intended. - 2010-07-23: Changed spelling from “nonstrict” to the much more popular “non-strict”.
- 2011-02-16: Fixed minor typo. (“constraint on result” → “constraint on the result type”)