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
