A Naive Stack Implementation In Elixir

So one of the things I’ve done recently to help me to learn a new language is to tackle creating certain data structures and common operations on those structures in a given language.  And lately I’ve been digging Elixir quite a bit.  So I decided to tackle one of the easiest things I could tackle–a simple, naive stack implementation in Elixir.  First here’s the actual Elixir code:

defmodule Stack do

defstruct elements: []

def new, do: %Stack{}

def push(stack, element) do
 %Stack{stack | elements: [element | stack.elements]}

def pop(%Stack{elements: []}), do: raise("Stack is empty!")
 def pop(%Stack{elements: [top | rest]}) do
 {top, %Stack{elements: rest}}

def depth(%Stack{elements: elements}), do: length(elements)

# Stack.new |> Stack.push(1) |> Stack.push(2) |> Stack.pop

First off, credit where credit’s due: this is more Saša Jurić’s code than it is mine.  I posted my initial code to Code Review and a few folks gave me some great suggestions on how to improve it. But his code seemed the best implementation so this is pretty much his code.

Looking at the code a bit closer, one thing long time OO folks will notice, and something that gave me a lot of trouble initially, is the fact that there’s no member variable to stash the stack in.  The stack has to be passed into each call and the new stack is returned.  This is a big leap in logic and even now after having played with functional for a few years it can still form a large stumbling block for me when I’m trying to solve a problem.

Another thing to notice is this line:

defstruct elements: []

This is within the scope of the module but what is it doing if there’s no member data associated with the module?  It’s easy to assume that modules are analogous to classes in OO and therefore it’s also easy to assume that elements is member data–but that would be a bad assumption.  Elements is actually an abstract data type closely associated with the Stack module.  It’s a way of specifying more information about the data that the various functions in Stack will work with.  You cannot access elements from outside of Stack and in fact it’s not private data within Stack.

One comment Saša made resonates for me. To paraphrase his point,  there is already a stack implementation in Elixir; it’s called a list.  So why bother to build another one?  It’s a fair question; my answer is that if I needed a stack, I’d rather see code that deals with “Stack” directly than see code that deals with lists and has comments littered all over the place that it’s using a list as a stack.  Of course, it’s syntactic sugar but at some level anything other than raw 1’s and 0’s is syntactic sugar.  It’s a question of making it easier for other developers to understand the intent of the code.

I share this not because it’s great or interesting code (although it was much improved by feedback from Johnny Winn, Saša and José Valim) but because someone may want to study this relatively simple code to learn more about Elixir.




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: