2
\$\begingroup\$

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)))
\$\endgroup\$
4
  • \$\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\$ Commented Jul 29, 2019 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\$ Commented Jul 29, 2019 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\$ Commented Jul 29, 2019 at 14:52
  • \$\begingroup\$ Please see What to do when someone answers. I have rolled back Rev 9 → 8 \$\endgroup\$ Commented Jul 31, 2019 at 15:46

3 Answers 3

Reset to default
4
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\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\$ Commented Jul 29, 2019 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\$ Commented Jul 30, 2019 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\$ Commented Jul 31, 2019 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\$ Commented Jul 31, 2019 at 16:08
1
\$\begingroup\$

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...

\$\endgroup\$
2
  • \$\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\$ Commented Jul 30, 2019 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\$ Commented Aug 1, 2019 at 10:44
0
\$\begingroup\$

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)  
                    mapfn
                    bin-tree))
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.