Had a very short look, but perhaps here http://jsoftware.com/pipermail/programming/2009-June/014985.html is something you can use.
R.E. Boss > -----Oorspronkelijk bericht----- > Van: [email protected] [mailto:programming- > [email protected]] Namens Dan Bron > Verzonden: maandag 24 augustus 2009 21:33 > Aan: Programming forum > Onderwerp: [Jprogramming] Recursive nesting, avoiding recursion > > Hey guys, > > I needed to represent a "nested list" like this: > > NEST =. ;: '(345 * _2 + +/@:(+/%#) * ]) - ''hello''"_ , <.' > > as analogously-nested set of boxes, like this: > > ] BOX =. (< (;:'345*_2+;+/@:') , (<;:'+/%#') , ;:'*]') , > ;:'-''hello''"_,<.' > +-----------------------------------+-+-------+-+-+-+--+ > |+---+-+--+-+-+-+-+--+---------+-+-+|-|'hello'|"|_|,|<.| > ||345|*|_2|+|;|+|/|@:|+-+-+-+-+|*|]|| | | | | | | > || | | | | | | | ||+|/|%|#|| | || | | | | | | > || | | | | | | | |+-+-+-+-+| | || | | | | | | > |+---+-+--+-+-+-+-+--+---------+-+-+| | | | | | | > +-----------------------------------+-+-------+-+-+-+--+ > > This is something I've had to do a number of times, with minor variations. > The most recent case was in the ae2 script [1], which is as above, > except instead of the actual J words I needed to nest their indices in the > original sentence. But I've encountered it in other guises over the > years: parsing XML, data representations from other languages, etc. > > So, what I would like is a general dyad to transform a "parenthesized" > list > into nested boxes: > > A. The right argument (y) is the "parenthesized list" > (in the example above, it's a list of J words, > some of which are boxed parens, but it could be > anything, like a string with {}s, boxes containing > XML elements, etc). > > B. The left argument (x) indicates or implies the "level" > or "depth" of each of the items of y . For example, > if y were NEST then the level of each word is: > > (345 * _2 + +/@:(+/%#) * ]) - 'hello'"_ , <. > 1 1 1 1 1 11 1222222 1 11 0 000 0 0 > > How to represent this is up to you. You could require > parens to be included or excluded from both x and y; > if included you could require their level to be be N > or N+1 or different for open and close parens; you > could use an integer for the level of each element, > like above, or just _1 0 1 to indicate "level > change", etc. > > The key thing is how to represent x is up to you, but > how to calculate x from y is up to your user [2]. > > C. The output is the nested-box analog of y. > > Here's how I do it in [1]: > > nest2Box =. cleanNest@:cutNest@:,&<~ > cleanNest =. bubble@:rmScaff > bubble =. >@:{.^:(1=#)L:1^:_ > rmScaff =. >@:{.L:1 > cutNest =. cutBot L:1^:maxDepth > cutBot =. ('';1) <@:,;.1 ] noParen;.2&>~ minMask > noParen =. <@:(}.@:}:^:(1<#)) > minMask =. (=<./)&.>@:{: > maxDepth =. 1 + >./@:>@:{: > > n2b =: nest2Box f. > > x =. (;:'()') (+/\@:(-/))@:(=/) NEST NB. Depth of each > element > y =. i.#NEST NB. Elements > x n2b y > +----------------------------------+--+--+--+--+--+--+ > |+-+-+-+-+-+-+-+------------+--+--+|17|18|19|20|21|22| > ||1|2|3|4|5|6|7|+-+--+--+--+|14|15|| | | | | | | > || | | | | | | ||9|10|11|12|| | || | | | | | | > || | | | | | | |+-+--+--+--+| | || | | | | | | > |+-+-+-+-+-+-+-+------------+--+--+| | | | | | | > +----------------------------------+--+--+--+--+--+--+ > > But I'm not too proud of it [3]. For one thing, it's not general; y > must > be open (not boxed), because of the way I use L: : > > x n2b NEST > |domain error: n2b > | x n2b NEST > > Which raises the question of why I use L: . Isn't nesting a textbook > example of a recursive problem? Shouldn't I be recursing from the top > down, rather than cutting from the bottom up? > > The reason is that I, like Jose, prefer fully fixable tacit verbs. There > are essentially two ways to recurse in J; having a named verb call its own > name, and anonymous recursion using $: . Neither method lends itself to > fully fixable tacit form. > > Named recursion doesn't permit fixing, and requires a verb be named when > ideally all verbs work the same when anonymous. And verbs that use $: > cause problems when fixed in the definition of other verbs. Essentially, > when a verb ("f") is fixed, if one of the verbs it calls ("g") uses $: , > then that $: stops referrring to f and starts referring to g , or > introduces an explicit context where it wasn't previously required (and > stops the verb from being fully tacit). On that note, I should mention > that I can picture approaches that generate and evoke code, but I consider > them ambiguously tacit at best. > > So, while I'm interested in all approaches (because I can do the work to > adapt them to the form I prefer), I'm particularly interested in verbs > which are tacit, fully fixable, and could be replaced everywhere by their > definition in parentheses. I think this implies cutting from the bottom > up, as I have. But I'm happy to be proven wrong. > > -Dan > > [1] > http://www.jsoftware.com/svn/DanBron/trunk/environment/anonymous_evoke2.ij > s > > [2] Allowing the user to calculate x, rather than calculating > it for him, makes future extensions easier. For > convenience, we could also provide cover verbs of > nest2Box to calculate x for common cases (like J words, > strings with {}s, etc). > > If we did, I think it would be useful to let the cover > verb's left argument be (potential) items from y that > represent "parentheses", in several forms: > > (A) A single item that counts as both open and > close parens, > (B) A list of 2 items which count as open and > close-parens respectively, > (C) A table of (B); a N by 2 table of items > that count as open-parens and close-parens. > > [3] If nothing else, improvements to nest2Box are welcome. For example, > bubble and rmScaff are essentially identical. (I know I implemented a > similar function in a different context, and IIRC it was a bit more > elegant. But I can't find that now.) > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
