Home > Uncategorized > Functional queues

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.

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: