## Functional Splay heap

Citing from Purely Functional Data Structures, page 52:

Splay trees, perhaps in combination with the ExplicitMin functor, are the fastest known implementation of heaps for most applications that do not depend on persistence and that do not call the merge function.

Here is my F# port:

type SplayHeap<‘a> = E | T of SplayHeap<‘a> * ‘a * SplayHeap<‘a>

exception Empty

module SplayHeap =

let empty = E

let isEmpty = function

| E -> true

| _ -> false

let rec partition pivot = function

| E -> E, E

| T(a,x,b) as t ->

if x <= pivot then

match b with

| E -> t, E

| T(b1,y,b2) ->

if y <= pivot then

let small, big = partition pivot b2

T(T(a,x,b1),y,small), big

else

let small, big = partition pivot b1

T(a,x,small),T(big,y,b2)

else

match a with

| E -> E, t

| T(a1,y,a2) ->

if y <= pivot then

let small, big = partition pivot a2

T(a1,y,small),T(big,x,b)

else

let small, big = partition pivot a1

small,T(big,y,T(a2,x,b))

let insert x t = let a, b = partition x t in T(a,x,b)

let rec merge = function

| E, t -> t

| T(a,x,b), t ->

let ta, tb = partition x t

T(merge(ta,a), x, merge(tb,b))

let rec findMin = function

| E -> raise Empty

| T(E,x,_) -> x

| T(a,_,_) -> findMin a

let rec deleteMin = function

| E -> raise Empty

| T(E,x,b) -> b

| T(T(E,x,b),y,c) -> T(b,y,c)

| T(T(a,x,b),y,c) -> T(deleteMin a, x, T(b,y,c))

## C++ Sudoku solver–new numbers

I continued to squeeze more performance out of my C++ Sudoku solver. Quite amazingly IMHO, a 9×9 Sudoku can now be solved in 0.000023 seconds. However, the solver is still single threaded and does not maximize the two cores on my machine so there is still room for improvement I guess.

This version is tagged as 4.0 and can be downloaded from http://bitbucket.org as usual:

https://bitbucket.org/d95danb/sudokucpp

As a final note I must say that AMD:s code analyst has been really helpful and easy to work with. Without a good profiler I would have been lost by now.

## 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.