I think the better space use for the parent vector calculation would
be because Hsu computes a full outer product when calculating 'i'
while my approach skips that representation. I am doing something
similar, but I don't need to store an outer product. (So I have O(n)
space and O(n^2) time where n is the length of the depth vector. Hsu
has O(n^2) space and O(n^2) time.)
I hope this helps,
--
Raul
On Tue, May 25, 2021 at 6:44 PM Raoul Schorer <raoul.scho...@gmail.com> wrote:
>
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
