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


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)


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