PG's Binary Search Trees in Clojure

paste.lisp.org

38 pointsnkh5 comments

Dumb question time: what's the difference between PG's BST and any other BST?

Up-votes?

Paul Graham's was wrong in his book (see http://www.paulgraham.com/howbroken.html) but fixed in his later code listing (see http://lib.store.yahoo.net/lib/paulgraham/acl2.lisp). The Clojure code looks like the broken version to me.

I think you're mistaken. The Clojure version seems to be derived from the Arc version at http://ycombinator.com/arc/bst.arc, which is turn derived from the corrected Common Lisp version.

You may also be interested by my implementation with / without various form of tail-recursion using recur or without: http://github.com/kototama/ansicommonlisp-book-clojure/blob/...

Reply on news.ycombinator.com