21 Queues from Lists

Suppose you have a list. When you take its first element, you get the element that was most recently linked to create it. The next element is the second most recent one that was linked, and so on. That is, the last one in is the first one out. This is called a LIFO, short for “last-in-first-out”, data structure. A list is LIFO; we sometimes also refer to this as a stack.

But there are many settings where you want the first-in to be the first-out. When you stand at a supermarket line, try to purchase concert tickets, submit a job request, or any number of other tasks, you want to be rewarded, not punished, for being there first. That is, you want a FIFO instead. This is called a queue.

The game we’re playing here is that we want one datatype but our language has given us another (in this case, lists), and we have to figure out how to encode one in the other. We’ve already seen how to encode sets with lists [Representing Sets by Lists]. Now let’s see how we can encode queues with lists.

With sets, we allowed the set type to be an alias for lists; that is, the two were the same. Another option we have when encoding is to create a completely new type that does nothing more than wrap a value of the encoding type. We’ll use that principle here to illustrate how that might work.

21.1 Using a Wrapper Datatype

Concretely, here’s how we’ll represent queues. For all the code that follows, it’s helpful to use the Pyret type-checker to make sure we’re composing code correctly:

data Queue<T>:
  | queue(l :: List<T>)
end

With this encoding, we can start define a few helper functions: e.g., a way to construct an empty queue and to check for emptiness:

fun mk-mtq<T>() -> Queue<T>:
  queue(empty)
end

fun is-mtq<T>(q :: Queue<T>) -> Boolean:
  is-empty(q.l)
end

Adding an element to a queue is usually called “enqueueing”. It has this type:

enqueue :: <T> Queue<T>, T -> Queue<T>

Here’s the corresponding implementation:

fun enqueue(q, e):
  queue(link(e, q.l))
end

Do Now!
Did we have a choice?

Yes, we did! We could have made the new element the first element or the last element.Be careful here: we mean the first or last element of the list that represents the queue, not of the queue itself. There, FIFO gives us no choice. We just happened to choose one representation. The other would be equally valid; we would just need to implement all the other operations consistently. Let’s stick to this one for now.

Now we come to a problem. What does it mean to “dequeue”? We need to get back the one element, but we also need to get back the rest. Let’s first write this as two functions, very analogous to first and rest on lists:

qpeek :: <T> Queue<T> -> T
qrest :: <T> Queue<T> -> Queue<T>

Let’s write out a few examples to make sure we know how these should work:

q_ = mk-mtq()
q3 = enqueue(q_, 3)
m43 = enqueue(q3, 4)
m543 = enqueue(m43, 5)

check:
  qpeek(q3) is 3
  qpeek(m43) is 3
  qpeek(m543) is 3
end

check:
  qrest(q3) is mk-mtq()
  qrest(m43) is enqueue(mk-mtq(), 4)
  qrest(m543) is enqueue(enqueue(mk-mtq(), 4), 5)
end

Now let’s implement these:

fun qpeek(q):
  if is-mtq(q):
    raise("can't peek an empty queue")
  else:
    q.l.get(q.l.length() - 1)
  end
end

fun qrest(q):
  fun safe-rest(l :: List<T>) -> List<T>:
    cases (List) l:
      | empty => raise("can't dequeue an empty queue")
      | link(f, r) => r
    end
  end
  queue(safe-rest(q.l.reverse()).reverse())
end

21.2 Combining Answers

However, it would be nice if we could obtain both the oldest element and the rest of the queue at once, if we want them both. That means the single function would need to return two values; since a function can return only one value at a time, it would need to use a data structure to hold both of them. Furthermore, note that both qpeek and qrest above have the possibility of not having any more elements! We might as well reflect that too in the type. Thus we end up with a type that looks like

data Dequeued<T>:
  | none-left
  | elt-and-q(e :: T, q :: Queue<T>)
end

Exercise
Write out the function to use this return type.

Observe that this also follows our principle of making exceptional behavior manifest in the return type: The Option Type, and especially in Summary.

Exercise
Write out the function using this return type.

21.3 Using a Picker

Does Dequeued look familiar? Of course it should! It’s basically the same as the pickers used for sets in Pyret: Picking Elements from Sets. If we make queues provide the same operations, we can reuse the Pick library already built into the language, and reuse any code that is written expecting the picker interface.

To do so, first we need to import the picker library:

include pick

Then we can write:

dequeue :: <T> Queue<T> -> Pick<T, Queue<T>>

Here are some examples showing how it would work:

check:
  dequeue(q_) is pick-none
  dequeue(q3) is pick-some(3, mk-mtq())
  dequeue(m43) is pick-some(3, enqueue(mk-mtq(), 4))
  dequeue(m543) is pick-some(3, enqueue(enqueue(mk-mtq(), 4), 5))
end

And here’s the corresponding code:

fun dequeue<T>(q):
  rev = q.l.reverse()
  cases (List) rev:
    | empty => pick-none
    | link(f, r) =>
      pick-some(f, queue(r.reverse()))
  end
end

In terms of big-O complexity, this is a dreadfully inefficient implementation, causing two reversals on every qrest or dequeue. To see how to do better, and to conduct a more sophisticated analysis, see An Example: Queues from Lists.

