Programming Praxis

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