# How Does This Naive Stack Implementation Look?

Consider this naive stack implementation in Elixir:

defmodule Stack do
defstruct name: "", value: 0

def init() do
_s = []
end

def push(name, value, s) do
s_new =  [%Stack{name: name, value: value}, s]
{:ok,s_new}
end

def pop(s) do
[h|tail] = s
{:ok, h, tail}
end

def depth(s) do
length(s)
end

end

#Use:
# s = Stack.init()
# {:ok, s} = Stack.push("a",1,s)
# {:ok, item, s} = Stack.pop(s)
# l = Stack.depth(s)


Am I using structs correctly? Any suggestions for more idiomatic code style?

• The usage is great. The only question/feedback is if you should rather define a struct named Stack.Item, since the struct is not representing the stack, but its items. Also, you could simply use a tuple (but I assume the point of the exercise is to structs, so... :D). – José Valim May 2 '14 at 6:38
• Yep, you're right @JoséValim--were this something I were doing for "real" I would use a tuple. It'd be simpler. But as you guessed, I did this as a learning exercise. – Onorio Catenacci May 2 '14 at 11:52
• Drat--and I just noticed that my stack depth is returning incorrectly. Ah well. – Onorio Catenacci May 2 '14 at 12:08

The mechanical usage of the struct seems correct, but I'm having some conceptual issues with the original code.

First, the Stack structure models a single element instead of the entire structure. I find this weird, and it makes it impossible to implement custom protocols for the stack abstraction. Your module seems to partially abstract stack elements, and partially the entire stack structure.

Second, what is the purpose of key/value? Stack should work on arbitrary elements. What is in those elements should be left to the client of the structure, and not hardcoded as a requirement of theStack module.

Then, function push/3 accepts the abstraction as the last argument. This is contrary to the recommended conventions (subject as the first argument), and makes it impossible to use the abstraction with pipe operator |>.

Even if the last issue was fixed, pipes still won't work since push returns the result in format of {:ok, ...}. This is not needed, especially since there is no possible error outcome.

Notice that this doesn't hold for pop, which must return two values: last element pushed, and the modified structure (a stack containing remaining elements).

Disregarding the fact that stack really doesn't require an abstraction (Elixir list is already a stack), here's my take on it:

defmodule Stack do
defstruct elements: []

def new, do: %Stack{}

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

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

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


This can then be used as:

iex(1)> Stack.new |> Stack.push(1) |> Stack.push(2) |> Stack.pop
{2, %Stack{elements: [1]}}

• I agree that normally you wouldn't want a stack on a non-generic type. But since I was trying to learn how to use structs, I sort of pretended that wasn't a concern. As José pointed out, I'd probably use a tuple not a struct (among several other changes I'd make); I was trying to figure out how structs fit into my general understanding of Elixir. Getting a better understanding of idiomatic Elixir code was a secondary benefit too. Regardless, your code looks like a big improvement on mine; thanks! – Onorio Catenacci May 2 '14 at 14:28
• For whatever it's worth I created my code before I saw your MEAP book. – Onorio Catenacci May 9 '14 at 11:55
• No problem. Please don't understand my response as a criticism. I was just trying to describe what I feel would be a more proper functional idiom. This is also the role of chapter 4 in the book. – sasajuric May 9 '14 at 15:18
• No worries. The feedback you shared was exactly the sort of thing I was hoping to get. I mention that I created my code before I started reading your book because I wouldn't want you to get the impression that I totally ignored the advice you give in the book. – Onorio Catenacci May 9 '14 at 15:26
• It's perfectly fine. Every technical book covers a lot of material, so it's normal if you don't remember everything at once. I certainly can't recall all the details after I read the book. I should also add that my book is a personal look on things, and not a collection of rules set in stone. So if you feel you disagree with any technique I'm recommending, and have some reasons for it - feel free to do it your way. After all, for better or worse, programming is not an exact science. – sasajuric May 9 '14 at 22:45

Keep in mind there is no reason to call init. Any state is being maintained outside the module. Also you can use recursion to iterate over the list. I don't typically use accumulators but in this case it seemed to fit. I also rely heavily on pattern matching. The EVM was designed with pattern matching optimization in mind so there isn't any drawback. Plus, it cleans up the assignments. Here is a solution that I came up with:

defmodule Stack do
defstruct name: "", value: 0

def push(name, val, s\\[]) do
{ :ok, [%Stack{name: name, value: val}] ++ s }
end

def pop([h]), do: { :ok, h, [] }
def pop([h|tail]), do: pop(tail, [h])

def pop([h|[]], acc), do: { :ok, h, acc }
def pop([h|tail], acc), do: pop(tail, acc ++ [h])

def depth(s), do: length s
end

#{ :ok, s } = Stack.push "a", "1"
#{:ok, [%Stack{name: "a", value: "1"}]}
#{ :ok, s } = Stack.push "b", "2"
#{:ok, [%Stack{name: "b", value: "2"}, %Stack{name: "a", value: "1"}]}
#{ :ok, item, s } = Stack.pop s
#{:ok, %Stack{name: "a", value: "1"}, [%Stack{name: "b", value: "2"}] }

#l = Stack.depth s
#1


push should insert into the first position and pop should remove the last item.

I hope this helps and if there is anything else just let me know.

• Actually, init is a good way to start the stack in case he wants to change its representation in the future. I would name it new/0 though, to map nicely to HashDict and HashSet, etc. Also, I prefer his version of push because the stack is being passed as first argument (which follows Elixir conventions). – José Valim May 2 '14 at 6:36
• A couple of things Johnny (1) Isn't it idiomatic to return a tuple with :ok as the first element in Elixir? (I'm referring to the four pop functions) (2) I'm not quite following the stuff about the accumulator? – Onorio Catenacci May 2 '14 at 11:57
• I would just return :ok if the operation can fail or have two results. For example, it doesn't look like push can ever fail, so I wouldn't return a tuple. pop can fail if the list is empty, however, since the response is already a tuple (with the element and new stack) I would simply make it return {element, stack} or :error in case the stack is empty (there is no need for :ok as first element here). – José Valim May 2 '14 at 17:51
• Thanks @JoséValim--I guess I was misunderstanding the convention on Elixir code. – Onorio Catenacci May 2 '14 at 19:10

José - Looking at it again, I see what you are saying about the init function to initiate a clean stack. I was thinking of this as an autonomous example and the init function just seemed superfluous. I was just trying to get away from the sense of state but being more of a pseudo gen_server example, the function fits. The binding also seemed excessive but that may be just a personal preference :)

Onorio - (1) It's idiomatic in Erlang to return a tuple and much of the Elixir standard lib does too. I believe it's to be compatible with Erlang expectations but José would be able to answer that better. There are a number of options in standard lib that add a ! to return only the value. That being said, I should have made that function private. I see the advantages of passing a tuple especially for error handling but I tend to use it sparingly. That could totally be an error on my part. (2) On the 3rd & 4th pop functions I use the acc accumulator to rebuild the list. I try to avoid this in my recursive calls like:

defmodule MyMod do
def map([], _), do: []
def map([h|t], func) do
[func.(h)] ++ map(t, func)
end
end

# MyMod.map([1,2,3,5], fn(n) -> n + 1 end)
#>[2,3,4,6]