I’m auditing the Data Structures course on Coursera. Auditing means I’m taking it for free and not paying them like they want me to. This also means I can’t submit solutions to quizzes. Instead, I will try to write things up here as I learn them.
First up, I’d like to attempt to implement a stack in Clojure and Ruby using an array as the base data structure.
Stack using an list in Clojure and an array in Ruby
A stack is known as a
Last In, First Out data structure. The simplest visualization of a stack are dinner plates…well, stacked on top one another. You can’t take and use the bottom plate without removing all the plates on top of it. It’s a simple data structure, really. The API for a stack is typically the following functions:
- push (add an item to the front)
- pop (remove and return the top item)
- top (return the top item without removing it)
- empty? (is the stack empty?)
My appreciation of Clojure’s coolness is well-documented on this blog. This appreciation continues here. There are a few sequence-like data structures in Clojure, such as a
map. For a while, I was confused as to the need for both a
list and a
vector. Tonight, though, the difference is clear and useful. A
list is optimized for pushing to the front of it. A
vector is optimized for pushing to the rear of it. This makes writing code for this blog post that much easier.
I’ll use the
list as the basis for my stack.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I’m sticking the list in an atom in order to keep state around. I’m also adding
* to the function names, so as not to clobber the built-in Clojure functions.
empty*? are straightforward to implement. Pushing onto the stack involves using
conj on the
list data structure which will add things to the front of the list. Returning the top element without removing it is also simple, as is comparing the number of items in the list to 0, which is our empty check.
pop* is a little trickier, as it’s a two step process. I need to remove the item from the stack, as well as return it. I can actually reuse
top* for the first step and then reset my atom to the rest of the list as a means of removing that first one.
Here is how the API works:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Nice! As I keep saying, well-designed languages make things so easy to use. I wonder if I’ll be able to do this as easily in Ruby.
Since everything in Ruby is an object, that’s what I’ll start with. Now, Ruby only has a
vector implementation, which might writing a stack implementation a bit more challenging. Luckily, the one thing I don’t need to worry about is the size of the stack.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Huh. It’s actually pretty simple, as well. Well, after I dug into Ruby’s Array docs, it got simple. The
insert method is pretty nice, though I suspect it is not nice at all from a performance point of view.
Here’s the API as implemented in Ruby:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Reflect and conclude
I think this is a good stopping point. Soon (I was going to say tomorrow night, but let’s face it, these posts aren’t that regular), I will implement a queue using the
vector data structures. I suspect that it will be equally as easy.
The differences between language philosophies are laid bare, I hope.
In Clojure, not only did I separate the functions that operate on the data structure from itself, I also managed to reuse a function I just created in order to implement another. To me, this is one of the core principles of functional programming and of Clojure. Each function is a self-contained unit of work that operates on the parameters passed into it. I could have just assumed that the
atom holding my list is just available, but I am already in the habit of not making that assumption.
On the other hand, my habit in Ruby is to create a class that contains the data that I need to perform computations on and the functions that do those computations. This is the most-straightforward way to do things in Ruby. It falls squarely on the language’s golden path. I could, with greater effort, to do what I did in Clojure. I could have made two classes, one as the container of the underlying data and another that holds the functions to operate on it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
I am likely over-complicating things, but that is because this style of writing code in Ruby is totally unfamiliar to me. Also, the underlying implementation is leaking through. I probably need to abstract further, but I honestly don’t know how. On further thought, the initial design looks better to me, as I only expose a very limited set of functions and I can change the underlying data structure and the implementations of the API functions. However, it’s also possible that a user of my stack API will realize that it’s really an array and start to depend on that.
EDIT: With help from my peeps at (Practicing Developer’s Slack channel)[https://practicingdeveloper.com/], I actually came up with a nicer implementation that doesn’t necessarily leak.
I would love to hear people’s thoughts on this. Has anyone had to implement their own stack data structure? What did you use as a basis? How did it work out for you?