Thank you, that makes sense.
And, I also see that I built a faulty value for ast.
Here's a fixed ast and a working depth vector verb:
t=:'.'
ast=:t;(t;t);(t;(t;t);t);<(t;(t;t;t);(t;t;t);t)
ast
+-+-----+-----------+---------------------+
|.|+-+-+|+-+-----+-+|+-+-------+-------+-+|
| ||.|.|||.|+-+-+|.|||.|+-+-+-+|+-+-+-+|.||
| |+-+-+|| ||.|.|| ||| ||.|.|.|||.|.|.|| ||
| | || |+-+-+| ||| |+-+-+-+|+-+-+-+| ||
| | |+-+-----+-+|+-+-------+-------+-+|
+-+-----+-----------+---------------------+
dv ast
0 1 2 1 2 3 2 1 2 3 3 2 3 3 2
(Apologies for any wonky formatting -- I am on a phone right now.)
Thanks,
--
Raul
On Mon, May 24, 2021 at 2:47 AM ethiejiesa via Programming <
programm...@jsoftware.com> wrote:
> Raoul Schorer <raoul.scho...@gmail.com> wrote:
> > Dear all,
> >
> > I am struggling with the translation of the following APL dyad to J:
> >
> > ∊ 0 {(⊢,(⍺+1)∇⊣)/⌽⍺,1↓⍵} y
> >
> > which is the expression to yield a depth vector from a tree in record
> > format (drawn from Dr. Hsu's thesis). Demo:
>
> Oh cool! I have been (very sparingly) messing about with Hsu's tree
> representation. For purely selfish reasons, I haven't looked at the thesis,
> trying to figure out the representation myself. However, I have only got
> so far
> as figuring out an algorithm for non-recursively generating random depth
> vectors.
>
> > t ← '∘'
> > ast ← t (t t) (t (t t) t) (t (t t t) (t t t) t)
> > ∊ 0 {(⊢,(⍺+1)∇⊣)/⌽⍺,1↓⍵} ast
> > 0 1 2 1 2 3 2 1 2 3 3 2 3 3 2
> >
> > In particular, I don't understand the control flow and termination
> > condition for the recursion. Dr. Hsu says that this uses tree reduction
> > with no base case.
>
> Anyway, my APL is pretty sketchy, but it looks like the ast representation
> there is something like this:
>
> 1) First element of list is node content,
> 2) Following nodes are child subtrees.
>
> So the algorithm should be conceptually simple. Replace the head atom with
> the
> current depth, bump current depth, and then recurse over the child
> subtrees. I
> believe that the "base case" is taken care of by (/), since at the leaves
> it
> should be operating on atoms.
>
> > dv =. {{ (];(>:x) dv [)/\ |.x;}.y }}
> >
> > results in an infinite loop. What am I missing? Is there some kind of
> > implicit termination condition in the ∇ primitive?
>
> The main problem is the (x;}.y) part. The recursion depends on the fact
> that
> (⍺,1↓⍵) equals ⍺ at the leaves, but (x;}.<'anything') is the same thing as
> (x;a:). Thus when y is a leaf, (x;}.y) turns into a tree!
>
> We can brute for a fix by replacing the (;) in (x;}.y) with
> (;`(<@[)@.(0=#@])):
>
> t=: '.'
> ast=: t;(t;t);(t;(t;t);t);<(t;(t;t;t);(t;t;t);t)
> f=: {{(],(>:x) f >@[)/ |. x ;`(<@[)@.(0=#@]) }.y}}
> 0 ;@f ast
> 0 1 2 1 2 3 2 1 2 3 3 2 3 3 2
>
> Hope that's somewhat comprehensible.
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
