Marshall, BQN is really interesting! I'll definitely study it (and maybe
steal 1-2 things along the way ;-).
Your function makes for a ~25% faster computation on my preliminary
testing, albeit at the price of ~3x the space. I'll have to think more
about it to understand the complexity of your expression, but it seems like
a nice improvement!
Henry, if I understood your last correctly your modification is almost
identical (within 5% both time & space -wise) . The expression is simpler
though, which is nice.
Cheers!
Raoul
On Sat, May 29, 2021 at 6:10 PM Henry Rich <henryhr...@gmail.com> wrote:
> 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 <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
>
>
> --
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
