Good algorithm!
Consider
'p g' =. |: 0 2 #: g2 =. ...
for the first 2 lines. (0,2^n) #: y avoids the divide and remainder.
Henry Rich
On 5/29/2021 11:50 AM, Marshall Lochbaum wrote:
It's possible to convert depths to parent indices without boxes, by
sorting a depth list with twice the input size. The idea is to list each
depth twice, with the first instance representing it as a child entry,
and the second, which is increased by one, representing it as a parent
entry. After sorting, the parents and children for each depth are
grouped together, so a child's parent is the most recent parent in the
sorted list.
The format of the grade result isn't particularly convenient. It has to
be split with division and remainder by 2, where the quotient is the
index in y and the remainder indicates if it is used as a parent.
Besides that, there's a pattern >./\p*i.#p to get the index of the most
recent 1 in p, and the rest is straightforward.
pv_flat =: 3 : 0
p =. 2| g2 =. /: ,y+/i.2
g =. <.g2%2
g /:~&:((-.p)&#) (>./\p*i.#p){g
)
When I built an array-based compiler for BQN I found that it tends to be
simpler not to convert to trees explicitly, and instead to order by
parenthesis (or other bracket) depth, which splits things into flat
expressions where a closed parenthesis denotes a subexpression result.
The paired parentheses serve the same purpose that the parent-child
doubling does here, and the natural depth computation (+/\-/'()'=/s)
automatically places open parentheses one higher than closed ones. Some
further discussion at
https://mlochbaum.github.io/BQN/implementation/codfns.html .
Marshall
On Wed, May 26, 2021 at 12:44:13AM +0200, Raoul Schorer 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 <[email protected]> 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 <[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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
--
This email has been checked for viruses by AVG.
https://www.avg.com
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
