Find the "Recursive Size" of a List

Question

Inspired by Find the “unwrapped size” of a list.

Define the Recursive Size, RS, of a list containing no lists as its length (number of items contained) and the Recursive Size of a list containing any lists as the sum of its length and the Recursive Size of those lists.

Challenge

Write a program or function that outputs the Recursive Size of any given list in as few bytes as possible.

The input is a list and may contain numbers, strings (if your language has them), and similar lists.

---

For example:

RS([]) = 0

RS([[]]) = 1

RS([4, 5, 6]) = 3
RS(["four", "five", "six"]) = 3
RS(["[[[[]]]]", "[][][][][]", "][][[[]]][]["]) = 3

RS([[4, 5, 6]]) = 4
RS([["four", "five", "six"]]) = 4
RS([["[[[[]]]]", "[][][][][]", "][][[[]]][]["]]) = 4

RS([[4], [5], [6]]) = 6
RS([["four"], ["five"], ["six"]]) = 6
RS([["[[[[]]]]"], ["[][][][][]"], ["][][[[]]][]["]]) = 6

RS([[[[[[[[[]]]]]]]]]) = 8

RS([[],[],[],[],[],[],[],[]]) = 8

RS([[],[],[[]],[[[[]]]]]) = 8

RS([0,[-1],[2.3,-4.3],[5,[6]],[7,[8,9,[10,11,[12,13,14]]]]]) = 22

Note that if your language has no strings but does have lists of characters, the examples containing "strings" above could actually be lists of characters and have larger results. As an example:

RS([['f','o','u','r'], ['f','i','v','e'], ['s','i','x']]) = 14

This is code-golf, so the shortest answer in bytes wins; no funny-business, as always.

A non-list input may produce any output.
I/O is as flexible as usual.

Answer 1

Jelly, 8 bytes

߀-ŒḊ?‘S

Try it online!

How it works

߀-ŒḊ?‘S  Main link. Argument: x

   ŒḊ?    If x has non-zero depth:
߀          Recursively map the main link over its elements.
  -         Else, yield -1.
      ‘   Increment all integers in the result.
       S  Compute the sum of the result.
          If x is an array, incrementing before adding is equivalent to computing
          the sum of the elements and the length.
          If x is an integer/character, incrementing -1 yields 0, as desired.

Answer 2

Python, 42 bytes

f=lambda x:x*0==[]and len(x)+sum(map(f,x))

For a non-list, output 0. For a list, output its length plus the sum of the recursive outputs for its elements.

Lists fall above numbers and below strings in the Python 2 ordering, requiring []<=x<''. Instead, we check x*0==[], whereas the result of 0 for a number or '' for a string.

Answer 3

JavaScript (ES6), 39 37 bytes

Saved 2 bytes thanks to @edc65

f=a=>a.map&&a.map(x=>a-=~f(x),a=0)&&a

Answer 4

Mathematica, 20 bytes

