Find minimum value in a BST: using boolean operators, and using conditionals

Question

I've been studying the BST code in Paul Graham's ANSI Common Lisp.

He provides (my comments):

(defun bst-min (bst)
  (and bst                               ; [3]
       (or (bst-min (node-l bst)) bst))) ; [4]

(defun bst-max (bst)
  (and bst                               ; [5]
       (or (bst-max (node-r bst)) bst))) ; [6]

;; [1] How do you find min and max of a bst?
;;     Recall, the core point is that all items in left subtree are lower,
;;     and all items in right subtree are higher, & this holds for the whole
;;     tree, -otherwise binary search would miss-, and not just within a
;;     single parent child relationship.
;; [2] Therefore, to find min, we just need to go left until we can go left
;;     no more, & that's the min. If the above property didn't hold, you
;;     might go left, then right, then left, and that final one there
;;     could be as low as you like; but no, it must be greater than its
;;     ancestor of which it is a right child.

;; [3] A null node has no min. The base case. Returns nil if bst is empty.
;; [4] For a non null node, the min is either the min of its left node, or
;;     if that's null, then it's this node, instead.
;; [5] A null node has no max. The base case. Returns nil if bst is empty.
;; [6] For a non null node, the max is either the max of its right node, or
;;     if that's null, then it's this node, instead.

I find this code more or less fine, but I still find it not easy to read or cognitively process.

I'm wondering whether that subjective fact is a feature of the code itself (i.e., is the code really hard to read), or whether it's something I need to stick with and then it will become very natural; remembering Hickey's advice about lisp that it is simple but not easy.

So, I produced this version by translating from a java implementation. It's easier for me to read (currently).

(defun bst-min (bst)
  (if (null (node-l bst))
      bst
      (bst-min (node-l bst))))

(defun bst-max (bst)
  (if (null (node-r bst))
      bst
      (bst-max (node-r bst))))

Is the first version somehow a relic of former days? Would anyone program like that now?

Question I would like to ask helpful peeps here is: which version would you favour and why?

Renzo · Accepted Answer · 2019-07-10 09:16:15Z

You are asking:

which version would you favour and why?

Instead of answering directly to your question, I will try to show why that formulation is not, at least in my opinion, “a relic of former days”, but quite idiomatic for Common Lisp (and other “terse” languages). My attempt is done by first recalling an important concept of the language, and then by showing how to apply this concept to your definition of the function, by successive refining of it.

In Common Lisp there is the concept of “Generalized Boolean”: the symbol nil (which represents also the empty list), represents false and all the other objects represent true. The concept is so deeply rooted in the language, and it so frequently used in defining primitive functions and special forms, that it has become an habit of programmers in this language to rely on this concept as much as possible, in order to shorten (and in some way to simplify) the code.

Let’s start from your definition:

(defun bst-min (bst)
  (if (null (node-l bst))
      bst
      (bst-min (node-l bst))))

First of all, this definition does not work for the edge case in which the tree is empty. In this case, (node-l bst) causes the error: The value NIL is not of the expected type NODE.

Let’s try to correct it by adding a check before that case:

(defun bst-min (bst)
  (cond ((null bst) nil)
        ((null (node-l bst)) bst)
        (t (bst-min (node-l bst)))))

Now we can note that the first two branches of the conditional have the same result: bst (which is nil in the first case), so that we can simplify the code by oring the two conditions:

(defun bst-min (bst)
  (if (or (null bst) (null (node-l bst)))
      bst
      (bst-min (node-l bst)))))

Since both the conditions of the or test the “emptyness” of an object (i.e. if it is equal to nil), for the concept of generalized boolean we can consider that (null x) is equivalent to (not x), and or with two not can be “simplified” to an and with positive tests and inversion of the branches of the if:

(defun bst-min (bst)
  (if (and bst (node-l bst))
      (bst-min (node-l bst))
      bst))

Note that this version is conceptually simpler than the previous versions, correct and more understandable (at least for me!).

However, we can note the presence of still an annoying point: (node-l bst) is called twice.

To remove the double call, we can note that, assuming that bst is not null, now the recursive call, (bst-min (node-l bst)) gives the correct result both if (node-l bst) is present or not (in fact we have modified the function to treat the nil case). So we can call only once the selector by first trying bst-min on it, and, if it returns nil, by returning bst instead. This is done with the macro or, that returns the first non-null argument by evaluating them from the left:

