How Does This Naive Stack Implementation Look?

Question

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?

Answer 1

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]}}

Answer 2

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.

Answer 3

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]