I'm surprised I have not yet linked to Chris Riesbeck's annotations on Paul Graham's ANSI Common Lisp.
Posted by jjwiseman at September 22, 2005 08:36 AMThis binary tree code is very inefficient. Inserting a new element, for example, copies the nodes above the point where the element is inserted. Exactly how much gets copied is left as an exercise for the reader, but such exercises should not be left for maintainers
Destructively modifying a tree as suggested comes at a price: no easy "undo" operation is possible any more, and sharing nodes in e.g., several versions of a tree is not possible anymore.
Depending on the situation, it might be better to rely on GC to get rid of the O(log(n)) copied nodes.
At ILS, the smart Lisp-hackers thought Riesbeck was clueless about code-efficiency-- he judged based on lines-of-code instead of cpu-cycles, and he never figured out how expensive a CONS really is.
How expensive is a CONS, really?
Posted by: Luke Gorrie on September 22, 2005 11:22 AMNow I know that CONS is what they teach the suckers.
Posted by: Tayssir John Gabbour on September 22, 2005 05:43 PM