Depth of nested list

[DavidM]

(09-09-2023 05:22 PM)John Keith Wrote:  A couple of vague ideas here:

Convert to string, initialize a counter, loop through the string and increment the counter when a left brace is encountered, and decrement when a right brace is encountered. The maximum value is the depth of nesting. Would be slow for large lists.

Unpack the list, check the type of each item, if a list is encountered, unpack it and so on, keeping track of max. depth. Probably faster since one rarely encounters lists with nesting more than three levels deep.

My first thought was the same as your first suggestion above. Then I (perhaps foolishly) wanted to see what it would take to use the second approach instead, as I thought it might be an opportunity to try a recursive implementation.

The following visits each object in the list given as an argument, and tracks the depth as it dives into embedded lists. After visiting each embedded object, it simply outputs the deepest level it encountered:

Code:

\<<
  1 DUP                     @ current/max depth defaults
  {                         @ main subroutine opening delimiter
    LIST\->                 @ explode current list
    1 SWAP START            @ loop for each object in current list
      DUP TYPE 5 SAME       @ is the current object a list?
      {                     @ yes, it's a list (THEN clause)
        ::\<-c INCR         @ increment current depth
        \<-m OVER <         @ check for new max depth being reached
        { ::\<-m STO }      @ yes, it's the new max depth (THEN clause)
        ::DROP              @ no, not a new max depth (ELSE clause)
        IFTE                @ if <SL3> then <SL2> else <SL1>
        \<-s EVAL           @ process current object as list
        ::\<-c DECR DROP    @ current depth completed, so decrement
      }                     @ end of processing for list object
      ::DROP                @ object was not a list, so just drop it (ELSE clause)
      IFTE                  @ if <SL3> then <SL2> else <SL1>
    NEXT                    @ process the next object
  }                         @ end subroutine delimiter
  \-> \<-c \<-m \<-s        @ local names (current depth, max depth, subroutine)
  \<<                       @ program to execute with locals in-scope
    \<-s EVAL               @ process the given list in SL1
    \<-m                    @ output the maximum depth encountered
  \>>
\>>

I have to say that this ended up being one of the ugliest RPL programs I've created in a while. I promise that was not intentional -- it just ended up being that way as I tried to save a few bytes here and there. Using IFTE instead of the traditional IF ... THEN ... ELSE ... END can definitely save a few bytes, especially when combined with the use of lists and null-tagged objects instead of executable objects. But all of that comes at a price, both in terms of readability and the quirkiness of using identifiers in lists. Unfortunately the compiled locals make it look even more cluttered. But it works as intended!