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. I mean depth-first. Even when the number of levels is fixed, even when it's shallow enough to use recursion in a language with a limited stack. The bookkeeping, the program structure are just awkward.
This maybe belongs on programming-fun rather than math-fun, but I don't see the awkwardness at all. ;;; 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)) Or if you prefer the syntax of a more recent language, in typescript this would be function depthFirstProcess(rootNode:Node, processingFunction: ((Node) => any)):void { rootNode.children.map((child: Node) => depthFirstProcess(child, processingFunction); processingFunction(rootNode); } Where is the awkwardness and the bookkeeping in this two-line function? Andy Latto andy.latto@pobox.com
Even in Prolog (where depth-first tree search is everything) it might make a program a bit scattered-looking. Well let's try. (I'm making up a dialect of Prolog here. "(car : cdr)" shall mean cons.)
(Decimal (d)) if (Digit d). (Digit d) if (Element d (0 1 2 3 4 5 6 7 8 9)). (Decimal (d : n)) if (NZDigit d) and (ZDecimal n). (NZDigit d) if (Element d (1 2 3 4 5 6 7 8 9)). (ZDecimal (d)) if (Digit d). (ZDecimal (d : n)) if (Digit d) and (ZDecimal n).
But all that aside, the digit-counting analogy sounds like a nice way to organize a tree search or a very-nested loop. Have an array of digit positions, and at each position a sub-array of possibilities. Then have a parallel array of indexes into those arrays. So, each time through the loop you increment the bottom digit with carry. Easy peazy, heh.
(I'm currently writing a test for a module with a big cross-product of test cases.)
--Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com