Seminar: Functional Data Structures and Algorithms

Winter 2017/18

Overview

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.

Dates

The presentations will be held in sessions of 2 – 3 talks each during the semester, each 14:00–17:00 in Seminar Room 00.09.038 (Alan Turing).

• Session 1, 4 December 2017
  • Martin Wauligmann, Matrices
• Session 2, 11 December 2017
  • Fabio Madge Pimentel, Finger Trees
  • Shuwei Hu, Zippers
  • Fabian Hellauer, Regular Expression Equivalence via Derivatives
• Session 3, 18 December 2017
  • Julian Erhard, Lenses
  • Roland Schmid, Priority Search Queues

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.

Formal requirements

Participants must hand in

• a complete (!) paper draft three weeks before their presentation to both Manuel Eberl and their advisor; this will be reviewed by other students
• a draft version of their presentation slides to their advisor one week before their talk
• the final versions of their paper and presentatio to both Manuel Eberl and their advisor on the day of the presentation.
• reviews of two papers they were assigned within one week before the respective presentation to Manuel Eberl

• The length of the paper should be roughly 10 pages.
• The length of the talk between 35 and 45 minutes (excluding Q&A session) and must not exceed 45 minutes.
• Reviews, presentations, and papers should be in English.
• There are no strict requirements on the form of the paper or slides. No template will be provided.
• All submissions are to be sent to Manuel Eberl.

• Reviewers receive the drafts of their assigned topics as soon as they are handed in.
• The main focus of the reviews should be the content and the presentation of the papers. Does it make sense? Is it well-structured? Is it understandable to someone who has not read the source material?
• Reviewers are not expected to read the cited source material.
• Spelling and grammar may also be mentioned, but are less important.
• A summary of the reviewed topic is not required.
• Reviews should be roughly one page long
• Reviewers may freely decide whether to use full sentences or bullet points.

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: Julian Brunner

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: Ondřej Kunčar

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

Allocation

• Applications must be made through the Matching platform.
• You must have attended the Functional Data Structures lecture to be allowed to participate in the seminar.
• The allocation of topics to the participants will be done by us according to the preferences given by the participants.
• Each participant will be assigned two other topics to review. Reviewers can choose to remain anonymous.
• There will be no kick-off meeting. If you have any questions about the seminar or the topics, send an email to Manuel Eberl.

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.