Scan a ragged list

hgl has a "scan" function called sc. What it does in general is a little bit abstract, so we will just talk about one specific way you can use it.

If we want to take a list of integers and get the partial sums of every prefix we can scan with + for sums and 0 as a starting value:

ghci> sc (+) 0 [1,2,3,4,5,6]
[1,3,6,10,15,21]


This moves left to right adding each value of the list to the accumulator and replacing it with the sum.

We can also scan things other than lists. We can scan all sorts of trees and list-like things. hgl more or less builds the scan function based on the type we give it.

One weirder example is ragged lists. These are lists that contain a mixture of values and other ragged lists. For example:

[1,2,3,[2,3,4],[],2,1,[4,8,[6],5],2]


The compiler has dreamed up a rather weird way to scan these. When the list contains values it behaves normally:

ghci> sc (+) 0 [1,2,3,[2,3,4],[],2,1,[4,8,[6],5],2]
[1,2,3,[2,3,4],[],2,1,[4,8,[6],5],2]
^1
[1,3,3,[2,3,4],[],2,1,[4,8,[6],5],2]
^3
[1,3,6,[2,3,4],[],2,1,[4,8,[6],5],2]
^6


but when it hits a list it splits the read head in two. One goes down that list and scans it, the other skips it and scans the rest of the outer list.

[1,3,6,[8,3,4],[],2,1,[4,8,[6],5],2]
^6
[1,3,6,[8,3,4],[],2,1,[4,8,[6],5],2]
^8     ^6
[1,3,6,[8,11,4],[],8,1,[4,8,[6],5],2]
^11      ^8
[1,3,6,[8,11,15],[],8,9,[4,8,[6],5],2]
^15      ^9
[1,3,6,[8,11,15],[],8,9,[4,8,[6],5],2]
^9
[1,3,6,[8,11,15],[],8,9,[13,8,[6],5],11]
^13         ^11
[1,3,6,[8,11,15],[],8,9,[13,21,[6],5],11]
^21
[1,3,6,[8,11,15],[],8,9,[13,21,[6],5],11]
^21
[1,3,6,[8,11,15],[],8,9,[13,21,[27],26],11]
^27 ^26
[1,3,6,[8,11,15],[],8,9,[13,21,[27],26],11]


This treats a ragged list as a sort of tree, where the main list forms a spine and each nested list is an offshoot from that spine.

Take a ragged list of positive integers as input and perform the scan shown above (sc (+) 0) returning the scanned list.

You may take and output a ragged list in any reasonable format.

This is so answers will be scored in bytes with minimizing the source size being the goal.

Test cases

[] -> []
[8] -> [8]
[1,2,3] -> [1,3,6]
[1,1,1,1,1] -> [1,2,3,4,5]
[[1],[1],[1]] -> [[1],[1],[1]]
[1,[1],[1],[1]] -> [1,[2],[2],[2]]
[1,2,3,[2,3,4],[],2,1,[4,8,[6],5],2] -> [1,3,6,[8,11,15],[],8,9,[13,21,[27],26],11]
[[1,2,3,4],[1,2,3],[1,2,3]] -> [[1,3,6,10],[1,3,6],[1,3,6]]

• May we output null in place of empty sub-arrays? Jan 6 at 19:26

Python, 57 54 53 bytes

f=lambda x,a=0:[i*0==0and(a:=a+i)or f(i,a)for i in x]

Attempt This Online!

Thanks to @ovs for -3 bytes.

Whython, 42 bytes

f=lambda x,a=0:[(a:=a+i)?f(i,a)for i in x]

Attempt This Online!

Uses the ? operator to catch TypeError: unsupported operand type(s) for +: 'int' and 'list' and recurse in that case.

• []==i*0 is a shorter type check
– ovs
Jan 5 at 15:46

BQN, 34 bytesSBCS

{×≠𝕩?(⊑𝕩)𝕤{=𝕨?𝕩∾˜⋈𝔽𝕨;𝕨+0∾𝕩}𝕊1↓𝕩;𝕩}


