## Okasaki’s Physicists Queues

### April 2, 2019

One of my favorite programming textbooks is Chris Okasaki’s Purely Functional Data Structures, which I pick up and re-read every year or so. Today’s exercise asks you to
implement Okasaki’s physicist’s queues, which you can read about in either his book (Figure 6.3 on page 73) or his thesis (Figure 3.4 on page 31). Queues provide two constructors `empty` and `snoc`, two accessors `head` and `tail`, and a single predicate `isEmpty`; it is an error if either `head` or `tail` are applied to an empty queue. This version comes from the book:

```structure PhysicistsQueue : QUEUE
struct
type alpha Queue = α list × int × α list susp × int × α list

val empty = ([], 0, \$[], 0, [])
fun isEmpty (_, lenf, _, _, _) = (lenf = 0)

fun checkw ([], lenf, f, lenr, r) = (force f, lenf, f, lenr, r)
| checkw q = q
fun check (q as (w, lenf, f, lenr, r)) =
if lenr < lenf then checkw q
else let val f' = force f
in  checkw (f', lenf + lenr, \$(f' @ rev r), 0, []) end

fun snoc ((w, lenf, f, lenr, r), x) =
check (w, lenf, f, lenr + 1, x :: r)

fun head ([], lenf, f, lenr, r) = raise EMPTY
| head (x :: w, lenf, f, lenr, r) = x
fun tail ([], lenf, f, lenr, r) = raise EMPTY
| tail (x :: w, lenf, f, lenr, r) =
check (w, lenf - 1, \$tl (force f), lenr, r)
end```

Your task is to implement Okasaki’s physicists queues. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2