Suggested Final Project Topics

Purely Functional Red/Black Trees

In purely functional programming languages, it’s not possible to modify data structures after they’ve been

constructed. Any updates that happen must be performed by building a new version of the data structure,

possibly sharing some existing pieces of the original structure in a read-only way.

Although red/black trees are tricky to implement in imperative languages, it’s possible to implement them

in purely functional programming languages, maintaining all the existing time bounds, in about a page of

code. This means that it’s possible to implement red/black trees in a way that lets us “go back in time” to

see what the data structure looked like in the past and to use them in programming languages and settings

where updates aren’t permitted.