Archive
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:
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.
Code Contemplation 