Consider the following function to traverse a BST

(defun bst-traverse (fn bst)          ; [1]
  (when bst
    (bst-traverse fn (node-l bst))
    (funcall fn (node-elt bst))       ; [2]
    (bst-traverse fn (node-r bst))))

;; [1] This is a higher order function - recieves a function which it calls on each node.
;; [2] The traverse which makes sense on a bst is the in-order traverse
;;     (i.e. left first, then node, then right, which this is.)

What are some nice uses of this function?

1) Cause a side effect at each node

(bst-traverse #'princ bst)

2) Cons each elt to a global var (also a side effect)

The idea here is this is a good way to get the BST els in descending order.

(defparameter *result* nil)
(bst-traverse (lambda (obj)
               (setf *result* (cons obj *result*)))

This leads me to wondering...

Is this higher order function any use at all without relying on a side-effect?

It seems maybe not. Why? - because it doesn't return anything always returns nil.

So, could we or should we make it return something to solve this 'problem'?

The general question I'm seeking to explore here is the purity or non-purity of higher order functions in practical use cases (and hence, how to use them well).

Any discussion/contributions appreciated.

For the record, I started off with this

(defun in-order-traverse (bst)
  (when bst
    (in-order-traverse (node-l bst))
    (format t "~A" (node-elt bst))
    (in-order-traverse (node-r bst))))

Then, when I wanted to get the BST els in reverse order, realised how completely un-reusable that function is in comparison to bst-traverse above. So, I'd like to get a better understanding of what the real flexibility of bst-traverse actually is and how to use it...

[I've realised - the function passed could return something - but how would the higher order function pick which invocation of the lambda to return the return value of if any?!]


Wondering if this would be along the right lines at all

(defun bst-accumulate (fn bst)
  (let (result)
    (when bst
      (bst-accumulate fn (node-l bst))
      (cons (funcall fn (node-elt bst)) result)
      (bst-accumulate fn (node-r bst)))

Update 2

bst-accumulate above is wrong. This is not the first time I've fallen into the trap of thinking that consing was setting state - actually the return value of the expression above which does the cons is just lost... To achieve what I wanted to achieve above, I must firstly wrap the cons in a setf so that result is actually modified. Plus there's a second problem; since bst-accumulate is recursive, it will end up redefining result on every call. To fix that, we need a helper function so that we keep the lexical var result outside of the recursive function, thusly: (this time I tested it before posting :)

(defun bst-accumulate (fn bst)
  (let (result)
    (labels ((bst-acc (fn2 bst2)
                      (when bst2
                        (bst-acc fn2 (node-l bst2))
                        (setf result (cons (funcall fn2 (node-elt bst2)) result))
                        (bst-acc fn2 (node-r bst2)))))
            (bst-acc fn bst)
  • \$\begingroup\$ "I must return cons for it to be useful". I'm reciting this over and over as I make a cup of tea :) \$\endgroup\$ – mwal Jul 29 '19 at 12:47
  • 2
    \$\begingroup\$ What does this traversal function have to do with binary search trees? It seems to treat it naïvely as just any old binary tree. \$\endgroup\$ – 200_success Jul 29 '19 at 14:46
  • 1
    \$\begingroup\$ @200_success That's a fair comment. Except for the fact that it is an in order traverse, there's nothing specific to binary search trees, as you point out. I could provide the entire code for the bst, but it was only this method I wanted to ask about. \$\endgroup\$ – mwal Jul 29 '19 at 14:52
  • \$\begingroup\$ Please see What to do when someone answers. I have rolled back Rev 9 → 8 \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Jul 31 '19 at 15:46

Is this higher order function any use at all without relying on a side-effect?

The answer to this question is obviously no, since the function returns always nil.

The general question I'm seeking to explore here is the purity or non-purity of higher order functions in practical use cases (and hence, how to use them well).

I'm not sure to understand what you are looking for, but if you want an example of recursive higher order function on binary trees that returns something (without performing side effects), consider the following one, in which the function gets another parameter that “combine” the results of the visit (assuming that an empty tree is represented with nil and that the function should return nil when an empty tree is passed to it):

(defun inorder-traverse (combine fn bin-tree)
  "in order traversal of a binary tree"
  (when bin-tree
    (funcall combine
             (inorder-traverse combine fn (node-l bin-tree))
             (funcall fn (node-elt bin-tree))
             (inorder-traverse combine fn (node-r bin-tree)))))

for instance:

(defun flatten (bin-tree)
  (inorder-traverse (lambda (x y z) (append x (list y) z))

returns the list of the leaves of a binary tree in order from left to right; if the tree is a BST, the list is sorted;

(defun reverse-flatten (bin-tree)
  (inorder-traverse (lambda (x y z) (append z (list y) x))

like the previous one, only in reverse order;

(defun map-tree (fn bin-tree)
  (inorder-traverse (lambda (left el right) (mk-tree el left right))

returns a new tree, with the same structure of the input one, and with the elements transformed by the function fn;

(defun my-copy-tree (bin-tree)
  (inorder-traverse (lambda (left el right) (mk-tree el left right))

makes a copy of a binary tree;

(defun reverse-tree (bin-tree)
  (inorder-traverse (lambda (left el right) (mk-tree el right left))

a symmetrical copy of a binary tree;


| improve this answer | |
  • \$\begingroup\$ Thank you Renzo, this is very mind expanding & provides much material for exploration. I knew you would come charging in to the rescue! :) \$\endgroup\$ – mwal Jul 29 '19 at 16:58
  • \$\begingroup\$ The map-tree function (and its relations) are amazing! :) So, may I attempt to abstract a principle? - we see here that by adding additional function parameters to a higher order function, one tends to make that higher order function even more flexible. The reason for that is that if one simply wants default behaviour for one of the function parameters, one just needs to pass in an identity function or its equivalent. In the case of the combine function, the "equivalent of the identity function" is simply to append its three params in the same order they are given. Anything to add? \$\endgroup\$ – mwal Jul 30 '19 at 14:01
  • \$\begingroup\$ @mwal, I substantially agree with your comment. You can even reproduce your first function (traversal only for side effects) by passing as combinethe function (constantly nil). \$\endgroup\$ – Renzo Jul 31 '19 at 13:27
  • \$\begingroup\$ Thanks. I note also that (constantly bin-tree) is an option, to always return the original tree, following the style of mapc, which may make a side-effects-only function more useful as it allows chaining. Hence, I've added the new function tap-tree (not sure what an appropriate naming for a function like that would be in cl?) as an additional answer below. \$\endgroup\$ – mwal Jul 31 '19 at 16:08

the typical operations like mapcar or reduce - which return a value - could also be provided in similar fashion for trees.

Note also that your function is not tail recursive and may cause a stack overflow...

| improve this answer | |
  • \$\begingroup\$ wow - I wonder what some of the reduce operations on trees look like. It would seem there may be whole families of them :) \$\endgroup\$ – mwal Jul 30 '19 at 14:04
  • \$\begingroup\$ Is any tree recursion necessarily not tail recursive? How does one refactor tree recursion to be tail recursive? (& would the compiler ever intervene to make it so? - I'm just cautiously starting to read about declare/declaim optimize). many thanks as always. \$\endgroup\$ – mwal Aug 1 '19 at 10:44

Following discussion in the comments on the accepted answer above, here is a function which utilises inorder-traverse given there to neatly allow side-effect-only in-order traversal of any binary tree, and return the original tree. Returning the original tree allows chaining, and was inspired by the function mapc.

I'm not sure whether calling this "tap", is the best way to name it - comments welcome.

(defun tap-tree (mapfn bin-tree)
  (inorder-traverse (constantly bin-tree)  
| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.