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: