Depth of nested list

[rickster]

Is there a way to programmatically find how deeply nested a list is?
I'm looking for syntax like :
{ 1 { 2 { 3 { 4 }5 } 6 } 7 } NEST --> 4
Failing a command to do the trick, I thought of stringifying
the list and counting the left braces. Is there a better way?
Any suggestions are welcome.

[Joe Horn]

Are you seeking an RPL solution, or something for the HP Prime?

[John Keith]

(09-09-2023 12:07 AM)Joe Horn Wrote:  Are you seeking an RPL solution, or something for the HP Prime?

Since NEST follows the list, I'm guessing RPL.

On the 50g I would convert to string and use SREPL to count the braces.

[DavidM]

(09-09-2023 10:34 AM)John Keith Wrote:  On the 50g I would convert to string and use SREPL to count the braces.

Counting the brackets would work in the given example, but not with others. Example: { { 1 } { 2 } { 3 } { 4 } { 5 } { 6 } { 7 } }, which I believe should have a nested depth of only 2. So there's a need to track the current depth as the opening and closing brackets are encountered when parsing.

Then there's situations like { "{{{}}{{" }. While it's probably overkill for the specific need here, it's the type of thing that I think about when coding System RPL. Unanticipated input in that environment can have serious consequences.

[Albert Chan]

depth(non-list) = 0
depth(lst) = 1 + max(map(depth, lst))

Code:

function depth(t)
    if type(t) ~= 'table' then return 0 end
    local n = 0
    for _, x in pairs(t) do n = max(n, depth(x)) end
    return 1 + n
end

lua> depth({ "{{{ Hello!", 1, {2, 3} , {4, {5}}})
3

[John Keith]

(09-09-2023 11:33 AM)DavidM Wrote:  

(09-09-2023 10:34 AM)John Keith Wrote:  On the 50g I would convert to string and use SREPL to count the braces.

Counting the brackets would work in the given example, but not with others. Example: { { 1 } { 2 } { 3 } { 4 } { 5 } { 6 } { 7 } }, which I believe should have a nested depth of only 2. So there's a need to track the current depth as the opening and closing brackets are encountered when parsing.

Oh yeah, duh! That's what happens when I post before coffee.

[DavidM]

(09-09-2023 03:00 PM)John Keith Wrote:  Oh yeah, duh! That's what happens when I post before coffee.

Perfectly understandable. I think I more often respond with these kind of half-thought-out ideas for algorithms than any kind of bulletproof ideas. But I think we should encourage them, because it’s fertile ground for learning.

You frequently spot good uses for the speedy SREPL, and sometimes I’m surprised at your creative ideas where it can be applied.

I could be mistaken, but from previous posts I believe rickster is probably looking for a 48gx solution here, so SREPL may not be an option regardless. Perhaps he can specify which platform he’s targeting here.

[John Keith]

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.

[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!

[DavidM]

(09-11-2023 12:55 PM)DavidM Wrote:  

Code:

...    LIST\->                 @ explode current list
    1 SWAP START            @ loop for each object in current list
...

And without even trying, I proved what I told John above about half-thought-out program ideas.

The program I posted fails miserably if the source list is either empty or contains an embedded list which is empty (the code snippet above shows why).

A simple way to fix that is to simply make sure that each list has at least one value, since the quantity and type of non-list items doesn't really matter. A fairly simple fix (which unfortunately contributes to the program's ugliness) is to just add something to each list encountered. I do this below by adding NOVAL to each encountered list:

Code:

\<<
  1 DUP                     @ current/max depth defaults
  {                         @ main subroutine opening delimiter
    NOVAL +                 @ add an element to insure non-empty list
    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
      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 dislike this kind of patch, and in practice I would likely come up with a better solution for something like this. For now, it will suffice.

[Gilles]

A solution in "RPL + ListExt library" or "newRPL + LstX library"

Code:

« 1 → n 
 « WHILE DUP LXIL SWAP OVER SAME NOT REPEAT 1 'n' STO+ END DROP n »
»

The idea is very simple : 'explode' inner list (LXIL) while something changes.

If you dont want to install the library, LXIL is :

Code:

'LXIL' « 1 « IF DUP TYPE 62 == THEN LIST→ DROP END » DOSUBS »

[Werner]

a recursive solution. store as NEST

NEST
\<<
  0. + @ avoid empty lists
  0. SWAP @ set up count
  1.
  \<<
    IF DUP TYPE 5. SAME
    THEN NEST
    ELSE DROP 0.
    END
    MAX
  \>>
  DOSUBS 1. +
\>>


Cheers, Werner