# 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;))
))