Recently I was looking at some basic computer science material and was reading about data structures, specifically, the “Stack” data structure. I noticed that all the examples tend to be strictly Object-Oriented, and I wondered why other language paradigms were not shown.
That was when I decided to think about what would a Stack look like using other programming paradigms. So that is what we will try to do in this post.
First, let’s look at how I would implement a Stack using pure OO.
In the above code, we are defining a
Stack class that has a private property called
#head and three methods called
pop , and
peak that allows you to add an item to the stack, take an item off, and look at the top item on the stack.
Stack is implemented using a linked list. If you are not familiar with linked lists, I recommend checking out the basecs article on linked lists but summarizing: A linked list is a list of objects called nodes. Each node has two properties: a value and reference to the next node. To traverse a linked list, you start at the first node, called the head, and keep going to the next node until you run out of nodes.
Our Stack keeps track of the head node in the private
#head property. When we call
peak it returns the value at the head node. When we call
push, it will create a new node with the value provided, assign the node at the
#head property to
next and assign that new node to the
#head property. Finally, when we call
pop, we pull the value off the
#head property, and then assign the value of
next to the
We are also making our
Stack iterable by assigning a generator function to the
To use the stack, we call
new Stack() and assign that to a variable. From there, we can do all the fun things to a stack you can. This is probably the most common way you will see a
The first step to making this more functional is to stop mutating our
Stack every time we call either the
pop method. So let’s make a new version called
Let’s talk about what we changed. We still have a private
#head property. Also our
peak and iterator or also still the same. What we changed was that we added a
constructor to our class. The
constructor allows us to initialize values in our
Stack when we call
new Stack() in our code. Our constructor lets us optionally pass in a node and assign it to the
#head property. This will allow us to initialize our
Stack with an existing linked list if we want.
push method, we still take in a value, assign it to a new node, and assign the value at the
#head property to the
next property of that new node. However, instead of changing the value of the
#head property, we are returning a new
Stack initialized with the new node. The same thing happens in our
pop method. We are returning a new
Stack initialized with the next node of our stack.
I think it is important to stop and reiterate why this is helpful. If two parts of our code were looking at that same
Stack and one part called
pop on it. The other part of our code would have no way of knowing that the value was changed on it. This can lead to unpredictable behavior. Making our Stack immutable ensures that we can write our code and be confident that some other part of our code won't change its values underneath us.
The next evolution into a more functional style is to move away from creating classes at all and instead define methods that take inputs and return values:
In the above code, instead of creating a class, we are defining an object with utility methods that know how to peak, push, and pop values on a linked list. Since our methods no longer have access to a head property, that value must be passed in as an argument to our methods. For that same reason, we also have created a function called
getIterator that will generate an iterator for us to use in those circumstances.
Other than that, our code works pretty much the same way as our
ImmutableStack. The only difference is that we have to pass in the
stack variable into every method call.
The above example is already following functional style, but we can go to one more level of inception. So let’s show you that code first:
First, it is more common in FP languages to group related functions in a module, so that was the first thing we did. We move all the methods into simple functions that we export from the
Generally speaking, all the functions work the same way, except for the
push function. A common pattern in functional programming is only to use one parameter per function. If you need more than one argument, you use a pattern known as “currying.” When you curry functions, your function will return a new function that requires the next argument. You keep doing this until you no longer need any arguments.
push function. We take an argument called
head and return a new function that takes an argument called
value. When we call that second function, it will still have access to that
head value, and it can complete the code we need to run.
One of the things this gives us is the ability to do is partial application. On line 48, we create a new function
stackPusher that will take a value and push it onto a new stack.
This gives us two things we can do. In one part of our code, we may know which stack we want to push on to, but we don’t yet know the value. Instead of trying to keep track of the stack in some type of global store, we can pass around a function that already knows which stack to use and needs to have a value passed in:
const stackPusher = push(stack) /* later in our code */ const newStack = stackPusher(5)
This can be helpful if we want to create multiple stacks with the same tail but with different heads. We can create a function from the push function that we can use to generate multiple lists with the same tail using different values:
const stackPusher = push(stack) const stack1 = stackPusher(5) const stack2 = stackPusher(2) const stack3 = stackPusher(3) const stack4 = stackPusher(8) const stack5 = stackPusher(12)
So there are four styles of code that you can use to do the same thing. One is a typical OO style, and the last is a typical FP style, with all the variations in between. I would recommend trying all these styles out and seeing which makes the most sense to you.