Seminar: Functional Data Structures and Algorithms

Winter 2017/18

Overview

TitleSeminar: Functional Data Structures and Algorithms
TermWinter 2017/18
Module typeBachelor's seminar (IN0014), Master's seminar (IN2107)
PreliminariesFunctional Data Structures (IN2347)
SWS2
ECTS4
OrganisationMohammad Abdulaziz, Manuel Eberl, Lars Hupel, Tobias Nipkow

Content

Every participant will receive a topic about which they will write a written paper and give a presentation to the other participants. Also, every participant will be required to give a short written review of the papers of two other participants. The precise schedule will be made available below.

Module type

The seminar can be attended as either a Bachelor's or Master's seminar. Each topic below indicates for which of the two it is intended. Some topics are suitable both for the Bachelor's and Master's seminar; however, for the Master's seminar, the students are supposed to cover the topic in more depth.

Allocation

Formal requirements

Participants must hand in

Furthermore: As for the reviews: The final grade is composed as follows: 20% Reviews written + 40% Presentation + 40% Paper

Dates

The presentations will be held in sessions of 2 – 3 talks each during the semester.

More details will follow at a later time.

List of Topics

The following list is preliminary and will be extended soon.

1. Zippers and the Algebra of Algebraic Data Types

Description: Zippers facilitate moving through a data structure (such as a list or a tree). With a zipper, it is e.g. possible to denote a certain position in a tree while modifying its values. There is an interesting correspondence between between zippers of algebraic data types and formal derivatives and combinatorial species, which is to be illustrated informally in the talk.
References: Zippers: [1] Functional Pearls: The Zipper [PDF], Derivatives: [2] The Derivative of a Regular Type is its Type of One-Hole Contexts [PDF]
Type: Bachelor Seminar, possibly Master Seminar if more focus is put on combinatorial species.
Advisor: Manuel Eberl

2. Finger Trees

Description: The goal of this master topic is to describe the general purpose data structure of finger trees, its properties, and applications.
References: [1] Finger Trees: A Simple General-Purpose Data Structure
Prerequisites: (Basic) Knowledge of functional programming language, knowledge of at least one search-tree data structure (e.g., AVL-tree, RB-tree, 2,3-tree, ...)
Type: Master Seminar
Advisor: TBA

3. Purely Functional Data Structures 1

Description: The student introduces and explains the technique of implicit recursive slowdown, demonstrates the technique using a concrete data structure (e.g., double-ended queues) and discusses the complexity and difference between functional and procedural implementation. A different topic from the book is also possible after a consultation with the advisor.
References: [1] Chris Okasaki: Purely Functional Data Structures [read online (may require eAccess)]
Type: Bachelor Seminar
Advisor: TBA

4. Purely Functional Data Structures 2

Description: The student introduces the technique of amortization and shows how to eliminate it (Chapter 5 in [1]). Demonstration on concrete data structures is expected.
References: [1] Chris Okasaki: Purely Functional Data Structures [read online (may require eAccess)]
Type: Bachelor Seminar
Advisor: Fabian Immler

5. Priority Search Queues

Description: Priority search queues are a blend of finite maps (or dictionaries) and priority queues, that is, they support both dictionary operations (for instance, accessing a binding with a given key) and priority queue operations (for instance, accessing a binding with the minimum value).
References: [1]
Type: Master Seminar
Advisor: Tobias Nipkow

6. Hash Array Mapped Trie/Ideal Hash Trees

Description: HAMTs are implementations of dictionaries, behaving similarly to hash tables. Internally, they use a trie-like structure. Ideal Hash Trees are the persistent variant of HAMTs, described by Phil Bagwell [1]. Currently, many functional programming languages, including Clojure and Scala, use Ideal Hash Trees as their default implementation of maps [2].
References: [1] [2]
Type: Bachelor or Master
Advisor: Lars Hupel

7. Lenses in Functional Programming

Description: Lenses, or "functional references", or "first-class labels" are a common concept in functional programming. They are used to deal with immutable data structures. In the simplest definition, a lens is a pair of a setter and a getter function. A getter function retrieves the value of a field in a record, whereas a setter function changes the value of a field, returning the updated record. What's nice about lenses is that they compose: If you have a lens for X in Y, and a lens for Y in Z, you can obtain a lens for X in Z. There's a multitude of resources on the web about lenses [1]. I recommend going through this overview on Stack Overflow [2] and a survey paper [3] first.
References: [1] [2] [3]
Type: Bachelor or Master
Advisor: Lars Hupel

8. Matrices

Description: Comparing functional representations of matrices like quad-trees and the encoding of shape invariants in the type [1]. Discuss common algorithms on those data structures.
References:
[1] Chris Okasaki. From Fast Exponentiation to Square Matrices: An Adventure in Types.
[2] David S. Wise. Matrix algorithms using quadtrees.
Type: Bachelor or Master
Advisor: Fabian Immler

9. Regular Expression Equivalence via Derivatives

Description: This paper describes a functional decision procedure for equivalence of regular expressions based on the notion of derivative of a regular expression.
References: [1]
Type: Master
Advisor: Tobias Nipkow

Tips

Services like Google Scholar can be useful to find relevant scientific papers for your topic. Afterwards, you can gain access to these publications using the university's eAccess. This step is necessary because scientific publisher's often demand high prices for the publications otherwise.