Atom Walk

The problem originally appeared on K listbox.

Problem

You're given a list of arbitrary complexity (no dictionaries involved):

  d:(10 20;(30 40 50;60 70);80)

Write a function dfw which computes the depth-first walk through d:

  dfw d
(0 1;(2 3 4;5 6);7)

The d.f.w. has the same structure as d: atom for atom, vector for vector, list for list, &c.

Solution

The first argument is the state, initialized to -1:

  dfw[-1;d]

In the course of execution, the state will grow to have the structure of d.

If d is an atom, dfw returns 1 + the maximum value reached in the state. Since the state is a list, and grows down and to the right, the maximum value is either 1+|/,//state or, more efficiently, 1+(*|:)/|state.

In (*|:)/| we repeatedly apply the monad 'last' to the reverse of the state until the result is the same twice-in-a-row. this is how we reach the bottom-right atomic value.

If d is a vector, return (1+*:/|state)+!#d.

If d is a list, then, since dfw is a dyadic function, we scan across d:

  1_ state _f\d

We drop the first item of the result, which is the initial state.

The function is therefore a conditional:

  dfw:{[i;d]:[@d;1+(*|:)/i;0>4:d;(1+(*|:)/i)+!#d;1_ i _f\d]}

  dfw[-1;d]
(0 1
 (2 3
  4 5 6)
 7)

If d is a list of rectangular arrays we can do without the recursion, using the shapes:

  d:(0;!4;2 3#!6)
  *:'1_(;!#,//d){(y#x 1;(*/y)_ x 1)}\^:'d

Note that we drop the first item of the scan. Also, note that the scan produces pairs, where the first of each pair is the desired result, and the second is the state, the iota vector undergoing successive drops.

Where d is a list of vectors, things are simpler still

  d:(!3;!4;!2)
  *:'1_(;!#,/d){(0,y)_ x 1}\#:'d

In each case we need to track the state. The hard part is seeing how scan and recursion (and in other problems, other constructs) can take the place of globals.

Paths

  lp:{:[@x;,();,/(!#x),/:'_f'x]}

returns the paths to all the atoms in a list. A similar function gets all the symbolic paths of a dictionary:

  dp:{[d;p]:[5=4:e:d . p;,/_f[d]'p,/:!e;,p]}

Combining the cases:

  paths:{:[(@x)&~5=t:4:x;,();,/ :[5=t;!x;!#x],/:'_f'x[]]}		/n.b. ,/ :

Now, a function which walks the atoms in any structure, list or dictionary, is::

  walk:{./[x;i;:;!#i:paths x]}

  a.b:7 7
  a.c.d:(8 8;9 9 9)
  a.c.e:4

  walk a
.((`b
   0 1
   )
  (`c
   .((`d
      (2 3
       4 5 6)
      )
     (`e;7;))
   ))