[math-fun] Counting vs. cross-products vs. tree traversal
Counting in decimal is analogous to walking a tree. A tree of unbounded depth for that matter. "Carrying" is like popping the stack and going to another [[great...] grand] parent node. The higher digits are further *up* the tree and it just keeps going up... I'm getting hypoxia just thinking about it. Grade-school kids (me included) eventually learn to count without a lot of thinking. 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. 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
It used to be call "back-tracking", which I also liked to think of as generalised counting when I rediscovered it. A lot of elementary combinatorial algorithms, eg. generating permutations, combinations, etc. are usefully regarded in this way --- especially when having to be recoded in yet another language on the umpteenth occasion ... WFL On 6/29/20, Steve Witham <sw@tiac.net> wrote:
Counting in decimal is analogous to walking a tree. A tree of unbounded depth for that matter. "Carrying" is like popping the stack and going to another [[great...] grand] parent node. The higher digits are further *up* the tree and it just keeps going up... I'm getting hypoxia just thinking about it.
Grade-school kids (me included) eventually learn to count without a lot of thinking.
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.
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
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
participants (3)
-
Andy Latto -
Fred Lunnon -
Steve Witham