This is approximately the ideal way of generating the tree, as long as
all paths which are present in the tree are listed.
(If leaves with empty values were not listed, this approach would
delete them from the tree. That's probably fine, but it's worth
documenting.)
That said, note also that this implementation adds an extra level of
boxing for the leaves. This could be fixed by replacing ] with >@] in
mktree.
Thanks,
--
Raul
On Sun, Sep 20, 2020 at 7:09 PM <xash@λ.land> wrote:
>
> This is much simpler; groups based on the first element, recursively call
> itself until no path is left, and links the result back together. Well, was
> at least a nice exercise with L:n yesterday. :-)
>
> ] leaves =. 'g';1
> ] paths =. (,0);1 0
> group =: {.&>@[ </. ]
> mktree =: ]`((group }.&.>)@[ $:&.> group)@.(0<#@;@[)
> paths mktree leaves
>
> On Sun, 20 Sep 2020 03:36:50 +0200
> x...@xn--wxa.land wrote:
>
> > Using L: to apply /. on each leaf (splitting paths) until finished, then
> > rebuilding the paths via {:: and using them to index into the elements.
> >
> > ] leaves =. 'g';1
> > ] paths =. (,0);1 0
> > NB. tree based on paths with <'' as elements:
> > structure=: ({.@> </. }.&.>)^:(*@#@;)L:1^:_
> > NB. <'' -> path -> leaves
> > mktree=: >@{~L:_ 0 ] i.L:1 [: }:@;L:1@{:: structure
> >
> > ] tree =. leaves mktree paths
> > (<'a') mktree (<'')
> >
> >
> > (Though there seems to be some '' included in the raze, so that
> > `leaves mktree path` is not strictly equal to `'g';<<1`.)
> >
> >
> > On Sun, 20 Sep 2020 02:11:07 +0200
> > Raoul Schorer <raoul.scho...@gmail.com> wrote:
> >
> > > Thanks Raul, your code helped me a lot to clarify my interpretation of the
> > > problem!
> > >
> > > I ended up using a recursive verb applying </. on the subset of path boxes
> > > that weren't empty. It's not that elegant and there are still corners to
> > > iron out. The reason why non-leaf nodes are rank 0 is because I have
> > > inputs
> > > that should not be transformed and the 'path' for those is an empty box, s
> > > I made the empty box a flag for a no-op (as in my 2nd example). If anyone
> > > has suggestions for improvements though, I'd be very interested!
> > >
> > > leaves =. 'g';1
> > > paths =. (,0);1 0
> > >
> > > mktree =: 3 : 0
> > >
> > > 'paths leaves' =. y
> > >
> > > pathb =. (<'')&= paths
> > >
> > > if. *./ pathb do. y return. end. NB.termination, nothing to modify
> > >
> > > currl =. leaves #~ -. pathb NB.unfinished branches, modifications pending
> > >
> > > finl =. pathb # leaves NB.final branches, nothing more to modify
> > >
> > > k =. {.@> paths #~ -. pathb
> > >
> > > modl =. k&(</.) L: 1 currl NB.modified leaves
> > >
> > > nextl =. modl (I.@:-. pathb) } (# pathb) # <''
> > >
> > > nextl =. finl (I. pathb) } nextl
> > >
> > > nextp =. }. &.> paths
> > >
> > > nextp ;< nextl
> > >
> > > )
> > >
> > > > L: 1 {: mktree^:_ paths;<leaves
> > >
> > >
> > > leaves =. <'a'
> > >
> > > paths =. <''
> > >
> > > > L: 1 {: mktree^:_ paths;<leaves
> > >
> > >
> > > Cheers,
> > >
> > > Raoul
> > >
> > > On Sat, Sep 19, 2020 at 7:08 PM Raul Miller <rauldmil...@gmail.com> wrote:
> > >
> > > > I should have said: this isn't going to be all that efficient on large
> > > > data structures.
> > > >
> > > > Efficiency on small data structures tends to be trivial (which has
> > > > tended to yield lots of potentially misleading concepts and claims
> > > > about efficiency in the popular press),
> > > >
> > > > Thanks,
> > > >
> > > > --
> > > > Raul
> > > >
> > > > On Sat, Sep 19, 2020 at 1:05 PM Raul Miller <rauldmil...@gmail.com>
> > > > wrote:
> > > > >
> > > > > Hmm...
> > > > >
> > > > > Would something like this fit what you are looking for?
> > > > >
> > > > > mktree=:1 :0
> > > > > (0#a:) m mktree y
> > > > > :
> > > > > for_p. m do. path=.;p [ leaf=.p_index{::y
> > > > > x=.path x insertnode leaf
> > > > > end.x
> > > > > )
> > > > >
> > > > > insertnode=:1 :0
> > > > > :
> > > > > len=. (#m)>.1+ndx=. {.x
> > > > > if.1<#x do.
> > > > > node=. (}.x) (ndx{::len{.m) insertnode y
> > > > > else.
> > > > > node=. y
> > > > > end.
> > > > > (<node) ({.x)} len{.m,a:
> > > > > )
> > > > >
> > > > > leaves =. 'g';1
> > > > > paths =. (,0);1 0
> > > > > tree =. paths mktree leaves
> > > > > tree -: 'g';<,<1
> > > > > 1
> > > > >
> > > > > That's not quite the same as your original specification, but I can't
> > > > > see any good reason to require that non-leaf nodes of the tree be rank
> > > > > zero.
> > > > >
> > > > > Also, this isn't going to be all that efficient -- but (if this is
> > > > > what you are looking for) there are some minor improvements available.
> > > > >
> > > > > Thanks,
> > > > >
> > > > > --
> > > > > Raul
> > > > >
> > > > > On Sat, Sep 19, 2020 at 11:51 AM Raoul Schorer
> > > > > <raoul.scho...@gmail.com>
> > > > wrote:
> > > > > >
> > > > > > Dear all,
> > > > > >
> > > > > > I am attempting to recover trees from a varying length path
> > > > > > encoding.
> > > > Chapter
> > > > > > 32: Trees <https://www.jsoftware.com/help/learning/32.htm> shows how
> > > > to do
> > > > > > it for fixed-length paths, but I wasn't able to find a suitable
> > > > solution to
> > > > > > the varying length case. To illustrate:
> > > > > >
> > > > > > leaves =. 'g';1
> > > > > > paths =. (,0);1 0
> > > > > > tree =. paths mktree leaves
> > > > > > tree -: 'g';<<1
> > > > > > 1
> > > > > >
> > > > > > What would be the definition of 'mktree'? Is there a "common idiom"
> > > > > > APL
> > > > > > solution to that?
> > > > > >
> > > > > > Thanks a bunch,
> > > > > > Raoul
> > > > > > ----------------------------------------------------------------------
> > > > > > 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
