**Title:**
The efficiency of purely functional data structures

**Proposer:** Hans-Wolfgang Loidl

**Suggested supervisors:** Hans-Wolfgang Loidl

**Goal:** Implement and assess purely functional data structures

**Description:**

Standard textbook algorithms over common data structures such as trees often use in-place updates for enhanced performance. While this often gains significant performance, it also complicates the algorithm.

In his textbook, Okasaki [1] describes purely functional implementations of a range of important data structures. The resulting algorithms are both efficient and easier to understand than their counterparts using in-place operations. The aim of this project is to implement some of these data structures and algorithms in the functional programming languages Ocaml and Haskell and to assess their performance.

**Resources required:** Linux, OCaml and Haskell compilers

**Degree of difficulty:** High

**Background needed:** Functional programming background (ML or Haskell)

**References:**

Last modified: Tue Jan 18 19:54:11 2011