It is indeed very much worthy of note! I am currently making a little
library of all the tree manipulation idioms in Hsu's thesis, with the final
goal of using them in an interpreter. It is therefore very useful to have
the inverse of those transformations to reverse the encoded results into
more usual J language terms for trees (i.e. nested boxes), if only to
visualize the result and also make it available to the L. L: S: family of
primitives.
As for the depth -> parent vector transform, an almost literal translation
of the thesis code is:
pv =: monad define
p =.i.@# y
i =. (</. i.@#) y
j =. ; 2 (0&{:: <@(<:@I.{[) 1&{::)\ i
j (;}.i) } p
)
which seems almost equivalent to your solution regarding time complexity,
although yours seems ~25% better spacewise on preliminary tests. Probably
because it avoids some intermediate result copying?
I am sure Dr. Hsu would be extremely interested if someone came up with
more efficient solutions for all those transforms, as they are the
foundation of his Co-dfns compiler and are therefore used pervasively.
Cheers,
Raoul
On Tue, May 25, 2021 at 11:16 PM Raul Miller <rauldmil...@gmail.com> wrote:
> 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 <rauldmil...@gmail.com> wrote:
> >
> > Oops
> >
> > dv=: 0, 1+ [:; [:dv&.> 1}.]
> >
> >
> > Thanks,
> >
> >
> > --
> >
> > Raul
> >
> >
> > On Mon, May 24, 2021 at 8:40 AM Raoul Schorer <raoul.scho...@gmail.com>
> 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 <rauldmil...@gmail.com>
> 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 <
> >> > 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
> >> >
> >> ----------------------------------------------------------------------
> >> 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
