Archive for 13th July 2010

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.


  • 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”)

Continue reading ‘Non-strict memoization’ »