Run online!

{×≠𝕩?(⊑𝕩)𝕤{=𝕨?𝕩∾˜⋈𝔽𝕨;𝕨+0∾𝕩}𝕊1↓𝕩;𝕩} # Function taking a nested list as 𝕩
×≠𝕩?                          ;𝕩  # If the list is empty, return it
1↓𝕩    # Tail of 𝕩
𝕊       # Recursive call on the tail
# If that fails, return the tail (for the base case)
⊑𝕩                           # The first element of the list
𝕤{      ...      }         # Call the inner function with parameters
#  - 𝕩: result of recursive call
#  - 𝕨: first element
#  - 𝔽: a reference to the outer function
=𝕨?<list>;<int>          #   Conditional, the rank of 𝕨 is 0 for ints and 1 for lists
𝔽𝕨                #   If 𝕨 is a list, call 𝔽 on that
𝕩∾˜⋈                  #   And insert the result in the front of 𝕩
0∾𝕩          #   If 𝕨 is an integer, prepend 0 to the list 𝕩
𝕨+             #   And add 𝕨 to each integer in the resulting nested list


I tried to handle the base case with ⎊ (Catch) instead of an explicit conditional, but couldn't get it to work properly. See the revision history for my failed attempts.

R, 111107103 98 bytes

Edit: -5 bytes each thanks to pajonk and Giuseppe

~=function(x,t=0)if(length(x),if(is.list(y<-el(x)),c(list(y~t),x[-1]~t),c(y+t,x[-1]~y+t)),x)


Try it online!

• -5 bytes? Also, shouldn't list() return list() instead of nothing (1st test case)? Jan 5 at 21:08
• @pajonk - Thanks, and you're right... although the distinction in R between NULL, list() and list(NULL) is sometimes quite difficult for me to get my head around! I think this new version should meet the spec... Jan 5 at 22:26
• @Giuseppe - Yes, of course, much nicer! Thanks. That last list() was really ugly.... Jan 6 at 7:20

Wolfram Language (Mathematica), 39 bytes

a_~f~b___:=Join[{f@@a},0&@@a+f@b]
_f={}


Try it online!

Input [list...]. Inputting [list] works, but returns inside an extra layer of {}.

