Implementing a queue based on a list zipper?

Questions / Help
, , , ,
1

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?

2

Looking at the queue implementation in Elixir in rosettacode, I get the gist of it.

We use two queues, (input/output queues). When we want to pop, the input queue becomes the output queues and is reversed. Next time we want to pop, we won’t need to reverse the output queue (because it isn’t empty).

This is not always O(1) but it looks like a good compromise.

3

I think the Erlang queue module implements kind of the same thing. When you call :queue.new() it yelds a similar initial state: {[], []}.

1 Like