Haskell: Queues without pointers
Posted by Eric Kidd Fri, 09 Feb 2007 01:01:00 GMT
Haskell has been tying my brain in knots. Sure, it keeps teaching me all sorts of amazing things, but it’s also forcing me to relearn the basics.
Right now, I’m trying to implement simple data structures in Haskell. It’s challenging, because most typical data structures are based on updating pointers, and Haskell doesn’t allow that. (Well, I could cheat, and use the IO monad, but where’s the fun in that?)
Fortunately, Chris Okasaki has done some amazing research into Haskell (and ML) data structures. He wrote an excellent thesis, which was later published as Purely Functional Data Structures. It’s a comprehensive book, well-written, and highly recommended for anyone programming in a functional language.
Let’s take a look at a data structure from Okasaki’s book: A purely functional queue. It’s competitive with a traditional queue (on average, at least), but it doesn’t use any pointers.
The queue API
A queue is a list of values to process. We can add values to the back of the queue, and retrieve values from the front.
In Haskell, we often begin by writing down the types of our functions. If we’re lucky, the code will fill itself in almost automatically. The first part of our API is easy:
-- A queue holding values of type 'a'.
data Queue a = ???
-- Create a new queue.
newQueue :: Queue a
-- Test whether a queue is empty.
empty :: Queue a -> Bool
The next part is a bit trickier. Since we can’t update our actual
Queue values, our data structure is read-only! We can work
around this by making enq and deq return an
updated version of the Queue:
-- Add an item to the back of the queue,
-- returning the updated queue.
enq :: Queue a -> a -> Queue a
-- Remove an item from the front of the
-- queue, returning the item and the
-- updated queue.
deq :: Queue a -> (a, Queue a)
We could use this API as follows:
q = newQueue `enq` 1 `enq` 2 `enq` 3
(x,q') = deq q -- x is 1
(y,q'') = deq q' -- y is 2
Now, the tricky bit: Making it run quickly.
Read more...
