Scan a ragged list

Question

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.

Task

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 code-golf 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]]

Answer 1

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.

Answer 2

BQN, 34 bytes^SBCS

{×≠𝕩?(⊑𝕩)𝕤{=𝕨?𝕩∾˜⋈𝔽𝕨;𝕨+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.

Answer 3

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
                           a+           with first element added
                       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].

Answer 4

R, 111 107 103 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!

Answer 5

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

Answer 6

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.

Answer 7

tinylisp, 116 108 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.

Answer 8

JavaScript (Node.js), 37 bytes

f=(v,a=0)=>v.map(z=>z.at?f(z,a):a+=z)

Attempt This Online!

Port of several of the other answers.

Answer 9

Japt, 25 12 bytes

emanresu's solution made me realise that, although I had the right method, my approach to it was all wrong - I honestly don't know what I was thinking!- so please upvote them if you're upvoting this.

˶Ô?ßDÔV:V±D

Try it

˶Ô?ßDÔV:V±D     :Implicit input of array U, with second input variable V defaulting to 0
Ë                :Map each D in U
 ¶               :  Is D strictly equal to
  Ô              :  Its reverse, if it's an array, or maximum, if it's an integer (see more detailed explanation below)
   ?             :  If true
    ß            :    Recursive call with arguments
     DÔ          :    U = D reversed (because reversing an array in JS mutates the original), and
       V         :    Current value of V
        :        :  Else
         V±D     :    Increment V by D

---

To (try to) explain how the Ô (which is a shortcut for the w method, without any arguments) allows us to differentiate between arrays & numbers by testing for strict equality:

While it's true that in JavaScript 2 arrays containing the exact same elements are not strictly equal as they are 2 distinct objects, an array assigned to a variable is, of course, equal to itself. Add to that that the reverse method for arrays (w in Japt) mutates the original array and that explains how an array assigned to a variable (D in this case) can be strictly equal to its reverse.

As to why a number does not equal its maximum, that's down to a peculiarity of Japt. Firstly, when applied to a number, Japt's w method returns the maximum of that number and the arguments passed to the method, as a Number. However, if no arguments are passed to the w method then the number it's applied to is returned as excpected but, for some reason, Japt converts the returned value to an Object and a Number cannot be strictly equal to an Object

---

Original, 25 bytes

Preserving this version as Conor O'Brien awarded it an unexpected boubty.

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

Try it

Answer 10

05AB1E, 30 29 bytes

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

Try it online or verify all test cases.

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

Answer 11

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!

Answer 12

BQN, 44 bytes^SBCS

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

Run online!

Answer 13

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.

Answer 14

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!