Invisible <voi### [at] devnull> wrote:
> On 06/09/2011 04:03 PM, Warp wrote:
> > Darren New<dne### [at] sanrrcom>  wrote:
> >> Then the old heap is in oldheap and the new heap is in newheap.
> >
> >    Is this supposed to be efficient?

> Modifying log N nodes of the old heap to construct the new one? I'd say 
> it's reasonably efficient, yes.

  Not modifying. *Copying*. There's a huge difference. (All in-place data
containers and algorithms *modify* the elements, that's not the problem.
The problem I see there with Haskell is that it *copies* the elements.)

  (Also: Imagine that the elements of the heap had some mutable data
container in them. Of course that's not purely functional anymore, but
AFAIK that's *possible* in Haskell. How can you avoid having to copy the
entire tree when you insert or remove a node? It's not like the new heap
and the old heap could share some of the nodes, because if you modify the
mutable container of one of those nodes, the other heap is going to see
the modification.)

-- 
                                                          - Warp

Post a reply to this message