Return to Answer

There is, Indeed, a Bug

Replace undefined with a Permanent Solution

If pop on an empty queue should be a runtime error, declare it as an error with a meaningful message. This will help you, or anyone else using your library, debug their code.

Alternatively, pop could return a Maybe value, and pop on an empty queue could then return Nothing, rather than crash the program.

There is, Indeed, a Bug

Use the Right Data Structure

In Haskell, a double-linked list is, as you know, inefficient, as removing an element from the end requires copying all other elements of the list.

In this case, you define four cases, which try to build a list from the middle out. Your push and pop operations still run in linear time, needing to recurse to the root of the structure and generate an entirely new list. This vitiates any advantage of storing the first and last elements in the outermost node.

You are better off using a self-balancing binary tree here, such as a red-black tree, which would be able to re-use the majority of the nodes on each operation. There are also functional FIFO queue structures using, e.g., a push list and a pop list, where the pop list is created by reversing the push list.

If you’re going to perform a linear-time copy of the data, the structure you probably want to use is a Data.Vector, which can add data to the right or shift it to the left as efficiently as possible, even amortizing most of the operations. For example, enqueueing elements could be a constant-time insertion at the end, and dequeueing them could be a constant-time increment of an offset from the beginning. Eventually, your queue will run out of space, and you will need to copy the entire thing to a new Vector. But many smaller queues might never need to do this, and would just get constant time. When the vector does get copied, this is fast because it performs one allocation and then copies a contiguous block of memory.

There is, Indeed, a Bug

As you thought, pop Nil can get called. Consider the following sequence of operations. Please read from the bottom up.

test =
  fst . pop $ -- Error! Attempts to pop Nil.
  fst . pop $ -- More 3 Nil 2
  push 3 $    -- More 3 (Unit 2) 1
  push 2 $    -- Two 2 1
  push 1 $    -- Unit 1
  Nil

Consider Using the Names Enqueue and Dequeue

This seems less ambiguous to me than push and pop operations, but those names are widely-used enough for queues that I won’t tell you they’re wrong.

Use the Right Data Structure

In Haskell, a double-linked list is, as you know, inefficient, as removing an element from the end requires copying all other elements of the list.

In this case, you define four cases, which try to build a list from the middle out. Your push and pop operations still run in linear time, needing to recurse to the root of the structure and generate an entirely new list. This vitiates any advantage of storing the first and last elements in the outermost node.

You are better off using a self-balancing binary tree here, such as a red-black tree, which would be able to re-use the majority of the nodes on each operation. There are also functional FIFO queue structures using, e.g., a push list and a pop list, where the pop list is created by reversing the push list.

If you’re going to perform a linear-time copy of the data, the structure you probably want to use is a Data.Vector, which can add data to the right or shift it to the left as efficiently as possible, even amortizing most of the operations. For example, enqueueing elements could be a constant-time insertion at the end, and dequeueing them could be a constant-time increment of an offset from the beginning. Eventually, your queue will run out of space, and you will need to copy the entire thing to a new Vector. But many smaller queues might never need to do this, and would just get constant time. When the vector does get copied, this is fast because it performs one allocation and then copies a contiguous block of memory.

There is, Indeed, a Bug

As you thought, pop Nil can get called. Consider the following sequence of operations. Please read from the bottom up.

test =
  fst . pop $ -- Error! Attempts to pop Nil.
  fst . pop $ -- More 3 Nil 2
  push 3 $    -- More 3 (Unit 2) 1
  push 2 $    -- Two 2 1
  push 1 $    -- Unit 1
  Nil

Or with the aid of import Data.Function ((&)):

  Nil &
  push 1 &     -- Unit 1
  push 2 &     -- Two 2 1
  push 3 &     -- More 3 (Unit 2) 1
  pop & fst &  -- More 3 Nil 2
  pop & fst    -- Error! Attempts to pop Nil.

Consider Using the Names Enqueue and Dequeue

This seems less ambiguous to me than push and pop operations, but those names are widely-used enough for queues that I won’t tell you they’re wrong.

Use the Right Data Structure

In Haskell, a double-linked list is, as you know, inefficient, as removing an element from the end requires copying all other elements of the list.

In this case, you define four cases, which try to build a list from the middle out. Your push and pop operations still run in linear time, needing to recurse to the root of the structure and generate an entirely new list. This vitiates any advantage of storing the first and last elements in the outermost node.

You are better off using a self-balancing binary tree here, such as a red-black tree, which would be able to re-use the majority of the nodes on each operation.

If you’re going to perform a linear-time copy of the data, the structure you probably want to use is a Data.Vector, which can add data to the right or shift it to the left as efficiently as possible, even amortizing most of the operations. For example, enqueueing elements could be a constant-time insertion at the end, and dequeueing them could be a constant-time increment of an offset from the beginning. Eventually, your queue will run out of space, and you will need to copy the entire thing to a new Vector. But many smaller queues might never need to do this, and would just get constant time. When the vector does get copied, this is fast because it performs one allocation and then copies a contiguous block of memory.

There is, Indeed, a Bug

As you thought, pop Nil can get called. Consider the following sequence of operations. Please read from the bottom up.

test =
  fst . pop $ -- Error! Attempts to pop Nil.
  fst . pop $ -- More 3 Nil 2
  push 3 $    -- More 3 (Unit 2) 1
  push 2 $    -- Two 2 1
  push 1 $    -- Unit 1
  Nil

Consider Using the Names Enqueue and Dequeue

This seems less ambiguous to me than push and pop operations, but those names are widely-used enough for queues that I won’t tell you they’re wrong.

Use the Right Data Structure

In Haskell, a double-linked list is, as you know, inefficient, as removing an element from the end requires copying all other elements of the list.

In this case, you define four cases, which try to build a list from the middle out. Your push and pop operations still run in linear time, needing to recurse to the root of the structure and generate an entirely new list. This vitiates any advantage of storing the first and last elements in the outermost node.

You are better off using a self-balancing binary tree here, such as a red-black tree, which would be able to re-use the majority of the nodes on each operation. There are also functional FIFO queue structures using, e.g., a push list and a pop list, where the pop list is created by reversing the push list.

If you’re going to perform a linear-time copy of the data, the structure you probably want to use is a Data.Vector, which can add data to the right or shift it to the left as efficiently as possible, even amortizing most of the operations. For example, enqueueing elements could be a constant-time insertion at the end, and dequeueing them could be a constant-time increment of an offset from the beginning. Eventually, your queue will run out of space, and you will need to copy the entire thing to a new Vector. But many smaller queues might never need to do this, and would just get constant time. When the vector does get copied, this is fast because it performs one allocation and then copies a contiguous block of memory.

There is, Indeed, a Bug

As you thought, pop Nil can get called. Consider the following sequence of operations. Please read from the bottom up.

test =
  fst . pop $ -- Error! Attempts to pop Nil.
  fst . pop $ -- More 3 Nil 2
  push 3 $    -- More 3 (Unit 2) 1
  push 2 $    -- Two 2 1
  push 1 $    -- Unit 1
  Nil

Consider Using the Names Enqueue and Dequeue

This seems less ambiguous to me than push and pop operations, but those names are widely-used enough for queues that I won’t tell you they’re wrong.