>>>     This is a good example of where it becomes confusing.
>
>> I think part of it may be that you're thinking "insert" actually inserts
>> something in the heap. Nope! "insert" is a function that when given a value
>> and a heap, gives you back the new heap you would have were you to insert
>> that given value into that given heap.

I'm not sure a person unfamiliar with Haskell would even get that far.

>    What happens to the old heap?

Nothing. (That's exactly the point, of course.)

If nobody is using the old heap any more, the garbage collector will 
remove it at some point.

If you /really/ wanted to split hairs, the insert function is only 
duplicating log N heap nodes. The remaining N - log N nodes (and the 
data they point to) are shared between the old and new heaps. And if the 
old heap is no longer needed, the log N nodes it doesn't share with the 
new heap will automatically be removed eventually.

And if you really, really want to get picky, actually saying

   heap' = insert 27 heap

merely creates an expression node which heap' points to. Only if you 
attempt to /inspect/ this heap is any code executed. (And even then, 
inspecting each node only causes that single node to be constructed. 
It's child nodes remain unevaluated until you look at them.)

Post a reply to this message