Has anyone got any applications that use a queue, a random-access list, or a heap? (Descriptions of these data structures given below.) I am looking for applications to use as benchmarks to test my automated benchmarking kit Auburn: http://www.cs.york.ac.uk/~gem/auburn/ Ideally I would like small, easy-to-run, non-artificial applications that spend a lot of time (eg. over 10%) using the data structure. Applications so far include: shellsort (queues), breadth-first search (queues), bucketsort (random-access lists), and heapsort (heaps). Please mail me if you have any applications (already coded or just the design/algorithm) or any suggestions. Thanks, Graeme. Queue ----- empty :: Queue a snoc :: Queue a -> a -> Queue a tail :: Queue a -> Queue a head :: Queue a -> a isEmpty :: Queue a -> Bool snoc places an element at the end of the queue, and head and tail remove the element at the front of the queue. The queue is FIFO: first-in first-out. Random-Access List ------------------ empty :: RAList a cons :: a -> RAList a -> RAList a tail :: RAList a -> RAList a update :: RAList a -> Int -> a -> RAList a head :: RAList a -> a lookup :: RAList a -> Int -> a isEmpty :: RAList a -> Bool cons, head, and tail are as the normal list operations. lookup returns the element at a given position, and update replaces this element with another. Heap ---- empty :: Ord a => Heap a isEmpty :: Ord a => Heap a -> Bool insert :: Ord a => a -> Heap a -> Heap a findMin :: Ord a => Heap a -> a deleteMin :: Ord a => Heap a -> Heap a merge :: Ord a => Heap a -> Heap a -> Heap a insert adds an element to a heap. findMin returns the smallest element in the heap. deleteMin removes this element. merge combines two heaps into one.
