BST traverse as higher order function 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*)))
             nums)


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?!]



Update 

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)))
  result))


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)
            result)))
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))
                    #'identity
                    bin-tree))


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))
                    #'identity
                    bin-tree))


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))
                    fn
                    bin-tree))


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))
                     #'identity
                     bin-tree))


makes a copy of a binary tree;

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


a symmetrical copy of a binary tree;

etc.