Hi all,

How to implement a queue in Elixir with O(1) insertion and O(1) deletion using a list zipper?

According to this blog post on zippers, one can use a list zipper to have a queue-like behaviour:

Zipper lists are conceptually simple enough to be easy to reinvent and replace with queues.

Considering the following zipper:

defmodule Zipper.ListZipper do
  defguard is_range(range) when is_struct(range, Range)

  def new, do: {[], []}

  def from_list(list) when is_list(list), do: {[], list}

  def from_range(range) when is_range(range), do: from_list(Enum.to_list(range))

  def to_list({prev, next}), do: Enum.reverse(prev) ++ next

  def prev({[], next}), do: {[], next}
  def prev({[head | tail], next}), do: {tail, [head | next]}

  def current({_, []}), do: nil
  def current({_, [current | _]}), do: current

  def pop({_, []} = lzip), do: {nil, lzip}
  def pop({prev, [current | tail]}), do: {current, {prev, tail}}

  def next({prev, []}), do: {prev, []}
  def next({prev, [head | tail]}), do: {[head | prev], tail}

  def replace({prev, []}, val), do: {prev, [val]}
  def replace({prev, [_ | next]}, val), do: {prev, [val | next]}

  def put({prev, next}, val), do: {prev, [val | next]}

  def delete({prev, []}), do: {prev, []}
  def delete({prev, [_ | next]}), do: {prev, next}
end

If I insert the sequence 1, 2, 3 into the list zipper, the current will point to the last element 3:

iex(9)> ListZipper.new()|> ListZipper.put(1) |> ListZipper.put(2) |> ListZipper.put(3)                                          
{[], [3, 2, 1]}

Now, I could use next to move the current to the first inserted element everytime I call put/2 (unless the zipper has only one element):

iex(10)> ListZipper.new()|> ListZipper.put(1) |> ListZipper.put(2) |> ListZipper.next() |> ListZipper.put(3) |> ListZipper.next()
{[3, 2], [1]}

However, I still need to go through the whole list to get the second element 2 :think
Is it possible, or did I misunderstood the quoted sentence in the blog post?