Ryan Ingram wrote:
On Sat, Nov 22, 2008 at 5:33 AM, Janis Voigtlaender
<[EMAIL PROTECTED]> wrote:
You can generally make a persistent data structure with the same
asymptotic bounds as the ephemeral structure, ...
I would be very careful with the "generally" here. At least, I am not
aware that this has been proved to always be possible.
Here's an informal proof:
You can use an intmap to emulate pointers, to turn any ephemeral data
structure into a persistent one. That adds at most a log-n factor to
lookups and updates. For many structures, this is enough to prove
asymptotic bounds equivalence.
However, the standard 'pointer' model for ephemeral structures makes
the assumption that memory size is limited; otherwise you have to add
a log(n) factor there anyways, both to hold the large pointer values
that get generated and to actually send the bits to the memory bus.
Given this assumption you can take log(memory size) as a constant and
argue that pointer lookup and update via the map is O(1).
Ah, that makes sense.
--
Dr. Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:[EMAIL PROTECTED]
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
