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
    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)

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: