Recursive Running Sum Redux – In Elixir! 🏃‍♂️

Previously, on Various And Sundry: I wrote a Perl script to calculate the running sum of an array. It used recursion.

Recursion? I love recursion! And you know what else I love? Elixir! So let’s solve the Weekly Challenge in Elixir next!

Elixir: A Prelude

It’s worthy of another essay entirely, but I love Elixir.

I don’t use it regularly. In fact, it had been years since I wrote a line of Elixir code before sitting down to write this script. I had to breeze through some documentation first to jog my memory of the syntax.

As a functional language, Elixir screams out to solve this challenge in a quick, logical, and readable way.

Let’s get to it.

Short But Sweet

I got my B.A. in Computer Science in college. I took one class that used a functional language, and that was Scheme. I remember little of that class besides that we coded aspects of the board game, Clue, as our programming projects. (Oh, and all the parenthesis!) The lessons learned in writing recursive functions always stuck around.

The number one rule: The recursive equation will continue until it hits its base case. Never forget the base case, and you’ll have a chance to be successful.

An accumulator often helps, too.

As a reminder, the challenge for Running Sum is this:

Write a script to return the running sum of the given array. The running sum can be calculated as sum[i] = num[0] + num[1] + …. + num[i].

As an example, the array (1, 1, 1, 1, 1) will return (1, 2, 3, 4, 5).

(I’ll bounce back and forth between array and list here. The challenge is written with Perl in mind, so that’s an array. This solution is in Elixir, which uses lists. We don’t need to nit-pick on this point, for the purposes of this exercise.)

I’ll jump straight to my code:

defmodule Runner do

    def running_sum([head | tail], new_list, sum) do
        sum = sum + head
        running_sum(tail, new_list ++ [sum], sum)
    end

    def running_sum([], new_list, _) do
        new_list
    end
end

Super simple: Pass in the full array ( (1, 1, 1, 1, 1) in the example above) along with the new list (which starts empty) and the running total (which starts as 0).

When that first list is empty, return the new list. The end.

Elixir’s pattern matching is a whole different way to think about functions if you’re used to the kind of functions you use in scripting languages like Perl, Python, Javascript, Ruby, etc. It’s such a cool feature that they’re all working on implementing it. (Raku included it in the language.)

The same goes for the pipeline operator in Elixir, which I didn’t have a use for with this challenge. Maybe next time!

Also, you’ll notice this line:

sum = sum + head

I said in a previous write-up that I love a good += operator, so why didn’t I use it here? Elixir doesn’t have it. It’s an immutable language. The equals symbol doesn’t exactly work the way you think it does. There’s a re-binding thing going on here and a pattern-matching thing happening and — I’m not the right person to explain it all. Just trust me on this.

Also, I could avoid this entire explanation by moving that line into the parameters of the running_sum/3 call on the next line and not assigning it to anything:

running_sum(tail, new_list ++ [sum + head], sum + head)

I just hate that duplication. There’s a way around it entirely that we’ll explore two sections from now, though. Keep scrolling down!

Let It Run!

I ran the three examples given in the challenge with this bit of copy-and-past brilliance:

IO.puts 'Exercise 1: '
list_of_numbers = [1, 2, 3, 4, 5]
IO.inspect list_of_numbers
IO.inspect Runner.running_sum(list_of_numbers, [], 0)

IO.puts 'Exercise 2: '
list_of_numbers = [1, 1, 1, 1, 1]
IO.inspect list_of_numbers
IO.inspect Runner.running_sum(list_of_numbers, [], 0)

IO.puts 'Exercise 3: '
list_of_numbers = [0, -1, 1, 2]
IO.inspect list_of_numbers
IO.inspect Runner.running_sum(list_of_numbers, [], 0)

Note that I’m using IO.inspect to print out the list. For very good reasons, IO.puts doesn’t work here for what we want. It translates the numbers into character codes and makes a mess of things. It’s a common gotcha for new Elixirists. ( And for those who haven’t written it in a while, as it turns out.)

That produces the following results:

Exercise 1: 
[1, 2, 3, 4, 5]
[1, 3, 6, 10, 15]
Exercise 2: 
[1, 1, 1, 1, 1]
[1, 2, 3, 4, 5]
Exercise 3: 
[0, -1, 1, 2]
[0, -1, 0, 2]

Works for me! Short, but sweet.

Wait! Can We Do It Another Way?

It bothered me that I had to set so much stuff up. I had to pass in a blank array and a starting sum of 0 to kick things off. Could I rewrite this with only 2 parameters to the function?

Yes, it’s possible. However, I don’t like the solution. I’m curious what you think.

defmodule Runner do

    ## First iteration
    def running_sum([head | tail], []) do
        running_sum(tail, [head])
    end

    ## Everything inbetween
    def running_sum([head | tail], new_list) do
        new_list = new_list ++ [head + List.last(new_list)]
        running_sum(tail, new_list)
    end

    ## Base Case
    def running_sum([], new_list) do
        new_list
    end

end

IO.puts 'Exercise 1: '
list_of_numbers = [1, 2, 3, 4, 5]
IO.inspect Runner.running_sum(list_of_numbers, [])

We end up with three functions (with an arity of 2 now) to handle the job. The base case happens when the initial list has been drained dry. Nothing changes there.

But there is now a starting function. When the accumulator (new_list) is passed in as empty, the first function is kicked off. It calculates the sum by adding the first value (head) from whatever is left of the initial list to the latest value in the new_list. Then, it adds that to the end of new_list.

Intellectually, this makes more sense to me. It lets the functions do the work. It doesn’t require an extra parameter to be around. I never have to reassign the sum variable in the middle of a function.

But it also seems like more work. That long line in the second function takes too long to break down and understand for a first-time reader of the code.

I prefer the tradeoff of one extra value to kick things off to the “simplicity” of a function/2 over a function/3.

I only submitted running_sum/3 in the end.

The Weekly Challenge Meta Note

I doubt I’m the first person to do a Weekly Challenge in Elixir. I see the stats include “Erlang” solutions, but I’m not sure if that’s a catch-all for both Elixir and Erlang.

I think I’ll be doing more in Elixir in any case, just to keep my functional mind sharp.

You can find the full script from this challenge on Github.