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 <[email protected]> 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, so
> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]>
> > 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