a_~f~b___:=                         when input is nonempty:
f@@a                 recurse on first element
(do nothing if it's an integer)
Join[{    },      f@b]     followed by recursion on remainder
0&@@             (or 0 if it's a list)
_f={}                               otherwise return empty list


Wolfram Language (Mathematica), 40 bytes

f=#/.{a_,b___}:>Join[{f@a},0&@@a+f@{b}]&


Try it online!

Input [list].

Pip-xp, 27 bytes

b|:0FdacPB:xNd?b+:d(fdb)c|l


Recursive main program, takes the list as a command-line argument. Attempt This Online!

Explanation

b|:0FdacPB:xNd?b+:d(fdb)c|l
a (1st arg) is the input list; b (2nd arg) is the starting
number for the scan
When the function is called as the main program, b is not
specified, so it is nil
b|:0                         If b is falsey (nil or 0), set it to 0 instead
c and d are also local variables which are nil b/c 3rd and
4th arguments are not given
Fda                      For each element d in the input list:
xNd                 Does d contain x (empty string)?
?                If so, it's an integer:
b+:d              Add it to b in-place
If not, it's a list of integers:
(f  )         Make a recursive call
d           using d as the new list
b          and the current value of b as the new starting point
cPB:                    Take that result and push it onto the end of c
(Pushing an element to a nil variable makes it a list)
c    After the loop, return c...
|   except if c is falsey, it's still nil...
l  so return empty list instead


Ruby, 39 bytes

f=->d,t=0{d.map{|x|x*0==0?t+=x:f[x,t]}}


Try it online!

Ruby has the same operator * for Integer and Array which takes the same right operand type(number).
If we multiply a number by 0 we get 0, if an Array we get an empty Array.

tinylisp, 116108 96 bytes

(d S(q((L A)(i L(i(a(h L)1)(c(a(h L)A)(S(t L)(a(h L)A)))(c(S(h L)A)(S(t L)A)))L
(d f(q((L)(S L 0


Try it online!

-8 bytes by removing (load library thanks to chunes in chat. -12 bytes thanks to some type abuse.

05AB1E, 30 29 bytes

0U"εdiXćy+š¬ëXD¬šUy®.V}sU"©.V


Explanation:

Unfortunately 05AB1E lacks recursive methods. We can however mimic this behavior by using "recursive_function_here®.V"©.V. One big disadvantage about this however, is that the variables will always be in the scope of the full program, rather than this recursive function. So instead, we use and modify a list as variable.

0U         # Start with X=[0] (or actually X=0, but it behaves as [0])
"..."    # Push a string with the recursive function explained below
©   # Store this string in variable ® (without popping)
.V # Evaluate it as 05AB1E code
# (after which the result is output implicitly)

ε          # Map each item y to:
di        #  If y is a (non-negative) integer:
X       #   Push list X
ć      #   Extract its head; pop and push remainder-list and first item
#   separated to the stack
y+    #   Add the current integer y to this head
š   #   Prepend it back to the remainder-list
¬  #   Push this prepended head again (without popping the list)
ë        #  Else (y is an inner list instead):
X       #   Push X
D      #   Push X again by duplicating
¬š    #   In this second X, prepend its own head
U   #   Pop and replace X with this modified list
y       #   Push the current list y
®.V    #   Do a recursive call with it
}        #  After the if-else statement:
s       #   Swap so the (potentially modified) X is at the top of the stack
U      #   Pop and replace X with this modified list


Python3, 74 bytes:

f=lambda x,h=0:x and[int==type(x[0])and(h:=h+x[0])or f(x[0],h)]+f(x[1:],h)


Try it online!

BQN, 44 bytesSBCS

0⊸{0=≠𝕩?𝕩;×≡⊑𝕩?(⋈𝕨𝕊⊑𝕩)∾𝕨𝕊1↓𝕩;a∾(a←𝕨+⊑𝕩)𝕊1↓𝕩}


Run online!

Charcoal, 51 bytes

⊞υ⊞Ｏθ⁰Ｆυ«≔⊟ιηＦＬι«≔§ικζ¿⁼ζ⁺ζ⟦⟧⊞υ⊞Ｏζη«≧⁺ζη§≔ικη»»»⭆¹θ


Try it online! Link is to verbose version of code. Explanation:

⊞υ⊞Ｏθ⁰


Temporarily push the initial accumulator to the list and push that list to the list of lists.

Ｆυ«


Loop over all of the lists.

≔⊟ιη


Remove the accumulator from the list.

ＦＬι«


Loop over the elements of the list.

≔§ικζ


Get the current element.

¿⁼ζ⁺ζ⟦⟧


Check whether it's a list. Adding an empty list to a list produces the original list, but adding it to an integer vectorises therefore producing the empty list rather than an integer.

⊞υ⊞Ｏζη


If it's a sublist then temporarily push the accumulator to the sublist and push the sublist to the list of lists.

«≧⁺ζη§≔ικη


Otherwise add the value to the accumulator and replace the value with the total.

»»»⭆¹θ


Pretty-print the result as the default output format doesn't handle ragged lists very well.

JavaScript (Node.js), 52 bytes

f=([h,...t],v=0)=>h?[h+0>h?f(h,v):v+=h,...f(t,v)]:[]


Try it online!

Japt, 25 bytes

W=Uv)?[W¶Ô?ßWÔ:V±W]cßUV:U


Try it

Or, if we can replace empty sub-arrays with null in the output:

Japt, 23 bytes

W=Uv)©[W¶Ô?ßWÔ:V±W]cßUV


Try it