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
[email protected] 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 <[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, 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 <[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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
