Learn Data Structures the Insane Way - Implementing a Stack in Google Sheets

People joke all the time about how tools like Google Sheets and Excel are usable for functional programming. Unfortunately, I've never seen more than a toy example. I'd like to change that. I'm going to release a series of functional programming posts using only Google Sheets. If you'd like to follow along, hit the follow button and check in every few days!

Show Me The Code

Before we get started, the finished Stack implementation can be found here. Feel free to create your own copy, mess around, etc.

What do we want out of a Stack?

A stack is one of the most basic of data structures. You can think of it as a big list of elements that you're always adding to or removing from. It has two mandatory operations, push, which appends an element, and pop which removes the element at the top of the stack. You can also have any number of arbitrary operations like length, peek, etc. This is what interacting with a stack in pseudocode might look like.

let my_stack = new Stack()
my_stack.push(3)     # [3]
my_stack.push(4)     # [3, 4]
my_stack.push("foo") # [3, 4, "foo"]
let x = my_stack.pop()
print(x)
>> "foo"
print(my_stack.length())
>> 2

Implementation

Implementing a small, limited capacity stack in almost any language is pretty trivial. However, there is a difference between functional languages and imperative languages: state changes. Without going in to too much detail, functional languages never change internal state, only create new state. Imperative languages change state willy nilly, leading to buggy code (As some would claim!) In the pseudocode above, we assume an imperative language. The stack has elements pushed on and popped off. It changes. In a real functional programming language, we would instead create a new stack at every step, with one modification each time. And that's exactly what we're going to do!

The big idea - at each timestep(column), we make one change to the array based on our inputs and the previous state, starting with an empty array. If the input command is a Push, we concatenate the value in Input to a copy of the previous state's stack. If the input command is a Pop, we copy over all the values in the stack except for the last one, which is copied to the Output field.

The magic happens in the formula for the Curr Stack

Some quick notes:

1. Google Sheets uses {arr1; arr_or_val} notation for array concatenation.
2. We need the ARRAY_CONSTRAIN function to avoid copying over the entire column. Since all columns in a sheet are the same length, you can't copy one over and then append to it.
3. Google Sheets hates zero-length arrays, hence the necessity of the NUL value. If you POP it off, you'll get all sorts of ugly #REF errors.

Thanks for reading!

Check out the Google Sheets link to play around with it yourself.

Next time I'll try writing an actual useful program with this guy. If you have anything you'd like to see, leave it in the comments below!