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

Ryan Ingram 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