From: Andy Latto <andy.latto@pobox.com> Date: 7/11/20, 1:24 AM

On Mon, Jun 29, 2020 at 6:01 PM Steve Witham <sw@tiac.net> wrote:

...

...In contrast I find tree-traversals (usually implicit) one of the most awkward tasks in programming.

This maybe belongs on programming-fun rather than math-fun, but I don't see the awkwardness at all.

The reason I posted here was the kids-can-count-in-decimal angle.

;;; GIven a function that, when called on a node of a tree, returns the list of child nodes, apply a given processing function to all nodes ;;; of the tree in depth-first order.

(defun depth-first-process (root-node children-function processing-function)      (map #'(lambda (child) (depth-first-process child children-function processing-function))               (funcall children-function root-node))      (funcall processing-function root-node))

Touche... def depth_first(root, children_of, process):     """     Given root-- a node,         children_of-- a generator that yields the sub-nodes of a node,         process-- a function to apply to every node,     Call process on every node, bottom-up, and return the last result.     """     for child in children_of(node):         depth_first(child, children_of, process)     return process(root) The case I was working on was like     for a in pick_As():        for b in pick_Bs(a):            for c in pick_Cs(a, b):                for d in pick_Ds(a, b, c):                    for e in pick_Es(a, b, c, d):                        run_the_test(a, b, c, d, e) or is it def pick_As(): for a in ...: pick_Bs(a) def pick_Bs(a): for b in ...: if constraintB(a, b): pick_Cs(a, b) def pick_Cs(a, b): for c in ...: if constraintC(a, b, c): pick_Ds(a, b, c) ... The digit-counter idea did get me through reasonably neatly.

Where is the awkwardness and the bookkeeping in this two-line function?

Well it doesn't start in your function, but as sensible-seeming constraints in a problem.  The awkwardness is when I find myself clumsily hogtied by perfectly good christmas light strings 3/4 of the way down a perfectly good tree. The digit counter idea gave me a static structure I could fit the constraints onto, with a main loop to zip up and down them.  --Steve