One thing to note is that by providing only a picker interface, we’re slightly changing the meaning of queues. The picker interface in Pyret is designed for sets, which don’t have a notion of order. But queues are, of course, very much an ordered datatype; order is why they exist. So by providing only a picker interface, we don’t offer the very guarantee that queues are designed for. Therefore, we should provide a picker in addition to an ordered interface, rather than in place of one.

At this point we’re done with the essential content, but here are two more parts that you may find interesting.

21.4 Using Tuples

Earlier, we created the Dequeued datatype to represent the return value from the dequeue. Indeed, it is often useful to create datatypes of this sort to document functions and make sure the types can be meaningfully interpreted even when their values flow around the code some distance from where they were created.

Sometimes, however, we want to create a compound datum in a special circumstance: it represents the return value of a function, and that return value will not live for very long, i.e., it will be taken apart as soon as it has returned and only the constituent parts will be used thereafter. In such situations, it can feel like a burden to create a new datatype for such a fleeting purpose. For such cases, Pyret has a built-in generic datatype called the tuple.

Here are some examples of tuples, which illustrate their syntax; note that each position (separated by ;) takes an expression, not only a constant value:

{1; 2}
{3; 4; 5}
{1 + 2; 3}
{6}
{}

We can also pull values out of tuples as follows:

{a; b} = {1; 2}

Evaluate a and b and see what they are bound to.

{c; d; e} = {1 + 2; 6 - 2; 5}

Similarly, see what c, d, and e are bound to.

Exercise
What happens if we use too few or too many variables? Try out the following in Pyret and see what happens:
{p; q} = {1}
{p} = {1; 2}
{p} = 1

Do Now!
What happens if instead we write this?
p = {1; 2}

This binds p to the entire tuple.

Exercise
How might we pull apart the constituents of p?

Now that we have tuples, we can write dequeue as:

fun dequeue-tuple<T>(q :: Queue<T>) -> {T; Queue<T>}:
  rev = q.l.reverse()
  cases (List) rev:
    | empty => raise("can't dequeue an empty queue")
    | link(f, r) =>
      {f; queue(r.reverse())}
  end
end

check:
  dequeue-tuple(q3) is {3; mk-mtq()}
  dequeue-tuple(m43) is {3; enqueue(mk-mtq(), 4)}
  dequeue-tuple(m543) is {3; enqueue(enqueue(mk-mtq(), 4), 5)}
end

And here’s how we can use it more generally:

fun q2l<T>(q :: Queue<T>) -> List<T>:
  if is-mtq(q):
    empty
  else:
    {e; rq} = dequeue-tuple(q)
    link(e, q2l(rq))
  end
end

check:
  q2l(mk-mtq()) is empty
  q2l(q3) is [list: 3]
  q2l(m43) is [list: 3, 4]
  q2l(m543) is [list: 3, 4, 5]
end

You should feel free to use tuples in your programs provided you follow the rules above for when tuples are applicable. In general, tuples can cause a reduction in readability, and increase the likelihood of errors (because tuples from one source aren’t distinguishable from those from another source). Use them with caution!

21.5 A Picker Method

Second, and this is truly optional: you may have noticed earlier that Sets had a built-in pick method. We have a function, but not method, that picks. Now we’ll see how we can write this as a method:

data Queue<T>:
  | queue(l :: List<T>) with:
    method pick(self):
      rev = self.l.reverse()
      cases (List) rev:
        | empty => pick-none
        | link(f, r) =>
          pick-some(f, queue(r.reverse()))
      end
    end
end

This is a drop-in replacement for our previous definition of Queue, because we’ve added a method but left the general datatype structure intact, so all our existing code will still work. In addition, we can rewrite q2l in terms of the picker interface:

fun q2lm<T>(c :: Queue<T>) -> List<T>:
  cases (Pick) c.pick():
    | pick-none => empty
    | pick-some(e, r) => link(e, q2lm(r))
  end
end

check:
  q2lm(m543)
end

We can also write generic programs over data that support the Pick interface. For instance, here’s a function that will convert anything satisfying that interface into a list:

fun pick2l<T>(c) -> List<T>:
  cases (Pick) c.pick():
    | pick-none => empty
    | pick-some(e, r) => link(e, pick2l(r))
  end
end

For instance, it works on both sets and our new Queues:

import sets as S    # put this at the top of the file

check:
  pick2l([S.set: 3, 4, 5]).sort() is [list: 3, 4, 5]
  pick2l(m543) is [list: 3, 4, 5]
end

Exercise
Do you see why we invoked sort in the test above?

The only weakness here is that for this last part (making the function generic), we have to transition out of the type-checker, because pick2l cannot be typed by the current Pyret type checker. It requires a feature that the type checker does not (yet) have.

contents ← prev up next →

I	Introduction
II	Foundations
III	Foundations: Bonus Materials
IV	Algorithms
V	Algorithms: Bonus Materials
VI	From Pyret to Python
VII	Programming with State
VIII	Advanced Topics
IX	Appendices

18	Partial Domains
19	Staging
20	Orderability and Hashing
21	Queues from Lists

21.1	Using a Wrapper Datatype
21.2	Combining Answers
21.3	Using a Picker
21.4	Using Tuples
21.5	A Picker Method