[Haskell-cafe] Re: Red-Blue Stack
Thomas Davie
tom.davie at gmail.com
Fri Sep 26 14:03:08 EDT 2008
On 26 Sep 2008, at 19:18, Stephan Friedrichs wrote:
> apfelmus wrote:
>> [..]
>>
>> Persistent data structures are harder to come up with than ephemeral
>> ones, [...]
>
> Yes, in some cases it's quite hard to find a persistent solution for a
> data structure that is rather trivial compared to its ephemeral
> counterpart. My question is: Is there a case, where finding a
> persistent
> solution that performs equally well is *impossible* rather than just
> harder? I mean might there be a case where (forced) persistence (as we
> have in pure Haskell) is a definite disadvantage in terms of big-O
> notation? Do some problems even move from P to NP in a persistent
> setting?
I'm fairly confident one could come up with a proof that you'll never
go from P to NP because of it along the lines of treating all memory
as being a list. Operations to modify memory are all in P (although
slow), so any algorithm that relies on mutation to be in P will stay
in P (although with a higher polynomial factor).
Bob
More information about the Haskell-Cafe
mailing list