[Haskell-cafe] Theoretical question: are side effects necessary?
ketil at malde.org
Sat Mar 17 07:48:00 CET 2012
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.
If I haven't seen further, it is by standing in the footprints of giants
More information about the Haskell-Cafe