rslt ← ival (accm ##.trav subs) tree    ⍝ Generic depth-first tree traversal.
rslt ← ival (accm ##.ravt subs) tree    ⍝ trav: parent-first, ravt: parent last.

[trav] and [ravt] traverse a [tree], applying left operand accumulating function
[accm] between the current value of the accumulator  (initial value [ival])  and
each node. Right operand function [subs] is required to  return a (possibly emp-
ty) vector of subtrees for each node.

[trav] and [ravt] differ only in the order in which they visit the nodes of  the
subject [tree].

[trav] visits (applies [accm] to) the parent node before visiting any children.
                                                  ¯¯¯¯¯¯
[ravt] visits the parent node after visiting any children.
                              ¯¯¯¯¯
Mnemonic: given this tree:

      t         trav visits: t r a v
    ┌─┼─┐       ravt visits: r a v t
    r a v

Both left and right operand functions are ambi-valent, with the current accumul-
ator value as left argument and current node as right argument.  To  borrow  the
type notation developed in →foldl←:

    trav ravt :: ⍺ (⍺ ∇ ⍵ → ⍺) ∇∇ (⍺ ∇ ⍵ → [⍵]) ⍵ → ⍺   ⍝ type of trav & ravt

Right operand function [subs] "projects" a tree structure onto its  right  argu-
ment. [tree] could be concrete, as with a collection of nested  namespaces,  but
could equally be a _notional_ tree, which is not instantiated in the workspace.

In particular, successive arguments, produced during the evaluation  of  a  pure
recursive function, may be viewed as a tree. This means that, theoretically, any
relationship that can be expressed as a pure recursive function,  may  be  coded
using [trav] or [ravt]: the ⍵th Fibonacci  number; arithmetic functions, such as
GCD and Ackermann; the solution(s) of a Sudoku puzzle; the best next move  in  a
game of chess; and so on.

An alternative interpretation is that right operand [subs] replaces the task  at
hand with 0 (base-case) or more sub-tasks and left  operand  [accm]  accumulates
the results of these sub-tasks to produce the answer.

For example, the ⍵th Fibonacci number may be expressed recursively as:

    ⍵, if ⍵ is 0 or 1
    the sum of the previous two Fibonacci numbers, otherwise.

Leading to this [trav] coding:

    fib ← {⍺+⍵×⍵∊0 1} trav {(⍵-2 1)~-2 1}   ⍝ ⍵th fibonacci number

    0 fib¨ 0 to 10                          ⍝ fibonacci sequence.
0 1 1 2 3 5 8 13 21 34 55

This trace operator shows  what's happening by displaying accumulator ⍺ and node
value ⍵ as a node is visited:

    tc←{                    ⍝ Indented trace of node visit.
        depth←¯2+⍴⎕SI       ⍝ depth of recursion
        tab←∊depth⍴⊂'·   '  ⍝ indentation vector
        ⎕←tab,⍕⍺ ⍵          ⍝ display of ⍺ and ⍵
        ⍺ ⍺⍺ ⍵              ⍝ node visit.
    }

    0 {⍺+⍵×⍵∊0 1}tc trav {(⍵-2 1)~-2 1} 5       ⍝ fib 5
0 5
·   0 3
·   ·   0 1
·   ·   ·   1 0
·   ·   1 2
·   ·   ·   1 0
·   ·   ·   1 1
·   ·   ·   ·   2 0
·   2 4
·   ·   2 2
·   ·   ·   2 0
·   ·   ·   2 1
·   ·   ·   ·   3 0
·   ·   3 3
·   ·   ·   3 1
·   ·   ·   ·   4 0
·   ·   ·   4 2
·   ·   ·   ·   4 0
·   ·   ·   ·   4 1
·   ·   ·   ·   ·   5 0
5

(muse:
·
·   The above naïve coding of the ⍵th Fibonacci is  very  inefficient.  Operator
·   →memo← effectively transforms the above _tree_ into the much smaller _graph_
·   which, by removing duplication, leads  to  an  evaulation  with  many  fewer
·   steps:
·
·   ┌─→─┐─→─┐─→─┐─→─┐─→─┐
·   5   4   3   2   1   0
·   └─→─┼─→─┤   │   │   │
·       └─→─┼─→─┤   │   │
·           └─→─┼─→─┤   │
·               └─→─┼─→─┤
·                   └─→─┘
)

Sometimes, there is only ever 1 (or 0 in the base case) sub-task.  In such cases
we have a "unary" tree (AKA "List") as for Euclid's algorithm for Greatest Comm-
on Divisor →gcd←:

    ⍵, if ⍺ is 0
    gcd of ⍵ and |⍵-⍺, otherwise

leading to this [trav] coding:

    gcd ← ⊢ trav {|⍵-⍺~0}           ⍝ Euclid's GCD.

    35 gcd 55                       ⍝ cf: 15∨35
5
    35 ⊢tc trav {|⍵-⍺~0} 55         ⍝ traced evaluation
35 55
·   55 20
·   ·   20 35
·   ·   ·   35 15
·   ·   ·   ·   15 20
·   ·   ·   ·   ·   20 5
·   ·   ·   ·   ·   ·   5 15
·   ·   ·   ·   ·   ·   ·   15 10
·   ·   ·   ·   ·   ·   ·   ·   10 5
·   ·   ·   ·   ·   ·   ·   ·   ·   5 5
·   ·   ·   ·   ·   ·   ·   ·   ·   ·   5 0
·   ·   ·   ·   ·   ·   ·   ·   ·   ·   ·   0 5
5

.. and this more efficient version, which uses residue in place of repeated sub-
traction:

    35 |tc trav {⍺~0} 55            ⍝ traced evaluation
35 55
·   20 35
·   ·   15 20
·   ·   ·   5 15
·   ·   ·   ·   0 5
5

(muse:
·
·   Perhaps, in cases where there can be more than one  sub-task at each node
·   (Fibonacci, chess problems, ...), an operator like [trav] could help with
·   organising their parallel evaluation, using multiple processors.
)

Technical notes:

The coding of the body of trav is surprisingly simple:

    ⊃∇⍨/⌽(⊂⍺ ⍺⍺ ⍵),⍺ ⍵⍵ ⍵
     │└┬┘  └─┬──┘  └─┬──┘
     │ │     │       └──── (possibly empty) vector of sub-trees.
     │ │     └──────────── new value of accumulator.
     │ └────────────────── left-to-right reduction →foldl←
     └──────────────────── recursive call on (⍺⍺ trav ⍵⍵).

At first sight, the code appears to be missing a test to back out of the recurs-
ion after a leaf-node has been visited.  In fact, this occurs automatically:  if
the vector of sub-trees (⍺ ⍵⍵ ⍵) is empty, the  sub-expression: (⊂⍺ ⍺⍺ ⍵),⍺ ⍵⍵ ⍵
is a 1-item vector and so the reduction ∇⍨/ passes it along  as  result  without
applying its operand function and thus avoiding the recursive call on trav.

[ravt] is essentially the same but with the  accumulation (... ⍺⍺ ⍵)  following,
rather than preceding, the recursive call:

        (⊃∇⍨/⌽(⊂⍺),⍺ ⍵⍵ ⍵)⍺⍺ ⍵      ⍝ visit nodes _after_ subnodes.

It is comforting to have the accumulator as left argument and the  subject  tree
on the right. Swapping (commuting) these arguments would give a slightly simpler
coding of the operator:

    vart←{                          ⍝ commuted version of trav,
        ⊃∇/(⍵ ⍵⍵ ⍺),⊂⍺ ⍺⍺ ⍵         ⍝ ... produces simpler coding.
    }

at the expense of a correspondingly less intuitive coding for the [accm] operand
function:

    accm ← {((0=≡⍺)/⍺),⍵}           ⍝ accumulating simple scalars
    subs ← {(0≠≡⍵)/⍵}               ⍝ non-atoms for processing
    list ← accm vart subs           ⍝ accumulation of atoms.

    'ab'('cd' 'e') list ''
abcde

(muse:
·
·   Right operand [subs] determines how (for example) a nested array or a  coll-
·   ection of namespaces, constitute a tree. Given such an association, left op-
·   erand [accm] defines a _property_ of the resulting  tree, such as  its  size
·   (number of nodes or leaves) or the enlisted vector of its leaves.
·
·   "Right Operand Currying", where an operator's right operand may be bound in-
·   dependently of its left operand, is useful in this situation. For example:
·
·       atree ← trav {(0≠≡⍵)/⍵}         ⍝ vector as tree.      Operand currying.
·                                       ⍝                      ¯¯¯¯¯¯¯
·       acount ← {⍺+1} atree            ⍝ property: node count.
·       aleaves ← {⍺,(0=≡⍵)/,⍵} atree   ⍝ property: leaf list.
·
·   By analogy, "Left _Argument_ Currying" would allow us to bind an initial ac-
·   cumulator value to produce a monadic derived function:
·
·       asize ← 0 acount                ⍝ array-as-tree size. Argument currying.
·       alist ← ⍬ aleaves               ⍝ enlist              ¯¯¯¯¯¯¯¯
·
·   Of course, left arguments may already be bound using the slightly less beau-
·   tiful composition:  asize ← 0∘acount  ⋄  alist ← ⍬∘aleaves
·
·   Either way:
·
·       asize (1 2)(3 4)                ⍝ tree size (see examples below).
·   7
·       alist 'ab'('cd' 'e')            ⍝ enlist.
·   abcde
)

Non-termination:

If the "tree" turns out to have cycles and is therefore a  more  general  graph-
structure, as may be the case with collections of  namespace  references,  it is
necessary to detect this condition to prevent further node traversal. Otherwise,
the traversal will fail to terminate. See example below.

Breadth-first search
--------------------
The equivalent coding for a breadth-first search, which visits all nodes at each
level _before_ proceeding to any of their subnodes, is  slightly  more  complex.
See also →search←.

    bftrav←{⎕ML←1           ⍝ Generic breadth-first tree traversal.
        ⍺ ⍺⍺{
            0=⍴⍵:⍺
            (⍺ ⍺⍺⊃⍵)∇(1↓⍵),(⍺ ⍵⍵⊃⍵)
        }⍵⍵,⊂⍵
    }

    subs ← {⍵.(1↓⍎¨'0',↓⎕nl 9)}             ⍝ sub-namespaces for space ⍵.

    't.r.rr' 't.a.aa' 't.v.vv' ⎕ns¨ ⊂''     ⍝ create tree.

    tree t                                  ⍝ depth-2 tree.
#.t
·   a
·   ·   aa
·   r
·   ·   rr
·   v
·   ·   vv

    ⍬ ,bftrav subs t                        ⍝ nodes in breadth-first order.
#.t #.t.a #.t.r #.t.v #.t.a.aa #.t.r.rr #.t.v.vv

Examples:

    subs ← {⍵.(1↓⍎¨'#',↓⎕nl 9)}     ⍝ sub-namespaces for space ⍵.

    accm ← {⍺+1}                    ⍝ counting nodes.
    0 accm trav subs #              ⍝ count of spaces.
3
    accm ← ,                        ⍝ accumulating into a vector.
    ⍬ accm trav subs #              ⍝ vector of spaces. C.f. →refs←
 #  #.notes  #.scripts

    ⍬ accm ravt subs #              ⍝ ravt visits node _after_ subnodes.
 #.notes  #.scripts  #

    usp ← {⍵.(1↓⍎¨'#',↓⎕nl 9)~⍺}    ⍝ unique sub-spaces, ignoring cycles.

    'xy'⎕ns¨⊂''                     ⍝ spaces x and y.
    (x y).(x y)←⊂x y                ⍝ create some cycles

    ⍬ ∪ trav usp x                  ⍝ vector of spaces in graph. C.f. →refs←
 #.x  #.y

⍝ A (nested) array may be                           ┌─┴─┐
⍝ considered as a tree with         (1 2)(3 4) ←→  ┌┴┐ ┌┴┐
⍝ depth-0 items as leaves:                         1 2 3 4

    subs ← {(0≠≡⍵)/,⍵}              ⍝ sub-items of array ⍵.

    accm ← {⍺+1}                    ⍝ counting nodes.
    0 accm trav subs (1 2)(3 4)     ⍝ node-count
7
    accm ← {⍺,(0=≡⍵)/,⍵}            ⍝ accumulating simple scalars
    ⍬ accm trav subs 'ab'('cd' 'e') ⍝ enlist
abcde

⍝ N-queens problem:

    accm ← {⍺,(⍺⍺=⍴⍵)/⊂⍵}           ⍝ accumulated leaves.

    subs←{⎕io←1                     ⍝ possible placements          \|/\  | \/| /
        dd←⌽⍳⍴⍵                     ⍝ diagonal                      ⍟  \ | /\|/
        ak←(⍵-dd),⍵,(⍵+dd)          ⍝ attacked cols in next row :       \|/  ⍟
        ⍵∘,¨(⍳⍺⍺)~ak                ⍝ subnodes                           ⍟
    }

    ⍬(4 accm)trav(4 subs)⍬          ⍝ 4-queens solutions vector.
 2 4 1 3  3 1 4 2

⍝ A similar expression for N-Queens using depth-first search is developed
⍝ in YouTube video:  https://www.youtube.com/watch?v=DsZdfnlh_d0

See also: refs acc foldl osc gcd search queens

Back to: contents

Back to: Workspaces