Length@Level[#,∞]&

Anonymous function. Takes an expression as input and returns a number as output. The Unicode character is U+221E INFINITY for \[Infinity]. Level[#,∞] gives a list of the input's subexpressions, and Length@ counts them.

Answer 5

Mathematica, 14 bytes

LeafCount@#-1&

Minor modification of my previous answer. As I explained there, LeafCount already takes care of nested atomic values, but it also counts the outermost list, which we need to subtract from the result.

Answer 6

Perl, 34 bytes

A recursive function! Yep, Perl doesn't only have regex but also have functions!

sub f{@_+f(map ref?@$_:(),@_)if@_}

If you want to test it, you can run something like :

perl -pE 'sub f{@_+f(map ref?@$_:(),@_)if@_}$_=f@{+eval}' <<< '[["four"], ["five"], ["six"]]'

Answer 7

Mathematica, 32 bytes

Length@#+Tr[#0/@#~Select~ListQ]&

Unnamed recursive function. The excerpt #0/@#~Select~ListQ calls the function again on each element of the input that's a list, and Tr sums those values up. Fortunately Mathematica is fine taking the length of the empty list and searching for qualifying elements from the empty list, so no base case is needed.

Answer 8

Factor, 105 bytes

Recursive function g.

: g ( o -- l ) [ dup [ sequence? ] [ string? not ] bi and [ [ g ] map sum 1 + ] [ drop 1 ] if ] map sum ;

Ungolfed (kinda):

: g ( o -- l ) 
[ dup 
  [ sequence? ] 
  [ string? not ] 
  bi and 
  [ [ g ] map sum 1 + ] 
  [ drop 1 ] 
  if 
] map sum ;

You'll find there are no calls to length because instead of using the length builtin, it's implemented through drop 1 on strings and non-sequences.

Answer 9

Haskell, 52 bytes

data L a=E a|N[L a]
r(N n)=1+sum(r<$>n)
r _=1
pred.r

Usage example:

*Main> pred.r $ N[E 0,N[E(-1)],N[E 2.3,E(-4.3)],N[E 5,N[E 6]],N[E 7,N[E 8,E 9,N[E 10,E 11,N[E 12,E 13,E 14]]]]] 
22

Haskell doesn't support mixed lists (e.g. Int and list of Int), so I go with a custom list type L which is either an element of some type a (-> E a) or a list of other Ls (-> N[L a]). Calculating the RS is a simple recursion where an E counts 1 and a N one plus the sum of the recursive sizes of its elements. The whole sum is off by 1, so I subtract it via pred.

Side note: the exact types and values of the elements are not important for the algorithm, so we could remove the polymorphism an deal with abstract elements only and go with data L=E|N[L].

Answer 10

Mathematica, 18 bytes

(c=-1;++c&//@#;c)&

Yet another Mathematica approach. Not as short as using the built-in LeafCount but still fairly concise. This makes use of the MapAll operator //@ which calls a function on every node of an expression, and we use that function to increment a counter c. As in the LeafCount case, this gives one more than we need, because it counts the outer list head as well, so we start the counter from -1.

Answer 11

C# (Visual C# Interactive Compiler), 50 bytes

int f(Array a)=>a.Length+a.OfType<Array>().Sum(f);

Try it online!

Uses the same technique as the previously submitted Java answer, but leverages LINQ to reduce the answer length.

Explanation:

// f is a method that a accepts
// an array of any underlying type
int f(Array a)=>
  // include the length of the
  // current array in the total
  a.Length+
  // filter the current list to elements
  // that are also arrays
  a.OfType<Array>()
    // recursively call f on each child
    // array and add to cumulative total
    .Sum(f);

Answer 12

05AB1E (legacy), 22 17 bytes

"ε¼D¸D˜Êi®.V"©.V¾

Try it online or verify all test cases.

Explanation:

This challenge poses multiple challenges to overcome in 05AB1E:

1. Although 05AB1E does have a recursive function since the Elixir rewrite (λ), it's only useful for integer sequences. Here is an answer of mine as example of the 05AB1E recursive function. Because of that, I had to find an alternative to do recursive calls, which I did by putting part of the code in a string, and execute that string as 05AB1E code recursively.
2. There also isn't an isList command in 05AB1E, so I had to use some workarounds to check this by utilizing wrapping into a list, deep flattening, and check for equality.
3. And third, there isn't a flatten for just one level of a multi-dimensional list. The flatten function ˜ is a deep flatten that removes all layers and makes a multi-dimensional list a single list with all inner-most values. (i.e. [[1,2],[[[3]],4]] becomes [1,2,3,4]).

I ended up with the code at the top to overcome all three of the above issues. It's split into three major parts. First we have the following:

"..."        # Create a string with 05AB1E code
     ©       # Save this string in the register (without popping)
      .V     # Execute the string as 05AB1E code

The string contains the following code:

ε            # Map each value in the given list by:
             # (this uses the input-list implicitly with the initial call)
 ¼           #  Increase the counter_variable by 1
 D           #  Duplicate the map-value
             #   i.e. STACK "A" becomes "A","A"
             #   i.e. STACK [["B","C"]] becomes [["B","C"]],[["B","C"]]
  ¸          #  Wrap it into a list
             #   i.e. "A" → ["A"]
             #   i.e. [["B","C"]] → [[["B","C"]]]
   D         #  Duplicate that again
             #   i.e. STACK "A",["A"] becomes "A",["A"],["A"]
             #   i.e. STACK [["B","C"]],[[["B","C"]]]
             #    becomes [["B","C"]],[[["B","C"]]],[[["B","C"]]]
    ˜        #  Flatten it
             #   i.e. ["A"] → ["A"]
             #   i.e. [[["B","C"]]] → ["B","C"]
     Ê       #  Check if the wrapped and wrapped+flattened lists are NOT equal
             #   i.e. ["A"] and ["A"] → 0 (falsey)
             #   i.e. [[["B","C"]]] and ["B","C"] → 1 (truthy)
      i      #  If they are:
       ®     #   Push the string from the register
        .V   #   Execute it as 05AB1E code
             #   (this is basically our recursive call, mapping the current value
             #    we duplicated initially again)

A map is used instead of a foreach-loop, because the map has an implicit y, and a foreach-loop need an explicit y. We only care about the counter_variable, though.

And finally, after all the maps and inner maps are done, we'll:

¾           # Push the counter_variable (which is output implicitly as result)

Answer 13

R, 65 bytes

R=function(L,`*`=sapply)"if"(any(L*is.list),sum(1+L*R),length(L))

Try it online!

Obvious recursive implementation of the spec.

Answer 14

C, 174 167 152 bytes

Recursive function f, which leaks memory (152):

#include"object.h"
size_t f(array_t*a){size_t t=0,i=0;for(;i<array_length(a);i++){object_t*o=array_get_copy(a,i,0);t+=o->type==6?f(o->ary):1;}return t;}

Recursive f which doesn't leak, using references, at 167:

#include"object.h"
size_t f(array_t*a){size_t t=0,i=0;for(;i<array_length(a);i++){object_t**o=array_get_ref(a,i,0);t+=*o->type==t_array?f(*o->ary):1;}return t;}

Ungolfed:

size_t get_recursize (const array_t* const a) {
  pfn();

  object_failnull(a);

  size_t out = 0;

  for (size_t i = 0; i < array_length(a); i++) {

    object_t** o = array_get_ref(a, i, NULL);

    if ( (*o)->type == t_array ) {

      out += get_recursize((*o)->ary);

    } else {
      ++out;
    }
  }
  return out;
}

"But how," you ask, "can this be answered in C? Surely, there are no managed arrays in C, and you can't really have heterogeneous arrays...?"

"Aha," I reply, "for I have been working on a simple system of "objects" for (GNU-ish) C11 and ISO C++11".

The full demo program for this function is:

#include "../calc/object/object.h"

size_t get_recursize (const array_t* const a);

define_array_new_fromctype(ssize_t);

int main (void) {

  size_t len = 6;

  static const ssize_t h[6] = { -1, 3, -5, 7, -9, 11 };

  array_t* a = array_new_from_ssize_t_lit(h, len, t_realint);

  size_t rsize = get_recursize(a);

  printf("Recursive size of a: %zu\n", rsize);

  object_t* asobj = object_new(t_array, a);
  array_destruct(a);

  array_t* b = array_new(NULL, -1);

  for (size_t j = 0; j < 10; j++) {
    array_append(b, asobj);
  }

  object_destruct(asobj);

  rsize = get_recursize(b);

  printf("Recursive size of b: %zu\n", rsize);

  asobj = object_new(t_array, b);
  array_destruct(b);

  array_t* c = array_new(NULL, -1);

  for (size_t i = 0; i < 100; i++) {
    array_append(c, asobj);
  }

  object_destruct(asobj);

  rsize = get_recursize(c);

  printf("Recursive size of c: %zu\n", rsize);

  array_destruct(c);

  return EXIT_SUCCESS;
}

size_t get_recursize (const array_t* const a) {
  pfn();

  object_failnull(a);

  size_t out = 0;

  for (size_t i = 0; i < array_length(a); i++) {

    object_t** o = array_get_ref(a, i, NULL);

    if ( (*o)->type == t_array ) {

      out += get_recursize((*o)->ary);

    } else {
      ++out;
    }
  }
  return out;
}

Right now, it lives here and you'll need that repo to use this.

You'll also need the Fowler-Noll-Vo hash library, libfnv, compiled for your platform. It's in that repository and you can also grab it here.

Then you can do cc -DNODEBUG size.c path/to/libfnv.a -o size.

The implementation isn't necessarily efficient:

$ valgrind --leak-check=full --track-origins=yes --show-leak-kinds=all ./size
==24127== Memcheck, a memory error detector
==24127== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==24127== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==24127== Command: ./size
==24127== 
Recursive size of a: 6
Recursive size of b: 60
Recursive size of c: 6000
==24127== 
==24127== HEAP SUMMARY:
==24127==     in use at exit: 0 bytes in 0 blocks
==24127==   total heap usage: 22,900 allocs, 22,900 frees, 615,584 bytes allocated
==24127== 
==24127== All heap blocks were freed -- no leaks are possible
==24127== 
==24127== For counts of detected and suppressed errors, rerun with: -v
==24127== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

But it does work! The last commit to master (which this program compiled on) was 2 days ago, which means this submission is valid.

Answer 15

Axiom 118 bytes

RS(a:Union(List(Any),Any)):INT==(a case List(Any)=>(g:List(Any):=a;leaf? g=>0;r:=#g;for i in g repeat r:=r+RS(i);r);0)

ungolfed

RS(a:Union(List(Any),Any)):INT==
  a case List(Any)=>
          g:List(Any):=a
          leaf? g=>0
          r:=#g
          for i in g repeat r:=r+RS(i)
          r
  0

results

(25) -> RS([])=0
   (25)  0= 0
                                        Type: Equation NonNegativeInteger
(26) -> RS([[]]) = 1
   (26)  1= 1
                                           Type: Equation PositiveInteger
(27) -> RS([4, 5, 6]) = 3
   (27)  3= 3
                                           Type: Equation PositiveInteger
(28) -> RS(["four", "five", "six"]) = 3
   (28)  3= 3
                                           Type: Equation PositiveInteger
(29) -> RS(["[[[[]]]]", "[][][][][]", "][][[[]]][]["]) = 3
   (29)  3= 3
                                           Type: Equation PositiveInteger
(30) -> RS([[4, 5, 6]]) = 4
   (30)  4= 4
                                           Type: Equation PositiveInteger
(31) -> RS([["four", "five", "six"]]) = 4
   (31)  4= 4
                                           Type: Equation PositiveInteger
(32) -> RS([["[[[[]]]]", "[][][][][]", "][][[[]]][]["]]) = 4
   (32)  4= 4
                                           Type: Equation PositiveInteger
(33) -> RS([[4], [5], [6]]) = 6
   (33)  6= 6
                                           Type: Equation PositiveInteger
(34) -> RS([["four"], ["five"], ["six"]]) = 6
   (34)  6= 6
                                           Type: Equation PositiveInteger
(35) -> RS([["[[[[]]]]"], ["[][][][][]"], ["][][[[]]][]["]]) = 6
   (35)  6= 6
                                           Type: Equation PositiveInteger
(36) -> RS([[[[[[[[[]]]]]]]]]) = 8
   (36)  8= 8
                                           Type: Equation PositiveInteger
(37) -> RS([[],[],[],[],[],[],[],[]]) = 8
   (37)  8= 8
                                           Type: Equation PositiveInteger
(38) -> RS([[],[],[[]],[[[[]]]]]) = 8
   (38)  8= 8
                                           Type: Equation PositiveInteger
(39) -> RS([0,[-1],[2.3,-4.3],[5,[6]],[7,[8,9,[10,11,[12,13,14]]]]]) = 22
   (39)  22= 22
                                           Type: Equation PositiveInteger
(40) -> RS([['f','o','u','r'], ['f','i','v','e'], ['s','i','x']]) = 14
   (40)  14= 14
                                           Type: Equation PositiveInteger

Answer 16

Clojure, 79 77 51 bytes

Input has to be a list, not vector. Both would be supported by using sequential?.

(defn f[i](if(seq? i)(apply +(count i)(map f i))0))

Previous:

(defn f[i](if(seq? i)(if(some seq? i)(apply +(count i)(map f i))(count i))0))

Answer 17

APL(NARS), 24 chars, 48 bytes

{⍬≡⍵:0⋄×≡⍵:(≢⍵)++/∇¨⍵⋄0}

This would be the litteral traslation of 'my' Axiom answer here... In APL the void list would be ´⍬´ Zilde, that you indicate with ´[]´, ´⊂⍬´ is ´[[]]´, ´1 2 3´ is ´[1,2,3]´ ecc Some test:

  RS←{⍬≡⍵:0⋄×≡⍵:(≢⍵)++/∇¨⍵⋄0}
  RS ⍬
0
  RS ⊂⍬
1
  RS  4 5 6
3
  RS ("four")("five")("six")
14
  RS ('f' 'o' 'u' 'r') ('f' 'i' 'v' 'e') ('s' 'i' 'x')
14
  RS ("(((())))")("()()()()()")(")()((()))()(")
33
  RS (⊂4 5 6)
4
  RS (⊂("four")("five")("six")) 
15
  RS (⊂("(((())))")("()()()()()")(")()((()))()(") )
34
  RS (,4) (,5) (,6)
6
  RS ⊂¨("four")("five")("six")
17
  RS ⊂¨("(((())))")("()()()()()")(")()((()))()(") 
36
  RS ⊂⊂⊂⊂⊂⊂⊂⊂⍬
8
  RS ⍬⍬⍬⍬⍬⍬⍬⍬
8
  RS ⍬⍬(⊂⍬)(⊂(⊂(⊂⍬)))
8
  RS 0(,¯1)(2.3 ¯4.3)(5 (,6))(7 (8 9 (10 11 (12 13 14))))  
22     

for print the other type of results the exercise propose we need one other function (both functions RS and Rs should be ok for the exercise)

  Rs←{⍬≡⍵:0⋄(''≡0↑⍵)∨0=≡⍵:0⋄(≢⍵)++/∇¨⍵}
  Rs ("four")("five")("six")
3
  Rs ("(((())))")("()()()()()")(")()((()))()(")
3
  Rs (⊂("four")("five")("six"))
4
  Rs (⊂("(((())))")("()()()()()")(")()((()))()(") )
4
  Rs ⊂¨("four")("five")("six")
6
  Rs ⊂¨("(((())))")("()()()()()")(")()((()))()(")
6
  Rs 0(,¯1)(2.3 ¯4.3)(5 (,6))(7 (8 9 (10 11 (12 13 14))))
22
  Rs ('f' 'o' 'u' 'r') ('f' 'i' 'v' 'e') ('s' 'i' 'x')
3

for see how appear some input we use the o function:

  o←⎕fmt
  o 0(,¯1)(2.3 ¯4.3)(5 (,6))(7 (8 9 (10 11 (12 13 14))))
┌5─────────────────────────────────────────────────────────┐
│  ┌1──┐ ┌2────────┐ ┌2─────┐ ┌2──────────────────────────┐│
│0 │ ¯1│ │ 2.3 ¯4.3│ │  ┌1─┐│ │  ┌3──────────────────────┐││
│~ └~──┘ └~────────┘ │5 │ 6││ │7 │    ┌3────────────────┐│││
│                    │~ └~─┘2 │~ │8 9 │      ┌3────────┐││││
│                    └∊─────┘ │  │~ ~ │10 11 │ 12 13 14│││││
│                             │  │    │~~ ~~ └~────────┘2│││
│                             │  │    └∊────────────────┘3││
│                             │  └∊──────────────────────┘4│
│                             └∊──────────────────────────┘5
└∊─────────────────────────────────────────────────────────┘

this print Zilde, and one 8 Zilde list:

  o ⍬
┌0─┐
│ 0│
└~─┘
  o ⍬⍬⍬⍬⍬⍬⍬⍬
┌8──────────────────────────────────────┐
│┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐│
││ 0│ │ 0│ │ 0│ │ 0│ │ 0│ │ 0│ │ 0│ │ 0││
│└~─┘ └~─┘ └~─┘ └~─┘ └~─┘ └~─┘ └~─┘ └~─┘2
└∊──────────────────────────────────────┘

Answer 18

Java, 96 bytes

int c(Object[]a){int r=a.length;for(var i:a)r+=i instanceof Object[]?c((Object[])i):0;return r;}

Try it online.

Explanation:

int c(Object[]a){  // Recursive method with Object-array parameter and integer return-type
  int r=a.length;  //  Result-sum, starting at the size of the input-array
  for(var i:a)     //  Loop over the input-array:
    r+=            //   Increase the result-sum by:
       i instanceof Object[]?
                   //    If the current item is an array:
        c((Object[])i) 
                   //     A recursive call with this item
       :           //    Else:
        0;         //     0 (so leave the result-sum the same)
  return r;}       //  Return the result-sum

Answer 19

Attache, 21 bytes

{#_+Sum!$=>IsArray\_}

Try it online!

Turns out the C# approach is pretty short in Attache.

Alternatives

25 bytes f[x]:=#x+Sum!f=>IsArray\x

26 bytes f[x]:=#x+Sum[f=>IsArray\x]

35 bytes f:=Sum##{If[IsArray@_,1+f@_,1]}=>Id

35 bytes f:=Sum@Map[{If[IsArray@_,1+f@_,1]}]

37 bytes f[x]:=Sum[{If[IsArray@_,1+f@_,1]}=>x]

Answer 20

Python, 72 bytes

l=lambda a:0if len(a)==0else len(a)+sum(l(i)for i in a if type(i)==list)