## Functional queues

I picked up the book Purely Functional Data Structures today. I bought it quite a while ago but, to be honest, I have not spent much time reading it. The book is being more of the abstract and theoretic kind and in order to actually understand what I was reading I felt like I needed to get some hands on experience. In chapter 5 the author gives pseudo code for a functional queue implementation. I started of by writing it down in F#:

type Queue<‘a> = List<‘a>*List<‘a>

module Queue =

// Invariant: f is empty iff r is also empty

let private checkf (f,r) =

match f with

| [] -> (List.rev r, [])

| _ -> (f,r)

let empty = ([], [])

let isEmpty (f,_) = List.isEmpty f

let head = function

| x::_, _ -> x

| _ -> failwith "empty queue"

let snoc (f,r) x = (f,x::r) |> checkf

let tail q =

let tail’ = function

| _::fs,r -> (fs,r)

| _ -> failwith "empty queue"

tail’ q |> checkf

The idea is to represent a queue by two lists; the front and the rear. I.e. the queue [1,2,3,4,5] can be represented by ([1,2,3],[5,4]). Note that the rear is stored reversed. We ensure that the front is never empty except when the entire queue is empty. This is done by the checkf function. This design can easily be extended to support a double-ended queue, or dequeue which is left as an exercise for the reader. The author kindly hints that we should now ensure that front and rear lists should be non-empty if the queue contains two or more elements. If this is violated the non-empty list should be split in halves to provide new front and rear lists (also noticing that one must be reversed). So here we are, my dequeue implementation in F#:

type Dequeue<‘a> = List<‘a>*List<‘a>

module Dequeue =

// Invariant: f and r are non-empty iff q contains two or more elements

// Helpers

let private singleOrEmpty = function

| [] -> true

| [_] -> true

| _ -> false

let private splitInHalves l =

let len = (List.length l) / 2

(Seq.take len l |> Seq.toList, Seq.skip len l |> Seq.toList)

let private checkf = function

| [], r when not(singleOrEmpty r) -> let r’,f’ = splitInHalves r in List.rev f’, r’

| q -> q

let private checkr = function

| f, [] when not(singleOrEmpty f) -> let f’,r’ = splitInHalves f in f’, List.rev r’

| q -> q

let private check q = (checkf >> checkr) q

// Empty

let empty = ([], [])

let isEmpty (f,r) = List.isEmpty f && List.isEmpty r

// Conversion

let toList (f,r) = f @ (List.rev r)

// Insert, inspect and remove the front element

let cons (f,r) x = (x::f, r) |> check

let head = function

| x::_,_ -> x

| [],[x] -> x

| _ -> failwith "empty queue"

let tail q =

let tail’ = function

| _::fs,r -> (fs,r)

| _ -> failwith "empty queue"

tail’ q |> check

// Insert, inspect and remove rear element

let snoc (f,r) x = (f,x::r) |> check

let last = function

| _,x::_ -> x

| [x],[] -> x

| _ -> failwith "empty queue"

let init q =

let init’ = function

| f,_::rs -> (f,rs)

| _ -> failwith "empty queue"

init’ q |> check

Yup. Not much to say more than that. Good exercise.