It's perhaps worth noting that you can convert a depth vector to a
parent vector (except for the root element, which has no parent --
though it's convenient to represent the root element as being its own
parent) using (i: <:@{:)\
For example:
ast=:t;(t;t);(t;(t;t);t);<(t;(t;t;t);(t;t;t);t=.'.')
dv=: 0, 1+ [:; [:dv&.> 1}.]
0,}.(i: <:@{:)\dv ast
0 0 1 0 3 4 3 0 7 8 8 7 11 11 7
You can convert a parent vector back to a depth vector using:
pv2dv=:{{
(0,1+}.)@(y&{)^:_ y
}}
There might be more efficient approaches?
Thanks,
--
Raul
On Mon, May 24, 2021 at 8:57 AM Raul Miller <[email protected]> wrote:
>
> Oops
>
> dv=: 0, 1+ [:; [:dv&.> 1}.]
>
>
> Thanks,
>
>
> --
>
> Raul
>
>
> On Mon, May 24, 2021 at 8:40 AM Raoul Schorer <[email protected]> wrote:
>>
>> Hi and thanks to all for helpting!
>>
>> Raul, I think you forgot to copy your working verb in your last.
>> Ethejiesa, good catch and great insight! Your verb yields a domain error on
>> J902, though.
>>
>> Cheers,
>> Raoul
>>
>> On Mon, May 24, 2021 at 2:35 PM Raul Miller <[email protected]> wrote:
>>
>> > 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 <
>> > [email protected]> wrote:
>> >
>> > > Raoul Schorer <[email protected]> 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
>> >
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