(defun bst-min (bst)
  (if bst
      (or (bst-min (node-l bst)) bst)
      bst))

which is equivalent to:

(defun bst-min (bst)
  (if bst
      (or (bst-min (node-l bst)) bst)
      nil))   ; <- note this, which is different from the previous definition

The idiomatic way of writing the previous definition in Common Lisp is to use when instead of if, since the former returns nil when the condition is false:

(defun bst-min (bst)
  (when bst
    (or (bst-min (node-l bst)) bst)))

which is finally equivalent (from the point of view of the computation performed) to the Graham's formulation. In fact, by calling macroexpand-1 in SBCL on the two bodies gives exactly the same result:

(IF BST (OR (BST-MIN (NODE-L BST)) BST))

So both definitions can be considered “idiomatic”, with that of Graham a little more “lispy”, given the homogenous use of logical operators.

Nice catch on the bug if there's an empty tree. Good answer! — Edward
– Edward, Commented Jul 9, 2019 at 21:05
The when form is a nice clarification for me at this point, but, onwards! Strangely I think this small function itself tells us a lot about what a BST is... — mwal
– mwal, Commented Jul 11, 2019 at 10:18

Edward · Accepted Answer · 2019-07-09 18:57:03Z

6

The aspect of the code that may cause difficulty to those new to Lisp appears to be the fact that in Common Lisp, nil has two meanings. It's the value of an empty list () and it's also false when used in boolean context. So when we have something like (or '(1 2 3) ()) the first non-NIL list is returned. When we use and it returns the last item if all items are true (that is, all lists are nonempty if we pass in lists). If you keep those facts in mind, you'll see that the first code is both consistent and logical. See also https://stackoverflow.com/questions/23826145/what-is-the-exact-difference-between-null-and-nil-in-common-lisp

I'd probably write the code the first way because it's a more compact way of expressing what you've done with if and also only evaluates node-l once instead of twice. But then, I'd still write car instead of first, so maybe I'm a relic of former days as well. :)

edited Jul 9, 2019 at 18:57

answered Jul 9, 2019 at 12:28

Edward

67.2k4 gold badges120 silver badges284 bronze badges

\$\begingroup\$ I do understand that point --the evaluation rules of the boolean operators as you have explained. I was proposing that even though we all understand how the code works (in the sense of being able to work it out if we examine it carefully), nevertheless it is still hard to process at first glance. Can you process code like that in a single glance? That's my really my point. \$\endgroup\$

mwal
– mwal

2019-07-09 16:08:53 +00:00
Commented Jul 9, 2019 at 16:08
1

\$\begingroup\$ When I see logical operators used with lists, yes, it's pretty clear to me what's happening. It's a Lisp idiom that will come to you after more practice. My Lisp is rusty, but that's one thing that I remembered, if that's of any help to you. \$\endgroup\$

Edward
– Edward

2019-07-09 16:12:07 +00:00
Commented Jul 9, 2019 at 16:12
\$\begingroup\$ I've also updated the answer to hopefully better explain that it's not you personally, but anyone new to Lisp that may find this a bit obtuse at first. Like many language idioms, this is acquired through practice and time. \$\endgroup\$

Edward
– Edward

2019-07-09 18:59:01 +00:00
Commented Jul 9, 2019 at 18:59

Add a comment |

coredump · Accepted Answer · 2019-07-12 08:52:54Z

Can you process code like that in a single glance? That's my really my point.

Yes, and it is in fact a way of expressing code that I miss in other languages, where the equivalent code feels needlessly verbose to me. This is the same for ternary operators when you are accustomized to if-expressions (as opposed to if-statements). And just like ternary operators, you can abuse the feature to produce unreadable code.

The example you give, however, is quite easy to read sequentially:

bst-min is given by an expression that depends on bst.
(and bst ...): in case bst is nil, I can stop reading here because I know the result is nil. Like an early return, this remove burden on your brain by first taking care of corner cases. Otherwise, the result is whatever ... returns. In ... I can keep reading while assuming bst is non-nil. I also know from here that any recursive call may evaluate to nil.
(or (bst-min (node-l bst)) bst))): I would have added a newline before the second bst, but this is still readable; the min is given by a recursive call with the left node of bst; if however that value is nil, use bst instead.

Stack Exchange Network

Find minimum value in a BST: using boolean operators, and using conditionals

3 Answers 3

You must log in to answer this question.

Hot Network Questions

Find minimum value in a BST: using boolean operators, and using conditionals

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions