[Haskell-cafe] Theoretical question: are side effects necessary?

[Ketil Malde]

Ryan Ingram <ryani.spam at gmail.com> writes:

> You can emulate mutation with at most O(log(n)) penalty using a map.  Given
> that memory is of fixed size, log2(n) <= 64, so for "real-world" programs
> this becomes O(1).

I'm not sure assuming fixed size memory is a good idea for a theoretical
discussion - your computer is no longer Turing complete, and one
type of implementation will likely be able to fit a different set of
programs in the given memory than the oher.

Another nit: this is O(log(n)) of working set, not input/problem size.
But I guess any algorithm must be at least O(working set size), so it's
still a log factor (or less) of the algorithmic complexity.

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants