Consider the following function to traverse a BST
(defun bst-traverse (fn bst) ;  (when bst (bst-traverse fn (node-l bst)) (funcall fn (node-elt bst)) ;  (bst-traverse fn (node-r bst)))) ;;  This is a higher order function - recieves a function which it calls on each node. ;;  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
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))) result))
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)))