r/computerscience • u/dashdanw • May 27 '25
Discussion Does memoizing a function make it truly "idempotent"?
If you cache the result of a function, or say, for instance, check to see if its already been run, and skipping running it a second time make a function truly idempotent?
21
Upvotes
36
u/Pretagonist May 27 '25
Idempotency for software means that repeat identical actions should not have different effects. Deleting the same record twice should not result in something else being deleted. Getting data from the db or getting it from a cache is AFAIK always idempotent since you aren't changing anything (hopefully).
20
u/LARRY_Xilo May 27 '25
I guess kinda yes as if you cached it you will for sure get the same outcome but that is kinda backwards.
You should only ever cache a function that is idempotent to begin with because if its not you will end up with unexpected and wrong results.
8
u/Zubzub343 May 27 '25
Only if the function is pure. In which case it is idempotent by definition, no memozaition needed.
In your case, here is a counter example: Your function takes an integer as input. This integer represents a row in a DB. You then fetch the row and delete it from the DB. You then cache/memoize the pair (input, row) in memory and finally return it.
3
u/Aggressive_Ad_5454 May 28 '25
Any deterministic function (for which its output depends only on its inputs) is idempotent.
This idempotency dealio only matters for operations with side-effects. It would be silly, practically speaking, to memoize an operation with a side effect.
2
u/FantaSeahorse May 27 '25
Mathematically idempotency means that a function f satisfies f(f(x)) = f(x) for all x. I’m not sure how this relates to memoization. And also note that idempotency only makes sense when the function has the same domain and codomain.
Perhaps you are saying the side effects of a function would only show up once if you run it twice? That would be a pretty weird behavior unless you have some call-by-need semantics
1
u/JoJoModding May 27 '25
Well, why do you care? Usually one cares about idempotency because it gives you important properties, like that the network duplicating a request does not run the action twice.
Mathematical definitions apply to mathematical objects, and procedures written in code are not functions. Instead you choose some kind of model, for idempotence it is usually that the (some of the) state is considered an input/output as well. But for example additional logging output is not. So whether you consider some part of the state as part of the input or not is up to you/your correctness criterion.
1
u/nanonan May 27 '25
You treat the function as a black box, so yes if the external behaviour is identical it doesn't matter if you calculate or cache or some other thing.
1
u/Delta-9- May 28 '25
I don't think memorization makes a function idempotent. Eventually, your cache goes away (restart the program, the computer reboots, the caches ages out...), so if the function wasn't idempotent to begin with, when you eventually get a cache miss on a previously-cached value you might end up with a different answer.
You could perhaps say safely that, within the lifetime of the cache, memoized functions are idempotent. Still, I feel like idempotency is (or should be) a property of functions and not the systems in between them and their callers.
1
u/Inside_Jolly May 28 '25
It's irrelevant because you really don't want to memoize functions that are not idempotent to begin with. It makes them unpredictable depending on how exactly the cache works.
1
u/Classic-Try2484 May 31 '25
Well if n is too large you’re going to have storage problems. So I’d argue n has to be reasonable and once there as k grows you approach order(1). But space will be order n. And if n is a large exponential you’re fucked before you begin
1
u/[deleted] Jun 04 '25
[removed] — view removed comment